Rolling Every Face
The puzzle
You roll a fair six-sided die over and over, keeping a list of which faces you have seen.
On average, how many rolls does it take before all six faces have appeared at least once?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Break the wait into stages: the wait for the first new face, then the second, and so on.
Hint 2
If a roll has probability p of being new, the average wait for a new one is 1/p.
Show the answer Hide the answer
14.7 rolls on average.
How to get there
The first roll is always new. Once you hold one face, each roll is new with probability 5/6, so the average wait for the second is 6/5.
Once you hold k faces, a roll is new with probability (6-k)/6 and the average wait is 6/(6-k). Expected waits add whether or not the stages are independent.
So the total is 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 6 times the sum of 1 to 1/6, which is 14.7.
The technique worth keeping
An expectation can be summed stage by stage even when the stages are not independent. Splitting a long wait into "wait for the next new thing" is the coupon collector argument, and it answers any "how long until I have seen them all" question.