# Consider a discrete time Markov chain

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}]$$

• What do you know about large powers of transition matrices? Are you aware of any relevant theorems here? Nov 20 at 21:12
• Do you have anything specifically applicable to periodic Markov chains like the one described here? Nov 20 at 21:14

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$$.
• @JamesAlexander Yes, both should be $0$ Nov 21 at 20:43