Markov Chains

Author :  Thomas Shores
University of Nebraska
Send comments to :  tshores@math . unl . edu

Markov Chains: An Application of Matrix Arithmetic

We are going to illustrate the idea of a Markov chain by way of an example:  Suppose two toothpaste companies compete for customers in a fixed market in which each customer uses either Brand A or Brand B.  Suppose also that a market analysis shows that the buying habits of the customers fit the following pattern in the quarters that were analyzed:  each quarter (three month period) 30% of A users will switch to B while the rest stay with A.  Moreover, 40% of B users will switch to A  in a given quarter, while the remaining B users will stay with B.  If we assume that this pattern does  not vary from quarter to quarter, we have an example of a Markov chain model. 

In tabular form:                                     Switch from
                                                         A             B
                                               A      0.7            0.4
		Switch to    
                                               B     0.3             0.6
                                               
 Notice that if a0 and b0 are the fractions of the customers using A and B, respectively, in a given quarter, a1 and b1 the fractions of customers using A and B in the next quarter, then our hypotheses say  that :

	a1  =  0.7 a0 + 0.4 b0 
	b1  =  0.3 a0 + 0.6 b0.

There is a matrix multiplication lurking here, namely:  
{a1 , b1} = {{0.7 , 0.4 }, { 0.3 , 0.6}} . {a0, b0}.

For example,  let's suppost the initial state is a0 = 0.3,  b0 = 0.7.  Here's a setup in Mathematica to get the next state:

a = {{0.7, 0.4}, {0.3, 0.6}}

MatrixForm[a]

x = {0.3, 0.7}

MatrixForm[x]

a . x

The preceding example illustrates the basic ingredients of a Markov chain: first, every element of the system we are studying is in exactly one of a fixed number of states (in our example, each customer uses either A or B).  Notice that  in any given quarter, the system can be completely described by a  STATE VECTOR of the form   X = {a,b}  (think of this as a column vector in this situation, so that multiplication by a 2×2 matrix makes sense), where a is the fraction of customers currently using A and b the fraction of customers currently using B.  Observe that the sum of these numbers must be 1.  The second condition for a Markov chain model is that the transition from one state to the next state (in our case, the transition from the state in one quarter to the next) is effected by multiplying the current state vector by a fixed square matrix with this property: each column of the matrix is a state vector;  this matrix is called the TRANSITION MATRIX of the system.  The transition matrix of our example occurs  in the preceding equation.  

Once  you have a transition matrix  A for a  Markov chain, it is very easy to predict what happens to a given state vector X after one period: the next state is simply A . X.   

In fact, it is easy to extend this idea to  any number of periods: The state vector X is transformed into  A . A . ... . A . X  after k periods, where the number of factors of  A is k.
Try it out on our example:  let's see what the distribution is three years later.

a . a . a . x

How about after ten?  And what happens if we start with a different state?  Something interesting is going on here.
	
What seems to be happening is that no matter where we start, the states tend towards some common value.  In other words, as  we  move along, multiplication by the matrix a has a smaller and smaller effect on the state vector.   This  inspires a definition: a  steady state vector for the matrix a is one  for which multiplication has no effect whatsoever, that is, a vector v such that  a.v = v.  Put another way, 
	
	0  =  v - a . v  = (I - a) . v
	
Of course, its important that we be able to find a steady state vector whose entries add up to 1 and are nonnegative;  otherwise, the vector cannot be a “state'' for the Markov chain.  Actually, it is sufficient that the entries of the vector be nonnegative with at least one positive entry, for then all we have to do is to divide the vector by the sum of its coordinates to get a state vector in the sense of Markov chains.  For this, you are going to need a new command from Mathematica, namely, NullSpace[I-a].  Try it.

Exercises

Suppose we have the transition matrix A:
                0.5  0.3   0.3
       A  =  0.1  0.6   0.2
                0.4  0.1   0.5
 (1)  Given that this is a Markov Chain transition matrix, find all steady states for
             this matrix.
 (2)  For the initial vectors x0 = {1,0,0} and y0 = {0,0.5,0.5}, follow the Markov process
             for ten periods.   Do these vectors tend towards the steady state?
             
                
Repeat the above exercise using the matrix B:
                 1    0      0  
       B  =   0   0.2  0.7  
                 0   0.8  0.3       
Use the initial vectors above.  Can you explain the results ?