Markov Chains (Puzzles and Game Theory)

[James Crook]

Jonathan Joo wrote:

For the markov chains one, I noticed that percentage is the rate of changing from A to E or vice versa (.4 or .7) over the total changing (.4+.7=1.1) ending up with .4/1.1 or 4/11, and .7/1.1 or 7/11. So would the probability of ending up in each state for the second markov graph be .15/.425 (6/17), .25/.425 (10/17) and .025/.425 (1/17)?

Terminology (from graph theory): 'Node' is another name for state.  'Edge' is another name for link.  'Weight' is another name for the strength of the link.

Your idea works perfectly for 2 node Markov chains.

There are two problems with it when using the three node graph.

Something that should ring alarm bells about your idea is that it does not use all the information.  You've only used the three links in the center, but there are three more links with strengths 0.075, 0.05 and 0.25 which are "just as good".  To show your idea can't work as-is, we could make all the links you have used 0.00001, increasing the weight of each link of a node to itself to make the values out of each node still sum up to 1.  You'd have to predict that the distribution would be equal to A,B and C, but it's quite clear that the other links would be what determine the distribution.

Now even if you include the weights of the other links, it's still not going to work!  I happen to know that if the weight of A->A was 1, and the weight of B->A and C->A unchanged, then "we'll end up in A" after long enough.  A is a black hole that everything falls into.

The way forward is to reformulate the problem.  Suppose we represent the probabilities of being in A,B,C at this moment as a vector

a

b

c

Then what are the equations that give the probability of being at A,B,C after one more step?

--James.

[Jonathan Joo]

Hi James,

Ok, I see where I disregarded the edges so that I was only using a small part of the information given. I also understand what you mean by the weights... but how are vectors used in this situation? So far, the only vectors I've learned about is vectors in a 2d plane, where <3,9> for example would be going 3 to the right and 9 up, and have a magnitude of 3sqrt(10). But how does a vector in form

a

b

c 

work?

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com
Sent: Saturday, July 9, 2011 1:46 PM
Subject: Markov Chains (Puzzles and Game Theory)

[Jonathan Joo]

[James Crook]

Well...  a vector in 3D with components a,b,c would have magnitude sqrt(a^2+b^2+c^2)

You've seen multiplication of a vector by a matrix in 2D, where the matrix can for example rotate the vector through an angle.

Try

cos t, -sin t

sin t, cos t

times some vector.  That matrix preserves area, both because its a rotation matrix and because its determinant is 1.

cos t, -sin t 0

sin t, cos t  0

0      0        1

is also a rotation matrix, this time in 3D.  So is

1   0    0

0 cos t, -sin t

0 sin t, cos t 

so is

cos t  0  -sin t

0      1     0

sin t  0    cos t.    

so we can represent rotations in 3D with matrices, and other changes like shearing (where the shape is not preserved).

Matrices can also provide a compact notation for writing out certain simultaneous equations.  We may choose to temporarily forget about the geometrical interpretation of matrices and vectors, and that is what we will do here, for a bit.

How many entries in a 3x3 matrix?  How many links are there in the 3 state diagram?  Can you write equations for the probability of landing up in each state after one move - given a,b,c as the initial probabilities of being in those states when you started? Can you write those equations more compactly using matrix notation?

--James. 

[Jonathan Joo]

Ahh... I think I see the connection a little better now.

How many entries in a 3x3 matrix? 9

How many links are there in the 3 state diagram? 9

Can you write equations for the probability of landing up in each state after one move - given a,b,c as the initial probabilities of being in those states when you started? 

P(a)=.9a+.15b+.25c

P(b)=.075a+.8b+.25c

P(c)=.025a+.05b+.5c

Can you write those equations more compactly using matrix notation?

      a     b      c

a   .9  .075  .025

b  .15   .8     .05

c   .25  .25   .5

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Tuesday, July 12, 2011 4:26 PM
Subject: Re: Markov Chains (Puzzles and Game Theory)

[James Crook]

Yes, so 'one step' on the markov chain is equivalent to multiplying the distribution vector 

a

b

c

by a matrix.

two steps is equivalent to multiplying by the matrix twice (or once by the squared matrix).

three steps is equivalent to multiplying by the matrix cubed...  and so on.

This immediately gives us a slightly faster way of looking at multiple steps, because we can calculate the matrix A squared, then A to the four then A to the eight, then A to the 16 then A to the 32 with 'only' 5 matrix multiplications.  

We could do that multiplication through the matrix calculator at http://www.bluebit.gr/matrix-calculator/

to save doing it by hand.

But there is another way to get what we want, which is the distribution after a large number of steps.  Another option on that calculator gives us eigenvectors.  Have a read of the definition section of:

http://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors

and tell me how you get on.

We're going to find an eigenvector which has eigenvalue 1.  That will mean that it is unchanged by A (and hence also unchanged by any power of A).  It will turn out this is the distribution we end up with after a large number of steps.

--James.

[Jonathan Joo]

Hi James,

Ok, so using the matrix multiplication tool, I got the numbers to be:

a: 0.625

b: 0.3125 

c: 0.0625

which adds up to 1. I'll take a look at eigenvectors next.

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Sunday, July 17, 2011 4:45 PM

[James Crook]

P(a)=.9a+.15b+.25c

0.9*0.625    + 0.15 * 0.3125 + 0.25 * 0.0625 = 0.625

0.075*0.625+ 0.8  *  0.3125 + 0.25 * 0.0625 = 0.3125

0.025*0.625 + 0.05* 0.3125 + 0.5 * 0.0625 = 0.0625

Perfect!

If you try the eigenvector calculator it will give you 

0.891, 0.445, 0.089

Which is an eignevector, and if you multiply by a constant to make the sum equal to one, then you get the answer we want.

--James.

[James Crook]

Jonathan -

I wrote this page for you:

http://onlinemathcircle.com/wiki/index.php?title=Matrix_Diagonalization

Have a look and tell me how you get on.

--James.

[Jonathan Joo]

Hi James,

I read over the article, and I learned what eigenvectors are. I'm still a little confused on what you do with the eigenvectors to come up with the diagonal matrix. 

Thank you!

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Friday, July 22, 2011 6:41 AM

[James Crook]

That's really good, and I'm particularly glad that you're asking about things that aren't quite clear.

Here's the deal...  I try to explain better, and then when you've got it, you update the wiki page to make it clearer for someone else?

The first thing to note is that each eigenvector has an associated eigenvalue.  Look at the example matrix A at the bottom of the wiki page:

http://onlinemathcircle.com/wiki/index.php?title=Matrix_Diagonalization

v_2 is 

0

0

1

And when we pre-multiply it by A it becomes:

0

0

2

So 

(a) v_2 is indeed an eigenvector - its direction is unchanged 

and 

(b) its eigenvalue is 2, since it is increased in magnitude by a factor of 2.

For the choice of A shown as an example we got three eignevectors v_1, v_2, v_3.  Someone chose to give them in order largest eigenvalue first.  That is often done, but is not essential.  With that choice for how to label the three vectors:

A x v_1 = 3 x v_1

A x v_2 = 2 x v_2

A x v_3 = 1 x v_3

I could just tell you that the diagonal matrix has 3,2 and 1 in that order on the diagonal, but it is better to actually see how it happens.  Here's how it happens:

We put the three equations together by making a new matrix S with columns v_1, v_2, v_3 in that order.  Now, you calculate:

A x S

Do it.  What you'll get is a matrix like S, but with the first column multiplied by 3, the second column multiplied by 2 and the third multiplied by 1 (i.e. unchanged).  That's not a surprise.  It's because we chose A's eigenvectors as the columns.

Now consider 

S x D

where D is a diagonal matrix, Diag(p,q,r) [That's just notation for a diagonal matrix with p as the first diagonal element, q as the second diagonal element, r as the third, and zero elsewhere]

Write it out, and you will see that S x D multiplies the columns of S, multiplying the first column by p, the second by q and the 3rd by r.    Do check that that is so.  You have to check that to understand what's going on. It doesn't matter what the values in S are, or the values p,q,r.  It's always true.  So if p, q, r are the eignevalues of A's eigenvectors, naturally in the same order as you put the vectors into S, we have:

S x Diag( p, q, r ) = A x S

S x Diag( 3, 2, 1 ) = A x S

That's because both formulas just multiply the columns of S (which are eigenvectors) by the corresponding eigenvalues.  And provided S has an inverse:

Diag( 3, 2, 1 ) = S^{-1} x A x S

And we have the formula for the diagonalisation of A.  Typically we will use the online calculator to find the eigenvectors (and hence S) and we'll also use the calculator to find the inverse of S.

So the quick answer is - put the eigenvalues along the diagonal, and you have the matrix D.

--James.