What is the expected number of fair coin flips until the pattern HHT first appears, and why does it differ from the expected wait for HTH when both patterns have probability 1/8 in any given three flips?

What is the expected number of fair coin flips until the pattern HHT first appears, and why does it differ from the expected wait for HTH when both patterns have probability 1/8 in any given three flips?

Approach: Set up states for the length of the current match against the pattern and solve the first-step equations, then compare how a failed attempt sets each of the two patterns back.

8. Track the longest suffix of the flips that is a prefix of HHT and write E0, E1, E2 for the expected remaining flips with 0, 1 and 2 characters matched. First-step analysis gives E2 = 1 + E2/2, so E2 = 2, then E1 = 1 + (E2 + E0)/2 and E0 = 1 + (E1 + E0)/2 solve to E1 = 6 and E0 = 8. HTH has an expected waiting time of 10 because of pattern overlap: the final H of one occurrence is the opening H of the next, so occurrences of HTH arrive in clumps. Both patterns occur once per 8 positions on average, and clumping of occurrences forces longer gaps between clumps, which is the wait measured from a fresh start. Conway's rule reproduces both numbers as 2^3 and 2^3 + 2^1.

Follow-up: What is the expected number of flips until HTHT first appears?

Key concepts: first-step analysis, pattern overlap, expected waiting time, clumping of occurrences.