Past exam of the mathematics course of the University of Cambridge / 2026 / ia / Paper 2 / 10F (Probability)

The waiting time is geometric with mean $1/p$.

First-step equations for states “no trailing H” and “one trailing H” give $E_0=1+q{E}_0+p{E}_1$, $E_1=1+q{E}_0$, hence $E_0=(1+p)/p^2$.

The word $HT$ has no proper self-overlap, so its mean waiting time is the reciprocal of its probability: $1/[p(1-p)]$. This also follows from two first-step equations.

The standard run recursion gives $E_n=1+p^{-1}+\cdots +p^{-n}=(1-p^n)/[(1-p)p^n]$.

For $k\ge n$, $p_k(n)=\left(\genfrac{}{}{0ex}{}{k-1}{n-1}\right)p^n(1-p{)}^{k-n}$. It is the sum of $n$ independent geometric variables, so the central limit theorem applies with mean $n/p$ and standard deviation $\sqrt{n(1-p)}/p$. Take
$k_a(n)=\lceil n/p+a\sqrt{n(1-p)}/p\rceil$ and $k_b(n)=\lfloor n/p+b\sqrt{n(1-p)}/p\rfloor$.