Solving Dice Problems with Markov Chains
probability
A colleague asked me an interesting probability problem involving dice. If you roll a die continuously, are you more likely to roll two consecutive 5’s or a 5 immediately followed by a 6? On average how many rolls are required to roll two consecutive 5’s? How about rolling 5 immediately followed by a 6?
Interactive Example
Solution
Reveal the Solution
The state machine diagram for rolling two consecutive 5’s:
The state machine diagram for rolling a 5 immediately followed by a 6:
Looking at the two state machine diagrams you can see that the second has a lower expected number of rolls to reach state \( q_2 \) since \( q_1 \) contains an additional transition into itself. However, can we compute how many fewer rolls are required?
Let \( t_n \) be the expected number of rolls required starting with state \( q_n \).
We can model rolling two consecutive 5's with the following equations:\begin{aligned} t_0 &= 1 + \frac{5}{6} t_0 + \frac{1}{6} t_1 \\ t_1 &= 1 + \frac{5}{6} t_0 \end{aligned}
Solving for \( t_0 \):
\begin{aligned} t_0 &= 1 + \frac{5}{6} t_0 + \frac{1}{6} t_1 \\ &= 1 + \frac{5}{6} t_0 + \frac{1}{6} \left( 1 + \frac{5}{6} t_0 \right) \\ &= \frac{7}{6} + \frac{35}{36} t_0 \\ &= 42 \text{ rolls} \end{aligned}
Likewise, we can model rolling a 5 immediately followed by a 6 with the following equations:\begin{aligned} t_0 &= 1 + \frac{5}{6} t_0 + \frac{1}{6} t_1 \\ t_1 &= 1 + \frac{4}{6} t_0 + \frac{1}{6} t_1 \end{aligned}
Let's simplify \( t_1 \) first:
\begin{aligned} t_1 &= 1 + \frac{4}{6} t_0 + \frac{1}{6} t_1 \\ &= \frac{6}{5} + \frac{4}{5} t_0 \end{aligned}
Solving for \( t_0 \):
\begin{aligned} t_0 &= 1 + \frac{5}{6} t_0 + \frac{1}{6} t_1 \\ &= 1 + \frac{5}{6} t_0 + \frac{1}{6} \left( \frac{6}{5} + \frac{4}{5} t_0 \right) \\ &= \frac{6}{5} + \frac{29}{30} t_0 \\ &= 36 \text{ rolls} \end{aligned}
Hence it takes 6 fewer rolls to roll a 5 immediately followed by a 6 compared to rolling two consecutive 5's.
General solution with absorbing Markov chains
To calculate the expected number of rolls we can first calculate the expected number of visits to reach transient states \( q_0 \) and \( q_1 \) given by
\begin{aligned} N &= \left( I - Q \right) ^ {-1} \\ &= \left( \begin{bmatrix} 1 & 0\\ 0 & 1\\ \end{bmatrix} - \begin{bmatrix} q_0 \rightarrow q_0 & q_0 \rightarrow q_1 \\ q_1 \rightarrow q_0 & q_1 \rightarrow q_1 \\ \end{bmatrix} \right) ^ {-1} \end{aligned}
where \( I \) is the identity matrix and \( Q \) is the transition matrix between transient states.
The expected number of rolls is the sum of the first row of matrix \( N \) as it is the sum of the expected number of visits from \( q_0 \) to transient states \( q_0 \) and \( q_1 \).
For rolling two consecutive 5’s:
\begin{aligned} N &= \left( I - Q \right) ^ {-1} \\ &= \left( \begin{bmatrix} 1 & 0\\ 0 & 1\\ \end{bmatrix} - \begin{bmatrix} \frac{5}{6} & \frac{1}{6}\\ \frac{5}{6} & 0\\ \end{bmatrix} \right) ^ {-1} \\ &= \begin{bmatrix} 36 & 6\\ 30 & 6\\ \end{bmatrix} \Rightarrow 36 + 6 = 42 \text{ rolls} \end{aligned}
For rolling a 5 immediately followed by a 6:
\begin{aligned} N &= \left( I - Q \right) ^ {-1} \\ &= \left( \begin{bmatrix} 1 & 0\\ 0 & 1\\ \end{bmatrix} - \begin{bmatrix} \frac{5}{6} & \frac{1}{6}\\ \frac{4}{6} & \frac{1}{6}\\ \end{bmatrix} \right) ^ {-1} \\ &= \begin{bmatrix} 30 & 6\\ 24 & 6\\ \end{bmatrix} \Rightarrow 30 + 6 = 36 \text{ rolls} \end{aligned}