Dice Game - Probability Theory

Question

There are many dice problems on here so there could be duplicate. If there is I apologize. Here is the question.

The game is given as follows: you are given 5 dice, and the goal of the game is to get all the dice to be showing the same value. On your first roll you roll all the dice, next you can re-roll which ever dice you choose, and you keep doing this until all the dice show the same value. So an example play of the game could go as follows

Roll 1: The dice show 1,1,2,3,4

Roll 2: You leave the two 1's and re-roll the 2,3, and 4 and now the 5 dice show 1,1,1,2,6

Roll 3: Re-roll the 2 and 6 and perhaps we get 1,1,1,1,1 and the game ends because we have all the dice showing the same value.

Here is the question:

Question 1: What is the optimal strategy for minimizing the number of rolls? i.e. if all the dice show different values is it better to re-roll all the dice or choose four to re-roll hoping the the value of the fifth die.

Question 2: Under the optimal strategy, what is the expected number of rolls to end the game?

Answer 1

I believe this could be done rather nicely with Markov Chains. Imagine the 5 states of the game (1,2,3,4,5,E) which correspond to the number of dice that are the same, and E is after the game. Then you can figure out the transition matrix, which is the probability that you go from one state to any of the others:

$P=\left( \begin{array}{cccccc} p(1\rightarrow1)&p(1\rightarrow2)&p(1\rightarrow3)&p(1\rightarrow4)&p(1\rightarrow5)&0\\ 0&p(2\rightarrow2)&p(2\rightarrow3)&p(2\rightarrow4)&p(2\rightarrow5)&0\\ 0&0&p(3\rightarrow3)&p(3\rightarrow4)&p(3\rightarrow5)&0\\ 0&0&0&p(4\rightarrow4)&p(4\rightarrow5)&0\\ 0&0&0&0&0&1\\ 0&0&0&0&0&1\\ \end{array} \right)$

where $p(i\rightarrow j)$ is the probability that you'll start a turn with $i$ dice the same and end it with $j$ the same (not necessarily the same number, so you'd need to be a little careful).

Now you start in state 1, so you can figure out what state you will be in after $n$ turns as:

$\left( \begin{array}{cccccc} 1&0&0&0&0&0 \end{array}\right)\cdot P^n$

This will be an array of 6 numbers, corresponding to the probability that you'll be in each of the 6 states after $n$ turns.

Answer 2

First, observe that if no number appears on multiple dice, you could re-roll all or all-but-one with equal effectiveness, so we will simplify by assuming that you will re-roll all.

Let $N(k)$ be the expected number of rolls to bring $k$ dice all onto a specified number. Thus for example $N(1) = 6$.

Now look at $N(2)$. On the next roll (of two dice), you will get no "successes" $\frac{25}{36}$ of the time, one success $\frac{10}{36}$ and two successes $\frac1{36}$ of the time. So $$ N(2) = 1 + \frac{25}{36}N(2)+ \frac{10}{36} N(1) = \frac{16}{6}+ \frac{25}{36}N(2)\\ N(2) = \frac{36}{11}\frac{16}{6}=\frac{96}{11} $$ On the first roll, you will get five identical numbers $\frac{1}{1296}$ of the time; four identical numbers $\frac{25}{1296}$ of the time, three identical numbers $\frac{100}{1296}$ of the time, and all five different $\frac{120}{1296}$ of the time. That last number is calculated by noting that there are six possible values for the missing numbers, and $120$ possible orderings of the five numbers; and the denominator is $6^5$. That means there are two identical numbers (but not three or more) $\frac{1050}{1296}$ of the time.

Unfortunately, the expected number of rolls from a position like $1,1,2,3,4$ is not simply $N(3)$ because the next roll (replacing the $2,3,4$) might be something like $2,2,2$ and that is progress despite not getting any more ones.

The expected number of rolls $E$ in that case is given by $$ E = 1 + \frac{15}{216}N(1)+ \frac{75}{216}N(2)+\frac{5}{216}N(2)+ \frac{120}{216}E $$ where the $\frac{5}{216}$ represents the cases of getting a triplet of some other number. Thus $$ E = \frac{216}{96}\left(1+ \frac{90}{216} + \frac{80}{216} \frac{96}{11} \right) =\frac94+\frac{90}{96}+\frac{80}{11} = \frac{1841}{176} $$ And finally, the expected number $A$ of rolls overall is $$ A = \frac{1296}{1176} \left(1+6\cdot\frac{25}{1296} +\frac{96}{11}\cdot \frac{100}{1296} + \frac{1841}{176} \cdot \frac{1050}{1296}\right) \\ = \frac{1}{1176} \left( 1296+150+\frac{9600}{11}+ \frac{1841\cdot 1050}{176}\right) $$ This works out to just under $11.3112$ rolls.