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

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?

– user940
Nov 25, 2015 at 21:09
• @ByronSchmuland: I had forgotten that I wrote an answer to that question.
– robjohn
Nov 25, 2015 at 21:38
• @robjohn Well, with over 4000 answers you can't be expected to keep track of them all!
– user940
Nov 25, 2015 at 21:55

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.$$

• why not $p_k\in \{ 1, 5/6, 4/6, 3/6, 2/6, 1/6\}$? Nov 25, 2015 at 20:50
• Typo, fixed it.
– Em.
Nov 25, 2015 at 20:52
• Still i do not get it why expectation is $1/p_k$? Nov 25, 2015 at 20:57
• A random variable that follows a geometric distribution with parameter $p$ on $\{1,2,3,\dots\}$ has mean equal to $\frac{1}{p}$. This is a well-known fact.
– Em.
Nov 25, 2015 at 21:24

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$.

• Following Byron Schmuland's comment, I see that I wrote this answer, which evaluates the expected number of rolls in another way.
– robjohn
Nov 25, 2015 at 21:38