### Twenty Heads in Succession: How Long will we Wait?

If three flips of a coin produce three heads, there is no surprise. But if 20 successive heads show up, you should be suspicious: the chances of this are less than one in a a million, so it is more likely than not that the coin is unbalanced. Waiting Time for a Single Head

On average, how many tosses are needed until the first head shows up? We argue recursively: let us denote the “waiting time” for one head by w1. We can write an equation that this quantity must satisfy:

w1 = 1 + ½ w1

We explain this as follows: the term “1” occurs because the first toss is always required. But on half of the occasions, it is a tail and we are back to square one, so the waiting time is again w1. This gives us the term “½ w1”. The solution is easily seen to be w1 = 2.

We proceed inductively. For N heads to occur, we must first obtain N-1, and the average waiting time for this is denoted wN-1, so we will need wN-1 + 1 tosses at least. But half the time this sequence will end in a tail, and we must start again. Reasoning as above, the waiting time for N heads therefore satisfies

wN = ( wN-1 + 1 ) + ½ wN         or           wN = 2 ( wN-1 + 1 )

This is an inhomogeneous finite difference equation for wN. Since zero heads require zero tosses, we may take the initial condition to be w0 = 0. Alternatively, we may start with w1 = 2. Seeking a solution of the form wN = a bN + c, we find that c = – a and the equation is satisfied only if a = 2 and b = 2, giving

wN = 2 ( 2N – 1 )

The N-th Mersenne number is denoted MN = 2N – 1 so we can also write the solution as

wN = 2 MN.

The waiting time for either N heads or N tails to occur is half this value, or MN.

If we let N = 20, the waiting time for twenty heads is

w20 = 2 ( 220 – 1 ) = 2,097,150

The collection That’s Maths, with 100 articles, has just been published by Gill Books. Available from