Waiting for THH

You flip a fair coin until the pattern THH 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 is also a start of THH. That gives four states, start with no progress, $T$ , $TH$ , and the finished $THH$ . Let $a$ , $b$ , $c$ be the expected flips still needed from start, from $T$ , and from $TH$ .

#The fallback from TH is the key

From start, a head is wasted and keeps you at start, while a tail advances to $T$ . From $T$ , a tail just resets to a fresh $T$ and a head advances to $TH$ . From $TH$ , a head finishes, but a tail does not erase everything, since that new tail is itself the first symbol of THH, so the chain falls back only to $T$ .

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

The catch is the tail from TH. It does not erase all progress, since the new tail is itself the first symbol of THH, so the chain falls back only to the T state. That shorter fallback is why THH is reached in fewer tosses than HHH.

#Solve

The three equations simplify to $a = 2 + b$ , $b = 2 + c$ , and $c = 1 + \tfrac{1}{2}b$ . Substituting the last into the second, $b = 3 + \tfrac{1}{2}b$ , so $b = 6$ , then $c = 4$ and

\E[\text{flips to THH}] = a = 8. \tag{2}

#Compare

THH takes only $8$ flips against HHH's $14$ . A stumble near the end of THH keeps its leading tail and costs little, whereas a tail at the end of an HHH attempt wipes the whole run and sends you back to the start.