Consider a square like this $$\begin{array}\\ 1 & - & 2\\ | & & |\\ 3 & - & 4 \end{array} $$ such that you can go from each state with chance $\tfrac{1}{2}$ to the neighbouring states. So we have the following transition matrix $$P = \begin{pmatrix}0 & \tfrac{1}{2} & \tfrac{1}{2}& 0\\ \tfrac{1}{2} & 0 & 0 & \tfrac{1}{2}\\ \tfrac{1}{2}&0 & 0 & \tfrac{1}{2}\\ 0 & \tfrac{1}{2} & \tfrac{1}{2}& 0 \end{pmatrix}. $$ Let $p_{i,j}(n)$ be the position $(i,j)$ in the matrix $P^n$. I want to find $p_{1,1}(n)$.
This is my approach:
- Diagonalize P, the eigevalues of $P$ are $-1,1,0,0$ therefore $P = U D U^{-1} $ where $$D = \begin{pmatrix}1 & 0 & 0 & 0\\ 0 & -1 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ \end{pmatrix} $$ Thus $P^n = U D^n U^{-1}$.
- We know that $p_{1,1}(0) = 1$ and $p_{1,1}(1) = 0$
I would say that $p_{1,1}(n) = A + (-1)^n B$ for $A,B \in \mathbb{R}$. But this is obviously not true because $A = B = \tfrac{1}{2}$ and therefore $$p_{1,1}(2) = \frac{1}{2} + \frac{1}{2} = 1. $$ This is not possible.
I intuitively see that there is symmetry, you can't go back to your start position in odd steps. But I want to make this more formal with linear algebra. I don't see why $$p_{1,1}(n) = \frac{1}{2}A + \frac{1}{2}(-1)^n B = \frac{1}{2} + \frac{1}{2}(-1)^n. $$ I guess this is true because two eigenvalues are zero. But I haven't found something that states this.
The mistake is in the equation $p_{1,1}(n)=A+(-1)^nB$. Instead, it should be $A+(-1)^nB+0^nC$, where $0^n$ is defined to be $1$ if $n=0$ and $0$ for integers $n>0$.
EDIT: By the way, this equation is derived as follows: \begin{align*} p_{1,1}(n)&=e_1^TP^ne_1 \\ &= e_1^TUD^nU^{-1}e_1\\ &= e_1^TU\begin{pmatrix}1^n & 0 & 0 & 0 \\ 0 & (-1)^n & 0 & 0 \\ 0 & 0 & 0^n & 0 \\ 0 & 0 & 0 & 0^n\end{pmatrix}U^{-1}e_1 \end{align*} where $e_1=(1,0,0,0)^T$. Then, since $e_1$ and $U$ are constant (i.e., not depending on $n$), expanding this out gives an equation of the form $p_{1,1}(n)=A+(-1)^nB+0^nC$.