As always, if you can't figure out how to do something, raise your hand. Also, when you are done call over the TA and show what you have before logging off.
A more interesting matrix is
0 0 0 0 0 0 1 1 1which says that whatever state the system is in, it will move to state 3 in the next step.
You might try multiplying that matrix by a "state-vector" s = [.33; .33; .33], which says that each of the three states is equiprobable. The result should be [0; 0; 1], which says that the probability is 1 of being in state 3 after one transition, even though you didn't know where you started!
And a more interesting matrix, still, is
.5 0 0 0 0 .5 .5 0 0 0 0 .5 .5 0 0 0 0 .5 .5 0 0 0 0 .5 1which says that at each step, you have a 50-50 chance of remaining in the same state, or going to the next higher state. Of course, state 5 is an equilibrium state and an attractor. Once you reach it, you stay in it. And there are paths that lead inexorably toward it.
Now it's your turn. Define a Markov transition matrix. What is the requirement for it to be well-formed? Each column must add to 1. Write a program which takes an nxn matrix and "normalizes" each column. So if a column does not sum to 1, make it sum to 1 (divide each cell in the column by the sum of the column).
Call your matrix A. Use imagesc to visualize A, A*A, A*A*A, etc. for small powers of A. Do you have an attractor? Does your system reach equilibrium, or does it loop?
Write a program to print every power of A (A*A is called the second power of A, A*A*A is the third power) less than 100. Can you automtically detect equilibrium? How? You will have to keep track of the last power of A and test for equality.
Actually, these powers of A say that in 10, 15, or 100 steps, the probability of making the transition from one state to another tends toward zero, or one, or some asymptote. Now actually define a vector of starting values. If A is a 4x4, then [0; 0; 1; 0] says that you start out in state 3 with probabilty 1. Meanwhile, [0; .5; .5; 0] says you start out in either state 2 or state 3, with respective probabilities of .5. If this vector is s0, then we have s1 = A*s0, s2 = A*A*s0, s3 = A*A*A*s0, etc. which shows the probabilities of each state in each time step. Start with a random s0 (remember that it must sum to 1), and show the powers of A applied to s0. Use imagesc on each of the vectors si.
Can you detect that the system has looped? This is harder, but you can do it! Yes, you will have to somehow store every power of A you have seen so far. This is a good time to play with a 3-dimensional array. You can store each iteration in an array called history, history(1:9,1:9,1) = A, if A is 9x9. history(1:9,1:9,2) = A^2. To check for repetition, once you generate a new power of A, check through your history(1:9,1:9,i) for a prior epoch when you had this same matrix.
Do the patterns you observe differ when your original matrix has many zeroes in it (we call this a sparse transition matrix -- it means that some states never "communicate" with other states)? Put the whole process in a loop so that it automatically re-starts with a new, possibly sparse transition matrix, each time it loops or reaches equilibrium. Show the TA that you can generate both sparse transition matrices and dense transition matrices.
Ok, that's it! Wasn't that fun?