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.

Transition Diagram:
(Missing arrows indicate zero probability.)

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.

Distribution After 1 Step:   vP

Distribution After 2 Steps:   vP²

Distribution After n Steps:   vPⁿ

P² is the two-step transition matrix for the system. Similarly, P³ is the three-step transition matrix, and Pⁿ is the n-step transition matrix. This means that the ijth entry in Pⁿ 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.

Let

P =		0.2	0.8	0
		0.4	0	0.6
		0.5	0.5	0

and let v = [ 100   200   300 ] be an initial distribution. Then the distribution after one step is given by

vP = [ 100   200   300 ]		0.2	0.8	0
		0.4	0	0.6
		0.5	0.5	0
= [ 250   230   120 ]

The distribution one step later is given by

vP2 = (vP)P
= [ 250   230   120 ]		0.2	0.8	0
		0.4	0	0.6
		0.5	0.5	0
= [ 202   260   138 ].

To obtain the two-step transition matrix, we calculate

P2 =		0.2	0.8	0			0.2	0.8	0
		0.4	0	0.6			0.4	0	0.6
		0.5	0.5	0			0.5	0.5	0

=		0.36	0.16	0.48
		0.38	0.62	0
		0.3	0.4	0.3

Thus, for example, the probability of going from State 3 to State 1 in two steps is given by the 3,1-entry in P², namely 0.3.

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

x + y + z + . . .	=	1
[x   y   z . . . ]P	=	[x   y   z . . .]

v = [x   y   z . . . ]

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

[x   y   z . . .].

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²⁵⁶ is usually more than good enough. (256 is a power of 2, and so the computation of P²⁵⁶ is especially fast on our Matrix Algebra Tool. Try it!) Warning;If the matrix does not stabalize fairly quickly, then there is a danger of significant computational: the larger the numer of computations required, the more serious this problem becomes.

The transition matrix

P =		0.2	0.8	0
		0.4	0	0.6
		0.5	0.5	0

that we looked at above is regular, since P³ 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

v = [35/99   40/99   24/99],

vP = [35/99   40/99   24/99]		0.2	0.8	0
		0.4	0	0.6
		0.5	0.5	0
= [35/99   40/99   24/99]
= v.

The long-term transition matrix is therefore

P =		35/99	40/99	24/99
		35/99	40/99	24/99
		35/99	40/99	24/99

(To check this, calculate P²⁵⁶ 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.)

P = [0.2, 0.8, 0
0.4, 0, 0.6
0.5, 0.5, 0]

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:

P =		S	T
		0	I

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

Q = (I-S)^-1.

Transition Diagram:
(States 3 and 4 are absorbing. Missing arrows indicate zero probability.)

Matrix:

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 non-absorbing 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.

In the above example,

Q = (I-S)-1 =		0.75	0		-1
		-0.2	0.8
=		4/3	0
		1/3	5/4

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

0 20/3 5/16 5/3

QT =		2/3	1/3
		1/6	5/6

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.)

S = [0.25, 0
0.2, 0.2]