# What is the probability of rolling all faces of a die after n number of rolls

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

• this is crossposted to math.se. Also the fractions in brackets are flipped. Mar 22, 2012 at 1:11

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