Consider a discrete time Markov chain

Question

Determine the value of $$𝑃(𝑋_{3000000}=2 | 𝑋_0=1); 𝑃(𝑋_{3000001}=2 | 𝑋_0=1); 𝑃(𝑋_{3000002}=2 | 𝑋_0=1).$$ If consider a discrete time Markov chain $X_1,X_2,\dots$ with a state space set $S=\{1,2,3,4,5,6\}$ and a transition probability matrix $$𝑃=\left[\begin{array}{cc} 0 & 0 & 0.5 & 0.5 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0.5 & 0.5\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0.5 & 0.5 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 \end{array}\right]$$

My Attempt: (Anyone can help me? What next? Thank you)

The probability of reaching state $2$ after a certain number of steps in a Markov chain can be computed using the transition probability matrix. In this case, to finding the probabilities of reaching state $2$ at time steps $3000000, 3000001,$ and $3000002,$ given that the chain starts in state $1.$

Let $(P_{ij}^{(n)})$ denote the probability of transitioning from state $(i)$ to state $(j)$ in $(n)$ steps. The probability of reaching state $(j)$ at time step $(n)$ starting from state $(i)$ is given by $((P^n)_{ij})$, where $(P)$ is the transition probability matrix.

Let's compute these probabilities:

1. $(P(X_{3000000} = 2 | X_0 = 1)):$

   $[P(X_{3000000} = 2 | X_0 = 1) = (P^{3000000})_{12}]$

2. $(P(X_{3000001} = 2 | X_0 = 1)):$

   $[P(X_{3000001} = 2 | X_0 = 1) = (P^{3000001})_{12} = (P^{3000000} \cdot P)_{12}]$

3. $(P(X_{3000002} = 2 | X_0 = 1)):$

   $[P(X_{3000002} = 2 | X_0 = 1) = (P^{3000002})_{12} = (P^{3000000} \cdot P^2)_{12}]$

Answer 1

Generally, calculating large powers of $P$ is difficult. However, this matrix has a "nice" form. In particular, it can be written as the Kronecker product $P = A \otimes B$, where $$ A = \pmatrix{0&1&0\\0&0&1\\1&0&0}, \quad B = \frac 12 \pmatrix{1&1\\2&0}. $$ We can now compute $P^k = [A \otimes B]^k = A^k \otimes B^k$.

$A$ is a permutation matrix, and as such its power follow a nice pattern. $A^k$ will have 3 different values depending on the remainder of $k$ modulo $3$. Either we have $A^k = A$ when $k \equiv 1\pmod 3$, $A^k = A^T$ when $k \equiv 2 \pmod 3$, and $A^k= I$ when $k \equiv 0 \pmod 3 $.

$B$ is a matrix associated with a simpler Markov chain; the powers $B^k$ quickly approach a limit as $k \to \infty$. In particular, we find that the left-eigenvector of $B$ associated with $\lambda = 1$ (and normalized to have sum of entries equal to $1$) is $v = (2/3,1/3)^T$. Thus, we have $$ \lim_{k \to \infty}B^k = \pmatrix{v^T\\v^T} = \frac 13 \pmatrix{2&1\\2&1}. $$ For $k = 3000000, 3000001, 3000002$, we have $B^k \approx \lim_{k \to \infty}B^k$, which is to say that $B^k$ is approximately equal to the matrix above.

Now, for $k = 3000000$, $k \equiv 0 \pmod 3$, which means that $A^k = I$. Thus, the transition matrix for $P$ is approximately $$ P = I \otimes B^k \approx I \otimes \frac 13 \pmatrix{2&1\\2&1} = \frac 13\pmatrix{ 2 & 1 & 0 & 0&0&0\\ 2&1&0&0&0&0\\ 0&0&2&1&0&0\\ 0&0&2&1&0&0\\ 0&0&0&0&2&1\\ 0&0&0&0&2&1}. $$ Thus, $P(X_k = 2 \mid X_0 = 1) = [P^k]_{1,2} \approx 1/3$.

For the other two values of $k$, you should find (by following the same procedure) that $P(X_k = 2 \mid X_0 = 1) = 0$.