Solution to the coin tossing problem

If X_N appears as XN then your browser does not support subscripts or superscripts. Please use this alternative version.

The chance that any fixed set of k+1 tosses gives k heads followed by a tail is:

In n tosses there are n-k possible starting points of such sequences. Therefore the expected number of wins is:

Using probability theory, one finds that the actual number of wins has what is called an approximate Poisson distribution. That is to say, the probability that you win exactly r pennies is given approximately by the Poisson probability:

Your average number of wins equals lambda. If lambda is big, then the number of wins will generally be big also, and if lambda is small then there will be only a small number of wins (perhaps 0).

The threshold between big and small occurs when lambda is a 'reasonable' number, say the value 1. When lambda = 1, then k is very close to log₂(n). In this threshold case the Poisson probabilities are given in the following table.

Substantially longer runs than log₂(n) are exceedingly unlikely, while substantially shorter runs are commonplace.

Acknowledgements

This solution was written by Geoffrey Grimmett. You may also be interested in his article "What a coincidence!" elsewhere in this issue.