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?

**General answer**

The average number of throws is actually

2For 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.^{N+1}- 2.

**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.

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

In this approximation, we have

M = 2"N heads in a row" events. Let's go to higher orders. Why?^{-N }L - 2^{-N-1 }L... = 2^{-N-1 }L...

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:

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.

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".

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 = 2It'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^{-N}L - 2^{-N-1}L +

+ 2^{-2N}L - 2^{-2N-1}L +...

M = 2Finally, the whole procedure is well-defined and convergent. "M" can be calculated by the following geometric series^{-N }L - 2^{-N-1 }L +

+ 2^{-2N }L - 2^{-2N-1 }L +

+ 2^{-3N }L - 2^{-3N-1 }L +...

M/L = 2which is easily summed up to see that^{-N-1}+ 2^{-2N-1}+ 2^{-3N-1}+...

L/M = 2which is the required average number of throws per a completed, nonoverlapping sequence of "N heads in a row".^{N+1}- 2

**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".

## snail feedback (0) :

Post a Comment