Penney's Game and Non-Transitive Patterns

The problem. Two players each pick a sequence of Heads/Tails of length 3 (e.g., HHT). A fair coin is flipped repeatedly; whoever's pattern appears first in the sequence wins. You get to pick your pattern second, after seeing your opponent's choice. Can you always choose a pattern that beats theirs? Surprisingly, yes — for every possible 3-flip pattern, there's another pattern that beats it with probability greater than 50%. And the "beats" relation is non-transitive: pattern B can beat A, C can beat B, and A can beat C, so there's no single best pattern to lock in.

The winning rule: steal the front, flip the back

Given the opponent's 3-flip pattern $X_1 X_2 X_3$, the standard beating strategy is: take the opposite of the middle flip, then repeat the opponent's first two flips as your last two. Concretely, your pattern is $\overline{X_2}\, X_1\, X_2$. For example, if the opponent picks HHH, flip the middle H to T and prepend it, using the first two of their pattern as your last two: your pattern is THH.

Why THH beats HHH: HHH can only ever appear as the very first three flips, or by extending an existing run of H's that started right after a T. But the instant a T appears anywhere with two H's following it, THH completes — and any run of H's long enough to become HHH necessarily passed through "a T, then H, then H" on the way there (unless the very first three flips are HHH outright). So THH is waiting at the door for almost every path that would otherwise build toward HHH. Working through the Markov chain over flip-by-flip progress gives $P(\text{THH beats HHH}) = \frac{7}{8}$ — a landslide, not a coin flip.

Worked example: HHT vs the field

Suppose the opponent picks HHT. The rule says: flip the middle (H→T), prepend it, keep first two as last two: your pattern is THH. Setting up the Markov chain over the states "no useful prefix," "H," "HH," "HHT" (opponent wins), "THH-progress" is involved by hand, but the known result for this matchup is $P(\text{THH beats HHT}) = \frac{3}{4}$. Notice the pattern: the "steal the front" strategy doesn't just marginally beat the opponent's choice — it beats it decisively, between 2:1 and 7:1 depending on the specific pattern chosen.

The general technique: sequence games are Markov chains, not coin-flip counting

The instinct to reason about pattern games by counting flips directly fails because patterns can overlap with themselves (like HHH, which shares a prefix/suffix structure) in ways that change how quickly they can recur, while others (like HTH) can't reuse partial progress as efficiently. The correct tool is to model the race as a Markov chain over "how much progress toward each pattern has been made so far," and compute absorption probabilities. Penney's game is the standard vehicle for teaching that lesson: it looks like elementary counting, but elementary counting gives the wrong answer, and it's non-transitivity — like rock-paper-scissors — that should be the real takeaway, since it shows "always go second" beats any fixed first choice.