Probability in a fixed die

Question

I have that transition matrix is $$\begin{bmatrix}0&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}\\\frac{1}{5}&0&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}\\\frac{1}{5}&\frac{1}{5}&0&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}\\\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&0&\frac{1}{5}&\frac{1}{5}\\\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&0&\frac{1}{5}\\\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&0\end{bmatrix}$$ If I did $P^{(n)}=P^{(n-1)}P$ I get that $$p_{66}^{(n)}=\frac{1}{5}(p_{61}^{(n-1)}+p_{62}^{(n-1)}+p_{63}^{(n-1)}+p_{64}^{(n-1)}+p_{65}^{(n-1)})$$

Answer 1

That is mistaken. Let's look at the probability distribution of $X_2$ given $X_0=6$.

\begin{align} & \Pr(X_2 = 6\mid X_0=6) \\[10pt] = {} & \Pr\Big( \underbrace{(X_1 = 1\ \&\ X_2 = 6)\text{ or }(X_1=2\ \&\ X_2=6)\text{ or }\cdots}_{\text{five disjuncts}}\mid X_0=6\Big) \\[10pt] = {} & \underbrace{\Pr\Big(X_1 = 1\ \&\ X_2 = 6 \mid X_0=6\Big) + \Pr\Big(X_1 = 2\ \&\ X_2 = 6 \mid X_0=6\Big) + \cdots\quad{}}_{\text{five terms}} \\[10pt] = {} & \underbrace{\left( \frac 1 5 \right)^2 + \left( \frac 1 5 \right)^2 + \cdots \quad {} }_{\text{five terms}} = \frac 1 5. \end{align}

And then: \begin{align} & \Pr(X_2 = 1\mid X_0=6) \\[10pt] = {} & \Pr\Big( \underbrace{(X_1 = 2\ \&\ X_2 = 6)\text{ or }(X_1=3\ \&\ X_2=6)\text{ or }\cdots}_{\text{four disjuncts}}\mid X_0=6\Big) \\[10pt] = {} & 4\left( \frac 1 5 \right)^2 = \frac 4 {25}. \end{align}

So we get $4/25$ for each of five outcomes and $1/5 = 5/25$ for the other outcome.

However, if we have $n$ instead of $2$, I think I'd express it as an $(n-1)$th power of a Markov chain transition matrix. And maybe it would admit a closed form by solving a recursion. And I say $n-1$ rather than $n$ because the problem as phrased goes from $1$ to $n$ rather than from $0$ to $n$.

The above shows why your first guess was wrong; now let's try to get it right. We have the transition matrix: $$ P = \begin{bmatrix}0&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}\\\frac{1}{5}&0&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}\\\frac{1}{5}&\frac{1}{5}&0&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}\\\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&0&\frac{1}{5}&\frac{1}{5}\\\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&0&\frac{1}{5}\\\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&\frac{1}{5}&0\end{bmatrix} $$

When a matrix has a constant diagonal and a constant off-diagonal, then one can use the following trick. Write it as a linear combination of the matrix that projects orthongonally onto the space spanned by $(1,1,1,\ldots,1)^T$ and the matrix of the complement of that projection. The mapping $(a_1,\ldots,a_6) \mapsto (\bar a,\ldots, \bar a)$, where $\bar a = (a_1+\cdots+a_6)/6$, is the first orthongonal projection. The complement is $(a_1,\ldots,a_6) \mapsto (\bar a_1-\bar a,\ldots, a_6 - \bar a)$. Those matrices are therefore $$ A= \begin{bmatrix} \frac16 & \frac16 & \frac16 & \frac16 & \frac16 & \frac16 & \\ \frac16 & \frac16 & \frac16 & \frac16 & \frac16 & \frac16 \\ \frac16 & \frac16 & \frac16 & \frac16 & \frac16 & \frac16 \\ \frac16 & \frac16 & \frac16 & \frac16 & \frac16 & \frac16 \\ \frac16 & \frac16 & \frac16 & \frac16 & \frac16 & \frac16 \\ \frac16 & \frac16 & \frac16 & \frac16 & \frac16 & \frac16 \end{bmatrix} \text{ and }B = \begin{bmatrix}\frac56&\frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}\\ \frac{-1}{6}&\frac56&\frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}\\ \frac{-1}{6}&\frac{-1}{6}&\frac 5 6&\frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}\\ \frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}&\frac56&\frac{-1}{6}&\frac{-1}{6}\\ \frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}&\frac56&\frac{-1}{6}\\ \frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}&\frac{-1}{6}&\frac56\end{bmatrix} $$ We will write $P=\alpha A + \beta B$.

The advantage of this is that we can then exploit the fact that \begin{align} A^2 & =A, \tag 1 \\ B^2 & =B, \tag 2 \\ AB =BA & =0. \tag 3 \end{align}

Solving the system, we get $\alpha= -1/5$ and $\beta=1$. Then by $(1)$, $(2)$, and $(3)$ above, we have $$ P^n= \alpha^n A + \beta^n B. $$

BTW, this experiment can be done with an ordinary (un-"fixed") die: just discard each outcome that is the same as the previous one.

Answer 2

Since $P$ is symmetric, we know from the spectral theorem that $P$ has real eigenvalues and is diagonalizable. Since $P$ is a doubly stochastic matrix, the stationary distribution is uniform, i.e. $$\pi=\left(\frac16,\frac16,\frac16,\frac16,\frac16,\frac16\right).$$ Since $P$ has a stationary distribution, we know that $1$ is an eigenvalue. In particular, $$P\begin{bmatrix}1\\1\\1\\1\\1\\1\end{bmatrix}=\begin{bmatrix}1\\1\\1\\1\\1\\1\end{bmatrix}.$$ Since $P$ is a stochastic matrix, we know that each eigenvalue $\lambda$ satisfies $|\lambda|\leqslant 1$. Further, if $\lambda_i$ are the eigenvalues of $P$, then $$\sum_{i=1}^6\lambda_i = \operatorname{Tr} P = 0. $$ Observe that if $v = (1, 0,\ldots, -1,\ldots, 0)$, i.e. the first component of $v$ is $1$, exactly one other component is $-1$, and the other components are zero, then $Pv=-\frac15 v$. Therefore $P=ADA^{-1}$ where $$ A = \begin{bmatrix}1&1&1&1&1&1 \\1&-1&0&0&0&0\\1&0&-1&0&0&0\\1&0&0&-1&0&0\\1&0&0&0&-1&0\\1&0&0&0&0&-1 \end{bmatrix}$$ and $$ D = \begin{bmatrix}1&0&0&0&0&0\\ 0 & -\frac15 & 0 &0 &0 &0\\ 0& 0& -\frac15 &0 & 0 &0\\ 0 & 0 & 0 & -\frac15 & 0 & 0\\ 0 & 0 & 0 & 0 & -\frac15 & 0 \\ 0 & 0 & 0 & 0 & 0 & -\frac15\end{bmatrix}$$ Since $D$ is diagonal, $$(ADA^{-1})^n = AD^nA^{-1}. $$ Now, from Wolfram we have $$ A^{-1} = \frac16\begin{bmatrix}1&1&1&1&1&1\\1&-5&1&1&1&1\\1&1&-5&1&1&1\\1&1&1&-5&1&1\\1&1&1&1&-5&1\\1&1&1&1&1&-5\end{bmatrix}. $$ I used Matlab to compute $AD^nA^{-1}$ as $$\small\frac16\begin{bmatrix}1+\left(-\frac15\right)^{n-1} & 1 - \left(-\frac15\right)^n & 1 - \left(-\frac15\right)^n & 1 - \left(-\frac15\right)^n & 1 - \left(-\frac15\right)^n & 1 - \left(-\frac15\right)^n\\ 1 - \left(-\frac15\right)^n & 1+\left(-\frac15\right)^{n-1} & 1 - \left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n\\ 1- \left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1+\left(-\frac15\right)^{n-1} & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n\\1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1+\left(-\frac15\right)^{n-1} & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n\\ 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1+\left(-\frac15\right)^{n-1} & 1-\left(-\frac15\right)^n \\ 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1-\left(-\frac15\right)^n & 1+\left(-\frac15\right)^{n-1}\end{bmatrix} $$ Hence, $$\mathbb P(X_n = 6 \mid X_0 = 6) = (P^n)_{66} = 1+\left(-\frac15\right)^{n-1}$$ and $$\mathbb P(X_n = 1\mid X_0 = 6) = (P^n)_{61} = 1-\left(-\frac15\right)^n.$$

Note that $$\lim_{n\to\infty} (P^n)_{ij} = \frac16 $$ for all $i,j$, consistent with the Markov chain being irreducible and aperiodic.