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 5×5 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 6×6 matrix. So the first row will be conditioned on not getting any sixes the first roll.
Best 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