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

## Single head

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.

## n heads

We now consider the expected wait for n > 1 consecutive heads. Let E_{n} 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 E_{n} = ½(E_{n−1} + 1) + ½(E_{n−1} + 1 + E_{n}), from which E_{n} = 2E_{n−1} + 2.

## Recurrence equation

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

For the *basis*, clearly E_{1} = 2^{1+1} − 2 = 2, as required.

For the *induction step*, we assume that E_{k} = 2^{k+1} − 2, where k 1.

We also have the recurrence relation: E_{k+1} = 2E_{k} + 2.

Hence E_{k+1} = 2(2^{k+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 2^{n+1} − 2.

Source: Traditional

Back to top