Waiting for HTH

You flip a fair coin until the pattern HTH appears as three consecutive tosses. What is the expected number of flips?

Reveal solutionHide solution

#States of progress

Track the longest tail of the tosses so far that starts HTH. The states are start, $H$ , $HT$ , and the finished $HTH$ . Let $a$ , $b$ , $c$ be the expected flips still needed from start, from $H$ , and from $HT$ .

#Mismatches and the reset

From start, a head advances to $H$ and a tail holds. From $H$ , another head keeps you at $H$ , since the fresh head is itself a new start of the pattern, while a tail advances to $HT$ . From $HT$ , a head finishes, but a tail resets all the way to start, since HTT shares nothing with the start of HTH.

a = 1 + \tfrac{1}{2}b + \tfrac{1}{2}a, \qquad b = 1 + \tfrac{1}{2}b + \tfrac{1}{2}c, \qquad c = 1 + \tfrac{1}{2}\cdot 0 + \tfrac{1}{2}a. \tag{1}

The costly step is the tail from HT. Unlike THH, which keeps its leading symbol, HTH throws away everything and restarts, which is why HTH takes longer to appear than THH.

#Solve

The three equations give $a = 2 + b$ , $b = 2 + c$ , and $c = 1 + \tfrac{1}{2}a$ . Substituting, $a = 4 + c = 5 + \tfrac{1}{2}a$ , so

\E[\text{flips to HTH}] = a = 10. \tag{2}

#Compare

HTH lands between THH at $8$ and HHH at $14$ . The tail from $HT$ wipes out all progress, which makes HTH slower than THH, yet its self-overlap is shallower than HHH's, so it still finishes well short of $14$ .