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.
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 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
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
w100 = 2 ( 2100 – 1 ) = 2.5 x 1030.
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