Summary of Chapter 9 in
Everything for Finite Math
Everything for Calculus
Everything for Finite Math & Calculus
Chapter 8 Summary Chapter G Summary
Utilities: Matrix Algebra Tool | Markov Process Simulation | Markov Process Utility
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, pij, of it going into state j the next time step, and pij 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 pij 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.
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.
P2 is the two-step transition matrix for the system. Similarly, P3 is the three-step transition matrix, and Pn is the n-step transition matrix. This means that the ijth entry in Pn is the probability that the system will pass from state i to state j in n steps.
Try our on-line 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.
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 two-step 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,1-entry in P2, 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 long-term transition matrix. If a Markov system is regular, then its long-term 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, P256 is usually more than good enough. (256 is a power of 2, and so the computation of P256 is especially fast on our Matrix Algebra Tool. Try it!)
The transition matrix
that we looked at above is regular, since P3 contains only non-zero entries. (Check this on your graphing calculator or on our on-line utility.)
The steady state probability vector is given by
The long-term transition matrix is therefore
(To check this, calculate P256 on the on-line 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 non-absorbing state to some absorbing state in one or more time-steps.
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 (n-m) (n-m) matrix (n = total number of states, so n-m = the number of nonabsorbing states), 0 is a zero matrix and T is an (n-m)m matrix.
The matrix S gives the transition probabilities for movement among the non-absorbing states. The fundamental matrix for the absorbing system is the 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 ijth entry of Q.
The total number of steps expected before absorption equals the total number of visits you expect to make to all the non-absorbing states. This is the sum of all the entries in the ith row of Q.
The product QT gives the probabilities of winding up in the different absorbing states. For instance, if the ith 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.
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.)
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.)
T = [0.5, 0.25
Top of Page