Wednesday, April 22, 2009 ... //

Waiting for N heads in a row

David Berenstein offered us the following:

Problem

You toss a coin and you win if you get N heads in a row. What is the average number of throws for a win?

The average number of throws is actually
2N+1 - 2.
For example, for N=3 heads in a row, you need 16-2=14 throws while for N=5 heads in a row, you need 64-2=62 throws to get five heads in a row. The numbers 2, 6, 14, 30, 62, and maybe 126 also appear as dimensions in the Kervaire invariant problem in mathematics.

A somewhat elegant derivation (LM)

Imagine that you throw the coin L times where L goes to infinity.

Any sequence of N consecutive throws clearly has the probability of "1/2^N" of being "N heads in a row". For a fixed and large "L", let's count the number of throws "M" that are the last throws completing a short sequence of "N heads in a row". Clearly, there are "L times the probability" i.e. "M = L/2^N" of such throws for a very large "L". All the throws are always independent from each other.

The average number of throws per one event of "N heads in a row" equals the opposite ratio "L/M", namely the number of throws, "L", divided by the number of the "N heads in a row" events, "M = L/2^N". The ratio would be "2^N", i.e. the inverted probability.

However, we shouldn't count the overlapping events.

We only allow a new sequence of "N heads in a row" if it appears at least "N" throws after the previous one. In the first approximation, this means that exactly 1/2 of the "N heads in a row" events have to be erased. They're the events (their last throws) that actually complete "N+1 heads in a row". All overlapping pairs of "N heads in a row" events have to include "N+1 heads in a row", so we have erased all the overlapping events.

In this approximation, we have
M = 2-N L - 2-N-1 L... = 2-N-1 L...
"N heads in a row" events. Let's go to higher orders. Why?

We have actually subtracted too much from "M". It is allowed to have "N+1 heads in a row" but only a small fraction of these events have to be double-counted. How many? Well, "2^{-N}" of them. That's because if one sequence of "N heads in a row" is immediately followed by another sequence of "N heads in a row", you should count the sequence of "2N heads in a row" twice.

However, once again, one is only allowed to add those events with "2N heads in a row" if they are followed by a tail, so one half of them:
M = 2-NL - 2-N-1L +
+ 2-2NL - 2-2N-1L +...
It's clear where we're going. The sequences of "2N heads in a row" have been properly counted as two events, but sequences of "3N heads in a row" should actually be counted as three events, assuming that the 3N+1-st throw is a tail, so we must refine "M" as
M = 2-N L - 2-N-1 L +
+ 2-2N L - 2-2N-1 L +
+ 2-3N L - 2-3N-1 L +...
Finally, the whole procedure is well-defined and convergent. "M" can be calculated by the following geometric series
M/L = 2-N-1 + 2-2N-1 + 2-3N-1 +...
which is easily summed up to see that
L/M = 2N+1 - 2
which is the required average number of throws per a completed, nonoverlapping sequence of "N heads in a row".

Appraisal

Isn't it much more transparent and intuitive than any of the derivations on that page or elsewhere on the Internet? ;-) That's the power of perturbative expansions.

Not the end of the story

In the fast comments, you will find a much simpler, recursive calculation of the expectation value of "L/M" as a function of "N" by "mathematician".