Expected number of turns in dice throwing

Question

I generated a transition probability matrix for a scenario where I throw five dice and set aside those dice that are sixes. Then, I throw the remaining dice and again set aside the sixes - then I repeat this procedure until I get all the sixes. $X_n$ here represents the number of dices that are sixes after n rolls.

$$\begin{pmatrix}\frac{5^5}{6^5} & \frac{3125}{6^5} & \frac{1250}{6^5} & \frac{250}{6^5} & \frac{25}{6^5} & \frac{1}{6^5}\\\ 0 & \frac{625}{6^4} & \frac{500}{6^4} & \frac{150}{6^4} & \frac{20}{6^4} & \frac{1}{6^4} \\\ 0& 0 & \frac{125}{6^3}& \frac{75}{6^3}& \frac{15}{6^3} & \frac{1}{6^3} \\\ 0 & 0& 0& \frac{25}{6^2}& \frac{10}{6^2}& \frac{1}{6^2}& \\ 0 & 0 & 0 & 0 & \frac{5}{6} & \frac{1}{6} \end{pmatrix}$$

I want to figure out how many turns it takes for me on average to get all sixes.

I'm not even sure where to start with this problem. Is it a right approach to write a program where I calculate $P^n$ and see when the 6th column all equals to 1?

Any pointers would be greatly appreciated.

Answer 1

Just a quick correction to your transition matrix...

$$P =\begin{pmatrix}\frac{5^5}{6^5} & \frac{3125}{6^5} & \frac{1250}{6^5} & \frac{250}{6^5} & \frac{25}{6^5} & \frac{1}{6^5}\\\ 0 & \frac{625}{6^4} & \frac{500}{6^4} & \frac{150}{6^4} & \frac{20}{6^4} & \frac{1}{6^4} \\\ 0& 0 & \frac{125}{6^3}& \frac{75}{6^3}& \frac{15}{6^3} & \frac{1}{6^3} \\\ 0 & 0& 0& \frac{25}{6^2}& \frac{10}{6^2}& \frac{1}{6^2}& \\ 0 & 0 & 0 & 0 & \frac{5}{6} & \frac{1}{6} \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} $$

and it only represents your transition probabilities on a single round of the game, not after n rolls.

One thing you can try doing is calculating

$$X_n = [1 \ 0 \ 0 \ 0 \ 0 \ 0] P^n = [p_{n,1} \ p_{n,2} \ p_{n,3} \ p_{n,4} \ p_{n,5} \ p_{n,6}]$$

The expected number of rounds played in this game would be given by

$$ S=1+\sum_{n=1}^\infty (p_{n,1}+p_{n,2}+p_{n,3}+p_{n,4}+p_{n,5}) $$

i.e. You're adding up all the elements in the first five columns for $n=1,2,3...$, since those represent the probability of still playing the game after n rounds. You can easily approximate $S$ using a spreadsheet. Calculating it analytically using this method might be tedious, but I would assume is definitely doable.

Answer 2

An other method

Each turn you set aside any die which shows a six.

Let $F_n$ be the expected number of turns until you set aside at least one of $n$ die.   Let $E_n$ be the expected number of turns until you set aside all $n$ die.   Let $p_n(k)$ be the (conditional)probability of setting aside $k$ die in a turn when given that you set aside at least one.

$$\begin{align}p_n(k) &=\binom nk\dfrac{ 5^{n-k}}{(6^n-5^n)}\mathbf 1_{k\in \{1,..,n\}} \\ F_n &= 6^n/(6^n-5^n) \\ E_1 &= F_1\\ &=6 \\ E_2 &= F_2+p_2(1)E_1 \\ &= 36/11+2(5/11)\cdot 6\\ & = 96/11 \\ E_3 &= F_3+p_3(1)E_2+p_3(2)E_1 \\ E_4 &= F_4+p_4(1)E_3+p_4(2)E_2+p_4(3)E_1 \\ E_5 &= F_5+p_5(1)E_4+p_5(2)E_3+p_5(3)E_2+p_5(4)E_1 \\ E_6 &= F_6+p_6(1)E_5+p_6(2)E_4+p_6(3)E_3+p_6(4)E_2+p_6(5)E_1 \end{align}$$

$$$$

Answer 3

If $E_n$ is the expected number required when $n$ out of $5$ are already a six then clearly $E_5=0$ and you can write (dropping your final column)

$$\begin{pmatrix}E_0 \\ E_1 \\ E_2 \\ E_3 \\ E_4 \end{pmatrix} =\begin{pmatrix}1 \\ 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} + \begin{pmatrix}\frac{5^5}{6^5} & \frac{3125}{6^5} & \frac{1250}{6^5} & \frac{250}{6^5} & \frac{25}{6^5} \\ 0 & \frac{625}{6^4} & \frac{500}{6^4} & \frac{150}{6^4} & \frac{20}{6^4} \\ 0& 0 & \frac{125}{6^3} &\frac{75}{6^3}& \frac{15}{6^3} \\ 0 & 0& 0& \frac{25}{6^2}& \frac{10}{6^2} \\ 0 & 0 & 0 & 0 & \frac{5}{6} \end{pmatrix} \begin{pmatrix}E_0 \\ E_1 \\ E_2 \\ E_3 \\ E_4 \end{pmatrix}$$

which you can either solve by hand or, if $M$ is that square matrix, find the row sums of $(I-M)^{-1}$

I think it should give you $E_5 \approx 13.023662$

Answer 4

Yet another way:

Let's call rolling all five dice a "turn". Let $X$ be the number of the first turn on which all five dice have rolled at least one six. If $X>n$ then we have at least one die which has not rolled a six by turn $n$. So $$\begin{align} E(X) &= \sum_{n>0} P(X > n) \tag{1} \\ &= \sum_{n=0}^{\infty} \{1 - [1-(5/6)^n)]^5 \} \\ &= \sum_{n=0}^{\infty} \left( 1 - \sum_{i=0}^5 (-1)^i \binom{5}{i} (5/6)^{ni} \right) \tag{2}\\ &= \sum_{i=1}^5 (-1)^{i+1} \binom{5}{i} \sum_{n=0}^{\infty} (5/6)^{ni} \\ &= \sum_{i=1}^5 (-1)^{i+1} \binom{5}{i} \frac{1}{1-(5/6)^i} \tag{3}\\ &= 13.02366 \end{align}$$

$(1)$ is true for any discrete random variable which only takes on non-negative values.

$(2)$ is by the binomial theorem.

$(3)$ is by the formula for the sum of an infinite geometric series.