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 (not necessarily consecutive). 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 his odds by choosing sequences according to:

1st player's choice	2nd player's choice	Odds in favour of 2nd player
HHH	THH	7 to 1
HHT	THH	3 to 1
HTH	HHT	2 to 1
HTT	HHT	2 to 1
THH	TTH	2 to 1
THT	TTH	2 to 1
TTH	HTT	3 to 1
TTT	HTT	7 to 1

Notice that in each case the second player's optimal choice is to precede the first player's sequence (underlined) with the opposite of the second symbol (bolded).

Intuitive understanding may be aided by considering the extreme case of HHH: If player 2 picks THH, and any coin flip lands tails, player 1 cannot win.

Steve Humble and Yutaka Nishiyama have suggest a variation on Penney’s Game using a pack of ordinary playing cards. The follows the same format using Red and Black cards, instead of Heads and Tails. At the start of a game each player decides on their three colour sequence for the whole game. Every time the 1st or 2nd player sequence of cards appears, all those cards are removed from the game as a “winning trick”. This continues until the full pack of 52 cards is used. At the end the player with the most “tricks” is declared the winner. An average game will consist of around 7 “tricks”. Due to the finite number of cards in a pack you can show that the second player`s chance of winning is greatly increased.

Below are the results from a computer simulation of 1000 games, each game played with a full pack of cards.

BBB vs RBB - RBB wins 995 times, 4 draws, BBB wins once BBR vs RBB - RBB wins 930 times, 40 draws, BBR wins 30 times BRB vs BBR - BBR wins 805 times, 79 draws, RBR wins 116 times RBB vs RRB - RRB wins 890 times, 68 draws, RBB wins 42 times BRR vs BBR - BBR wins 872 times, 65 draws, BRR wins 63 times RBR vs RRB - RRB wins 792 times, 85 draws, RBR wins 123 times RRB vs BRR - BRR wins 922 times, 51 draws, RRB wins 27 times RRR vs BRR - BRR wins 988 times, 6 draws, RRR wins 6 times

See 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 Series A. Volume 30, Issue 2, (1981), pp183-208.
• Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, "Winning Ways for your Mathematical Plays", 2nd Edition, Volume 4, AK Peters (2004), p. 85.
• S. Humble & Y. Nishiyama, "Humble-Nishiyama Randomnss Game - A New Variation on Penney's Coin Game",IMA Mathematics Today. Vol 46, No. 4 August 2010, pp194-195.

External links

• Play Penney's game against the computer
• S. Humble & Y. Nishiyama, "Winning Odds", Plus Magazine [1], Issue 55, June 2010.