Roll It All

Solution

Answer: 14.7

We roll a fair \(6\)-sided die until we have seen every face \(1,2,3,4,5,6\) at least once. It helps to think of the process in stages depending on how many distinct numbers we have already seen. Getting the first number will always have an expected value of \[ 1 \] roll. The first roll must produce the first distinct value. Now suppose we already have \(1\) unique number. There are \(5\) new values we have not yet seen. The probability that the next roll gives a new value is \[ \frac{5}{6}, \] while the probability that we repeat the same value we already have is \[ \frac{1}{6}. \] Let \(E_2\) be the expected number of rolls needed to obtain the second distinct value. If the next roll succeeds (probability \(5/6\)), we finish in one roll. If it fails (probability \(1/6\)), we used one roll and are back in the same situation. This gives the recursive equation \[ E_2 = \frac{5}{6}(1) + \frac{1}{6}(1 + E_2). \] \[ E_2 = \frac{6}{5}. \] So it takes an average of \[ \frac{6}{5} \] rolls to progress from \(1\) distinct number to \(2\) distinct numbers. Now suppose we already have \(2\) distinct numbers. There are \(4\) new numbers remaining. The probability the next roll gives a new value is \[ \frac{4}{6}, \] and the probability we repeat one of the two existing values is \[ \frac{2}{6}. \] Let \(E_3\) be the expected rolls needed to obtain the third distinct value. The recursion becomes \[ E_3 = \frac{4}{6}(1) + \frac{2}{6}(1 + E_3). \] \[ E_3 = \frac{6}{4}. \] A pattern appears. The expected rolls needed to gain the next new face when we already have \(k\) distinct values is \[ \frac{6}{6-k}. \] So the expected rolls needed for each stage are \[ 1, \frac{6}{5}, \frac{6}{4}, \frac{6}{3}, \frac{6}{2}, \frac{6}{1}. \] Adding these together gives the total expected number of rolls: \[ 1 + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1} = 14.7 \] Thus the expected number of rolls required to see all \(6\) faces at least once is 14.7.