HTH vs HTT Pattern Race
Alice and Bob are watching a single stream of fair coin flips. Alice wins as soon as the pattern $\text{HTH}$ appears. Bob wins as soon as $\text{HTT}$ appears. Whichever pattern shows up first in the sequence determines the winner.
What is the probability that Alice wins?
Hints
- Both HTH and HTT start with the same two-letter prefix. What does that tell you about the moment the race is decided?
- Set up a Markov chain with states based on the longest suffix matching a prefix of either target pattern. There are only three non-terminal states: $S$, $H$, and $HT$.
- From state $HT$, the very next flip decides the winner -- $H$ for Alice, $T$ for Bob -- each with probability $1/2$. Now check whether the chain reaches $HT$ with any bias.
Worked Solution
How to Think About It: Both patterns start with $\text{HT}$, so the race is really about what happens after we see $\text{HT}$. If the next flip is $H$, Alice wins ($\text{HTH}$). If it is $T$, Bob wins ($\text{HTT}$). That immediately suggests the answer might be $1/2$. But you need to be careful -- maybe the way the sequence reaches state $\text{HT}$ is biased somehow? The right way to check is to set up a Markov chain on the longest suffix of the current sequence that matches a prefix of either target pattern.
Quick Estimate: Once you realize both patterns share the prefix $\text{HT}$, and the deciding flip is a single fair coin, you should guess $1/2$ right away. The only thing left to verify is that there is no bias in how often you reach state $\text{HT}$ conditional on who eventually wins -- and since $\text{HT}$ is an absorbing bottleneck that both patterns must pass through, there is no such bias.
Approach: Build a Markov chain on the relevant suffixes and solve for the probability of Alice winning from the start state.
Formal Solution:
Define states by the longest suffix of the sequence seen so far that is a prefix of either $\text{HTH}$ or $\text{HTT}$:
- $S$ (start): no useful suffix
- $H$: last flip was $H$
- $HT$: last two flips were $H, T$
- $\text{HTH}$: Alice wins (absorbing)
- $\text{HTT}$: Bob wins (absorbing)
Transitions (each branch has probability $1/2$):
| State | Flip $H$ | Flip $T$ | |-------|----------|----------| | $S$ | $H$ | $S$ | | $H$ | $H$ | $HT$ | | $HT$ | Alice wins | Bob wins |
Note the key transitions: - From $S$, a $T$ does not advance either pattern, so we stay at $S$. - From $H$, another $H$ keeps us in state $H$ (we still have a trailing $H$). - From $HT$, the next flip is decisive.
Let $p_S$, $p_H$, $p_{HT}$ be the probability Alice wins from each state.
From $HT$: $$p_{HT} = \frac{1}{2}(1) + \frac{1}{2}(0) = \frac{1}{2}$$
From $H$: $$p_H = \frac{1}{2} p_H + \frac{1}{2} p_{HT} = \frac{1}{2} p_H + \frac{1}{4}$$
Solving: $p_H = \frac{1}{2}$.
From $S$: $$p_S = \frac{1}{2} p_H + \frac{1}{2} p_S = \frac{1}{4} + \frac{1}{2} p_S$$
Solving: $p_S = \frac{1}{2}$.
Answer: The probability that Alice wins is $\dfrac{1}{2}$. The two patterns are equally likely to appear first because they share the prefix $\text{HT}$, and the deciding flip from state $\text{HT}$ is a fair coin.
Intuition
This problem is a special case of Penney's game, where two players compete to see whose chosen three-letter pattern appears first in a sequence of fair coin flips. The surprising general result is that for most pairs of patterns, the race is NOT fair -- one pattern tends to appear first more often. But HTH vs HTT is the exception. Because both patterns funnel through the same bottleneck state $\text{HT}$, and the final deciding flip is a single fair coin, neither side has an edge. The Markov chain collapses the entire race down to that one decisive moment.
Contrast this with, say, HHH vs THH. There, THH wins with probability $7/8$ because after a $T$ (which sends HHH back to the start), the sequence is already one step toward THH. The lesson: in pattern races, what matters is not just the length of the pattern but how the patterns overlap with each other and with the sequence's recent history. When two patterns share the same prefix and diverge only at the last letter, the race comes down to a single coin flip and is always fair.