6
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Did probability Nov 26 '15 at 0:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ Maybe helpful: math.stackexchange.com/questions/266505/… $\endgroup$ – user940 Nov 25 '15 at 21:09
  • $\begingroup$ @ByronSchmuland: I had forgotten that I wrote an answer to that question. $\endgroup$ – robjohn Nov 25 '15 at 21:38
  • $\begingroup$ @robjohn Well, with over 4000 answers you can't be expected to keep track of them all! $\endgroup$ – user940 Nov 25 '15 at 21:55
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ why not $p_k\in \{ 1, 5/6, 4/6, 3/6, 2/6, 1/6\}$? $\endgroup$ – mkropkowski Nov 25 '15 at 20:50
  • $\begingroup$ Typo, fixed it. $\endgroup$ – Em. Nov 25 '15 at 20:52
  • $\begingroup$ Still i do not get it why expectation is $1/p_k$? $\endgroup$ – mkropkowski Nov 25 '15 at 20:57
  • $\begingroup$ 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. $\endgroup$ – Em. Nov 25 '15 at 21:24
4
$\begingroup$

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.