Die fixed so it can't roll the same number twice in a row, using markov chains?

Question

Studying for probability test and the following question came up:

A six sided die is 'fixed' so that it cannot roll the same number twice consecutively. The other 5 sides each show up with a probability $\frac{1}{5}$. Calculate

P($X_{n+1} = 5 \mid X_1 = 5$) and P($X_{n+1} = 1 \mid X_1 = 5$)

What happens as $n \rightarrow$ $\infty$?

It appears to be a markov chain problem but all I can think to do is to find the eigenvalues of the transition matrix. This seems unfeasible given that it's 6x6. My guess for the second part is that the probability tends to 1/6, as the first value becomes less and less relevant.

Answer 1

Collapse the six states into the two states you actually care about: "$5$" and "not-$5$". There is a well-defined transition probability from each of these to the other, so we can now work with a $2 \times 2$ matrix instead of a $6 \times 6$ matrix.

This is a very common trick with Markov chains. The hard part is making sure that you don't lose any information by grouping the states together. (Here, if we had a different probability of going $1 \to 5$ than of going $2 \to 5$, this wouldn't work.)

Answer 2

Excellent suggestion by @Misha. Since $6$ is a small number, you may want to numerically explore this problem by computing the powers of the transition probability matrix.

$$ P = \begin{bmatrix} 0 & 1/5 & 1/5 & 1/5 & 1/5 & 1/5 \\ 1/5 & 0 &1/5 & 1/5 & 1/5 & 1/5 \\ 1/5 & 1/5 & 0 &1/5 & 1/5 & 1/5 \\ 1/5 & 1/5 & 1/5 & 0 & 1/5 & 1/5 \\ 1/5 & 1/5 & 1/5 & 1/5 & 0 & 1/5 \\ 1/5 & 1/5 & 1/5 & 1/5 & 1/5 & 0 \end{bmatrix} \enspace.$$

You'll see that $P^k$ quickly converges to a matrix where all coefficients are $1/6$. In fact, $P^5$ is already quite close. Of course, you can also repeat the experiment with the reduced chain with two states.

You can also find the steady-state probabilities (they are well-defined in this case) by solving:

$$ \begin{bmatrix} -1 & 1/5 & 1/5 & 1/5 & 1/5 & 1/5 \\ 1/5 & -1 &1/5 & 1/5 & 1/5 & 1/5 \\ 1/5 & 1/5 & -1 &1/5 & 1/5 & 1/5 \\ 1/5 & 1/5 & 1/5 & -1 & 1/5 & 1/5 \\ 1/5 & 1/5 & 1/5 & 1/5 & -1 & 1/5 \\ 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \\ p_5 \\ p_6 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \enspace. $$

It comes as no surprise that the solution is $[1/6, 1/6, 1/6, 1/6, 1/6, 1/6]^T$. Once again, the smart way to solve this problem is the one suggested by Misha, but sometimes numerical explorations reinforce our grasp of a concept.

Answer 3

There are two great answers already, but just for completeness I'll mention that the transition matrix $P$ (as written by @FabioSomenzi) is a circulant matrix, and its eigenvectors and eigenvalues can be written explicitly. The eigenvector matrix is the DFT matrix, in fact. Circulant matrices are sometimes covered in matrix analysis / numerical linear algebra courses (although probably not at the introductory level).

Answer 4

Misha’s answer is the best approach to this problem, but finding the eigenvalues of the full $6\times6$ transition matrix is actually very easy because of its special structure.

Observe that we can write the transition matrix as $M=\frac15(\mathbb1_6-I_6)$, where $\mathbb 1_6$ is the $6\times6$ matrix consisting entirely of $1$s. So, if $\mathbf v$ is an eigenvector of $\mathbb1_6$ with eigenvalue $\lambda$, then $M\mathbf v=\frac15(\mathbb1_6\mathbf v-\mathbf v)=\frac15(\lambda-1)\mathbf v$, which means that $\frac15(\lambda-1)$ is an eigenvalue of $M$. The rank of $\mathbb1_6$ is obviously one, so $0$ is an eigenvalue with multiplicity 5, and the other eigenvalue is $\operatorname{tr}\mathbb1_6=6$. Therefore, the eigenvalues of $M$ are $1$ and $-\frac15$.

Of course, we already knew that one of the eigenvalues of $M$ is $1$ with right eigenvector $(1,1,1,1,1,1)^T$ because it’s row-stochastic, and that’s the only eigenvalue we care about for computing the steady-state distribution. The corresponding left eigenvector can be found by computing the kernel of $M^T-I$ or by observing that by symmetry, its left and right eigenvectors are transposes, therefore a left eigenvector of $1$ is $(1,1,1,1,1,1)$, which after normalizing it so that its entries sum to unity gives the result you expected. Computing the $n+1$ step probabilities is a bit messy, but again, because $M$ is symmetric, the eigenspace of $-\frac15$ is the orthogonal complement of the span of this vector, so it’s pretty easy to diagonalize the matrix. You might also observe that if you subtract any two columns from each other, you get a vector with $\pm\frac15$ in the elements corresponding to the column numbers and zero everywhere else, so vectors with a single $1$ and $-1$ are all eigenvectors of $-\frac15$. It’s not hard to come up with an eigenbasis once you’ve noticed this.

Answer 5

Another approach to solving this is with simple recurrence.

$$P(X_{n+1}=5)=\frac{P(X_n\neq5)}5$$and $$P(X_n\neq5)=1-P(X_n=5)$$

So if we let $a_n=P(X_n=5)$, then

$$a_{n+1}=\frac{1-a_n}5$$

We know that $a_1=1$. We can also see easily that the stable state is $a=(1-a)/5$, or $a=1/6$. Letting $b_n=a_n-\frac16$, we have $$ b_{n+1}+\frac16=\frac{1-b_n-\frac16}5 $$ or $$ b_{n+1}=-\frac{b_n}5 $$ which is easily solved as $$ b_n=C\left(-\frac15\right)^n $$ Noting that $b_1=\frac56$, we get $$ a_n=\frac16-\frac16\left(-\frac15\right)^{n-2} $$

Answer 6

An alternative approach for the part about $n \to \infty$ that does not require any calculations:

There is no probabilistic difference between the numbers $1,2,\ldots,6$ on the die. So, since the Markov chain is clearly aperiodic and has a finite number of states, we can conclude by symmetry that

\begin{equation} \lim_{n \to \infty} \mathbb{P}(X_n = i \mid X_1 = j) = \frac{1}{6}. \end{equation}

Answer 7

I have a similar question.

Dice is rolled and lands on six. A. Probability dice lands on six after 2 more rolls (ASSUME 20%)

B. Probability dice lands on six after 3 more rolls