Expected Number of Coin Tosses to Get Five Consecutive Heads
Let $e$ be the expected number of tosses. It is clear that $e$ is finite.
Start tossing. If we get a tail immediately (probability $\frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $\frac{1}{4}$), then the expected number is $e+2$. Continue $\dots$. If we get $4$ heads then a tail, the expected number is $e+5$. Finally, if our first $5$ tosses are heads, then the expected number is $5$. Thus $$e=\frac{1}{2}(e+1)+\frac{1}{4}(e+2)+\frac{1}{8}(e+3)+\frac{1}{16}(e+4)+\frac{1}{32}(e+5)+\frac{1}{32}(5).$$ Solve this linear equation for $e$. We get $e=62$.
Lets calculate it for $n$ consecutive tosses the expected number of tosses needed.
Lets denote $E_n$ for $n$ consecutive heads. Now if we get one more head after $E_{n-1}$, then we have $n$ consecutive heads or if it is a tail then again we have to repeat the procedure.
So for the two scenarios:
- $E_{n-1}+1$
- $E_{n}{+1}$ ($1$ for a tail)
So, $E_n=\frac12(E_{n-1} +1)+\frac12(E_{n-1}+ E_n+ 1)$, so $E_n= 2E_{n-1}+2$.
We have the general recurrence relation. Define $f(n)=E_n+2$ with $f(0)=2$. So,
\begin{align} f(n)&=2f(n-1) \\ \implies f(n)&=2^{n+1} \end{align}
Therefore, $E_n = 2^{n+1}-2 = 2(2^n-1)$
For $n=5$, it will give us $2(2^5-1)=62$.