The following is useful in solution of many types of problems that reduce down to a Markov chain.

Supposing we have the matrix

and we wish to raise it to the 10th power. Let us say we are only interested in

We could of course use a CAS to compute P^10 and then just look. For instance entering MatrixPower[P,10] into mathematica yields

Here we will look at two other methods.

If we start with

where the names of the boxes denote the position in the matrix. For instance p11 means first row and first column. Then

and

If we say

then using A we can form the linear set of recurrences

with a(1)=1 and b(1)=3.

The system can be solved and results in the solution

Since a_n is

we only need to substitute n = 10 to get our answer of 4783807 which agrees with B).

Was there an easier way? A way that does not require that we guess at the recurrence?

If we get the eigenvalues of P

then using some linear algebra we know the solution is of the form:

where c1 and c2 are constants to be determined from the initial conditions. We already have P^1 so we compute P^2 to get the other.

We form the simultaneous set of equations.

Solving for c1 and c2 we get

Plugging in n = 10 we again get 4783807 as in B).