= Pattern waiting time
{wiki}
A <pattern waiting time> is the number of <observations> required until a specified finite pattern first occurs in a <stochastic process>. Overlaps between possible occurrences affect the answer; treating <sliding windows> as independent generally gives the wrong mean.
For independent fair coin tosses, let $E_0$ be the expected additional tosses to first see HH with no current matching prefix, and $E_1$ the expectation after one H. Then $E_0=1+(E_0+E_1)/2$ and $E_1=1+E_0/2$, giving $E_0=6$. For HT, the analogous equations give four. The patterns have the same <probability> in a fixed two-toss window, but different self-overlap structure.
Back to article page