Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2012-03-16 02:13:42

From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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


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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.


Board footer

Powered by FluxBB