# Solution to puzzle 82: Consecutive heads

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.

## Lemma

The expected wait, E, for an event of probability p, is 1/p.

### Proof

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:

• with probability ½, a further head; or
• with probability ½, a tail, after which we must obtain n consecutive heads.

It follows that En = ½(En−1 + 1) + ½(En−1 + 1 + En), from which En = 2En−1 + 2.

## Recurrence equation

We now guess that the solution to this recurrence equation is En = 2n+1 − 2, which may easily be proved by mathematical induction.

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.