Dice Strategy
Jane Street
What is the expected number of rolls of a 6 sided die to get each face at least once?
Answer
Let's go one by one. The first time we roll, we are guaranteed to get a new face, so 1 roll needed to get the first new face. The second time, we've already seen one face, so we have a $\frac{5}{6}$ chance of rolling a new one. So how many rolls does it take to get the second face?
We can treat this as a Markov Chain sub-problem: we've already seen one face, and need extra E rolls to see the second face. There's 5/6 chance we need only one more roll, and 1/6 chance we see the first face again, in which case we've used up one roll, and still need E more. Therefore, $E = \frac{5}{6} \cdot 1 + \frac{1}{6}\cdot (1+E)$. Solving for E, we get 6/5. So we need 6/5 rolls after the first roll to get two different faces.
This logic extends to all subsequent rolls. Once we have two different faces, there's a 4/6 chance of rolling a new face, i.e. 6/4 further rolls on average. Extending this until we've seen all faces, we get the following:
$$E = 1 + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1}=14.7$$