Determining invariant probability measure and calculating $\lim_{n}p_{ij}^{(n)}$

Question

Consider the Markov chain $(X_n)_{n\in\mathbb{N}_0}$ with state space $E=\left\{1,2,3\right\}$ and transition matrix $$ P=\frac{1}{2}\begin{pmatrix}0 & 1 & 1\\1 & 0 & 1\\1 & 1 & 0\end{pmatrix}. $$ (i) Does an invariant probability measure $\pi$ exist? If yes, then determine $\pi$. (2) Does $p_{ij}^{(n)}$ converge for $i,j\in E$ as $n\to\infty$? If yes, then determine $\lim_{n\to\infty}p_{ij}^{(n)}$ for $i,j\in E$. Do not use the convergence theorem for this part!

(i) $P$ is irreduccible, that is, there is only one communicating class $C=E$. $C$ is closed and finite, so it is positive recurrent. From this it follows that $C$ carries an invariant probability measure $\pi$. In order to determine $\pi$ I solved $$ (x,y,z)\cdot P=(x,y,z)\text{ with }x+y+z=1, $$ getting $\pi=(x,y,z)=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$.

(2) From the convergence theorem and (1) I know that it has to be $$ \lim_{n\to\infty}p_{ij}^{(n)}=\pi_j=\frac{1}{3}. $$ But the task is to get this without the convergence theorem.

How can this be done?

For example for $i=1, j=2$, it is - as far as I see -

$$ p_{12}^{(2)}=\frac{1}{2^2},~~~~~p_{12}^{(3)}=3\cdot\frac{1}{2^3},~~~~~p_{12}^{(4)}=6\cdot \frac{1}{2^4},~~~~~p_{12}^{(5)}=9\cdot\frac{1}{2^5} $$

Answer 1

The question asks to compute $P^n$ for every $n$, where $$2P=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}=3J-I,\qquad 3J=\begin{pmatrix}1&1&1\\1&1&1\\1&1&1\end{pmatrix}.$$ This is pure algebra, only, playing with $3\times3$ matrices in the ring $\mathbb R[J]$.

Note (and this will be the only matrix computation we shall need) that $$9J^2=(3J)^2=\begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix}=3(3J),$$ hence,

$$\forall n\geqslant1,\qquad J^n=J.$$

For every real parameter $x$, the power series expansion of the exponential yields $$\mathrm e^{xJ}=I+\sum_{n\geqslant1}\frac{x^n}{n!}J=I+(\mathrm e^{x}-1)J.$$ As a consequence, $$\mathrm e^{2xP}=\mathrm e^{x(3J-I)}=\mathrm e^{-x}\mathrm e^{3xJ}=\mathrm e^{-x}I+(\mathrm e^{2x}-\mathrm e^{-x})J.$$ Identifying the coefficients of each $\frac{x^n}{n!}$ from both sides yields, for every $n\geqslant0$, $$2^n\,P^n=(-1)^nI+\left(2^n-(-1)^n\right)J,$$ that is, $$P^n=J+z^n\,(I-J),\qquad z=-\frac12.$$ Thus, $$p_{ii}^{(n)}=\frac{1+2z^n}3,\qquad p_{ij}^{(n)}=\frac{1-z^n}3\quad (i\ne j).$$ This approach can be generalized to every dimension $d+1\geqslant2$, yielding $$p_{ii}^{(n)}=\frac{1+d\,z^n}{d+1},\qquad p_{ij}^{(n)}=\frac{1-z^n}{d+1}\quad (i\ne j),\qquad z=-\frac1d.$$