Pattern Race: HHT vs HTH
Two players are racing on a sequence of fair coin flips. Player 1 wins when the pattern HHT appears in the running sequence; Player 2 wins when HTH appears. Both players watch the same sequence of flips -- the game ends the moment either pattern shows up as the last three flips.
- What is the probability that Player 1 (HHT) wins?
- What is the probability that Player 2 (HTH) wins?
- Why aren't the probabilities equal, even though both patterns have the same length and the coin is fair?
Hints
- Think about what happens once you've seen two heads in a row (state HH). Can Player 2 win from that point? What does that imply about Player 1's advantage?
- Set up a Markov chain with states $\{\emptyset, H, HH, HT\}$ tracking the relevant suffix of the flip sequence. Write equations for $p_s =$ P(Player 1 wins from state $s$).
- From state $HH$, solve $p_{HH} = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot p_{HH}$ to get $p_{HH} = 1$. Then use $p_{HT} = p_{\emptyset}/2$ and $p_{\emptyset} = p_H$ to reduce everything to one equation in $p_{\emptyset}$.
Worked Solution
How to Think About It: Your first instinct might be 50/50 -- both patterns are length 3, the coin is fair, what could break the symmetry? But the patterns have very different "self-reinforcing" properties. Think about what happens when you're in state HH (two heads in a row): from there, tails completes HHT immediately, and heads keeps you in HH. Player 2 can never win from HH -- you're locked into Player 1's territory. Contrast this with state HT: heads gives Player 2 the win, but tails sends you all the way back to the start. That asymmetry is everything.
Quick Estimate: Here's an informal way to see Player 1 must win more often. Once the first H appears (which happens quickly), half the time you go to HH and half the time to HT. From HH, Player 1 wins with certainty (as argued above). From HT, it's a coin flip: Player 2 wins outright or you reset. So a rough argument: Player 1 wins at least half the time from the first H, and "resets" mostly help Player 1 by eventually cycling back through H to HH. A probability above 1/2 is certain -- and we'll show it's exactly 2/3.
Approach: Set up a Markov chain on the shared flip history. The relevant states are the suffixes of the current sequence that form a prefix of one or both patterns.
Formal Solution:
The states track the longest suffix of flips so far that is a prefix of either target pattern:
- $\emptyset$: no useful suffix (start state, or after an isolated T)
- $H$: last flip was H
- $HH$: last two flips were HH
- $HT$: last two flips were HT
Transitions (each with probability
- From $\emptyset$: $H \to H$, $T \to \emptyset$
- From $H$: $H \to HH$, $T \to HT$
- From $HH$: $H \to HH$ (still HH), $T \to$ Player 1 wins (HHT complete)
- From $HT$: $H \to$ Player 2 wins (HTH complete), $T \to \emptyset$ (reset)
Let $p_s$ denote the probability that Player 1 wins starting from state $s$.
From $HH$: A tail completes HHT (Player 1 wins); a head keeps you in $HH$. $p_{HH} = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot p_{HH} \implies p_{HH} = 1$ Once in state $HH$, Player 1 wins with certainty.
From $HT$: A head completes HTH (Player 2 wins, so Player 1 loses); a tail resets to $\emptyset$. $p_{HT} = \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot p_{\emptyset} = \frac{p_{\emptyset}}{2}$
From $H$: A head goes to $HH$ (Player 1 wins for sure); a tail goes to $HT$. $p_H = \frac{1}{2} \cdot p_{HH} + \frac{1}{2} \cdot p_{HT} = \frac{1}{2} + \frac{p_{\emptyset}}{4}$
From $\emptyset$: A head goes to $H$; a tail stays at $\emptyset$. $p_{\emptyset} = \frac{1}{2} \cdot p_H + \frac{1}{2} \cdot p_{\emptyset} \implies p_{\emptyset} = p_H$
Substituting $p_{\emptyset} = p_H = \frac{1}{2} + \frac{p_{\emptyset}}{4}$: $p_{\emptyset} - \frac{p_{\emptyset}}{4} = \frac{1}{2} \implies \frac{3}{4} p_{\emptyset} = \frac{1}{2} \implies p_{\emptyset} = \frac{2}{3}$
Answer: Player 1 (HHT) wins with probability $\boxed{\dfrac{2}{3}}$, and Player 2 (HTH) wins with probability $\dfrac{1}{3}$.
Intuition
The surprising 2/3 vs 1/3 split comes down to a structural asymmetry hidden inside the patterns: HHT contains a "trap" state (HH) that Player 1 owns outright, while HTH does not. Once the sequence hits HH, the next flip either ends the game in Player 1's favor or keeps it in HH -- Player 2 is completely locked out. The HT state, by contrast, is balanced: one outcome wins for Player 2, the other resets entirely. So HH is a one-way ratchet for Player 1, while HT is a fair coin flip for Player 2. This kind of pattern-overlap analysis is directly connected to the Conway leading number method, which gives a slick way to compute pattern race probabilities without building the full Markov chain.
In practice, this type of problem shows up whenever you are reasoning about stopping times or first-passage distributions -- option expiry, order fill timing, hitting a P&L threshold. The lesson is that "symmetric-looking" setups can have dramatically asymmetric probabilities once you account for what happens when a sequence partially matches and then fails. The overlap structure of a pattern with itself and with its competitor determines which side has the structural edge -- and that edge can be substantial.