HTH vs HH: Which Pattern Appears First?
A fair coin is tossed repeatedly. The game ends the moment either the pattern $HH$ or the pattern $HTH$ appears as consecutive flips -- whichever comes first.
What is the probability that $HTH$ appears before $HH$?
Model the process as a Markov chain over states that track the relevant suffix of the flip sequence. Set up and solve the system of linear equations exactly.
Hints
- Model the process as a Markov chain. States should capture only the relevant suffix of the flip sequence -- the part that represents progress toward either pattern.
- The key states are: start/reset ($S_0$), one $H$ seen ($S_H$), and $HT$ seen ($S_{HT}$). Draw the transitions carefully -- from $S_H$, a second $H$ immediately ends the game.
- Let $p_s$ be the probability $HTH$ wins from state $s$. Write equations: $p_0 = \frac{1}{2}p_H + \frac{1}{2}p_0$, $p_H = \frac{1}{2}p_{HT}$, $p_{HT} = \frac{1}{2} + \frac{1}{2}p_0$. Solve.
Worked Solution
How to Think About It: Competing-pattern races are solved by first-step / suffix-state analysis: the only history that matters is the longest current suffix that is a prefix of a target pattern. The structural asymmetry is the whole story — $HH$ finishes in $2$ symbols, $HTH$ in $3$, and crucially they *share the leading $H$*. Every time you are one flip into $HTH$ (state $H$), the very next $H$ completes $HH$ and kills you. So $HH$ is always "closer," and the naive guess that $HTH$ wins less than half the time is correct — the trap would be to expect symmetry.
Quick Estimate: Reason from the first useful flip. You only care once an $H$ appears (state $H$). From there, one flip decides a lot: with prob $\tfrac12$ the next flip is $H$ and $HH$ wins immediately (you lose the race for $HTH$). So *just from reaching state $H$*, you already forfeit half the time on the spot — an upper bound of $\tfrac12$ on winning, and you must still complete the extra third symbol afterward, dragging it below $\tfrac12$. A one-level refinement: after the surviving $HT$ (prob $\tfrac12$), the next flip wins with prob $\tfrac12$, else you reset. Rough win $\approx \tfrac12\cdot\tfrac12 \approx \tfrac14$ per attempt from state $H$ — landing right on the exact $\tfrac13$ once resets are folded in. Estimate: around one-third, comfortably under a half.
Approach: Suffix states, then a three-equation balance solved by back-substitution.
Formal Solution:
States by relevant suffix; $p_s$ = probability $HTH$ wins from state $s$:
- $S_0$: no useful progress (start, or a trailing $T$ off a reset)
- $S_H$: suffix $H$ (one step into both patterns)
- $S_{HT}$: suffix $HT$ (two steps into $HTH$, $HH$ derailed)
- absorbing $WIN$ ($HTH$), $LOSE$ ($HH$)
Transitions (each flip prob $\tfrac12$):
$$p_0 = \tfrac12 p_H + \tfrac12 p_0 \;\Rightarrow\; p_0 = p_H,$$ $$p_H = \tfrac12\cdot 0 + \tfrac12 p_{HT} = \tfrac12 p_{HT}\quad(H\to HH\ \text{loses};\ T\to HT),$$ $$p_{HT} = \tfrac12\cdot 1 + \tfrac12 p_0\quad(H\to HTH\ \text{wins};\ T\to \text{reset to } S_0).$$
Back-substitute. From the third, $p_{HT} = \tfrac12 + \tfrac12 p_0$. Feed into the second: $p_H = \tfrac12\big(\tfrac12 + \tfrac12 p_0\big) = \tfrac14 + \tfrac14 p_0$. Using $p_0 = p_H$:
$$p_0 = \tfrac14 + \tfrac14 p_0 \;\Rightarrow\; \tfrac34 p_0 = \tfrac14 \;\Rightarrow\; p_0 = \tfrac13.$$
Then $p_{HT} = \tfrac12 + \tfrac16 = \tfrac23$ and $p_H = \tfrac16$. The game starts in $S_0$, so the win probability is $p_0 = \boxed{\tfrac13}$.
Answer: $P(HTH\ \text{before}\ HH) = 1/3$.
Intuition
The asymmetry here is striking: even though $HTH$ is a longer pattern, it wins only $1/3$ of the time against $HH$. The reason is that $HH$ has a structural advantage -- the moment you see the first $H$, you are already halfway there, and the next flip either completes it or transitions to a state ($HT$) that has to work hard to get $HTH$ before resetting. $HTH$ can never "ambush" $HH$ the way $HH$ can ambush $HTH$.
This illustrates a general principle in competing pattern problems: shorter patterns are not always dominant, but patterns that overlap with themselves (like $HH$, where seeing $HH$ means you already have the second $H$ for another $HH$) tend to be harder to beat. The Markov chain approach is the clean, general way to handle these -- it avoids the combinatorial mess of directly counting sequence lengths and is the method you should default to in any interview.