Penney’s Game

Alice and Bob play a game. Alice chooses a sequence of 3 coin flips. Then Bob chooses another sequence of the same length. They flip a coin over and over again and a player wins as soon as their sequence appears.

What sequence should Alice pick? Does it matter? After all, if you flip a coin 3 times, every sequence has the same chance of occurring.

Well, here’s one choice Alice should avoid. Suppose Alice picks HHH. Then if Bob picks THH, Alice can only win if the first 3 flips are all heads. Bob wins with probability 7/8.

How to play

This game, known as Penney’s game, is trickier than it may seem. But with a few clever observations, we can figure out the best strategies for sequences of any size.

Define:

aintOver goals s is True when no element of goals appears in the string s, that is, the game is still ongoing.
wins goals k s is True when the string in goals of index k has just won the game described by s, that is, the string s ends with the goal string of index k and this is the first goal string of any index to appear.

aintOver goals s = not $ any (`isInfixOf` s) goals

wins goals k s = (goals!!k) `isSuffixOf` s && aintOver goals (init s)

-- From Data.List:
isPrefixOf [] _         =  True
isPrefixOf _  []        =  False
isPrefixOf (x:xs) (y:ys)=  x == y && isPrefixOf xs ys
isSuffixOf xs ys = isPrefixOf (reverse xs) (reverse ys)
isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
tails [] = [[]]
tails xs@(x:xt) = xs : tails xt

-- These should all be True:
aintOver ["HHH", "THH"] "HHTHTHTH"
wins ["HHH", "THH"] 0 "HHH"
wins ["HHH", "THH"] 1 "HHTHTHTHH"

The following shows all coin flip sequences of a given length:

allFlips n = replicateM n "HT"
allFlips 4

For HHH versus THH, we see:

There are many sequences of length 4 where neither player has won yet (though Bob will inevitably win soon enough).
It is impossible for Alice to win in 4 flips.
Bob has 2 ways to win in 4 flips.

filter (aintOver ["HHH", "THH"]) $ allFlips 4
filter (wins ["HHH", "THH"] 0) $ allFlips 4
filter (wins ["HHH", "THH"] 1) $ allFlips 4

Some 4-letter strings are absent from these lists because they do not represent any game. For example, HHHH is an invalid game because it was already over after the 3rd coin flip.

Let’s switch to a less trivial example. Suppose Alice, knowing that HHH is a poor choice, picks HTH. Next, Bob picks HHT, with an innocent expression on his face. Who is more likely to win? Both goals have two Hs and one T, so maybe no one has an advantage?

goals = ["HTH", "HHT"]
filter (aintOver goals) $ allFlips 4
filter (wins goals 0) $ allFlips 4
filter (wins goals 1) $ allFlips 4

There are two games of length 4 where Bob wins, but only one where Alice wins. Already there is an asymmetry worth investigating.

As we wish to compute probabilities, we care more about the number of combinations than particular combinations. Hence for a given 0-indexed list of goal strings, define:

$f (n)$ to be the number of $n$ -letter strings where no one has won yet.
$g_{k} (n)$ to be the number of ways that the $k$ th goal string wins on the $n$ th flip.

f n   = length $ filter (aintOver goals) $ allFlips n
g k n = length $ filter (wins goals k)   $ allFlips n

Then the probability that the $k$ th goal string wins a game is:

$\sum_{n} g_{k} (n) 2^{- n}$

It looks like we’re close to solving the problem, but this is an infinite sum, and our functions have exponential time complexity. We’ll need to be smarter.

Recursion to the rescue

Let $X$ be a string of length $n$ where neither player has won yet. There are 2 ways to append one more letter to get a string of length $n + 1$ , namely H or T, and then either the game continues or someone wins:

$2 f (n) = f (n + 1) + g_{0} (n + 1) + g_{1} (n + 1)$

(Aside: can we prove this from our code via equational reasoning?)

We check this formula for $n = 4$ for our example:

f 4
f 5
g 0 5
g 1 5

This is a great start, but as we have three functions, we need more recurrence relations.

Again let $X$ be a string of length $n$ where neither player has won yet. This time, we append Alice’s goal string $A$ , which we denote $X | | A$ .

If nothing else, Alice wins. For example, if $X$ is TTHTT then $X | | A$ is TTHTTHTH and Alice has just won.

However, we might have gone too far, so to speak. It could be that some strict prefix of $X | | A$ describes a game that is over. For example, if $X$ is HTTTH then $X | | A$ is HTTTHHTH, which is an invalid game because Bob already won one flip earlier.

This subtlety occurs exactly when a proper suffix of $A$ is also the prefix of some goal pattern, possibly itself. In our example, HT is both a prefix of $A$ and a suffix of $B$ . As we append $A$ to a string ending in H, we complete $B$ before we complete $A$ .

This motivates the following. For any strings $X, Y$ , define the correlation $X Y$ to be the set of positive integers $r$ such that the last $r$ letters of $X$ are the same as the first $r$ letters of $Y$ .

The autocorrelation of a string $X$ is the correlation $X X$ . We must have $| X | \in X X$ as $X$ is a prefix and suffix of itself; below this counts the catch-all case of Alice winning once the entirety of $A$ is appended.

correlate s t = filter (\r -> take r t `isSuffixOf` s) [1..length t]
autocorrelate s = correlate s s

correlate "HTH" "HTH"
correlate "HHT" "HTH"

-- Example from paper.
correlate "HTHTTH" "HTTHT"
correlate "HTTHT" "HTHTTH"

Then the above subtlety is:

$f (n) = \sum_{r \in A A} g_{0} (n + r) + \sum_{r \in B A} g_{1} (n + r)$

f 5
g 0 (5 + 1) + g 0 (5 + 3) + g 1 (5 + 2)

Similarly:

$f (n) = \sum_{r \in A B} g_{0} (n + r) + \sum_{r \in B B} g_{1} (n + r)$

What is the matrix?

We now have 3 recurrence relations involving $f, g_{0}, g_{1}$ , and we’ll soon see these are enough to figure out who wins. Define generating functions:

$F (z) = \sum_{n \in [0. .]} f (n) z^{- n}$

$G_{k} (z) = \sum_{n \in [0. .]} g_{k} (n) z^{- n}$

Thus the probability Alice wins is $G_{0} (2)$ , and the probability Bob wins is $G_{1} (2)$ .

For a correlation $X Y$ and any element $z$ of any ring, define:

$X Y_{z} = \sum_{r \in X Y} z^{r - 1}$

We call this correlateBase in our code because a subset of $[1. . n]$ can be represented by an $n$ -bit number which in turn can be interpreted as a base- $z$ number.

correlateBase z x y = sum $ (z^) . pred <$> correlate x y

From our first recurrence relation, and since $f (0) = 1$ and $g_{0} (0) = g_{1} (0) = 0$ :

$(z - 2) F (z) + z G_{0} (z) + z G_{1} (z) = z$

The other two recurrence relations imply:

$F (z) - z A A_{z} G_{0} (z) - z B A_{z} G_{1} (z) = 0$

$F (z) - z A B_{z} G_{0} (z) - z B B_{z} G_{1} (z) = 0$

We can now solve for $F (z), G_{0} (z), G_{1} (z)$ . A unique solution exists because the determinant of these 3 linear equations is:

$ϕ (z) = | \begin{matrix} z - 2 & z & z \\ 1 & - z A A_{z} & - z B A_{z} \\ 1 & - z A B_{z} & - z B B_{z} \end{matrix} |$

The product of the main diagonal entries is a polynomial of degree higher than all other terms of the determinant because it’s where the autocorrelations reside (recall $| X | \in X X$ ), ensuring a nonzero determinant.

Solving for $G_{0} (z)$ and evaluating at $z = 2$ :

$G_{0} (2) = \frac{B B_{2} - B A_{2}}{B B_{2} - B A_{2} + A A_{2} - A B_{2}}$

In other words, the odds that Alice wins are:

$\frac{B B_{2} - B A_{2}}{A A_{2} - A B_{2}}$

oddsBase q a b = (num `div` d, denom `div` d) where
  go = correlateBase q
  num = go b b - go b a
  denom =  go a a - go a b
  d = gcd num denom
oddsCoin = oddsBase 2

oddsCoin "HTH" "HHT"

We see in the HTH versus HHT battle, Alice’s odds are 1 to 2, that is, Bob is twice as likely to win.

The above generalizes for alphabets with $q$ different symbols, in which case Alice’s odds of winning are:

$\frac{B B_{q} - B A_{q}}{A A_{q} - A B_{q}}$

For example, the PIN number 2357 is easier to guess than 0000 in the sense that it’s more likely to show up first if we stab digits at random.

oddsBase 10 "2357" "0000"

We can also generalize to any number of players; even zero players.

Let $S_{1}, \dots , S_{m}$ be the goal strings for some nonnegative integer $m$ such that no goal string is a substring of any other goal string. This was implied in our earlier examples because the goal strings were distinct and had the same length; here, there is no such constraint on the lengths. (We index from 1 this time to get nicer formulas.)

Then:

$(z - q) F (z) + z G_{1} (z) + \dots + z G_{m} (z) = z$

and for $k \in [1. . m]$ :

$F (z) - z (S_{1} S_{k})_{z} G_{1} (z) - \dots - z (S_{m} S_{k})_{z} G_{m} (z) = 0$

Table for one

Consider the solitaire variant of this game, namely, suppose Alice is the lone player. What goal $A$ should Alice choose to minimize the expected number of flips?

The probability of needing more than $n$ random letters is $f (n) q^{- n}$ , hence the expected wait time is:

$\sum_{n} f (n) q^{- n}$

From above, this turns out to be:

$F (q) = q A A_{q}$

Presumably, Alice should choose a sequence that minimizes the wait time, such as HTT for sequences of length 3.

eThrows q a = q * correlateBase q a a

[(a, eThrows 2 a) | a <- allFlips 3]

Then she has the best chance of seeing her goal show up before Bob’s, and has at least even odds of winning, right?

Wrong!

After you. I insist.

The early bird gets the worm, but the second mouse gets the cheese.

If Alice chooses HTT, then Bob chooses HHT:

oddsCoin "HTT" "HHT"

Again, Bob is twice as likely to win.

If Alice tries to pre-empt this by choosing HHT herself, then Bob chooses THH:

oddsCoin "HHT" "THH"

This time, Bob is three times more likely to win! (Alice only wins if the first two flips are both heads.) What’s going on?

From Bob’s goal string, we get Alice’s goal by adding the right letter, but not the other way around. This hints that the expected wait time to reach Bob’s goal starting from Alice’s string is much longer than the other way around.

Imagine a long random string of coin flips. We expect it to contain many occurrences of both $A$ and $B$ . If we randomly snip this string in two, we’re more likely to interrupt a transition from $A$ to $B$ than the other way around. Starting from where we made the cut, we’re more likely to encounter $B$ first.

We can quantify the expected wait time from one string to another with the following handy generalization:

Let $X$ be a string that contains none of the goals $S_{1}, \dots , S_{m}$ , though we allow $X$ to be a substring of a goal. (Indeed, setting $X$ to the empty string yields the previous generalization.)

Define $f (n)$ to be the number of strings of length $n$ that start with $X$ and contain none of the goal strings, and $g_{k} (n)$ to be the number of strings of length $n$ that start with $X$ and end with $S_{k}$ , and otherwise contain no occurrences of any goal string.

Then it can be shown:

$(z - q) F (z) + z G_{1} (z) + \dots + z G_{m} (z) = z^{1 - | X |}$

and for $k \in [1. . m]$ :

$F (z) - z (S_{1} S_{k})_{z} G_{1} (z) - \dots - z (S_{m} S_{k})_{z} G_{m} (z) = z^{1 - | S_{k} |} (X S_{k})_{z}$

Returning to Alice and Bob, set $X = B$ and again consider the solitaire variant with $A$ as the lone goal. Then we find the expected wait time to reach $A$ after $B$ is:

$q A A_{q} - q B A_{q}$

eThrowsFrom q a b = q * correlateBase q a a - q * correlateBase q b a

This leads to an alternative derivation of the formula for Alice’s odds. But more importantly, we can use the expected wait time to shed light on Bob’s optimal strategy.

Let $A = a_{1} \dots a_{m}$ be Alice’s goal. Then Bob maximizes his chance of winning by choosing $B = b a_{1} \dots a_{m - 1}$ for some $b$ .

The case $m = 2$ is small enough to be verified directly from the formula for Alice’s odds. Brute force shows Bob should choose $b \neq a_{1}$ and when possible, also ensure that $b \neq a_{2}$ .

When $a_{1} = a_{2}$ , his odds of winning are $q + 1$ to $q - 1.$ When $a_{1} \neq a_{2}$ , Bob has even odds when $q = 2$ (where he must choose $b = a_{2}$ ), and for $q \geq 3$ his odds to win are $q$ to $q - 1.$

bruteCoin a = [(b, oddsCoin a b) | b <- allFlips $ length a, b /= a]
bruteCoin "HH"
bruteCoin "HT"

For goal strings of length 3, it turns out Bob should choose his first flip to be the opposite of his third flip.

bobs a = (`oddsCoin` a) <$> filter (/= a) ['H':ai, 'T':ai] where ai = init a

bobs <$> allFlips 3

bobs <$> allFlips 5

We see that for coin flipping goals of length 5, the best strategy for Alice is to pick a goal that caps Bob’s odds of winning at 17 to 9. More generally, it turns out for $m \geq 4$ , Alice’s best choice is one head at the beginning, two heads at the end, and tails otherwise, or the same string with everything flipped, though with optimal play Bob’s advantage is always close to 2 to 1.

For general $m$ , it is unknown if there is a simple scheme for picking $b$ optimally. For $q = 2$ , the best choice for $b$ seems unique, but no proof of this is known.

Penney’s game is nontransitive, like the game of rock, paper, scissors. If one player moves first, they suffer a great disadvantage.

Sketch of proof

Define the periods of a string as follows:

periods s = filter (\r -> drop r s `isPrefixOf` s) [1..length s]

-- In terms of the autocorrelation:
periods' s = tail $ reverse $ (length s -) <$> 0 : autocorrelate s

periods "abcabc"
periods "abcabcd"
periods "abcdabc"
periods "aaaaaa"

We can interpret periods as the prefixes of $S$ that can be repeated to generate a string beginning with $S$ .

The basic period of a string is its shortest period:

basicPeriod s = head $ periods s

The periods of a string are the same as its autocorrelation except we count the number of removed letters rather than the number that remain, and we exclude zero but include the string length. Half-empty versus half-full.

Let $k$ be the length of Alice’s goal string $A$ .

Assume $k \geq 3$ , as the smaller cases are easily dispatched.

Let $A^{'}$ be all but the last letter of $A$ (Haskell’s init function), and let $r$ be the basic period of $A^{'}$ . Select $b$ so that it differs from the $r$ th letter of $A^{'}$ , and set $B = b : A^{'}$ , where we have borrowed Haskell’s notation for consing a list of letters.

Let $C$ be a string of length $k$ whose tail (borrowing another term from Haskell) differs from $A^{'}$ . Then it turns out the odds of $B$ appearing before $A$ must exceed the odds of $C$ appearing before $A$ . This does not imply Bob’s best choice is $B$ ; indeed, we can easily find examples where Bob can do better than $B$ . But it does imply the tail of any best choice must be $A^{'}$ .

This is easy to show when $r = 1$ . Relabel so that $A$ is HH…H and $B$ is TH…H. Let $C$ be any string of length $k$ whose tail contains at least one letter that differs to H.

We have:

$A C_{q} \geq 0 = A B_{q}$

Also:

$C C_{q} \geq q^{k} = B B_{q}$

Lastly, let $m$ be the number of trailing Hs in $C$ . We have $m < k - 1$ because of how we chose $C$ , hence:

$C A_{q} \leq q + \dots + q^{m} < q + \dots + q^{k - 1} = B A_{q}$

Therefore:

$\frac{A A_{q} - A B_{q}}{B B_{q} - B A_{q}} > \frac{A A_{q} - A C_{q}}{C C_{q} - C A_{q}}$

In other words, the goal $B$ has strictly better odds of beating $A$ than any goal whose tail differs to the tail of $A$ .

Here we happen to know $B$ is optimal, as $B \neq A$ and by symmetry all other choices of the first letter have the same odds, which we can compute with a touch of algebra. Bob’s odds of victory are:

$\frac{q^{k} - 1}{q^{k} - 2 q^{k - 1} + 1}$

It remains to handle the cases $r \geq 2$ .

Let $t$ be the basic period of $B$ .

Suppose $t \leq k - 2$ . By construction $t$ is also a period of $A^{'}$ , and is not a multiple of $r$ . It can be shown this implies $t + r \geq k$ . Briefly, suppose at least one integer less than $k - r$ is period of $A^{'}$ yet is not a mulitple of $r$ , and let $s$ be the smallest such integer. Then we can show $s - r$ is a period of $A^{'}$ , contradicting the minimality of $s$ .

This implies $t \geq (k + 1) / 2$ , which can be refined to $t \geq (k + 2) / 2$ .

When $t > k - 2$ we also have $t \geq (k + 2) / 2$ because $k - 1 \geq (k + 2) / 2$ for $k \geq 4$ and $k = 3, t = 2$ leads to a contradiction.

This bound then leads to bounds for $A B_{q}$ and $B B_{q} - B A_{q}$ which yield:

$\frac{A A_{q} - A B_{q}}{B B_{q} - B A_{q}} \geq \frac{A A_{q} - \frac{q^{⌊ k / 2 ⌋} - 1}{q - 1}}{q^{k - 1} - q^{k - 2} + q^{⌊ k / 2 ⌋ - 2}}$

This shows Bob’s odds of winning are at least:

$\frac{q}{q - 1} - O (q^{k / 2})$

as $k \to \infty$ .

We have $C A_{q} \leq q^{k - 3} + q^{k - 4} + \dots + 1$ and $C C_{q} \geq q^{k - 1}$ which implies:

$\frac{A A_{q} - A C_{q}}{C C_{q} - C A_{q}} \leq \frac{A A_{q}}{q^{k - 1} - \frac{q^{k - 2} - 1}{q - 1}}$

It remains to show one bound is strictly greater than the other. This turns out to only take a few steps when $q \geq 3$ , while $q = 2$ becomes a tedious case analysis.

References

Guibas and Odlyzko, String Overlaps, Pattern Matching, and Nontransitive Games.

Ben Lynn blynn@cs.stanford.edu 💡