Expected Number of Dice Rolls to See All Sides

Question

I want to check if the solution to the following question is an application of the property $E[X + Y] = E[X] + E[Y]$.

The question:
What is the expected number of rolls needed to see all six sides of a fair die?

The solution: We find that as we continue to make rolls and as we continue to see new values, the probability of seeing a new value changes overtime, from 1 to $\frac{5}{6}$ to $\frac{4}{6}$ and so on until we get to $\frac{1}{6}$. By treating each roll as a Geometric Random Variable, we find that the expected value of each of these rolls is given by $\frac{1}{p}$, so for example after the first roll, the second roll's expected value would be $\frac{6}{5}$.

By adding up all these expectations, we find that the expected number of rolls needed to see all six sides of a fair die is 14.7

I'm asking because I'm having difficulty reconciling this solution with my understanding of the definition of expectation for discrete random variables, which is $E[X] = \Sigma xp(x)$.

Answer 1

Your linearity of expectation argument summing geometric random variables gives $$\frac{6}{6}+\frac{6}{5}+\frac{6}{4}+\frac{6}{3}+\frac{6}{2}+\frac{6}{1} = 14.7.$$

If instead you insisted on your $\sum x\, p(x)$ calculation, you could say the probability of first seeing the sixth face on the $x$th roll (with $x \ge 6$) is $$p(x)=\frac{6!\,S_2(x-1,5)}{6^x}$$ where $S_2(\,,\,)$ is a Stirling number of the second kind, since you want to have seen a total of five distinct faces after $x-1$ rolls, followed by seeing the final face on the $x$th roll. You would get an expectation of $$6\times\frac{720\times 1}{46656}+ 7\times\frac{720\times 15}{279936}+8\times\frac{720\times 140}{1679616}+9\times\frac{720\times 1050}{10077696}+\cdots$$ and this infinite sum also turns out to be $14.7$.

Answer 2

The usual approach is to let $T_k$ be the number of throws needed to roll the $k$th different number (after the $k-1$th number has been rolled). Then the total number of throws is $T=T_1+\cdots+ T_6$.

You could compute the expectation using the formula in the question, but this would require computing $\sum_k k P[T=k]$, but computing $P[T=k]$ is a bit of a pain.

Instead we can use linearity to get $E[T]=E[ \sum_k T_k ] = \sum_k E[T_k]$ and then we just need to worry about computing $E[T_k]$, since $E[T_k]$ is easier to compute.

After the $k-1$th number has been rolled, the probability of rolling a $k$th different number is $p_k={6-(k-1) \over 6}$ and we repeat the throw until a different number is thrown. Hence we have the geometric distribution $E[T_k] = \sum_k k P[T_k = k] = \sum_{k=0}^\infty k (1-p_k)^{k-1} p_k = {1 \over p_k}$. Hence $E[T] = \sum_{i=1}^6 {6 \over 6-(i-1)}$

Answer 3

I will say some words on a natural model of the problem, then change it slightly to get closer to the solution. The long story is written in such a manner that the yellow line when we apply the linearity of the expectation in the form $\bbox[yellow]{E[X+Y+\dots]=E[X]+E[Y]+\dots}$ is explicitly isolated. The random variable of the number of times till all faces occur is a random variable $N$, it has the values $6,7,8,\dots$ and i will say some words about how the isolated probabilities $p(6):=\Bbb P(N=6)$, $p(7):=\Bbb P(N=7)$, $p(8):=\Bbb P(N=8)$, ... may appear. It turns out that $N$ is a complicated random variable, but it is (combinatorially) splitted as $N=N_a+N_b+\dots$ with "simpler" terms $N_a$, $N_b$, ... and for these the corresponding probabilities $p_a(1):=\Bbb P(N_a=1)$, $p_a(2):=\Bbb P(N_a=2)$, $p_a(3):=\Bbb P(N_a=3)$, ... and $p_b(1):=\Bbb P(N_b=1)$, $p_b(2):=\Bbb P(N_b=2)$, $p_b(3):=\Bbb P(N_b=3)$, ... and so on are "much simpler".

After having a pedant story we can still shorten it successively till we cannot recognize anything anymore, only the one-liner survives: $$ 6\left(\frac 11+\frac 12+\frac 13+\frac 14+\frac 15+\frac 16\right) =\frac{147}{10}\ . $$ Let's start.

---

The natural model for the problem is the (probability) space $$ \begin{aligned} \Omega &= \{\ \omega=(\omega_1,\omega_2,\dots,\omega_n,\dots)\ : \text{ all components in }\Omega_0\ \}\ ,\\ &\qquad\text{ where}\\ \Omega_0 &=\{1,2,3,4,5,6\}\ . \end{aligned} $$ Above, $\Omega_0 =\{1,2,3,4,5,6\}$ models (the result of) one roll, it comes with no natural order, and an infinite "chain" $\omega$ with components in $\Omega_0$ is a typical element of $\Omega$. The $\sigma$-algebra on it is the one generated by the sets of the shape $$ A(\omega_1,\omega_2,\dots,\omega_n)\ , $$ defined to be the set of all those $\omega\in\Omega$ having the tuple $(\omega_1,\omega_2,\dots,\omega_n)$ exactly in this order on the first $n$ components. The probability on $\Omega$ is determined by giving to the above generic set the probability $1/6^n$.

---

We remodel. Consider $\Omega_0'$ to be the space of the letters $a,b,c,d,e,f$, and we want an order on this space, the one with $a<b<c<d<e<f$. Consider similarly the space $\Omega'$ of chains $\omega'$ of elements in $\Omega_0'$, but require the following properties for each such chain $\omega'$: In the chain $\omega'$

• the first occurrence of $a$ is before the first occurrence of $b$,
• which happens further before the first occurrence of $c$,
• which happens further before the first occurrence of $d$,
• which happens further before the first occurrence of $e$,
• which happens further before the first occurrence of $f$.

So $\omega'_1=a$. Then $a$ repeats some zero, one, two, ... times, then it comes $b$, if it comes at all. Then $a$ and/or $b$ repeat in some order some zero, one, two, ... times, then it comes $c$, if it comes at all. Then $a$ and/or $b$ and/or repeat in some order some zero, one, two, ... times, then it comes $d$, if it comes at all. And similar stuff happens for $e$ and $f$, if they do occur.

We would like to have a / the "natural" map,
$$ f:\Omega\to\Omega'\ , $$ working for us. How is it defined? Let us pick an $\omega\in\Omega$. Assume that all elements of $\Omega_0$ appear as components in $\omega$.

This happens for all $\omega$ that avoid a specific zero set $Z\subset\Omega$. I would hate this $Z$ below in discussion, so let me become neutral in the exposition, i.e. we completely ignore $Z$-elements below.

Then we have a translation of symbols (from one language to an other one) $\Omega_0\to\Omega_0'$ determined by this $\omega$, we map to $a$ the first element of $\omega$, which is $\omega_1$, we look forward in $\omega$ till a first component differs from $a$, and we map this component to $b$. We look forward from this position till we see a component different from $a,b$, and we map this one to $c$. And so on.

Example:

4544564455564255441621163... is mapped to
abaabcaabbbcadbbaaecdeecf...

The above describes in words the way $f$ works.

It is important to notice that on $\Omega'$ we have also the "natural" $\sigma$-algebra generated by the sets of the shape $$ A(\omega'_1,\omega'_2,\dots,\omega'_n)\ , $$ the set of $\Omega'$ chains starting with the tuple $(\omega'_1,\omega'_2,\dots,\omega'_n)$, which is "ordered" w.r.t. the first occurrences of the letters $a<b<c<d<e<f$, and contains all these six symbols. The probability of this set is $$ \Bbb P'(\ A(\omega'_1,\omega'_2,\dots,\omega'_n)\ ) :=\Bbb P(\ f^{-1}A(\omega'_1,\omega'_2,\dots,\omega'_n)\ ) =\frac 1{6^{n-6}}\ . $$

---

Using $f$ we translate, and move the modeling from $\Omega$ to $\Omega'$. We no longer want to see any $\Omega$.

---

Now define the following random variables on $\Omega'$:

• $N_a$ is the time / number of steps needed to see the first $a$, so $X_a=1$, since $\omega'_1=a$ for all $\omega'\in\Omega'$.
• $N_b$ is the time needed to see the first $b$, after seeing the first $a$.
• $N_c$ is the time needed to see the first $c$, after seeing the first $b$.
• $N_d$ is the time needed to see the first $d$, after seeing the first $c$.
• $N_e$ is the time needed to see the first $e$, after seeing the first $d$.
• $N_f$ is the time needed to see the first $f$, after seeing the first $e$.
• Finally, $$ \tag{$*$} N=N_a+N_b+N_c+N_d+N_e+N_f$$ is the time needed to see for the first time all six values $a,b,c,d,e,f$.

The above functions are measurable, for instance the event $N^{-1}(n)=\{N=n\} =\{\omega\ :\ N(\omega)=n\}$ is the union of all $A(\omega'_1,\omega_2',\dots,\omega'_n)$ with $\omega'_n=f$ and on the other components we have only the values $a,b,c,d,e$, at least once each.

---

We finally compute $\Bbb E[N]$ as a sum of the expectation of the six terms in $(*)$. Of course, $\Bbb E[N_a]=\Bbb E[1]=1$. To compute the other mean values, let us use the following notations:

• The probability to see $b$ at one and any roll after having seen only $a$ is $5/6$, any value among $1,2,3,4,5,6$ excepting $a$ is leading to a $b$. So the probability so see a $b$ in one roll after the $a$'s is $p=p(b)=5/6$, the success probability, and the opposite is $q=q(b)=1-p(b)=1/6$. The mean time needed to obtain the first $b$ is - using $p,q$ for short $$ \begin{aligned} &1\cdot p+2q\cdot p+3q^2\cdot p+4q^3\cdot p+5q^4\cdot p+\dots\\ &\qquad =p\cdot \frac{\partial}{\partial q}(1+q+q^2+q^3+q^4+q^5+\dots) =p\cdot \frac{\partial}{\partial q}\frac 1{1-q} \\ &\qquad=p\cdot\frac1{(1-q)^2}=p\cdot\frac 1{p^2}=\frac 1p\ . \end{aligned} $$ (The above contains the explicit probabilities for the events $N_b=1$, $N_b=2$, $N_b=3$, and so on.) So $$ \Bbb E[N_b]=\frac 1{p(b)}=\frac 1{5/6}=\frac 65\ . $$
• The probability to see $c$ at one and any roll after having seen only $a,b$ is $4/6$, any value among $1,2,3,4,5,6$ excepting $a,b$ is leading to a $c$. So the probability so see a $c$ in one roll after the $a$'s and $b's$ is $p=p(b)=4/6$, the success probability, and the opposite is $q=q(b)=1-p(b)=2/6$. The mean time needed to obtain the first $c$ is thus with the same computation $$ \Bbb E[N_c]=\frac 1{p(c)}=\frac 1{4/6}=\frac 64\ . $$
• I a similar manner we obtain for the further letters $d,e,f$ the success probabilities $p(d)=3/6$, $p(e)=2/6$, $p(f)=1/6$, (and if we want we can use also $p(a)=6/6$), so $$ \Bbb E[N_d]=\frac 1{p(d)}=\frac 1{3/6}=\frac 63\ ,\\ \Bbb E[N_e]=\frac 1{p(e)}=\frac 1{2/6}=\frac 62\ ,\\ \Bbb E[N_f]=\frac 1{p(f)}=\frac 1{1/6}=\frac 61\ . $$

Finally: $$ \bbox[yellow]{\qquad \Bbb E[N] = \Bbb E[N_a] + \Bbb E[N_b] + \Bbb E[N_c] + \Bbb E[N_d] + \Bbb E[N_e] + \Bbb E[N_f] \qquad \\ \qquad= 6\left(\frac 11+\frac 12+\frac 13+\frac 14+\frac 15+\frac 16\right) =\frac{147}{10}\ . \qquad } $$

---

Now, after having everything typed precisely, we may want to start to cut. (Please consider the following as an involuntar joke, if it is to close to reality.)

Let us see how i would do it, if there is not too much time and place for a full explanation.

We can cut the spaces $\Omega$ and $\Omega'$, since they are just the expected sets. The $\sigma$-algebras on them are also "clear", so usual solutions never mention them. I may also want to come out without them. Same happens with the probability $\Bbb P$, it may not even be mentioned as a letter. The meaning of the second space $\Omega'$ is also tautologically clear, we use $\Omega$ only, but tacitly, and here $N;N_a,N_b,N_c,N_d,N_e,N_f$ are the natural stopping times associated to the events of seeing for the first time in a path / chain $\omega$ all faces for $N$, respectively the first first face (for $N_a)$, respectively the first second face (for $N_b$), ...

Now instead of writing $\Omega$ and anything related we can compute the conditional probabilities $\Bbb P(N_b=n_a+n_b\ |\ N_a=n_a)$, and $\Bbb P(N_c=n_b+n_c\ |\ N_b=n_b)$, and so on. By a hand wave. There is some binomial model for each such computation, and usually there is no $\Bbb P$ in the proposition, the success probabilities $p(b)=5/6$, $p(c)=4/6$, and so on are mentioned. Well, the letters $b,c,...$ are also tacitly avoided, and the propositions tend to use only the stopping times $N_a,N_b,N_c,N_d,N_e,N_f$. So we mention only that the modeling can be done for the conditionally stopped stopping times using binomial models with the corresponding success probabilities.

The expectation of such a repetead binomial experiment is known, $1/p$, where $p$ is the success probability, so we have to compute only in this evident one-liner solution: $$ \sum_{\substack{p=k/6\\k=1,2,3,4,5,6}}\frac 1p=\sum_{1\le k\le 6}\frac 6k\ . $$ (And usually, one lets the others compute this sum, this is a too trival task. And the number has no relevant meaning, after the real work was done.)