Markov equilibrium probabilities

[modelling]

Homework Statement

A Markov process with 4 states evolves in unit time steps with a transition probability
matrix given by
P =

|0.5 0 0.3 0.2|
|0.1 0.4 0.2 0.3|
| 0 0.4 0.4 0.2|
|0.1 0.1 0.1 0.7|


Find the equilibrium probabilities for this system. What is the most likely state for the
system after many time steps?

Homework Equations

Im not sure what equations to use

The Attempt at a Solution

I have written the first two steps free hand using the method on this video at 33 minutes in but I am not sure if I need to use a formula instead of writing it out fully. Its taking a very long time and I only have up to n=2 steps.

 

[modelling]

I found how to multiply the matrix to get the 2nd/3rd/4th stage and so on but it is very slow by hand because i have to find each individual value for the matrix. I don't understand what they mean by find the equilibrium probabilities ? and what is the most likely state after many steps ... after how many steps ??

 

[Doc Al]

I found how to multiply the matrix to get the 2nd/3rd/4th stage and so on but it is very slow by hand because i have to find each individual value for the matrix. I don't understand what they mean by find the equilibrium probabilities ? and what is the most likely state after many steps ... after how many steps ??

How many steps? How about infinitely many?

When equilibrium has been reached, the state will not change during the next iteration. Set that up and solve for that state.

 

[Doc Al]

If you want a decent video lecture on the topic, try this:
https://www.youtube.com/watch?v=cP3c2PJ4UHg

 

[modelling]

I've watched the lecture and been reading over it but still don't know how to answer the question. Please help

 

[statdad]

Hint: call the equilibrium probabilities [itex] a, b, c, d [/itex]

The condition mentioned in the movie essentially says that this
[tex]
\begin{bmatrix} a & b & c & d \end{bmatrix} P = \begin{bmatrix} a & b & c & d \end{bmatrix}
[/tex]

From which you can write down a 4 by 4 system of linear equations. It will, unfortunately, have infinitely many solutions, so:
Remove the first equation from the set
Replace it with a + b + c + d = 1

The solutions to that new system gives the equilibrium probabilities.

Nothing more until you at at least have the systems of equations set up.

 

[modelling]

Is it possible to calculate the initial state vector then do the brute force method instead of having to go through the longer method which involves the x, y equations etc.. ?

Can i determine what my initial state vector is by looking at my transition matrix ? Possibly through eigenve

 

[Ray Vickson]

Is it possible to calculate the initial state vector then do the brute force method instead of having to go through the longer method which involves the x, y equations etc.. ?

You cannot "calculate" the initial state vector, except if you are told it is the equilibrium distribution. Typically, the initial state probability vector is given to you as input data.

Anyway, what is so hard about solving 4 linear equations in 4 unknowns? Basically, that is the standard way of doing such problems. The alternative, of taking high powers of P and seeing what is the limit involves a lot more work (although in some ways is better for understanding the system behaviour over time).

If you don't feel like solving a 4x4 system by hand, you can always load the problem into a spreadsheet and let the spreadsheet solver do it for you. Alternatively, you can go so a website that has such solvers available for free use.

 

[statdad]

"Is it possible to calculate the initial state vector then do the brute force method instead of having to go through the longer method which involves the x, y equations etc.. ?"

Ray has hit the main points: I'll emphasize that this brute force method really does nothing to further the understanding of what equilibrium probabilities are, and - there is no general theorem (that I know of) that says "You'll hit the equilibrium probabilities by this power, which depends on the number of states in this way".

There are some general guidelines - but I won't repeat them here.

From your final partial question - about eigenvectors, I assume - the vector of equilibrium probabilities is a left eigenvector, with eigenvalue 1. That was the point of the video.

 

[modelling]

I have each equation setup as

0.5a +0.1b + 0c + 0.1d = a
0a + 0.4b + 0.4c + 0.1d = b
0.3a + 0.2b + 0.4c + 0.1d = c
0.2a + 0.3b + 0.2c + 0.7d = d

Not sure how what to do next..

 

[statdad]

I have each equation setup as

0.5a +0.1b + 0c + 0.1d = a
0a + 0.4b + 0.4c + 0.1d = b
0.3a + 0.2b + 0.4c + 0.1d = c
0.2a + 0.3b + 0.2c + 0.7d = d

Not sure how what to do next..

Gather all the variables to the left (so that each right hand side is zero)
For the first equation you should get
-.5a + .1b + .1d = 0

When you've done that you have a 4 by 4 system that has infinitely many solutions. At that point
follow the rest of the instructions from my original post.

 

[modelling]

Ok now I have:

-0.5a + 0.1b + 0c + 0.1d = 0
0a - 0.6b + 0.4c + 0.1d = 0
0.3a + 0.2b -0.6c + 0.1d = 0
0.2a + 0.3b + 0.2c - 0.3d = 0

So the next step is:

a + b + c + d = 1
0a - 0.6b + 0.4c + 0.1d = 0
0.3a + 0.2b - 0.6c + 0.1d = 0
0.2a + 0.3b + 0.2c - 0.3d = 0

?

Whats the fastest way to solve this system ?
I always struggled with these equations in school and that was years ago :P

 

[Ray Vickson]

Gather all the variables to the left (so that each right hand side is zero)
For the first equation you should get
-.5a + .1b + .1d = 0

When you've done that you have a 4 by 4 system that has infinitely many solutions. At that point
follow the rest of the instructions from my original post.

Those 4 equations in 4 unknowns contain a redundancy: if any three of them hold, the fourth holds as well. (This comes from the fact that all rows of P sum to 1.) So, the usual way is to leave out one of the four and replace it by the normality condition a+b+c+d=1. It should not matter which of the four you leave out, except maybe for the effects of roundoff errors in numerical computation. If you do exact rational arithmetic throughout, it makes no difference at all.

Sorry statdad: I meant to reply to 'modelling' rather than to you, but I hit the wrong button.

 

[modelling]

Whats the best way to solve the system at this stage ? Sorry I haven't solved equations like these in a long time.

 

[Ray Vickson]

Whats the best way to solve the system at this stage ? Sorry I haven't solved equations like these in a long time.

(1) Use Gaussian elimination. For example, use the first equation to solve for 'a' in terms of b, c and d. Plug this expression for 'a' into the other three equations, and simplify. This gives you three equations in the three unknowns b,c and d; you have 'elimanated' 'a' from those three remaining equations---hence the name of the method. Proceed in the same way, for example by using one of the three equations to solve for (say) b in terms of c and d. Then substitute that solution into the remaining two and simplify again. That will leave two equations in the two unknowns c and d, etc.

OK, it takes a while and needs lots of work (and can be susceptable to roundoff errors) but is basically straightforward. It can be made more efficient by appropriate matrix methods, but the basics are exactly as outlined above.

(2) Use a spreadsheet solver; if you have EXCEL or equivalent, check out the "Solver" tool; it may need to be installed from the original disc if it hasn't been already.

(3) Use Maple or Mathematica if you have them; you can also try the free scaled-down version of Mathematica, called 'Wolfram Alpha'; see https://www.wolframalpha.com/

In my old age I have gotten lazy and just do everything in Maple.

(4) Go to one of the numerous free on-line linear solvers. Just Google 'linear equation solver'. I have not, personally, tried them out.

 

[modelling]

just solving it out there I think I've got a=0,b=d,c=-1,d=1/b.. Thats probably rubbish. What seems strange is that this question is worth about only 2 or 3 marks in the exam and I don't know how it takes this long.. especially solbing the equations for a,b,c,d

I need to be able to do this in an exam so I can't use excel etc. to help.

Can someone clarify what a,b,c,d are equal to ?

 

[statdad]

a) The solutions have to be numbers, not variables
b) a, b, c, d will represent the equilibrium probabilities.

You have a system of 4 equations in four unknowns. If you have access to a spreadsheet with matrix functions, or to a calculator that works with matrices, you can write down the coefficient matrix A, the right side matrix B, and get the solution as [itex] A^{-1}B[/itex].

Or, if you have a calculator with matrix functions and it will do row operations, as suggested above, enter the augmented matrix and reduce it.

If you wish to try an on-line solver this is a reliable one.
http://www.zweigmedia.com/RealWorld/tutorialsf1/scriptpivot2.html

Enter your problem and hit "reduce completely"

 

[modelling]

Ok I've figured out the gaussian elimination method and I'm getting the right answer now. Thanks for the help !

 

[statdad]

Good. Best of luck with future problems.