A fair coin is tossed repeatedly until n consecutive heads occur. What is the expected number of times the coin is tossed?
Consider first the expected number of tosses until a single head appears.
The expected wait, E, for an event of probability p, is 1/p.
Either the event occurs on the first trial with probability p, or with probability 1 − p the expected wait is 1 + E.
Therefore E = p·1 + (1 − p)(1 + E), from which E = 1/p.
(Notice that we have implicitly assumed that E is finite, which is something that, a priori, we do not necessarily know.)
Therefore the expected wait for a single head to appear = 1 / ½ = 2.
We now consider the expected wait for n > 1 consecutive heads. Let En be the expected wait for n consecutive heads.
In order to obtain n consecutive heads, we must first obtain n − 1 consecutive heads, followed by:
It follows that En = ½(En−1 + 1) + ½(En−1 + 1 + En), from which En = 2En−1 + 2.
For the basis, clearly E1 = 21+1 − 2 = 2, as required.
For the induction step, we assume that Ek = 2k+1 − 2, where k 1.
We also have the recurrence relation: Ek+1 = 2Ek + 2.
Hence Ek+1 = 2(2k+1 − 2) + 2 = 2(k+1)+1 − 2.
This completes the proof by induction.
Therefore the expected number of times you would need to toss a fair coin in order to obtain n consecutive heads is 2n+1 − 2.