# 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?

## 2 Answers

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.

• how did you simplify it to e=2^N+1-2; more specifically please tell me what formula you used for 1/2+2/4+..+N/2^N i know for inifinite it is 2 but what formula is there for a finite series? – james black Feb 14 '18 at 9:20
• it seems very hard to transform into a difference of two infinite serieis for this case unlike 1/2+1/4+...1/2^n – james black Feb 14 '18 at 9:20
• @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.