Penney's game

A possible sequence in Penney's game: heads, tails, heads

Graphs of best responses for Penney's games of sequence lengths 3 and 4 – each sequence is dominated by the sequence pointing to it with the given probability (italics) or odds (normal text)

Penney's game, also known as Penney Ante, named after its inventor Walter Penney, is a binary (head/tail) sequence generating game between two players. Player A selects a sequence of heads and tails (of length 3 or larger), 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.

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.

Analysis of the three-bit game

For the three-bit sequence game, the second player can optimize their 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

An easy way to remember the sequence is for the second player to start with the opposite of the middle choice of the first player, then follow it with the first player's first two choices.

So for the first player's choice of 1-2-3

the second player must choose (not-2)-1-2

where (not-2) is the opposite of the second choice of the first player.

An intuitive explanation for this result is that in any case that the sequence is not immediately the first player's choice, the chances for the first player getting their sequence-beginning, the opening two choices, are usually the chance that the second player will be getting their full sequence. So the second player will most likely "finish before" the first player.

Analysis using probability tree diagrams

Probability tree (HTT THT)

Probability tree diagram reduction (HTT THT)

To analyse the odds of winning between two strategies, one can use a probability tree diagram to model the distribution of coin flip sequences.

For example, the game between "HTT" and "THT" can be modelled with the probability tree on the right. The blue dotted lines represent that the probability distribution of the outcomes of the game does not change between the two nodes. Nodes which can be excluded from the state space are colored gray. This tree can be reduced to the second tree pictured on the right either manually or through graph reduction. It can be shown in the second tree that each sequence has an equal chance of appearing first.

To create a probability tree diagram for comparing two sequences of length n, one begins by drawing the full diagram for n coin flips. Then, reductive relationships can be drawn between nodes that contain the same information for calculating the outcome for the game. In the case of "HTT" and "THT", The line connecting the node "HH" and "H" signifies that the game state is not distinguishable between "HH" and "H". This is clear as the game state is determined by each player's progress in their sequence and in "H", "HH", and "HH..."(any string containing one or more 'H's), the player with "HTT" has progressed one step in their prediction sequence and the player with "THT" has made no progress. Another example is the game between "HTT" and "HTH", where it can be trivially shown that the game state is not different between "T", "TT", or any amount of 'T's in a row.

To reduce the graph, nodes which are never reached(i.e. nodes that appear on a path succeeding a relationship that travels closer to the root node) can be discarded, and nodes which point directly backwards can also be discarded. The probability and outcome following each leaf node can be calculated recursively to find the winning probability for each player. However, a program must account for cycles within the graph.

Using a reduced probability tree diagram, it is possible to calculate a player's probability of winning manually. An example is shown below for the pictured case. In cases(such as the "HTT" versus "THT" case) which contains cycles, an infinite geometric sum can be calculated. The ratio is constant as it is the probability of taking a path that returns to the current state(and thus, taking any such path does not change this ratio as the state is identical afterwards).

For player 2(sequence THT): The game can begin with T or H.

Beginning with T:

$${\begin{aligned}a&={\frac {1}{2}}\cdot {\frac {1}{2}}\cdot {\frac {1}{2}}={\frac {1}{2^{3}}}\\r&={\frac {1}{2}}\cdot {\frac {1}{2}}={\frac {1}{2^{2}}}\\\end{aligned}}$$ $${\begin{array}{l}S_{n}=2^{-3}+2^{-5}+2^{-7}+\cdots +2^{-n}\\2^{-2}\left(S_{n}\right)=2^{-5}+2^{-7}+2^{-9}+\cdots +2^{-\left(n+2\right)}\\S_{n}\left(1-2^{-2}\right)=2^{-3}-2^{-\left(n+2\right)}=2^{-3}\\S_{n}={\frac {2^{-3}}{1-2^{-2}}}={\frac {1}{6}}\\\end{array}}$$ As n approaches infinity, ${\textstyle 2^{-n}}$ approaches 0.

Beginning with H:

$${\begin{aligned}a&={\frac {1}{2}}\cdot {\frac {1}{2}}\cdot {\frac {1}{2}}={\frac {1}{2^{2}}}\\r&={\frac {1}{2}}\cdot {\frac {1}{2}}={\frac {1}{2^{2}}}\\\end{aligned}}$$ $${\begin{array}{l}S_{n}=2^{-2}+2^{-4}+2^{-6}+\cdots +2^{-n}\\2^{-2}\left(S_{n}\right)=2^{-4}+2^{-6}+2^{-8}+\cdots +2^{-\left(n+2\right)}\\S_{n}\left(1-2^{-2}\right)=2^{-2}-2^{-\left(n+2\right)}=2^{-2}\\S_{n}={\frac {2^{-2}}{1-2^{-2}}}={\frac {1}{3}}\\\end{array}}$$

Total:

$${\begin{aligned}P={\frac {1}{6}}+{\frac {1}{3}}={\frac {1}{2}}\end{aligned}}$$

Thus, with "HTT" against "THT", the probability for player 2 to win is ${\textstyle {\frac {1}{2}}}$. As Penney's game is a Zero-sum game, Player 1 wins the other half of the time.

First-player strategy for more than three bits

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 $(2^{k-1}+1):(2^{k-2}+1)$.

Second-player strategy for more than three bits

Andrew Odlyzko and Leonidas J. Guibas proved that, for a q-sided die and k>=3, all choices that player B has the maximise his probability of winning are obtained by prefixing the first k-1 items of player A's sequence with an appropriate character b. This translates to Penney's game in the case q=2, thus for k>=3 the most optimal strategy for player B is either T$,a_{1},a_{2},a_{3},\cdots ,a_{k-1}$ or H$,a_{1},a_{2},a_{3},\cdots ,a_{k-1}$ where player A's sequence is denoted $a_{1},a_{2},a_{3},\cdots ,a_{k}$. The proof can be found in "String Overlaps, Pattern Matching, and Nontransitive Games" pp 195-200(See references). János A. Csirik proved that these strategies are never equally good.

Variation with playing cards

One suggested variation on Penney's Game uses 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. The game is played as follows. At the start of a game each player decides on their three colour sequence for the whole game. The cards are then turned over one at a time and placed in a line, until one of the chosen triples appears. The winning player takes the upturned cards, having won that "trick". The game continues with the rest of the unused cards, with players collecting tricks as their triples come up, until all the cards in the pack have been used. The winner of the game is the player that has won the most tricks. An average game will consist of around 7 "tricks". As this card-based version is quite similar to multiple repetitions of the original coin game, the second player's advantage is greatly amplified. The probabilities are slightly different because the odds for each flip of a coin are independent while the odds of drawing a red or black card each time is dependent on previous draws. Note that HHT is a 2:1 favorite over HTH and HTT but the odds are different for BBR over BRB and BRR.

Below are approximate probabilities of the outcomes for each strategy based on computer simulations:

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 no 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

Variation with a Roulette wheel

Recently Robert W. Vallin, and later Vallin and Aaron M. Montgomery, presented results with Penney's Game as it applies to (American) roulette with Players choosing Red/Black rather than Heads/Tails. In this situation the probability of the ball landing on red or black is 9/19 and the remaining 1/19 is the chance the ball lands on green for the numbers 0 and 00. There are various ways to interpret green: (1) as a "wild card" so that BGR can be read at Black, Black, Red and Black, Red, Red, (2) as a do-over, the game stops when green appears and restarts with the next spin, (3) as just itself with not extra interpretation. Results have been worked out for odds and wait times.

See also

• Nontransitive game
• Matching pennies

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), pp 183–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. 885.
• 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, pp 194–195.
• Steve Humble & Yutaka Nishiyama, "Winning Odds", Plus Magazine, Issue 55, June 2010.
• Ed Pegg, Jr., "How to Win at Coin Flipping", Wolfram Blog, 30 November 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.
• Robert W. Vallin "A sequence game on a roulette wheel", The Mathematics of Very Entertaining Subjects: Research in Recreational Math, Volume II, Princeton University Press, (to be published in 2017)
• James Brofos, "A Markov Chain Analysis of a Pattern Matching Coin Game." arXiv:1406.2212 (2014).

External links

• An online simulation of Penney's game
• Some variants of Penney's game