Comparing Binary Pattern Arrival Times via Prefix

Welcome to the first lesson of your short course on interesting mathematical problems. We'll start with a fascinating and counter-intuitive puzzle in probability known as Penney's Game. It's a simple game involving coin flips, but the outcome often defies initial intuition.

In this lesson, you will learn how to determine the winner in a "pattern race" between two sequences of coin flips. Our goal is to compute the precise probability that one pattern appears before another by analyzing the way these patterns overlap with themselves and with each other. We'll start with the game's paradox, build some intuition using state diagrams, and then learn a powerful algorithm to solve any two-pattern race.

The Paradox of Penney's Game

Imagine a game where two players, Alice and Bob, choose different sequences of three coin flips (e.g., Alice picks HTH, Bob picks HHT). They then start flipping a fair coin repeatedly. The first player to see their chosen sequence appear in the stream of flips wins.

At first glance, since any specific sequence of three flips (like HTH or HHT) has the same probability of occurring ( $1/ 2^{3} = 1/8$ ), it seems like the game should be fair, or at least that no player has a significant advantage regardless of the choice. However, this is not the case. The game is non-transitive, much like rock-paper-scissors, and the second player to choose a sequence can always pick one that gives them a distinct advantage.

To get a feel for this paradox and the game's surprising dynamics, let's watch a video from the Numberphile channel.

Penney's Game - Numberphile

This video provides an excellent and engaging introduction to Penney's Game.

Please watch the first part of the video, which introduces the game, shows it being played, and reveals the "cycle of winning" that makes the game non-transitive. Focus on the section from the beginning up to the explanation of the cycle. Pay attention to how, for any choice the first player makes, there's a better choice for the second player.

The key insight from the video is that this isn't about the probability of a sequence appearing in a fixed set of three flips. It's about which sequence appears first in a continuous stream. The structure of the patterns and how they can overlap is what creates the advantage.

Consider the classic example of Alice choosing HHH and Bob choosing THH. Alice can only win if the very first three flips are HHH. Why? Because for HHH to appear at any later point for the first time, the flip immediately preceding it must have been a T (otherwise, an earlier HHH would have already won). But if the sequence is ...THHH, then Bob's sequence, THH, has already appeared. Therefore, Bob wins in every scenario except the 1-in-8 chance that the first three flips are HHH. This gives Bob a winning probability of 7/8.

Building Intuition with State Machines

The "overlap" concept can be formalized by thinking about the game as a state machine. Since you have a background in machine learning and applied mathematics, you might find it natural to model this problem using Markov chains. The state of our system can be defined by the most recent flips, and we transition between states as new flips occur. The patterns we are looking for become absorbing states.

The following video provides a clear explanation of this approach. It visualizes how the game progresses and how overlaps between patterns influence the probabilities of reaching one absorbing state before another.

An Unintuitive Coin Flip Problem (With Secret Markov Chains)

This video uses the concept of Markov chains to explain why the probabilities in this problem are unequal.

Watch the segments from the simplified two-flip case and from the original three-flip problem. As you watch, notice how the chosen patterns alter the structure of the state transition diagram. Specifically, see how overlaps (or lack thereof) can remove pathways into one of the winning states, making it less likely to be reached.

As the video demonstrates, the key is how the patterns can "set up" themselves or their opponent. A pattern that overlaps with itself significantly (like HHH) can be "reset" by a single wrong flip, whereas a pattern that leads into the opponent's sequence gives the opponent an advantage. This state-based view explains why the probabilities are skewed, but calculating them from the full transition matrix can be cumbersome. Fortunately, there's a much more direct method.

A General Formula for Pattern Races

The mathematician John Conway developed a brilliantly simple algorithm to calculate the odds for any pair of sequences. The method relies on quantifying the overlap between the two patterns, A and B.

Let's define an "overlap score" between two patterns $X$ and $Y$ of the same length $k$ . We'll denote this score as $⟨ X, Y ⟩$ .

The score is calculated by comparing the prefix of $Y$ with the suffix of $X$ for every possible overlap length from 1 to $k$ .

⟨ X, Y ⟩ = i = 1 \sum k 2^{i - 1} \cdot I (suffix of X of length i = prefix of Y of length i)

where $I$ is the indicator function (it is 1 if the condition is true, and 0 otherwise).

We need to compute four such scores:

$⟨ A, A ⟩$ : How A overlaps with itself.
$⟨ B, B ⟩$ : How B overlaps with itself.
$⟨ A, B ⟩$ : How a suffix of A can start B.
$⟨ B, A ⟩$ : How a suffix of B can start A.

Once we have these four values, the odds that Alice (A) wins against Bob (B) are given by the formula:

Odds(A wins) = \frac{⟨ B , B ⟩ - ⟨ B , A ⟩}{⟨ A , A ⟩ - ⟨ A , B ⟩}

If the odds are $x / y$ , the probability of A winning is $x / (x + y)$ .

Example: A = HTH vs. B = HHT

Let's calculate the odds for this pair. Here, $k = 3$ .

$⟨ A, A ⟩$ for A = HTH:
- Length 1: Suffix 'H' == Prefix 'H' (Yes) $\to 2^{0} = 1$
- Length 2: Suffix 'TH' == Prefix 'HT' (No) $\to 0$
- Length 3: Suffix 'HTH' == Prefix 'HTH' (Yes) $\to 2^{2} = 4$
- $⟨ A, A ⟩ = 1 + 0 + 4 = 5$
$⟨ B, B ⟩$ for B = HHT:
- Length 1: Suffix 'T' == Prefix 'H' (No) $\to 0$
- Length 2: Suffix 'HT' == Prefix 'HH' (No) $\to 0$
- Length 3: Suffix 'HHT' == Prefix 'HHT' (Yes) $\to 2^{2} = 4$
- $⟨ B, B ⟩ = 0 + 0 + 4 = 4$
$⟨ A, B ⟩$ for A = HTH, B = HHT:
- Length 1: Suffix 'H' of A == Prefix 'H' of B (Yes) $\to 2^{0} = 1$
- Length 2: Suffix 'TH' of A == Prefix 'HH' of B (No) $\to 0$
- Length 3: Suffix 'HTH' of A == Prefix 'HHT' of B (No) $\to 0$
- $⟨ A, B ⟩ = 1 + 0 + 0 = 1$
$⟨ B, A ⟩$ for B = HHT, A = HTH:
- Length 1: Suffix 'T' of B == Prefix 'H' of A (No) $\to 0$
- Length 2: Suffix 'HT' of B == Prefix 'HT' of A (Yes) $\to 2^{1} = 2$
- Length 3: Suffix 'HHT' of B == Prefix 'HTH' of A (No) $\to 0$
- $⟨ B, A ⟩ = 0 + 2 + 0 = 2$

Now, we plug these into the formula:

Odds(A wins) = \frac{4 - 2}{5 - 1} = \frac{2}{4} = \frac{1}{2}

The odds are 1 to 2 in favor of A winning. This means Bob is twice as likely to win as Alice.

Probability Alice (HTH) wins: $1/ (1 + 2) = 1/3$
Probability Bob (HHT) wins: $2/ (1 + 2) = 2/3$

This powerful algorithm provides the answer for any pair of binary patterns. For a more formal treatment of this formula and its derivation, you can refer to the following resource.

Probability - Penney's Game

This webpage by Ben Lynn provides a rigorous mathematical derivation of the formula we just used. It uses concepts like recurrence relations and generating functions, which may be familiar to you.

I encourage you to read the sections Recursion to the rescue and What is the matrix?. The "correlation" XY and the term XY_z defined in the text correspond directly to our overlap score \langle X, Y \rangle when z=2. This reading will show you how the formula is derived by setting up and solving a system of linear equations based on generating functions that describe the game's states.

The derivation shows that the simple overlap calculation is a neat encapsulation of a more complex dynamic process, solvable with standard tools from applied mathematics.

Conclusion

In this lesson, we explored the surprising probabilities of Penney's Game. We've seen that what appears to be a fair game of chance is actually a deterministic puzzle based on pattern structure.

Here are the key takeaways:

Penney's Game is non-transitive: The second player to choose a pattern always has an advantage.
Overlaps are key: The winning probability is determined by how patterns overlap with themselves and each other. A high self-overlap (like in HHH) can be a disadvantage, as it creates a "brittle" pattern that is easily disrupted. An overlap with your opponent's pattern can either give you a "head start" or unfortunately lead you to set them up for a win.
Conway's algorithm provides a solution: We learned a straightforward method to compute the odds for any two-pattern race by calculating four overlap scores.
The math behind the magic: The algorithm has a solid mathematical foundation in recurrence relations and generating functions, which model the probabilistic evolution of the game.

In our next lesson, we will tackle another famous problem with a startlingly counter-intuitive probabilistic result: the 100 Prisoners Problem. It will take us into the world of permutations and cycle decomposition.

Comparing Binary Pattern Arrival Times via Prefix–Suffix Overlaps

Recommended resources

The Paradox of Penney's Game

Building Intuition with State Machines

A General Formula for Pattern Races

Example: A = HTH vs. B = HHT

Conclusion