HTH Before HHT

You flip a fair coin repeatedly. What is the probability that the pattern HTH appears before the pattern HHT?

Reveal solutionHide solution

#The hidden asymmetry

The triplets are not symmetric, because of what each shares with the other. Once two heads in a row appear, a single following tail finishes HHT immediately, whereas reaching HTH from that same HH is impossible without passing through HHT first. That trap is what tilts the race.

#The state machine

Track the longest current suffix that is a prefix of either target. There are four transient states, the start $\varnothing$ , then $H$ , $HH$ , and $HT$ , plus two absorbing states $W$ for HTH and $L$ for HHT. Each toss is fair.

Every edge has probability one half. The only way out of HH is a tail into HHT, so once two heads land in a row the race is lost for HTH. That dead end is why HTH arrives first only one third of the time.

#The transition matrix

Ordering the states $\varnothing, H, HH, HT, W, L$ , one toss moves the chain by

P = \begin{pmatrix} \tfrac12 & \tfrac12 & 0 & 0 & 0 & 0\\[2pt] 0 & 0 & \tfrac12 & \tfrac12 & 0 & 0\\[2pt] 0 & 0 & \tfrac12 & 0 & 0 & \tfrac12\\[2pt] \tfrac12 & 0 & 0 & 0 & \tfrac12 & 0\\[2pt] 0 & 0 & 0 & 0 & 1 & 0\\[2pt] 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}. \tag{1}

The last two rows are absorbing, each a lone $1$ on the diagonal. From $HH$ a tail drops the chain into $L$ , and from $HT$ a head lifts it into $W$ .

#Absorption equations

Let $a_i = \PP(\text{HTH first} \mid \text{state } i)$ , with $a_W = 1$ and $a_L = 0$ . Reading the transient rows,

a_{\varnothing} = \tfrac12 a_{\varnothing} + \tfrac12 a_H, \qquad a_H = \tfrac12 a_{HH} + \tfrac12 a_{HT}, \tag{2}

a_{HH} = \tfrac12 a_{HH} + \tfrac12 (0), \qquad a_{HT} = \tfrac12 (1) + \tfrac12 a_{\varnothing}. \tag{3}

The third equation forces $a_{HH} = 0$ , the dead end. The first gives $a_{\varnothing} = a_H$ . Then $a_H = \tfrac12 a_{HT}$ and $a_{HT} = \tfrac12 + \tfrac12 a_{\varnothing} = \tfrac12 + \tfrac12 a_H$ . Substituting $a_H = \tfrac12 a_{HT}$ ,

a_{HT} = \tfrac12 + \tfrac14 a_{HT} \implies a_{HT} = \tfrac23, \qquad a_H = a_{\varnothing} = \tfrac13. \tag{4}

#HH never yields HTH

Starting from $\varnothing$ ,

\PP(\text{HTH before HHT}) = \tfrac13. \tag{5}

Once the chain reaches $HH$ it can only end as HHT, so HHT wins two times out of three even though the triplets seem alike.