Collect All Six Faces

Question

On average, how many rolls of a fair die does it take to see every face at least once?

Accepted Answer

Split the process into 6 stages. When you have already seen k distinct faces, each roll shows a new face with probability frac6-k6, so the expected wait for the next new face is frac66-k. By linearity: mathbbE = sum_k=0^5 frac66-k = 6left(frac11 + frac12 + frac13 + frac14 + frac15 + frac16right) = 6 cdot frac4920 = frac14710 = 14.7. This is the coupon collector problem: for n types, mathbbE = n H_n approx n(ln n + 0.577). Two interview-critical ideas inside it: 1. Decompose into independent waits: linearity of expectation doesn't care that the stages have different rates. 2. The last coupon dominates: the final face alone takes 6 expected rolls, nearly half the total. "Almost done" is an illusion in collection problems.

Collect All Six Faces

Problem

Your answer

Hints

More Expected Value to train on