HHT Before THH in Coin Flips
You flip a fair coin repeatedly. Two players are watching: Player A wins if the sequence HHT appears before THH, and Player B wins if THH appears first.
What is the probability that HHT appears before THH?
Hints
- Set up a Markov chain with states tracking the longest suffix of the flip sequence that is relevant to either pattern. The absorbing states are HHT (Player A wins) and THH (Player B wins).
- From state $HH$, notice that HHT must eventually occur -- flipping H keeps you at $HH$, and flipping T completes HHT. So $p_{HH} = 1$.
- From state $T$, show that you can never reach $HH$ without first completing $THH$. This forces $p_T = 0$, which dramatically limits HHT's winning chances.
Worked Solution
How to Think About It: This is a Penney's game problem -- comparing which of two three-letter sequences appears first in an infinite stream of fair coin flips. The key insight is that these probabilities are NOT symmetric, even though both sequences have the same single-occurrence probability of $(1/2)^3$. The structure of how the sequences overlap with each other matters enormously. To solve it, set up a Markov chain where the states track the longest relevant suffix of the flips seen so far.
Quick Estimate: Think about what happens after the first flip. If the first flip is T (probability $1/2$), we are in a state that favors THH -- we already have the first letter of THH and none of HHT. From state T, the only way HHT can win is if we eventually get to HH, but every time we reach TH, one more H gives THH and we lose. If the first flip is H (probability $1/2$), it's more balanced. This asymmetry suggests $P(\text{HHT wins}) < 1/2$, probably significantly less.
Approach: Define Markov chain states based on the relevant suffix and solve a system of linear equations.
Formal Solution:
Define states by the relevant suffix of flips observed: - $\emptyset$: start (no relevant suffix) - $H$: last flip was H (and no longer relevant suffix) - $T$: last flip was T - $HH$: last two flips were HH - $TH$: last two flips were TH - $HHT$: absorbing -- HHT wins - $THH$: absorbing -- THH wins
Let $p_s$ = probability HHT wins from state $s$.
State $HH$: Flip H $\to$ stay at $HH$; flip T $\to$ $HHT$ (win!). $$p_{HH} = \frac{1}{2} p_{HH} + \frac{1}{2}(1) \implies p_{HH} = 1$$
Once you reach $HH$, HHT is guaranteed to win eventually -- you either get T immediately (HHT) or keep flipping H until you do.
State $TH$: Flip H $\to$ $THH$ (lose!); flip T $\to$ $T$. $$p_{TH} = \frac{1}{2}(0) + \frac{1}{2} p_T$$
State $T$: Flip H $\to$ $TH$; flip T $\to$ stay at $T$. $$p_T = \frac{1}{2} p_{TH} + \frac{1}{2} p_T \implies p_T = p_{TH}$$
Substituting $p_T = p_{TH}$ into the equation for $p_{TH}$: $$p_{TH} = \frac{1}{2} p_{TH} \implies p_{TH} = 0$$
So $p_T = 0$. Once you're in state $T$, HHT can never win. Why? From $T$, you need $H$ to make progress toward HHT, but that gives $TH$. From $TH$, getting $H$ completes $THH$ (loss), and getting $T$ sends you back to $T$. HHT requires entering through $HH$, but you can never reach $HH$ from $T$ without passing through $TH \to THH$ first.
State $H$: Flip H $\to$ $HH$; flip T $\to$ $T$. $$p_H = \frac{1}{2} p_{HH} + \frac{1}{2} p_T = \frac{1}{2}(1) + \frac{1}{2}(0) = \frac{1}{2}$$
State $\emptyset$: Flip H $\to$ $H$; flip T $\to$ $T$. $$p_{\emptyset} = \frac{1}{2} p_H + \frac{1}{2} p_T = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot 0 = \frac{1}{4}$$
Answer: $P(\text{HHT before THH}) = \dfrac{1}{4}$. THH is the heavy favorite, winning $3/4$ of the time.
Intuition
This is a beautiful example of how sequence structure creates asymmetry in Penney's game. The critical mechanism is the "trap" structure: once the sequence enters state $T$, HHT can never win. To build HH from scratch, you need two consecutive heads. But if T ever appears between your heads, you land in state $T$ or $TH$, and from $TH$ the next H completes THH. So HHT can only win if the game starts H-H (probability $1/4$), leading to state $HH$ where HHT is guaranteed. Any other opening gives THH the eventual win.
Penney's game is a famous example of non-transitive competition: for any three-letter sequence your opponent picks, you can always find another sequence that beats it with probability $> 1/2$. This has direct connections to tournament design, non-transitive dice, and market microstructure problems where the order of information arrival determines outcomes. In a betting context, if someone offers you even money on HHT vs. THH, you should take THH -- your edge is $3/4 - 1/4 = 1/2$, and Kelly criterion says bet aggressively.