1
Brad VanHoozer, Jonathan Truex
Markov Chains
Markov Chains are used by scientists in a variety of fields, including physics, biology, sociology, and business. The best way to explain what a Markov chain is by an example:
A taxi company has divided the city into three regions: Northside (N), Downtown (D), and Southside (S). Of the fares the company picks up in N, 50% stay in the region, 20% are taken to D, and 30% go to S. Of the faresthe company picks up in D, 10% go to N, 40% stay in D, and 50% go to S. Finally, of the faresthe company picks up in S, 30% go to N, 30% go to D, and 40% stay in S.
We can represent all of this information with a graph: [Include graph]
We can also represent all of this information with the matrix [write NDS, ‘from’, and ‘to’]
T is called the transition matrix. Any entryTij is the probability that a taxi will start in i and end in j after one fare. An extremely important fact about Markov Chains is that the next state depends only on the current state. An important fact about transition matrices is that they do not change. Let us use probability notation, where, for example, P(ND1) represents the probability that a taxi will start in N and be in D after one fare.
Suppose we want to find the probability that a taxi that starts in D will be in N after two fares. Therefore, we want to find P(DN2). Notice that a taxi can be in any of N, D, or S after just one fare. So, there are three possibilities to consider. The first is if the taxi started in D, was in N after the first fare, and remained in N for the second fare. Thus, find P(DN1)*P(N1N2). From the information above, this is (.1)(.5). What are the probabilities of the other two possibilities?
To find P(DN2), add the three probabilities together to get:
P(DN2) = P(DN1)*P(N1N2) + P(DD1)*P(D1N2) + P(DS1)*P(S1N2)
= (.1)(.5) + (.4)(.1) + (.5)(.3) = .24
Notice this can be succinctly expressed with matrices:
= .24
Notice that this is the second row of T(which represents the probability that a taxi from D will go to N, D, or S) times the first column of T(which represents the probability that a taxi will arrive at N from N, D, or S).
Let[write NDS] represent initial conditions
To find the probability that a taxi will be in N after one fare (given the initial conditions),
P(NN1) + P(DN1) + P(SN1) = (.25)(.50) + (.40)(.10) + (.35)(.30)
= = .27
Find the probability that a taxi will be in S after one fare (given the initial conditions).
Find the probability that a taxi will be in D after one fare (given the initial conditions).
We can combine these operations:
This is distribution vector after one fare.
What will the distribution vector be after 2, 3, …, n, fares?
Will the distribution keep changing every fare?
Calculate the final distribution if the initial conditions are
Does the final state depend on the initial distribution?
We canmathematically explain this independence of the final distribution from the initial one by noticing that, as , Tnbecomes so large that X0 is irrelevant in the calculation .
Consider another application of a Markov chain:
Of all people who buy X-shampoo one month, 90% will buy X-shampoo again next month, 5% will buy Y-shampoo next month, and 5% will change to another brand next month. Of all people who buy Y-shampoo one month, 10% will change to X-shampoo next month, 70% will buy Y-shampoo again next month, and 20% will change to another brand next month. Of all people who buy other brands of shampoo one month, 20% will change to X-shampoo next month and 20% will change to Y-shampoo next month.
We can represent all of this information with a graph: [Include graph]
Represent all of this information with atransition matrix:
T is called the transition matrix. Tij is the probability that someone will start using shampoo i and end using shampoo j after one month. Let us use probability notation, where, for example, P(ND1) represents the probability that a taxi will start in N and be in D after one fare. Let us use probability notation, where, for example, P(XY1) represents the probability that someone will start usingX-shampoo and end using Y-shampoo after one month.
Suppose the current market share is
To find the percentage of people who will use X-shampoo next month,
(.4)(.9) + (.3)(.1) + (.3)(.2) = .45
Notice this can be succinctly expressed with matrices:
= M0T
Find the percentage of people who will use Y-shampoo next month.
Find the percentage of people who will use other shampoo next month.
We can combine these operations:
This is the distribution vector after one month.
What will the distribution vector be after 2, 3, …, k, months?
Will the monthly distribution keep changing every month?
Calculate the final distribution if the current market share is
Does the final state depend on the initial distribution?
We can mathematically explain this independence of the final distribution from the initial one by noticing that, as , Tnbecomes so large that X0 is irrelevant in the calculation .
In College Town, Pizza Company gets a lot of business. They get so many calls each night that they have to operate three kitchens to fill all the orders. They decided to spread the kitchens out so that each one is near one of the housing sections of the university. Since the same people own all three branches of Pizza Company, they only hired one set of delivery drivers to serve all three kitchens. After a driver makes a delivery, he or she goes to the nearest kitchen to pick up the next order. Therefore, the location of a delivery person's next order depends only on his or her present location. The kitchens are logically named according to their area of campus. Of the calls to kitchen A, 30% are delivered in area A, 30% go to area B, and 40% go to area C. Of the orders placed at kitchen B, 40% go to area A, 40% go to area B, and 20% go to area C. Of the calls to kitchen C, 50% go to area A, 30% go to area B, and 20 go to area C. The picture below depicts the situation.
Create a 3 x 3 matrix using this data.
This matrix is a transition matrix and can be used to answer problems regarding the data.
We will assume that it takes each delivery person the same amount of time to make one delivery. Therefore, after one delivery, of the cars that began in A, 30% will again be in A, 30% will be in B, and 40% will be in C. Since we only have three locations, and each delivery person must be somewhere after each delivery, the probability that a car is in one of those three locations must be one. This is why eachrow 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 transition matrix does not change during the time we are observing.
If you begin at kitchen C, what is the probability that you will be in area B after 2 deliveries? This gives us 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. This gives us (.5)(.3) + (.3)(.4) + (.2)(.3) = .33 or a 33% chance we will be in kitchen B after two deliveries. If we begin at kitchen B what is the probability we will end in kitchen C after two deliveries?
Do you know what the probability matrix would look like that describes where a car would be after exactly 2 deliveries? What about 3, 4, or 5 deliveries? Can you predict the probability matrix for the cars after a night of deliveries?
To do this it is very simple. Instead of writing out long equations you simply have to multiply the transition matrix. If you wanted to know the probability after two deliveries, simply multiply the transition matrix by itself. After three deliveries multiply the transition matrix by itself three times.
Now find the rest of the matrices for 3,4, and 5 deliveries.
Find the matrix after 10 deliveries. What do you notice about these matrices?
Project AMP A Quesada Director Project AMP