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: Ask what has to happen before HH first appears. If the very first two flips are HH, the next T completes HHT, and THH cannot finish first because it needs a T followed by two more H's. Otherwise some flip before the first HH is a T, so the flip just before that first HH must be T (if it were H, HH would have appeared one flip earlier). That T plus the HH is THH, completed at the same moment HH first shows up, before HHT can add its T. So HHT wins exactly when the game opens HH: $P = \tfrac{1}{2}\cdot\tfrac{1}{2} = \tfrac{1}{4}$. The Markov chain below confirms it.
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 expected gain is $3/4 - 1/4 = 1/2$ per unit staked, and the Kelly fraction $f^{*} = 2p - 1 = 1/2$ says stake half your bankroll.