Penney's Game, math that surprises you lesson

Two players each pick a pattern of three coin results, such as heads, heads, heads. A fair coin is then tossed again and again, and the player whose pattern turns up first wins. Every pattern of three has the same chance, $1/8$ , of filling any particular three tosses, so it seems the choice cannot matter. Yet whatever the first player picks, the second player can pick a pattern that comes first with probability at least $2/3$ . This page shows where that advantage comes from and computes the exact chances with a state diagram.

Key terms

Penney’s game

Definition Penney’s game, described by Walter Penney in 1969, is played with a fair coin, writing H for heads and T for tails. The first player names a pattern of three results, such as HHT. The second player, after hearing it, names a different pattern of three. The coin is then tossed again and again, each toss independent of the others, which forms one sequence shared by both players. After each toss from the third on, the last three results are compared with both patterns, and the player whose pattern appears first as three consecutive results wins. Two different patterns cannot both be the last three results at the same toss, so there are no ties, and the game ends with probability $1$ .

Every pattern has probability $1/8$ of filling any fixed block of three tosses, yet the second player can always choose a pattern that is more likely to appear first. The reply starts with the opposite of the middle symbol of the first player’s pattern and continues with that pattern’s first two symbols. Against HHT, for example, the middle symbol is H, so the reply is T followed by HH, which is THH. Depending on the first choice, the reply appears first with probability $2/3$ , $3/4$ or $7/8$ . The resolution is that the windows of three tosses overlap, so the race is not decided by the chances of fixed blocks. The reply ends with the first two symbols of the first player’s pattern, so whenever those two symbols come right after the opposite of the middle symbol, the reply is complete one toss before the first player could finish a pattern from them.

In plain words The second player’s pattern is built to finish just as the first player’s pattern is getting started. A fixed block of three tosses treats every pattern alike, but a race along one shared sequence, checked at every toss, does not.

Example Let the first player pick HHH and the second THH. If the first three tosses are all heads, which has probability $(1/2)^3 = 1/8$ , then HHH is complete at toss $3$ and wins. Otherwise a tail appears among the first three tosses, and from then on HHH cannot come first. Any run of three heads that ends later has a tail somewhere before it. The last such tail is followed by heads all the way into the run, so that tail and the next two heads form THH, which is complete before the run reaches its third head. So THH wins with probability $1 - 1/8 = 7/8$ , and HHH can only win at once.

The table gives the reply for every first choice and the probability that the reply appears first. Checking all seven possible replies to each first choice shows that the reply in the table is the best one in every case.

First player	Second player	Second player wins with
HHH	THH	$7/8$
HHT	THH	$3/4$
HTH	HHT	$2/3$
HTT	HHT	$2/3$
THH	TTH	$2/3$
THT	TTH	$2/3$
TTH	HTT	$3/4$
TTT	HTT	$7/8$

Starting from THH and taking the reply again and again gives TTH, then HTT, then HHT, and then THH again. Each of these four patterns is beaten by the next one, so, as with nontransitive dice, no pattern is a best choice.

Coin toss sequence

Definition A coin toss sequence is the list of results of repeated tosses of a coin, in order, such as HTTHH. This page assumes a fair coin and independent tosses, so each toss is H or T with probability $1/2$ whatever came before, and each particular sequence of $n$ results has probability $(1/2)^n$ . In particular, each of the $8$ patterns of three results has probability $1/8$ of filling any fixed block of three consecutive tosses. In an endless sequence any given pattern appears at some point with probability $1$ . The separate blocks made of tosses $1$ to $3$ , tosses $4$ to $6$ and so on are independent, so the chance that the pattern fills none of the first $m$ of them is $(7/8)^m$ , which shrinks to $0$ as $m$ grows.

In plain words A fair coin has no memory, and no list of results is more likely than any other list of the same length. Each pattern is equally likely in any one chosen place.

Example The sequence HTTHH has probability $(1/2)^5 = 1/32$ , the same as HHHHH. Its windows of three, ending at tosses $3$ , $4$ and $5$ , are HTT, TTH and THH. In a game of HHH against THH, the second player wins at toss $5$ . The winning window, tosses $3$ to $5$ , is neither of the separate blocks made of tosses $1$ to $3$ and tosses $4$ to $6$ , but overlaps both, which is why the race has to check every window and not only separate blocks.

Overlapping patterns

Definition Two windows of three consecutive tosses that start one toss apart share two tosses, and two that start two tosses apart share one. Because of these shared tosses, the events that a pattern fills two overlapping windows are not independent, so the chance that a pattern appears at least once, or before another pattern, cannot be found by treating the windows as separate trials. What a failed attempt leaves behind is the longest ending of the sequence so far that is also a beginning of a pattern. Two patterns overlap when an ending of one equals a beginning of the other. A pattern overlaps itself when an ending shorter than the whole pattern equals its beginning of the same length.

In plain words Each new toss drops the oldest of the last three results and adds a new one, so a near miss can still be put to use. A pattern whose end can serve as its own beginning tends to arrive in clusters, and a pattern whose end is the opponent’s beginning waits just ahead of the opponent.

Example The pattern HHH overlaps itself, since its ending HH equals its beginning HH. The pattern THH does not, since its endings H and HH differ from its beginnings T and TH. Among the $16$ equally likely sequences of four tosses, HHH appears in HHHH, HHHT and THHH, while THH appears in HTHH, THHH, THHT and TTHH. Each pattern fills the first window in $2$ of the sequences and the second window in $2$ , so each fills $4$ windows in all. But HHH packs two of its windows into HHHH, so it appears in only $3$ sequences, while THH, which can never fill two overlapping windows, appears in $4$ . So within four tosses HHH appears with probability $3/16$ and THH with $4/16$ . The clustering also slows HHH down. When each pattern is waited for on its own, HHH takes $14$ tosses on average and THH only $8$ .

State diagram

Definition A state diagram for a race between two patterns has a start state, one state for each beginning of one or two symbols of either pattern, and one end state for each pattern. The current state is the longest ending of the sequence so far that is a beginning of one of the patterns, or the start state when there is none. Each toss moves the game along the arrow labeled H or T, each taken with probability $1/2$ , to the new state, or to an end state when a pattern is complete. For a chosen player, let $w_s$ be the probability that this player wins when the game is in state $s$ . Then $w = 1$ at that player’s end state and $w = 0$ at the other end state, and for every other state $s$

\begin{aligned} w_s &= \tfrac12\, w_{\text{after H}} \\[0.4em] &\quad + \tfrac12\, w_{\text{after T}}, \end{aligned}

where the two terms on the right are the values at the states reached from $s$ by a head and by a tail. From every state some pattern is completed with probability $1$ , and for that reason these equations have exactly one solution. Its value at the start state is the player’s chance of winning the game.

In plain words The diagram forgets the whole past except the part that can still help a pattern. Each arrow is one toss, and a player’s chance in a state is the average of the chances in the two states one toss later.

Example Let the first player pick HTH and the second HHT. The states are the start, H, HH and HT. Let $p_s$ be the probability that HHT wins from state $s$ .

From the start, T leaves no useful ending, since both patterns begin with H, and H leads to state H. So $p_{\text{start}} = \tfrac12 p_{\text{start}} + \tfrac12 p_{\text{H}}$ , which gives $p_{\text{start}} = p_{\text{H}}$ .
From HH, another H leaves HH as the useful ending, and T completes HHT. So $p_{\text{HH}} = \tfrac12 p_{\text{HH}} + \tfrac12$ , which gives $p_{\text{HH}} = 1$ .
From HT, H completes HTH, and T leaves HTT, whose endings T and TT begin neither pattern, so the game is back at the start. So $p_{\text{HT}} = \tfrac12 \cdot 0 + \tfrac12 p_{\text{start}} = \tfrac12 p_{\text{H}}$ .

From H, a head leads to HH and a tail leads to HT, so

\begin{aligned} p_{\text{H}} &= \tfrac12 \cdot 1 + \tfrac12 \cdot \tfrac12\, p_{\text{H}} \\[0.4em] &= \tfrac12 + \tfrac14\, p_{\text{H}}. \end{aligned}

Then $\tfrac34 p_{\text{H}} = \tfrac12$ , so $p_{\text{H}} = 2/3$ . The pattern HHT wins with probability $p_{\text{start}} = 2/3$ and HTH with $1/3$ .

Check yourself

The first player picks TTT. Which reply does the rule give, and why does it win with probability $7/8$ ?

Show the answer

The middle symbol of TTT is T, so the reply starts with H and continues with TT, which gives HTT. The argument for HHH against THH works with heads and tails swapped. If the first three tosses are all tails, which has probability $1/8$ , TTT wins at toss $3$ . Otherwise a head appears among the first three tosses. Any run of three tails that ends later then has a head somewhere before it, and the last such head is followed by tails all the way into the run. That head and the next two tails form HTT, which is complete before the run reaches its third tail. So HTT wins with probability $1 - 1/8 = 7/8$ .

Change the rule so that the sequence is cut into separate blocks, tosses $1$ to $3$ , tosses $4$ to $6$ and so on, and a pattern counts only when it fills a whole block. Who is favored in HHH against THH now?

Show the answer

Neither player. The blocks share no tosses, so they are independent, and each block is HHH with probability $1/8$ , THH with probability $1/8$ and neither with probability $3/4$ . The game is decided by the first block that is one of the two patterns, and in that block the two patterns are equally likely. Adding up the chances that HHH fills block $1$ , or block $2$ after a block of neither, and so on,

\begin{aligned} &\tfrac18 + \tfrac34 \cdot \tfrac18 + \left(\tfrac34\right)^2 \cdot \tfrac18 + \cdots \\[0.4em] &\quad = \frac{1/8}{1 - 3/4} = \frac12. \end{aligned}

So each player wins with probability $1/2$ . Without overlapping windows, a near miss cannot help either pattern, and the second player’s advantage disappears.

The first player picks HHT, and the second player answers with THH. Use a state diagram to find the chance that THH wins.

Show the answer

The states are the start, H, HH, T and TH. Let $q_s$ be the probability that THH wins from state $s$ .

From T, another T leaves T as the useful ending, and H leads to TH. From TH, H completes THH, and T leaves THT, whose useful ending is T. So $q_{\text{T}} = \tfrac12 q_{\text{T}} + \tfrac12 q_{\text{TH}}$ and $q_{\text{TH}} = \tfrac12 + \tfrac12 q_{\text{T}}$ . The first equation gives $q_{\text{T}} = q_{\text{TH}}$ , and then the second gives $q_{\text{T}} = 1$ . Once a tail has appeared, THH wins with probability $1$ .
From HH, another H leaves HH, and T completes HHT. So $q_{\text{HH}} = \tfrac12 q_{\text{HH}}$ , which gives $q_{\text{HH}} = 0$ .
From H, a head leads to HH and a tail leads to T, so $q_{\text{H}} = \tfrac12 \cdot 0 + \tfrac12 \cdot 1 = \tfrac12$ .

From the start, a head leads to H and a tail to T, so

\begin{aligned} q_{\text{start}} &= \tfrac12 \cdot \tfrac12 + \tfrac12 \cdot 1 \\[0.4em] &= \tfrac34. \end{aligned}

So THH wins with probability $3/4$ , as in the table. The pattern HHT wins exactly when the first two tosses are both heads, which has probability $1/4$ . Then the first tail completes HHT, while a tail among the first two tosses hands the game to THH.

Penney's Game

Video 1, chapter 15

Key terms

Penney’s game

Coin toss sequence

Overlapping patterns

State diagram

Check yourself