Main Page  Everything for Finite Math  Everything for Applied Calc  Everything  Topic Summaries  On Line Tutorials  On Line Utilities  
 
Finite mathematics topic summary: markov systems 
Markov Systems, State Transition Diagram, Transition Matrix
A Markov system (or Markov process or Markov chain) is a system that can be in one of several (numbered) states, and can pass from one state to another each time step according to fixed probabilities. If a Markov system is in state i, there is a fixed probability, p_{ij}, of it going into state j the next time step, and p_{ij} is called a transition probability. A Markov system can be illustrated by means of a state transition diagram, which is a diagram showing all the states and transition probabilities. (See example opposite.) The matrix P whose ijth entry is p_{ij} is called the transition matrix associated with the system. The entries in each row add up to 1. Thus, for instance, a 22 transition matrix P would be set up as in the following figure. 
Example
Transition Diagram:
Matrix: 

Distribution Vectors and Powers of the Transition Matrix
A distribution vector is a row vector with one nonnegative entry for each state in the system. The entries can represent the number of individuals in each state of the system. A probability vector is a row vector in which the entries are nonnegative and add up to 1. The entries in a probability vector can represent the probabilities of finding a system in each of the states. If v is an initial distribution vector and P is the transition matrix for a Markov system, then the distribution vector after 1 step is the matrix product, vP.
P^{2} is the twostep transition matrix for the system. Similarly, P^{3} is the threestep transition matrix, and P^{n} is the nstep transition matrix. This means that the ijth entry in P^{n} is the probability that the system will pass from state i to state j in n steps. Try our online utility which computes powers of the transition matrix and its action on the distribution vector. Even better (and far more flexible) is our Matrix Algebra Tool, (updated in November 2003) where you can compute several things simultaneously, have the answers shown in fraction or decimal form, and also compute inverses and even complicated expressions involving several matrices. 
Example
Let
and let v = [ 100 200 300 ] be an initial distribution. Then the distribution after one step is given by
The distribution one step later is given by
To obtain the twostep transition matrix, we calculate
Thus, for example, the probability of going from State 3 to State 1 in two steps is given by the 3,1entry in P^{2}, namely 0.3. 

Long Term Behavior of Markov Systems
If P is a transition matrix for a Markov system, and if v is a distribution vector with the property that vP = v, then we refer to v as a steady state (distribution) vector. To find a steady state distribution for a Markov System with transition matrix P, we solve the system of equations given by
Long Term Behavior If the higher and higher powers of P approach a fixed matrix P^{}, we refer to P^{} as the steady state or longterm transition matrix. If a Markov system is regular, then its longterm transition matrix is given by the square matrix whose rows are all the same and equal to the steady state probability vector
Using technology, it is often possible to approximate P^{} with great accuracy by simply computing a very large power of P. How large? You know it is large enough when the rows are all the same to withing the accuracy you desire. For small matrices like the ones in the textbook, P^{256} is usually more than good enough. (256 is a power of 2, and so the computation of P^{256} is especially fast on our Matrix Algebra Tool. Try it!) 
Example
The transition matrix
that we looked at above is regular, since P^{3} contains only nonzero entries. (Check this on your graphing calculator or on our online utility.) The steady state probability vector is given by
The longterm transition matrix is therefore
(To check this, calculate P^{256} on the online utility.) Using the Matrix Algebra Tool Open the Matrix Algebra Tool and enter the matrix P using the following format (note the commas between each pair of entries in each row.): (If you like, you can just copy the blue text below and paste it into the window.)
0.4, 0, 0.6 0.5, 0.5, 0] 

Absorbing Markov Systems
An absorbing state is a state from which there is a zero probability of exiting. An absorbing Markov system is a Markov system that contains at least one absorbing state, and is such that it is possible to get from each nonabsorbing state to some absorbing state in one or more timesteps. In analyzing an absorbing system, we number the states so that the absorbing states come last. The transition matrix P of an absorbing system then looks like this:
Here I is an mm identity matrix (m = the number of absorbing states), S is a square (nm) (nm) matrix (n = total number of states, so nm = the number of nonabsorbing states), 0 is a zero matrix and T is an (nm)m matrix. The matrix S gives the transition probabilities for movement among the nonabsorbing states. The fundamental matrix for the absorbing system is the matrix

Example
Transition Diagram:
Matrix: 

Calculating the Expected Number of Steps to Absorption
To obtain information about the time to absorption in an absorbing Markov system, we first calculate the fundamental matrix Q. The number of times, starting in state i, you expect to visit state j before absorption is the ij^{th} entry of Q. The total number of steps expected before absorption equals the total number of visits you expect to make to all the nonabsorbing states. This is the sum of all the entries in the i^{th} row of Q. The product QT gives the probabilities of winding up in the different absorbing states. For instance, if the i^{th} row of QT is [x y z t], then starting in state i, there is a probability x of winding up in the first absorbing state, a probability y of winding up in the second absorbing state, and so on. 
Example
In the above example,
Thus, for example, the number of times, starting in State 2, you expect to visit State 1 before absorption is the (2,1) entry of Q. That entry is 1/3. In other words, if you start in State 2, you can expect to visit State 1 an average of 1/3 times before absorption. The product QT is
Since the second row is [1/6 5/6], this means that, starting in State 2, there is a 1 in 6 chance of winding up in the first absorbing state (State 5), and a 5 in 6 change of winding up in the second absorbing state (State 6). Using the Matrix Algebra Tool Computing Q: Open the Matrix Algebra Tool and enter the matrix S using the following format (note the commas between each pair of entries in each row): (If you like, you can just copy the blue text below and paste it into the window.)
0.2, 0.2] Computing QT: Open the Matrix Algebra Tool and enter the matrices S and T using the following format: (If you like, you can just copy the blue text below and paste it into the window.)
0.2, 0.2] T = [0.5, 0.25
