# Solution to puzzle 25: Die: mean throws

What is the expected number of times a fair die must be thrown until all scores appear at least once?

The expected wait for all scores to appear = expected wait for one score + expected wait for second score + ... + expected wait for sixth and final score.  The probabilities of these events are, respectively, 6/6, 5/6, 4/6, 3/6, 2/6, 1/6.

## Lemma

The expected wait, E, for an event of probability p, is 1/p.

### Proof

Either the event occurs on the first trial with probability p, or with probability 1 − p the expected wait is 1 + E.
Therefore E = p·1 + (1 − p)(1 + E), from which E = 1/p.
(Notice that we have implicitly assumed that E is finite, which is something that, a priori, we do not necessarily know.)

Therefore the expected wait for all scores to appear = 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 14.7.

## Mean, median, and mode

Notice that the arithmetic mean (expected wait) of this probability distribution function is higher than the median, as calculated in puzzle number 24.  This is because the distribution is skewed to the left.  The histogram below shows the shape of the distribution.  It plots the probability, p, of obtaining all scores following a given number of throws, against the number of throws.  The mode of the distribution is 11, when p  0.084.  This is the single most likely number of throws following which all scores are represented.

## n-sided die

The expected wait for all scores to appear on an n-sided die is n(1/1 + 1/2 + ... + 1/n).
For large n, this is asymptotically equal to n(ln n + Y + 1/2n), where Y = 0.5772156649... is the Euler-Mascheroni Constant.
In fact, for n = 6, this approximation is already accurate to within 0.1%.