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 consecutive 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 probability 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.
The optimal strategy for the first player (for any length of the sequence no less than 4) was found by J.A. Csirik (See References). It is to choose HTTTT.....TTTHH (k − 3 T's) in which case the second player's maximal odds of winning is (2k − 1 + 1):(2k − 2 + 1).
Steve Humble and Yutaka Nishiyama have suggested a variation on Penney’s Game using a pack of ordinary playing cards. The Humble-Nishiyama Randomness Game 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” and all cards that have already been turned over are discarded. 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 repeated nature of this game, the second player`s chance of winning is greatly increased.
Below are the probabilities of the outcomes for each strategy.
| 1st player's choice | 2nd player's choice | Probability 1st player wins | Probability 2nd player wins | Probability of a draw |
|---|---|---|---|---|
| BBB | RBB | 0.11% | 99.49% | 0.40% |
| BBR | RBB | 2.62% | 93.54% | 3.84% |
| BRB | BBR | 11.61% | 80.11% | 8.28% |
| BRR | BBR | 5.18% | 88.29% | 6.53% |
| RBB | RRB | 5.18% | 88.29% | 6.53% |
| RBR | RRB | 11.61% | 80.11% | 8.28% |
| RRB | BRR | 2.62% | 93.54% | 3.84% |
| RRR | BRR | 0.11% | 99.49% | 0.40% |
If the game is ended after the first trick, there is a negligible chance of a draw. The odds of the second player winning in such a game appear in the table below.
| 1st player's choice | 2nd player's choice | Odds in favour of 2nd player |
|---|---|---|
| BBB | RBB | 7.50 to 1 |
| BBR | RBB | 3.08 to 1 |
| BRB | BBR | 1.99 to 1 |
| BRR | BBR | 2.04 to 1 |
| RBB | RRB | 2.04 to 1 |
| RBR | RRB | 1.99 to 1 |
| RRB | BRR | 3.08 to 1 |
| RRR | BRR | 7.50 to 1 |
[edit] See also
[edit] 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 Randomness Game - A New Variation on Penney's Coin Game",IMA Mathematics Today. Vol 46, No. 4, August 2010, pp194–195.
- S. Humble & Y. Nishiyama, "Winning Odds", Plus Magazine, Issue 55, June 2010.
- Ed Pegg, Jr., "How to Win at Coin Flipping", Wolfram Blog, November 30, 2010.
- J.A. Csirik, "Optimal strategy for the first player in the Penney ante game", Combinatorics, Probability and Computing, Volume 1, Issue 4 (1992), pp 311-321.
[edit] External links
- Play Penney's game against the computer
