How many rolls to see all six faces?

Question

You roll a fair six-sided die repeatedly and stop once all six faces have appeared at least once. What is the expected number of rolls? Give the general formula for an n-sided die.

Accepted Answer

Break the process into stages by how many distinct faces you have collected so far. Once you hold k distinct faces, each new roll shows a fresh face with probability \frac{n - k}{n}. The number of rolls to go from k distinct to k+1 distinct is therefore geometric, and a geometric random variable with success probability p has expected value 	frac1p. So the expected rolls to get the (k+1)-th new face is \frac{n}{n-k}. By linearity of expectation, sum over the stages k = 0, 1, \dots, n-1: E[	ext{rolls}] = \sum{k=0}^{n-1} \frac{n}{n-k} = n\left(\frac{1}{n} + \frac{1}{n-1} + \cdots + \frac{1}{1…

How many rolls to see all six faces?

Your answer

More Probability questions