# Expected number of coin tosses to land n heads

In reading about how to calculate the expected number of (fair) coin tosses to land n Heads in a row, using the equations produces the following:

$$E(1|H) = 2$$ $$E(2|H) = 6$$ $$E(3|H) = 14,$$ and so on. What I also noticed is that given the following probabilities of landing N heads in a row (using $\frac1{2^n}$) we have:

$$P(1|H) = \frac1{2}$$ $$P(2|H) = \frac1{4}$$ $$P(3|H) = \frac1{8},$$ and so on.

From this it looks like we can calculate the expected number of tosses for a run of n heads by summing up the inverse of the probabilities for landing n head from 1 to n:

For instance the expected number of tosses for $3$ heads is just $8 + 4 + 2 = 14.$

It is not clear to me from reading through the derivations and formulas of the expected values why this pattern emerges. Is this simply another way of stating the formulas using concrete values for P?

Take André Nicolas's answer and generalise it when aiming for $N$ 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 $N-1$ heads then a tail, the expected number is $e+N$. Finally, if our first $N$ tosses are heads, then the expected number is $N$. Thus $$e=\frac{1}{2}(e+1)+\frac{1}{4}(e+2)+\frac{1}{8}(e+3)+\frac{1}{16}(e+4)+\cdots+\frac{1}{2^N}(e+N)+\frac{1}{2^N}(N).$$ Solve this linear equation for $e$.
Taking the terms involving $e$ to the left-hand side, you get $$\frac{e}{2^N} = \frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\cdots +\frac{N}{2^N}+\frac{N}{2^N}$$ which can be simplified to $e=2^{N+1}-2$, i.e. $e=2+4+8+\cdots+2^N$, which is what you have observed.
• @jamesblack If $S=\sum_{k=0}^n kr^k$ then you can show $S(1-r)^2=r-(n+1)r^{n+1}+nr^{n+2}$ – Henry Feb 14 '18 at 13:46
Let $E_n$ be the expected number of coin tosses needed to flip $n$ consecutive heads. Assuming you have correctly computed $E_1,E_2,E_3$, consider the following: in order to land four consecutive heads, you first need to land three consecutive heads - on average, you need $E_3$ tosses. If in the next toss you get a head, you get four consecutive heads with $E_3+1$ tosses. Otherwise, if you get a tail, you are back to square zero. Since, on average, you need two tosses in order to get a head, we have: $$E_4 = 2(E_3+1)$$ and in general: $$E_n = 2^{n+1}-2$$ as suspected.