Finding $n$-th power of transition matrix

Question

Is there any shortcut to find $P^{n}=\begin{pmatrix} 1-p & p \\ q & 1-q \end{pmatrix}^n$ quickly and elegantly?

This type of matrix often comes up while dealing with Markov chains. Diagonalization takes way too much time. I need to find eigenvalues, eigenvectors and all that...

Answer 1

Hint

Let $$J=\begin{pmatrix}0&1\\1&0 \end{pmatrix}$$.

Then $$P=(1-q) I +p J$$

And $$[J,I]=0$$ so you can use the standard binomial development and use $J^2=I$.

---

To be more precise as $JI=IJ$ you have: $$P^n= \left( (1-q) I +p J \right)^n=\sum_{k=0}^n \begin{pmatrix} n \\k\end{pmatrix}(1-q)^k p^{n-k} I^k J^{n-k}$$ and: $$J^m = \begin{cases} J \text{ if } m \text{ is odd}\\I \text{ if } m \text{ is even.} \end{cases}$$

Answer 2

Let $S$ be the matrix $$ S= \begin{bmatrix} 1&p\\1&-q \end{bmatrix} \ , $$ which has on the columns the eigenvectors to the eigenvalues $1, 1-p-q$. Then $$ \begin{aligned} S^{-1}PS &= \begin{bmatrix} 1&0\\0&1-p-q \end{bmatrix} \ , \\ P &= S \begin{bmatrix} 1&0\\0&1-p-q \end{bmatrix} S^{-1}\ , \\[2mm] &\qquad\text{ so } \\[2mm] P^n &= S \begin{bmatrix} 1^n&0\\0&(1-p-q)^n \end{bmatrix} S^{-1}\ . \end{aligned} $$

Answer 3

The eigenvalues are $1, -(p+q-1)$

$P = \frac {1}{p+q}\begin{bmatrix} 1&-p\\1&q \end{bmatrix}\begin{bmatrix} 1\\&-(p+q-1) \end{bmatrix}\begin{bmatrix} q&p\\-1&1 \end{bmatrix}\\ P^n= \frac {1}{p+q}\begin{bmatrix} 1&-p\\1&q \end{bmatrix}\begin{bmatrix} 1\\&\lambda^n \end{bmatrix}\begin{bmatrix} q&p\\-1&1 \end{bmatrix}\\ P^n =\frac {1}{p+q}\begin{bmatrix} q+p\lambda^n&p(1-\lambda^n)\\q(1-\lambda)^n&p+q\lambda^n \end{bmatrix} $

Answer 4

If a $2x2$ real matrix $A$ has distinct real eigenvalues $\lambda_1$ and $\lambda_2$, it can be split into a linear combination of projections onto its eigenspaces $A=\lambda_1P_1+\lambda_2P_2$ with $P_1P_2=P_2P_1=0$. Since any projection is idempotent, with this decomposition we have $A^n = \lambda_1^nP_1+\lambda_2^nP_2$. The two projection matrices for this decomposition are $$P_1 = {A-\lambda_2 I \over \lambda_1-\lambda_2} \\ P_2 = {A-\lambda_1 I\over \lambda_2-\lambda_1}.$$ The eigenvalues of your matrix $P$ are easily found by inspection: $1$ is always an eigenvalue of a stochastic matrix and the other is $\operatorname{tr}P-1=1-p-q$. Assuming that $p$ and $q$ are both nonzero, applying the above decomposition to $P$ gives $$P^n = \begin{bmatrix}{q\over p+q} & {p\over p+q} \\ {q\over p+q} & {p\over p+q} \end{bmatrix} + (1-p-q)^n \begin{bmatrix}{p\over p+q} & -{p\over p+q} \\ -{q\over p+q} & {q\over p+q}\end{bmatrix}.$$