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
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).
In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.