Penney's game

Penney's game (named after its inventor Walter Penney) is a binary (head/tail) sequence generating game between two players. At the start of the game, the two players agree on the length of the sequences to be generated. This length is usually taken to be three, but can be any larger number. Player A then selects a sequence of heads and tails of the required length, and shows this sequence to player B. Player B then selects another sequence of heads and tails of the same length. Subsequently, a fair coin is tossed until either player A's or player B's sequence appears as a subsequence of the coin toss outcomes. The player whose sequence appears first wins.

The interesting feature of Penney's game is that - provided sequences of at least length three are used - the second player (B) has an edge over the starting player (A). This is because the game is nontransitive such that for any given sequence of length three or longer one can find another sequence that has higher likelihood of occurring first.

For the three-bit sequence game, the second player can optimise her odds by choosing sequences according to:

Notice that in each case the second player's optimal choice is to precede the first player's sequence with the reciprocal of the second symbol, and to eliminate the last symbol.

ee also

*Nontransitive game

References

* Walter Penney, Journal of Recreational Mathematics, October 1969, p. 241.
* Martin Gardner, "Time Travel and Other Mathematical Bewilderments", W. H. Freeman, 1988.
* L.J. Guibas and A.M. Odlyzko, "String Overlaps, Pattern Matching, and Nontransitive Games", Journal of Combinatorial Theory 30 (1981), pp183-208.

External links

* Play Penney's game [http://www.haverford.edu/math/cgreene/390b-00/software/CoinFlip.html against the computer]