Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#1 2012-03-17 01:13:42

bobbym
Administrator

Offline

Matrix moves.

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).


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Board footer

Powered by FluxBB