Application to Markov Chains
Introduction Suppose there is a physical or mathematical system that has n possible states and at any one time, the system is in one and only one of its n states. As well, assume that at a given observation period, say k th†† period, the probability of the system being in a particular state depends only on its status at the k-1st period. Such a system is called Markov Chain or Markov process. Let us clarify this definition with the following example.
Example Suppose a car rental agency has three locations in Ottawa: Downtown location (labeled A), East end location (labeled B) and a West end location (labeled C). The agency has a group of delivery drivers to serve all three locations. The agency's statistician has determined the following:
1. Of the calls to the Downtown location, 30% are delivered in Downtown area, 30% are delivered in the East end, and 40% are delivered in the West end
2. Of the calls to the East end location, 40% are delivered in Downtown area, 40% are delivered in the East end, and 20% are delivered in the West end
3. Of the calls to the West end location, 50% are delivered in Downtown area, 30% are delivered in the East end, and 20% are delivered in the West end.
After making a delivery, a driver goes to the nearest location to make the next delivery. This way, the location of a specific driver is determined only by his or her previous location.
We model this problem with the following matrix:
T is called the transition matrix of the above system. In our example, a state is the location of a particular driver in the system at a particular time. The entry sji in the above matrix represents the probability of transition from the state corresponding to i to the state corresponding to j. (e.g. the state corresponding to 2 is B)
To make matters simple, let's assume that it takes each delivery person the same amount of time (say 15 minutes) to make a delivery, and then to get to their next location. According to the statistician's data, after 15 minutes, of the drivers that began in A, 30% will again be in A, 30% will be in B, and 40% will be in C. Since all drivers are in one of those three locations after their delivery, each column sums to 1. Because we are dealing with probabilities, each entry must be between 0 and 1, inclusive. The most important fact that lets us model this situation as a Markov chain is that the next location for delivery depends only on the current location, not previous history. It is also true that our matrix of probabilities does not change during the time we are observing.
Now, letís start with a simple question. I f you begin at location C, what is the probability (say, P) that you will be in area B after 2 deliveries? Think about how you can get to B in two steps. We can go from C to C, then from C to B, we can go from C to B, then from B to B, or we can go from C to A, then from A to B. To figure out P, let†† P(XY) denote the probability of going from X to Y in one delivery (where X,Y can be A,B or C). Do you remember how probabilities work? If two (or more) independent events must both (all) happen, to obtain the probability of them both (all) happening, we multiply their probabilities together. To obtain the probability of either (any) happening, we add the probabilities of those events together.
This gives us P = P(CA)P(AB) + P(CB)P(BB) + P(CC)P(CB) for the probability that a delivery person goes from C to B in 2 deliveries. Substituting into our formula using the statistician's data above gives P = (.5)(.3) + (.3)(.4) + (.2)(.3) = .33.This tells us that if we begin at location C, we have a 33% chance of being in location B after 2 deliveries.
Let's try this for another pair. If we begin at location B, what is the probability of being at location B after 2 deliveries? Try this yourself before you read further! The probability of going from location B to location B in two deliveries is P(BA)P(AB) + P(BB)P(BB) + P(BC)P(CB) = (.4)(.3)+(.4)(.4) + (.2)(.3) = .34. Now it wasn't so bad calculating where you would be after 2 deliveries, but what if you need to know where you will be after 5, or 15 deliveries? That could take a LONG time. There must be an easier way, right? Look carefully at where these numbers come from.†† As you might suspect, they are the result of matrix multiplication.. Going from C to B in 2 deliveries is the same as taking the inner product of row 2 and column 3. Going from B to B in 2 deliveries is the same as taking the inner product of row 2 and column 2. If you multiply T by T, the (2, 3) and† (2,2) entries are respectively, the same answers that you got for these two questions above. The rest of T2 answers the same type of question for any other pair of locations X and Y.
You will notice that the elements on each column still add to 1 and each element is between 0 and 1, inclusive. Since we are modeling our problem with a Markov chain, this is essential. This matrix indicates the probabilities of going from location i to location j in exactly 2 deliveries.
Now that we have this matrix, it should be easier to find where we will be after 3 deliveries. We will let p(AB) represent the probability of going from A to B in 2 deliveries. Let's find the probability of going from C to B in 3 deliveries: it is†† p(CA)P(AB) + p(CB)P(BB) + p(CC)P(CB) = (.37)(.3) + (.33)(.4) + (.3)(.3) = .333. You will see that this probability is the inner product of row 2 of T2 and column 3 of T. Therefore, if we multiply T2 by T, we will get the probability matrix for 3 deliveries.
By now, you probably know how we find the matrix of probabilities for 4, 5 or more deliveries. Notice that the elements on each column still add to 1. Therefore, it is important that you do not round your answers. Keep as many decimal places as possible to retain accuracy.
, , ,
What do you notice about these matrices as we take into account more and more deliveries? The numbers in each row seems to be converging to a particular number. Think about what this tells us about our long-term probabilities. This tells us that after a large number of deliveries, it no longer matters which location we were in when we started. At the end of the week, we have (approximately) a 38.9% Chance of being at location A, a 33.3% chance of being at location B, and a 27.8% chance of being in location C. This convergence will happen with most of the transition matrices that we consider.
Remark If all the entries of the transition matrix are between 0 and 1 EXCLUSIVELY, then convergence is guaranteed to take place. Convergence may take place when 0 and 1 are in the transition matrix, but convergence is no longer guaranteed.
For an example, look at the matrix
Think about the situation that this matrix represents in order to understand why Ak oscillates as k grows.
Sometimes, you will be given a vector of initial distributions to describe how many or what proportion of the objects are in each state in the beginning. Using this vector, you can find out how many (or what proportion) of the objects are in each state at any later time. If the initial distribution vector consist of numbers between 0 and 1, it tells you what proportion of the total number of objects are in each state in the beginning, and the elements in the column sum to one. Alternatively, the vector of initial distributions could contain the actual number of objects or people in each state in the beginning.† In this case, all the elements will be nonnegative and the elements in each row will add to the total number of objects or people in the entire system. In our example above, the vector of initial distributions tells us what proportion of the drivers originally begins in each area. For example, if we start out with a uniform distribution, we will have 1/3 of our drivers in each area. Thus, the vector
is the vector of initial distribution. After one delivery, the distribution will be (approximately) 40% of our drivers in area A, 33.4% in area B, and 26.6% in area C. We found this by multiplying our initial distribution matrix by our transition matrix, as follows:
After many deliveries, we saw that some convergence occurs, so that the area from which we start doesn't matter. This will mean that we will obtain the same right-hand side no matter with which initial distribution we start. For example,
Notice that each right-hand side is the same as one of the columns of our transition matrix after many deliveries. This is exactly what we expected because we said that about 38.9% of the people will be in area A after many deliveries regardless of what percentage of the people were in area A in the initial distribution. Check this with several initial distributions to convince yourself of the truth of this statement.
If the initial distribution indicates the actual number of people in the system, the following can represent our system after one delivery:
Did you notice that we now have a fractional number of people in areas A and C after one delivery? We know that this cannot happen, but this gives us a good idea of approximately how many delivery people are in each area. After many deliveries, the right-hand side of this equality will also be very close to a particular vector. For example,
The particular vector that the product converges to is the total number of people in the system (54 in this case) times any columnn of the matrix that Ak converges to as k grows,
Try some examples to convince yourself that the vector indicating the number of people in each area after many deliveries will not change if people are moved from one state to another in the initial distribution. Also notice that the number of people in the entire system never changes. People move from place to place, but the system never loses or gains people. This can also be illustrated easily using block multiplication: Since, for large N, TN =† [w† w† w] has its 3 columns the same, then if† v = (coulmn vector) (p1, p2, p3) is the initial distribution vector ,TN v = [w† w† w] (p1, p2, p3) (transpose)= p1w+ p2w+ p3w =( p1+ p2+ p3)w =(total number of people initially) w.
I hope the above example gave you a good idea about the process of Markov chains. Now here is the general setting:
Definitions For a Markov chain with n states, the state vector is a column vector whose ith component represents the probability that the system is in the ith state at that time. Note that the sum of the entries of a state vector is 1. For example, vectors X0 and X1 in the above example are state vectors. If pij is the probability of movement (transition) from one state j to state i, then the matrix T=[ pij] is called the transition matrix of the Markov chain.
The following Theorem gives the relation between two consecutive state vectors:
If Xn+1 and Xn are two consecutive state vectors of a Markov chain with transition matrix T, then Xn+1=T Xn
For a Markov chain, we are usually interested in the long-term behavior of a general state vector Xn. In other words, we would like to find the limit of Xn as n→∞. It may happen that this limit does not exist, for example let
Clearly Xn oscillates between the vectors (0, 1) and (1, 0) and therefore does not approach a fixed vector.
A question is: what makes Xn approach a limiting vector as n→∞. The next theorem will give an answer,† first we need a definition:
Definition A transition matrix T is called regular if, for some integer r, all entries of Tr are strictly positive. (0 is not strictly positive).
For example, the matrix
is regular since
A Markov chain process is called regular if its transition matrix is regular.
We state now the main theorem in Markov chain theory:
1. If T is a regular transition matrix, then as n approaches infinity, Tn→S where S is a matrix of the form [v, v,Ö,v] with v being a constant vector.
2. If T is a regular transition matrix of a Markov chain process, and if X is any state vector, then as n approaches infinity, TnX→p, where p is a fixed probability vector (the sum of its entries is 1), all of whose entries are positive.
Consider a Markov chain with a regular transition matrix T, and let S denote the limit of Tn as n approaches infinity, then TnX→SX=p, and therefore the system approaches a fixed state vector p called the steady-state vector of the system. Now since Tn+1=TTn and that both Tn+1 and† Tn approach S, we have S=TS. Note that any column of this matrix equation gives Tp=p. Therefore, the steady-state vector of a regular Markov chain with transition matrix T is the unique probability vector p satisfying Tp=p.
Is there a way to compute the steady-state vector of a regular Markov chain without using the limit? Well, if we can solve Tp=p, for p, then yes! You might have seen this sort of thing before (and certainly will in your first linear algebra course) Recall the definition of an eigenvector and an eigenvalue of a square matrix:
Given a square matrix A, we say that the number λ is an eigenvalue of A if there exists a nonzero vector X satisfying: AX=λX. In this case, we say that X is an eigenvector of A corresponding to the eigenvalue λ.
It is now clear that a steady-state vector of a regular Markov chain is an eigenvector for the transition matrix corresponding to the eigenvalue 1.
Recall that the eigenvalues of a matrix A are the solutions to the equation det(A- λI)=0 where I is the identity matrix of the same size as A. If λ is an eigenvalue of A, then an eigenvector corresponding to λ is a non-zero solution to the homogeneous system (A- λI)X=0. Consequently, there are infinitely many eigenvectors corresponding to a fixed eigenvalue.
Example If you have lived in Ottawa for a while, you must have realized that the weather is a main concern of the population. An unofficial study of the weather in the city in early spring yields the following observations:
1. It is almost impossible to have two nice days in a row
2. If we have a nice day, we just as likely to have snow or rain the next day
3. If we have snow or rain, then we have an even chance to have the same the next day
4. If there is a change from snow or rain, only half of the time is this a change to a nice day.
a. Write the transition matrix to model this system.
b. If it is nice today, what is the probability of being nice after one week?
c. Find the long time behaviour of the weather.
Solution 1) since the weather tomorrow depends only on today, this is a Markov chain process. The transition matrix of this system is
where the letters N, R, S represent Nice, Rain, Snow respectively.
2) If it is nice today, then the initial state-vector is
After seven days (one week), the state-vector would be
So, there is about 20% chance of being nice in one week.
3) Notice first that we are dealing with a regular Markov chain since the transition matrix is regular, so we are sure that the steady-state vector exists. To find it we solve the homogeneous system (T-I)X=0 which has the following coefficient matrix:
Reducing to reduced echelon form gives
The general solution of this system is
So what solution do we choose? Remember that a steady-state vector is in particular a probability vector; that is the sum of its components is 1: 0.5t+t+t=1 gives t=0.4. Thus, the steady-state vector is
In the long term, there is 20% chance of getting a nice day, 40% chance of having a rainy day and 40% chance of having a snowy day.