Thanks to Mikhail for posing this problem.
On average, how many rolls would it take to see every face on a particular die?
Consider a die with n sides. To answer this question, we’ll want to break this problem down into n smaller problems, each of which will be solved in the same manner.
Specifically, take a time in this process where we still need to see k sides. Let the expected number of rolls it’ll take to see a unique side in this situation be E_k. With probability \frac{k}{n} we will see a new side on the next roll, and with probability \frac{n-k}{n} we will see a repeat face on the next roll. In the first situation, we just take 1 roll. In the second situation, we take 1 roll plus an additional E_k rolls because rolling a die is independent and memoryless—no roll changes the outcome of future rolls.
So, we can write an equation for our expected value:
E_k = \frac kn\cdot 1 + \frac{n-k}{n}\left(1 + E_k\right).Solving for E_k gives us an expected value of \frac nk. So in each stage we expect it to take \frac nk rolls to see one of the k faces we have not yet rolled.
Since we want this to happen for all values of k from 1 to n, we add this up to get our total expected number of rolls.
\sum_{k=1}^n E_k = \sum_{k=1}^n \frac nkIn the case that Mikhail sent me, he was interested in n = 20. This gives us
\sum_{k=1}^{20}\frac{20}{k},which is barely less than 72.
You can easily calculate by hand that for n=6 the expected number of rolls is 14.7.