How to compute the powers of $2\times2$ Markov matrices Consider a Markov chain $(X_n)$ with state space $E=\{1,2\}$. If given a transition matrix 
$$P=\pmatrix{1-a&a\\b&1-b}\;,$$
with $0<a,b<1$.
How to find out the $n$-th power to the matrix $P$?
Meanwhile, how to find the stationary distribution of the Markov Chain and the mean recurrence time?
 A: 
The algebraic way: work in the ideal $\langle P\rangle$...

Note that $P=(1-c)I+Q$ where $c=a+b$ and $$Q=\begin{pmatrix}b&a\\ b&a\end{pmatrix},$$ hence $Q^2=cQ$, more generally, $Q^k=c^{k-1}Q$ for every $k\geqslant1$ hence $$P^n=(1-c)^nI+\sum_{k=1}^n{n\choose k}(1-c)^{n-k}Q^k=(1-c)^nI+\sum_{k=1}^n{n\choose k}(1-c)^{n-k}c^{k-1}Q,$$ that is, $P^n=(1-c)^nI+r_nQ$ where $$r_n=\sum_{k=1}^n{n\choose k}(1-c)^{n-k}c^{k-1}=\frac1c\sum_{k=0}^n{n\choose k}(1-c)^{n-k}c^{k}-\frac1c(1-c)^n=\frac{1-(1-c)^n}c.$$ Thus, for every $n\geqslant0$,$$P^n=\begin{pmatrix}(1-c)^n+r_nb&r_na\\ r_nb&(1-c)^n+r_na\end{pmatrix},$$ and finally, $$P^n=\frac1{a+b}\begin{pmatrix}b+a(1-a-b)^n&a-a(1-a-b)^n\\ b-b(1-a-b)^n&a+b(1-a-b)^n\end{pmatrix}.$$ Exercise: (1) Why is the expression for $P^n$ especially simple when $a+b=1$? (2) What is the limit of $P^n$ when $n\to\infty$, in the general case? (3) Simplify the computations above, (proving and) using the fact that the sums of the rows of $P^n$ are $1$, for every $n$.
A: The two eigenvalues of your matrix P are: $ p_1 = 1 $, $ p_2 = 1-(a+b) $
Here two things can happen : $ p_1 \neq p_2$ or $p_1 = p_2$. Since $p_1 = p_2\implies a=-b $ and that 0 < a,b , we can eliminate this possibility.
So P has two different eigenvalues, P is a 2x2 square matrix, hence it is diagonalizable in a basis of eigenvectors. One of them can be $ \begin{pmatrix} 1\\1\end{pmatrix} $ for the eigenvalue 1. I'll let you find the other.
When you have found the other vector, if you write the matrix B defined as such: $B = (V_1 V_2)$ where $V_1$ is the eigenvector for 1, $V_2$ the other, you have:
$B^{-1}*P*B = D  = \pmatrix{1&0\\0&1-(a+b)}\;$
Now : $ (B^{-1}*P*B)^n = B^{-1}*P^n*B = D^n =  \pmatrix{1&0\\0&(1-(a+b))^n}\; $
You can then get $P^n$ easily.
By the way, one other method would be using lagrange's interpolation. You take the polynomials that respectively have 1 and 1-(a+b) as roots and the value 1 at the other eigenvalue (I'll note them $P_1$ and $P_2$), and write :
$X^n = a_n*P_1(X) +b_n*P_2(X)$ You find the two coefficients $a_n$ and $b_n$ with the conditions: 
$ P_1(1)=0, P_1(1-(a+b))=1; P_2(1)=1, P_2(1-(a+b)) =0 $
Replace everything ang you'll have what you want by evaluating the relation in X=P
A: Claim:
$$(a+b)P^n=(1-a-b)^n\pmatrix{a&-a\\-b&b}+\pmatrix{b&a\\b&a}$$
Surely true for $n=0$. Assume true for $n=k$.
Then
$$(a+b)P^{k+1}=\pmatrix{1-a&a\\b&1-b}\left ((1-a-b)^k\pmatrix{a&-a\\-b&b}+\pmatrix{b&a\\b&a}\right )$$
$$...algebra...=(1-a-b)^{k+1}\pmatrix{a&-a\\-b&b}+\pmatrix{b&a\\b&a}$$
So true for all n by induction.
