Before going on with a new idea I suggest a look at "Matrix Moves" in this thread.
Supposing we have the stochastic matrix
The central problems of Linear Algebra are the solution of a simultaneous set of linear equations or Ax = b and determining the eigenvalues of a matrix.
The eigenvalues are usually computed using a computer and we will not break with tradition, they are
There is a little theorem that says if a square matrix has distinct eigenvalues then it is diagonalizable. So this one is diagonalizable.
To do it we need the Eigenvectors of A:
To check whether we have diagonalized it we plug in to
Okay, so what? The useful fact is that to get A^k we only now need the following matrix equation.
Now D^k is easy to get because to raise a matrix with just diagonal elements like D to the kth power you just take each element and raise it to the kth power.
So if we wanted A^10 we would compute
And we are done!
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.