Solution
Waiting for HTH
Show the problem again
A fair coin is flipped repeatedly until the three most recent flips are, in order, heads, tails, heads. What is the expected number of flips, counting the final one? Give an exact number.
Worked solution
The answer is 10. Track how much of HTH has been built. Let a be the expected remaining flips from scratch (or after a T that ends no progress), b after a trailing H, and c after a trailing HT. Then a = 1 + (1/2)b + (1/2)a, b = 1 + (1/2)b + (1/2)c (another H keeps us at H), c = 1 + (1/2)·0 + (1/2)a (a T after HT destroys all progress). Solving gives a = 10, b = 8, c = 6. The quick route is Conway's overlap rule: for a fair coin the expected wait for a pattern is the sum of 2^k over every k for which the length-k prefix equals the length-k suffix. For HTH this holds for k = 3 and k = 1, giving 8 + 2 = 10. The self-overlap is what makes HTH slower than HTT (which waits only 8).
Source: Classic pattern waiting-time exercise; the overlap method is due to John Conway. Statement written for AxiomIQ.