Every face at least once
A fair six-sided die is rolled until each of the six faces has appeared at least once. Find the expected number of rolls.
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Split the rolls into stages: stage starts when different faces have been seen and ends when a new face appears.
During stage , each roll shows a new face with probability . How long does a stage last on average?
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. The total waiting time is a sum of independent geometric waiting times, one for each new face. Linearity of expectation does the rest.
Step 1: stages. Let be the number of rolls needed to see the -th new face once faces have been seen. The total is .
Step 2: each stage. With faces seen, a roll shows a new face with probability , independently of the other rolls. So is geometric with mean .
Step 3: add.
So it takes rolls on average. Most of that is the last stage: the final face alone costs rolls on average.
In general. With equally likely faces the answer is , where is the -th harmonic number.