Markov transition matrix: $\lim \limits_{n\to \infty} P^n$ and $\lim \limits_{n\to \infty} \frac1n \sum_{k=1}^n P^k$

Question

Given the Markov transition matrix

$$P=\left( \begin{array}{ccccccc} 0 & 0 & 1 & 0 & 0\\ 0 & 0.3 & 0 & 0 & 0.7\\ 1 & 0 & 0 & 0 & 0\\ 0.4 & 0 & 0 & 0.2 & 0.4\\ 0 & 0.7 & 0 & 0 & 0.3 \\ \end{array} \right)$$

write these two limits:

• $\lim \limits_{n\to \infty} P^n$
• $\lim \limits_{n\to \infty} \frac1n \sum_{k=1}^n P^k$

Is there a systematic way to calculate these matrixes without computing every single entry?

---

I added a aswer, but it is incomplete.

Answer 1

I have an idea. By rearranging rows (and columns to have the same chain, just states relabeled), we are getting two block matrices for recurrent classes and one row for transient state \begin{pmatrix} 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 \\ 0.4 & 0 & 0.2 & 0 & 0.4 \\ 0 & 0 & 0 & 0.3 & 0.7 \\ 0 & 0 & 0 & 0.7 & 0.3 \\ \end{pmatrix} Now, the third row of $\lim\limits_{n \to \infty}P^n$ should be all zeros, because the state is transient, so the probability of finding chain in this state, given non-zero probability distribution of starting in this state is $0$. The Left-Upper block, due to periodicity, have no limit, it either \begin{pmatrix}0 & 1\\1 & 0\\\end{pmatrix} or \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix}. Hence the $\lim$ itself doesn't exist. But, the second block matrix plays it good and have a $\lim$ \begin{pmatrix} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \end{pmatrix}

Thus, the second question make sense, as LU block could be averaged and the answer is \begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0\\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ \end{pmatrix}

Answer 2

I found the solution of the exercise, but I can't figure out how to computing the mean limit.

First, compute the stationary distribution:

• $\pi_0, \pi_2$ are undefined because states $0$ ad $2$ are periodic

• for $\pi_1, \pi_3, \pi_4$ we can use the definition of stationary distribution: $$\sum_i \pi_i=1$$ $$\pi_j = \sum_{j \neq i} p_{i,j}\pi_i$$ $$\pi_i \geq 0$$ therefore:

  • $\begin{cases} \pi_1 + \pi_4 = 1\\ \pi_1 = 0.3\pi_1 + 0.7\pi_4\end{cases} \implies \pi_1 = \pi_4=0.5$

  • $\pi_3 = p_{3,0} · \pi_0 + p_{3,1} · \pi_1 + p_{3,2} · \pi_2 + p_{3,4} · \pi_4$

.

Solution to $\lim \limits_{n\to \infty} P^n$

.

Entries $ij$ of the matrix $\lim \limits_{n\to \infty} P^n$ will be $\pi_i u_{i, j}$, where $u_{i, j}$ is the probability to be absorbed in the class of state $j$, starting from $i$.

Using first step analysis we found: $$ \begin{cases} u_{0,0} = u_{0,2} = u_{2,0} = u_{2,2} = 0 \\ u_{1,1} = u_{1,4} = u_{4,1} = u_{4,4} = 0.5\\ u_{3,1} = u_{3,4} = \sum_i p_{3,i} u_{i,1} = 0.2 u_{3,1} + 0.4 u_{1, 1} \implies u_{3, 1} = 0.25 \\ \end{cases} $$

All others absorbig probabilities are $0$.

Signing with a '-' the undefined probabilities: $$ \lim \limits_{n\to \infty} P^n = \begin{pmatrix} - & 0 & - & 0 & 0\\ 0 & 0.5 & 0 & 0 & 0.5 \\ - & 0 & - & 0 & 0 \\ - & 0.25 & - & 0 & 0.25 \\ 0 & 0.5 & 0 & 0 & 0.5 \\ \end{pmatrix}$$

.

Solution to $\lim \limits_{n\to \infty} \frac1n \sum_{k=1}^n P^k$

.

It is the following but I can't figure out why: $$ \lim \limits_{n\to \infty} \frac1n \sum_{k=1}^n P^k = \begin{pmatrix} 0.5 & 0 & 0.5 & 0 & 0\\ - & - & - & - & - \\ 0.5 & 0 & 0.5 & 0 & 0 \\ 0.25 & 0.25 & 0.25 & 0 & 0.25 \\ - & - & - & - & - \\ \end{pmatrix} $$

Someone can complete this answer?