Learn / Library / Expected value

Long coin pattern

Expected valueHard

A fair coin is flipped repeatedly. What is the expected number of flips until the pattern $HHTHH$ (heads, heads, tails, heads, heads) first appears?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Check which prefixes of the pattern are also suffixes of it.

Solution

The expected waiting time for a pattern is the sum of $2^{k}$ over every length $k$ for which the first $k$ flips equal the last $k$ flips.
Here length $1$ matches ( $H$ and $H$ ) and length $2$ matches ( $H H$ and $H H$ ), and length $5$ matches trivially.
Lengths $3$ ( $HHT$ against $THH$ ) and $4$ ( $HHTH$ against $HTHH$ ) do not match.
So the expectation is $2^{5} + 2^{2} + 2^{1} = 32 + 4 + 2 = 38$ .

Answer: $38$