Toss one die over and over, and record the outcomes. Toss the die until all six outcomes, 1, 2, 3, 4, 5, and 6, occur. What is the expected number of tosses until we see all six?
More generally: Let's have n possible outcomes, each one having probability 1/n. What
is the expected number of trials needed to see all n outcomes?
Two relevant theorems:
1. The expected value of a sum of random variables is the sum of their expected values.
2. The expected number of trials needed to see a result that has probability p is 1/p.
If we have already seen k out of n outcomes, then the probability p of seeing a new one
is p = (n-k)/n. Therefore by theorem 2, the expected value e(k) of the number of trials until it happens is e(k) = n/(n-k).
By theorem 1, the expected number of trials to see all n outcomes, is the sum of the
expected number of trials of seeing the first outcome plus the expected number of
trials to see another outcome, and so on ... . This sum is,
e(0) + e(1) + ... + e(n-1) = n/n + n/(n-1) + ... + n/1 = n*(1 + 1/2 + ... + 1/n)
For n = 6,
6*(1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) = 14.7