Probability – Expected Number of Coin Tosses to Land n Heads

conditional-expectationprobability

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?

Best Answer

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.

Related Question