How many throws of a die until every possible result is obtained? [duplicate]

Question

A die is thrown until every possible result (i.e., every integer from 1 to 6) is obtained. Find the expected value of the number of throws.

How do I do that? I understand that probability for the single result is $\{1, 5/6, \ldots , 1/6\}$, but what about the expected value?

Answer 1

This is a very popular problem. I learned it as the "collector's problem".

Essentially, you want to model rolling a die until a new face is shown as a geometric distribution with $p_k = \frac{7-k}{6}$ where $k = 1,\dotsc,6$ is the number of faces you have seen. So, if $X_k$ denotes rolling until you see $k$th different face, then $X_k\sim\text{Geom}(p_k)$ on $\{1,2,3,\dots\}$. It follows that $X = X_1+\dotsb+X_6$ is the number of rolls until you have seen all six faces. Then $$E[X] = E[X_1]+E[X_2]+\dotsb+E[X_6] = \frac{6}{6}+\frac{6}{5}+\dotsb+\frac{6}{1}=14.7.$$

Answer 2

While waiting for face $k$, the probability of rolling faces already rolled is $\frac{k-1}n$. Therefore, the expected number of rolls to get face $k$, after rolling face $k-1$, is $$ \begin{align} \sum_{j=1}^\infty\overbrace{\left(\frac{k-1}n\right)^{j-1}}^{\text{roll $j-1$ already rolled}}\ \ \overbrace{\frac{n-k+1}n\vphantom{\left(\frac kn\right)^1}}^{\text{roll $1$ not rolled}}\,j &=\frac{n-k+1}n\frac1{\left(1-\frac{k-1}n\right)^2}\\ &=\frac{n}{n-k+1} \end{align} $$ Thus, the expected number of rolls to get all the faces is $$ \begin{align} \sum_{k=1}^n\frac{n}{n-k+1} &=n\sum_{k=1}^n\frac1k\\ &\sim n\log(n)+\gamma n+\frac12-\frac1{12n}+O\left(\frac1{n^3}\right) \end{align} $$ where $\gamma$ is the Euler-Mascheroni Constant. The asymptotic expansion is gotten using the Euler-Maclaurin Sum Formula.

For a $6$-sided die, the expected number of rolls is exactly $14.7$.

Using the terms given in the asymptotic expansion for $n=6$ gives $14.69996$. The approximation gets better for larger $n$.