<s>[INST] Finding the Long Term behavior of a stochastic matrix. I am struggling to find a formula for $P_{11}^n$ of a $3$ x $3$ stochastic matrix. I am comfortable with handling the 2x2 case as it usually just involves converting the system into a recurrence relation between $P_{11}^{n+1}$ and $P_{11}^n$. However I am unsure of what to do in the 3x3 case. The specific matrix I am having a problem with is 
\begin{bmatrix}
    0 & 2/3 & 1/3  \\
    1/3 & 0 & 2/3  \\
    2/3 & 1/3 & 0
\end{bmatrix}
 [/INST] Here $P$ is a doubly stochastic matrix - both the rows and the columns sum to one. This implies that $P$ has the unique stationary distribution $\pi$ which is the uniform distribution. We can verify this by computing
$$
\begin{bmatrix}\frac13&\frac13&\frac13\end{bmatrix}\begin{bmatrix}
    0 & 2/3 & 1/3  \\
    1/3 & 0 & 2/3  \\
    2/3 & 1/3 & 0
\end{bmatrix}
= \begin{bmatrix}\frac13&\frac13&\frac13\end{bmatrix}.
$$
However, the $n$-step probabilities do not have a nice form:
$$
P^n = \left(
\begin{array}{ccc}
 \frac{1}{3} \left(2\ 3^{-\frac{n}{2}} \cos \left(\frac{5 n \pi }{6}\right)+1\right) & \frac{1}{6} \left(2\ 3^{-\frac{n}{2}} \left(\sqrt{3} \sin \left(\frac{5 n \pi }{6}\right)-\cos \left(\frac{5 n \pi }{6}\right)\right)+2\right) & \frac{1}{6} \left(2-2\ 3^{-\frac{n}{2}} \left(\cos \left(\frac{5 n \pi }{6}\right)+\sin \left(\frac{5 n \pi }{6}\right) \sqrt{3}\right)\right) \\
 \frac{1}{6} \left(2-2\ 3^{-\frac{n}{2}} \left(\cos \left(\frac{5 n \pi }{6}\right)+\sin \left(\frac{5 n \pi }{6}\right) \sqrt{3}\right)\right) & \frac{1}{3} \left(2\ 3^{-\frac{n}{2}} \cos \left(\frac{5 n \pi }{6}\right)+1\right) & \frac{1}{6} \left(2\ 3^{-\frac{n}{2}} \left(\sqrt{3} \sin \left(\frac{5 n \pi }{6}\right)-\cos \left(\frac{5 n \pi }{6}\right)\right)+2\right) \\
 \frac{1}{6} \left(2\ 3^{-\frac{n}{2}} \left(\sqrt{3} \sin \left(\frac{5 n \pi }{6}\right)-\cos \left(\frac{5 n \pi }{6}\right)\right)+2\right) & \frac{1}{6} \left(2-2\ 3^{-\frac{n}{2}} \left(\cos \left(\frac{5 n \pi }{6}\right)+\sin \left(\frac{5 n \pi }{6}\right) \sqrt{3}\right)\right) & \frac{1}{3} \left(2\ 3^{-\frac{n}{2}} \cos \left(\frac{5 n \pi }{6}\right)+1\right) \\
\end{array}
\right).
$$
</s>