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 w_{1}. We can write an equation that this quantity must satisfy:

w_{1} = 1 + ½ w_{1}

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 w_{1}. This gives us the term “½ w_{1}”. The solution is easily seen to be w_{1} = 2.

**Waiting Time for N Heads**

We proceed inductively. For N heads to occur, we must first obtain N-1, and the average waiting time for this is denoted w_{N-1}, so we will need w_{N-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

w_{N} = ( w_{N-1} + 1 ) + ½ w_{N} or w_{N} = 2 ( w_{N-1} + 1 )

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

w_{N }= 2 ( 2^{N} – 1 )

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

w_{N} = 2 M_{N}.

The waiting time for *either* N heads *or* N tails to occur is half this value, or M_{N}.

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

w_{20} = 2 ( 2^{20} – 1 ) = 2,097,150

or about two million tosses.

**Waiting Time for 100 Heads**

What about a sequence of one hundred heads in a row? The waiting time is then

w_{100} = 2 ( 2^{100} – 1 ) = 2.5 x 10^{30}.

Allowing ten tosses per minute, or 5,265,000 per year, the average waiting time for a sequence of one hundred heads is about half a trillion trillion years. If you notice this happening, you should certainly question the fairness of the coin (or suspect a method of tossing that systematically favours heads).

* * *

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