Pattern Race: HTH vs HHT
You and a friend are flipping a fair coin repeatedly. You win if the pattern $HTH$ appears before $HHT$; your friend wins if $HHT$ appears first.
What is the probability that you win?
Hints
- Both patterns start with $H$, so condition on the first head appearing and analyze what happens next.
- After the first $H$, there are four equally likely two-flip outcomes: $TH$, $HT$, $HH$, $TT$. Which ones end the game, and which reset it?
- If you see $HH$, the next tail completes $HHT$ -- your friend is guaranteed to win from that state.
Worked Solution
How to Think About It: Both target patterns start with $H$, so nothing interesting happens until the first head appears. Once you see that first $H$, the next two flips determine which pattern gets completed or whether the game resets. This is a classic Markov chain / pattern-matching problem, but you can solve it with a clever shortcut: condition on the first $H$ and enumerate the four possible two-flip continuations.
Quick Estimate: The two patterns $HTH$ and $HHT$ are not symmetric -- $HHT$ has a structural advantage because $HH$ is a "self-reinforcing" prefix (if you see $HHH$, you are still in position for $HHT$ once a tail comes). So we should expect the probability of $HTH$ winning to be less than $1/2$. Rough guess: somewhere around $1/3$ to $2/5$.
Approach: Condition on the first $H$ and analyze the four possible outcomes of the next two flips.
Formal Solution:
Eventually, a head must appear. Once we see the first $H$, consider the four equally likely outcomes for the next two flips:
| Next two flips | Sequence so far | Result | |---|---|---| | $TH$ | $H \to HTH$ | You win | | $HT$ | $H \to HHT$ | Friend wins | | $HH$ | $H \to HHH$ | Friend will win (see below) | | $TT$ | $H \to HTT$ | Game resets |
Let's verify each case:
- $TH$ (prob $1/4$): The sequence is $HTH$ -- you win immediately.
- $HT$ (prob $1/4$): The sequence is $HHT$ -- your friend wins immediately.
- $HH$ (prob $1/4$): The sequence is $HHH\ldots$ We now have a run of heads. Eventually a tail must appear, giving us $HH\ldots HT$. The last three characters are $HHT$ -- your friend wins. (The key insight: once you see $HH$, the $HHT$ pattern is guaranteed to complete before $HTH$ can appear, because the next tail creates $HHT$.)
- $TT$ (prob $1/4$): The sequence is $HTT$. Neither pattern overlaps with the suffix $TT$, so the game is completely reset -- we are back to waiting for the first $H$.
Since case 4 resets the game, the eventual winner must come from cases 1, 2, or 3. These three outcomes are equally likely (each has probability $1/4$), and only case 1 is a win for you.
Therefore: $$P(\text{you win}) = \frac{P(\text{case 1})}{P(\text{case 1}) + P(\text{case 2}) + P(\text{case 3})} = \frac{1/4}{1/4 + 1/4 + 1/4} = \frac{1}{3}$$
Answer: The probability that $HTH$ appears before $HHT$ is $\dfrac{1}{3}$.
Intuition
This problem is a great example of Penney's game, where two players choose three-flip patterns and race to see which appears first in a sequence of fair coin flips. A surprising result from Penney's game is that for any pattern your opponent chooses, there exists another pattern that beats it with probability greater than $1/2$ -- the game is non-transitive. Here, $HHT$ beats $HTH$ with probability $2/3$, which is a substantial edge.
The key asymmetry is about what happens after partial matches. The pattern $HHT$ has a powerful self-reinforcing property: once you see $HH$, any additional $H$s keep you in the winning state (still waiting for a $T$ to complete $HHT$). By contrast, $HTH$ is fragile -- if the sequence goes $HTT$, the partial match is completely destroyed and you start over. In Markov chain terms, $HHT$ has an absorbing-like structure that $HTH$ lacks. This asymmetry is why experienced competitors in Penney's game know to exploit prefix-suffix overlaps when choosing their patterns.