5
$\begingroup$

It is fairly easy to figure out what is the average number of rolls it would take to roll all faces of a die [$1 + 6/4 + 6/4 + 6/3 + 6/2 + 6/1 = 14.7$], but that got me thinking of a seemingly more complicated problem.

If you roll a die 1-5 times, the odds of all faces showing is obviously 0. If you roll a die 6 times, the odds of all faces showing can easily be calculated as

$$1 * (5/6) * (4/6) * (3/6) * (2/6) * (1/6) = .0154$$

or 1.54%

This is where I get stuck. How to do it $n=7$ or more times and calculate it for general $n$?

Any tips are helpful!

$\endgroup$
  • 1
    $\begingroup$ this is crossposted to math.se. Also the fractions in brackets are flipped. $\endgroup$ – deinst Mar 22 '12 at 1:11
6
$\begingroup$

So you want to know the probability of getting all the faces at least once after rolling the die $n$ times. It is convenient to introduce the number $N_k$ of faces that have been seen after $k$ steps. Obviously, we have $N_1=1$. Also, $N_{k+1}=N_k$ with probability $\frac{N_k}{6}$ and $N_{k+1}=N_k+1$ otherwise -- in other words, the process $\{ N_k \}_{k \geq 1}$ is an Markov chain. One can thus easily compute the vector $V_k=(\mathbb{P}[N_k=1],\mathbb{P}[N_k=2], \ldots, \mathbb{P}[N_k=6])$ for $k=1,2, \ldots$ and solve the problem. One finds $V_{n+1} = V_0 \, A^{n}$ where $V_0=(1,0,\ldots,0)$ and $A$ is the transition matrix of the Markov chain:

$$A = \begin{pmatrix} 1/6 &5/6 &0 &0 &0 &0 \\ 0 &2/6 &4/6 &0 &0 &0\\ 0 &0 &3/6 &3/6 &0 &0 \\ 0 &0 &0 &4/6 &2/6 &0 \\ 0 &0 &0 &0 &5/6 &1/6\\ 0 &0 &0 &0 &0 &1 \end{pmatrix}$$

To find $V_n$, diagonalize $A$ and then compute the powers. This gives

$$V_{n+1} = \frac{1}{6^{n+1}}\begin{pmatrix}1\\-5\\10\\-10\\5\\1\end{pmatrix}^{tr} \begin{pmatrix} 6^n &0 &0 &0 &0 &0 \\ 0 &5^n &0 &0 &0 &0 \\ 0 &0 &4^n &0 &0 &0 \\ 0 &0 &0 &3^n &0 &0 \\ 0 &0 &0 &0 &2^n &0\\ 0 &0 &0 &0 &0 &1 \end{pmatrix} \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & 1 & -2 & 1 \\ 0 & 0 & -1 & 3 & -3 & 1 \\ 0 & 1 & -4 & 6 & -4 & 1 \\ -1 & 5 & -10 & 10 & -5 & 1 \end{pmatrix} $$

For example, after rolling a die 7 times, set $n=6$ in the preceding formula to get

$$V_7 = \begin{pmatrix}6,1890,36120,126000,100800,15120\end{pmatrix} / 6^7$$

From left to right, these are the chances of having observed exactly 1, 2, ..., through 6 faces. The chance of having seen all 6 faces is the last entry, $15120/6^7 = 35/648 \approx 0.054$. In general, the last entry of $V_{n+1}$ equals

$$\Pr[\text{All faces seen after } n+1 \text{ throws}] = 1-5\ 2^{2-n}+5\ 3^{1-n}(1+2^n)-6^{1-n}(1+5^n).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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