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ⁿ⁺¹ − 2, which may easily be proved by mathematical induction.

For the basis, clearly E₁ = 2¹⁺¹ − 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ⁿ⁺¹ − 2.

Source: Traditional