# Markov Chains: Dice Problem I'm not sure how to start

The Problem: You start with five dice. Roll all the dice and put aside those dice that come up 6. Then roll the remaining dice, putting aside those dice that come up 6. And so on. Let $X_n$ be the number of dice that are sixes after $n$ rolls.

a) Describe the transition matrix $P$ for this Markov Chain. I'm just trying to figure out how to construct this transition matrix..

At first I thought I can just have something like (I just put the first row for simplicity since I realized this was wrong)

$$\begin{bmatrix} 1 & 1/4 &1/4 & 1/4 &1/4 \\ \end{bmatrix}$$

I realize this is wrong since the sum exceeds 1. I also realize that I was trying to construct a 5x5 matrix but I would just have the probability that the other dice come up six after rolling one individual dice.

Can someone give me some advice on how to start this? Thank you in advance.

Edit: The only thing I've thought of is creating a massive matrix that has a row for the probability of a success with dice 1, 2, 3, 4, 5, 1&2, 1&3, 1&4 etc. etc. I.e. each row represents a different possibility. But this seems a bit too large..

Edit2: I think I realize that I can have it be a 6x6 matrix. So the first row will be conditioned on not getting any sixes the first roll.

• This chain is for $X_n$ which can only take values in $\{0, 1, \dots, 5\}$ so its transitions between these values are governed by a $6 \times 6$ matrix. You just need to work out $P(X_{n+1} = j | X_n = i)$, and in particular this sequence of RVs surely converges on a single state so you should see that non-recurrence in your matrix. Sometimes with problems like this if I'm really stuck I try to code up a simulation of the chain first in the hopes of finding inspiration that way, and as a way of checking that my proposed transition matrix is correct – jld Feb 6 '18 at 15:47

## 1 Answer

The Markov chain determines $X_n$ which takes values in $S = \{0, 1, 2, 3, 4, 5\}$. The $6 \times 6$ transition matrix $P$ will determine the probability mass over $S$ for $X_{n}$ when $X_{n-1}$ takes a certain value. That is, you need the matrix $P$ that defines for all $x \in S$ and all $i \in S$, $$\Pr(X_n = i \mid X_{n-1} = x)\,.$$

Note that since $X_n$ counts the number of 6s till time $n$, it cannot decrease. So in the transition matrix, the probabilities are zero for whenever $i$ is less than $x$. So let's start filling the transition matrix, starting from the bottom row. When $x = 5$, that is $X_{n-1} = 5$, then the next state must be 5 because all dice are out of play, so all the mass is on state $5$. $$P = \left[ \begin{array}{cccccc} . & . & . &. &.&.\\ . & . & . &. &.&.\\ . & . & . &. &.&.\\ . & . & . &. &.&.\\ . & . & . &. &.&.\\ 0 & 0 & 0 &0 &0&1\\ \end{array} \right]\,.$$

Now, lets fill the 5th row (that is $X_{n-1} = 4$. Since the number of 6s so far is four, that means, that the number of dice still in play is 1. When I roll do the experiment this $n$th time, I am only rolling the one die. So $\Pr(X_n = 5 \mid X_{n-1} = 4) = \Pr(\text{rolling a 6 for a single die}) = 1/6$. The rest of the probability goes to the state $4.$ So,

$$P = \left[ \begin{array}{cccccc} . & . & . &. &.&.\\ . & . & . &. &.&.\\ . & . & . &. &.&.\\ . & . & . &. &.&.\\ 0 & 0 & 0 & 0 & \frac{5}{6}& \frac{1}{6}\\ 0 & 0 & 0 &0 &0&1\\ \end{array} \right]\,.$$

I'll fill one more row for you. for when $X_{n-1} = 3$, then there are two dice to roll. For $X_n = 5$, both dice should be 6, which happens with probability $1/36$. For $X_n = 4$, exactly one die has to be a 6, which happens with probability $2 \times \frac{1}{6} \times \frac{5}{6} = \frac{10}{36}$. The rest of the probability goes to the state $X_n = 3$.

$$P = \left[ \begin{array}{cccccc} . & . & . &. &.&.\\ . & . & . &. &.&.\\ . & . & . &. &.&.\\ 0 & 0 & 0 & \frac{25}{36} & \frac{10}{36}& \frac{1}{36}\\ 0 & 0 & 0 & 0 & \frac{5}{6}& \frac{1}{6}\\ 0 & 0 & 0 &0 &0&1\\ \end{array} \right]\,.$$

Since this is self-study, I will let you fill in the rest of the rows.

EDIT Seeing Chaconne's comment, here I check the final matrix $P$ obtained by looking at $P^t$ at $t = 1000$. I know that eventually all the mass should be at the state $X_n = 5$ irrespective of the starting value. The output matches this result.

> Pt <- P
> for(t in 2:1000)
+ {
+   Pt <- Pt%*%P
+ }
> Pt
[,1]          [,2]          [,3]          [,4]         [,5] [,6]
[1,]    0 9.418588e-317 2.859314e-237 4.340182e-158 3.294003e-79    1
[2,]    0 1.883718e-317 1.143726e-237 2.604109e-158 2.635202e-79    1
[3,]    0  0.000000e+00 2.859314e-238 1.302054e-158 1.976402e-79    1
[4,]    0  0.000000e+00  0.000000e+00 4.340182e-159 1.317601e-79    1
[5,]    0  0.000000e+00  0.000000e+00  0.000000e+00 6.588005e-80    1
[6,]    0  0.000000e+00  0.000000e+00  0.000000e+00 0.000000e+00    1

• +1. But something's wrong with your matrix power: most likely, accumulated floating point error has reduced it from 52 bits to just 1-4 bits of precision. This is easy to check: because $P$ is upper triangular, its diagonal elements $(1-1/6)^k,k=0,1,2,3,4,5,$ are its eigenvalues. Therefore their $n^{\text{th}}$ powers will be the diagonal elements of the upper-triangular matrix $P^n$. The 1000th powers are 1, 6.59E-80 (not 5.49E-80), 4.34E-159 (not 3.01E-159), 2.86E-238, 1.88E-317, and 1.24E-396. A much better way to compute matrix powers is to diagonalize the matrix first. – whuber Feb 6 '18 at 18:33
• @whuber Nicely spotted. My previous loop was going from 1:1000, so the previous output actually was $P^{1001}$. I fixed it so that the loop now goes from $2:1000$. Thanks! Of course, I should go ahead and diagonalize the matrix as well, but this seems to work fine here. – Greenparker Feb 6 '18 at 21:30