MTH 244 Linear Algebra:   Markov Chains

Objectives

1. To examine modeling of certain transition systems as Markov chains.
2. To apply the model to certain real world problems.

Prerequisites

1. Linear systems and matrices.
2. Linear transformations.
3. Elementary concepts of probability.

Background

Certain systems, such as population movement and genetics, change through a finite number of states over time and behave randomly according to certain probabilities. If the probability that the system will be in a particular state during a given time period depends only on its state during the previous time period, the system is called a Markov chain. Such a system can be modeled using transition matrices. A transition matrix is an nxn square matrix T, where n is the number of states of the system, whose elements tij are nonnegative (representing probabilities) and whose columns sum to 1. They are also called stochastic matrices, probability matrices, and Markov matrices. For each i and j,tij is the probability that given the system was in state j in one time period, it will be in state i during the next time period.

Example: Population movement between city, suburbs, and country. Suppose the population in the state of Indiana is divided into three categories (states): city dwellers, suburban dwellers, and country dwellers; and each year the population distribution changes according to the following transition matrix:

For example, the entry t3,2 in this matrix represents the probability of given state 2 (living in the suburbs) during one time period, being in state 3 (living in the country) during the next time period. In this case t3,2= 0.01 is the probability of moving from the suburbs to the country during any given year. Another way of interpreting this is that on the average, 1% of the people living in the suburbs will move to the country during any given year. A state vector

represents the state of the system at time period j and has element xi = probability that the system is in state i at time j. The elements are all nonnegative and sum to 1 (since they represent the probabilities of all possible states). The following theorem allows us to compute the state of the system at any time period given some initial state vector:

Theorem: If T is the transition matrix for a Markov chain and x(n) is the state vector at time period n, then x(n+1) = Tx(n).

From this result, given an initial state vector x(0), we can compute states from successive powers of T applied to x(0):

If we apply the above to our population example with an initial probability distribution of

,

we can predict the population trend over future time periods as in MATLAB session below.

» T = [.94 .02 .02; .04 .97 .03; .02 .01 .95];Enter transition matrix T.

» x0=[.55; .20; .25]; Enter initial state vector x(0).

» T*x0                                       Population distribution after one year.

ans =
0.5260                             52.6% in the city
0.2235                             22.35% in the suburbs
0.2505                             25.05% in the country

» T^10*x0                     Population distribution after 10 years.
ans =
0.3803
0.3733
0.2464

» T^10                       10-step transition matrix.
ans =                                                              t(10)1,2 tells us, for example, that 14.14%
0.5758 0.1414 0.1414                                  of those that lived in the suburbs initially
0.2890 0.7755 0.2369                                  will have moved to the city after 10 years.
0.1352 0.0831 0.6217

» T^200*x0                                              Population distribution after 200 years.
ans =
0.2500
0.5417
0.2083

» T^201*x0                                          Population distribution after 201 years.
ans =                                                     Notice there is no change from 200 to 201
0.2500                                                  to the four decimal places shown.
0.5417
0.2083

Note that the above MATLAB session seems to indicate that after enough time (200 years or perhaps less) the system has reached a steady state distribution of

.

This means that after a sufficient period of time the distribution remains steady at 25% in the city, 54.17% in the suburbs, and 20.83% in the country. This will always happen if the transition matrix T is regular -- that is, if for some power of T all of the components are positive ( > 0). The Markov chain represented by T is then said to be a regular Markov chain.

Laboratory on Markov Chains

1. Marketing. Suppose three soft drink companies Royal King, Peppy Cola, and Crown Cola produce the same cola product and each year their market share changes as follows: Royal King keeps 85% of the market share, loses 5% to Peppy Cola, and 10% to Crown Cola. Peppy Cola keeps 80% of its customers, loses 10% to Royal King and 10% to Crown Cola. Crown Cola keeps 90% of its customers and loses 5% to Peppy Cola and 5% to Royal King. Assume during the current year Royal King has 1/2 of the market, and Peppy Cola and Crown Cola each have 1/4 of the market.

a) Set up the transition matrix for this Markov process and write down the initial state vector.

T = 

b) Compute and fill out the market share forecast for the next five years.
 
 
1
2
3
4
5
Royal King
          
Peppy Cola
          
Crown Cola          

c) Experiment to compute Tnx0 for n sufficiently high to determine the steady state vector. Write down the steady state vector and Tn for the n used:           d) What do you observe about the columns of Tn and the steady state vector? e) Using at least two other initial state vectors (make sure the entries are non-negative and sum to 1), determine the steady state vectors by the same method. Write down the initial state vectors used, and power of T computed.                 i ) Initial state vector: _______________ Steady state vector: ___________

                    Power of T used ________

               ii) Initial state vector: _______________ Steady state vector: ___________

                   Power of T used ________
 

2. Gambling. Suppose that a gambler is playing a game of chance where in each game he/she has probability 0.35 of winning amount $100, 0.40 of losing amount $100, and 0.25 of staying even. Assume that the gambler starts with an initial stake of $300 and plays until he/she has won $600 or has gone broke. The possible states for the gambler are S0 = $0 winnings, S1 = $100 winnings, ...., S6 = $600 winnings. The transition matrix T and initial state vector would be:

a) Compute the steady state vector for this problem using the initial state vector above.

b) Interpret your answer for part a) in terms of the expected long-term outcome for the gambler.

 c) Find the steady state vector for each of the alternative starting money amounts:
 
$0
$100
$200
$400
$500
$600

 

d) Explain your results.

e) Does this represent a regular Markov chain? _________ Why?

3. Politics. Assume there are three political parties, Republican, Democrat, and United, which have consistent voting patterns from year to year represented by the following transition matrix T and initial voter distribution x(0). (Here tij = the proportion of members of party j who switch to party i during the next year.)

a) Use MATLAB to find a steady state vector as in exercise 1 and the example in the Background Section, and explain what this means in terms of long-term voter behavior.

b) Experiment with the transition matrix T to see if you can determine a way for the Republicans to achieve a better steady state vector (i.e, a higher percentage of Republicans over the long term). Write down a T (make sure the columns sum to one), determine the steady state vector, and explain your results.