Chapter 6: Markov Chains

6.1 What is a Markov Chain?

In many real-world situations (for example, values of stocks over a period of time, weather patterns from day to day, results of congressional elections over a period of elections, and so forth) analysts would like to be able to predict the future, both in the short term and in the long term. In this chapter you will see how probability and matrix theory can be combined to analyze the short and long term behavior of certain kinds of phenomena which can be modeled as Markov Chains. Example 6.1. Johns Truck Rental does business in North Carolina, South Carolina and Virginia. As with most rental agencies, customers may return the vehicle that they have rented at any of the companys franchises throughout the three state area. In order to keep track of the movement of its vehicles, the company has accumulated the following data: 50% of the trucks rented in North Carolina are returned to North Carolina locations, 30% are dropped off in Virginia, and 20% in South Carolina. Of those rented in South Carolina, 40% are returned to South Carolina, 40% are returned in North Carolina, and 20% in Virginia. Of trucks rented in Virginia, 50% are returned in Virginia, 40% in North Carolina, and 10% in South Carolina. Here are some additional things that the company might like to know. Question 1: If a truck is presently in North Carolina, what is the probability that it will again be in North Carolina after it has been rented twice? Question 2: If a particular truck is now in Virginia, what is the probability that it will be back in North Carolina next July 4? Question 3: If a new truck is put in service this week, what fraction of the life of that truck will it spend in each of the three states? Question 4: All routine servicing of vehicles is performed at the franchises in North Carolina. If a truck in Virginia needs servicing, on the average how many more times will it be rented before it is deposited in North Carolina and can be serviced? The scenario described in Example 6.1 is a special case of a Markov Chain. The three states (North Carolina, South Carolina, and Virginia) represent the possible locations of a truck at any point in time. The data that is given about how the trucks pass back and forth from one state to another are called transition probabilities. By the end of this chapter you will know how to answer each of the four questions posed above, and

210

Chapter 6: Markov Chains

you will know how to model lots of different kinds of situations as a Markov Chain. So what is a Markov Chain anyway? Suppose a series of experiments is run and suppose each time the experiment is conducted, the set of possible outcomes or states remains the same. Moreover, each time the experiment is repeated, the probability a given outcome occurs depends (at most) on the outcome of the previous trial which was just run. Such a series of experiments constitutes a Markov Chain. In Example 6.1 the states are literally states: N.C., S.C., and VA. The probability of a truck landing in a state depends on where the truck was rented, that is, on which state it was in previously. Example 6.2. In working with a particular gene for fruit flies, geneticists classify an individual fruit fly as dominant, hybrid or recessive. In running an experiment, an individual fruit fly is crossed with a hybrid, then the offspring is crossed with a hybrid and so forth. The offspring in each generation are recorded as dominant, hybrid or recessive. The probabilities the offspring are dominant, hybrid or recessive depends only on the type of fruit fly the hybrid is crossed with rather than the genetic makeup of previous generations. In this example the states are dominant, hybrid, and recessive. The probabilities involved will be considered a little later in this section. Example 6.3. A psychologist runs a series of experiments with a mouse in a maze containing 3 rooms. (See the diagram below.) Each hour the doors are opened briefly. 50% of the time the mouse chooses to leave the room it is in and go to an adjoining room. If it does leave the room it is in, it is equally likely to choose any of the available doors. So if the mouse is in room 1, it either stays in room 1 (probability .5) or it goes to room 3 (probability .5). Similarly if the mouse is in room 2, it can stay in room 2 (probability .5) or go to room 3 (probability .5). But when the mouse is in room 3, there is a .5 probability it will stay in room 3, a .25 probability it will go to room 1, and a .25 probability it will go to room 2. The three rooms are the 3 states in this example.

1 2
Example 6.4. Asthmatics are questioned every 8 hours to determine if their condition is excellent, good, fair, or poor. These 4 possible conditions of the patient constitute the 4 states for a Markov Chain. Example 6.5. Toss a coin repeatedly. The set of possible outcomes on each toss is {H, T}. This is a 2-state Markov Chain. No matter which outcome occurs on one toss, the probabilities for each of the two states (heads and tails) is .5 on the next toss.

Section 6.1: What is a Markov Chain?

211

Example 6.6. Kathy and Melissa are playing a game and gambling on the outcome. Kathy has $3 and Melissa has $2. Each time the game is played, the winner receives $1 from the loser. Assume the game is fair and that the girls quit playing when either of them runs out of money. If the states are the amount of money Kathy has at any time then this is a 6-state Markov Chain (since at any time Kathy has either $0, $1, $2, $3, $4, or $5). The short term aspects of Markov Chains will be considered in this section and the next one and the question of whats likely to happen in the long run will be looked at in the last two sections. For instance, the first of the 4 questions posed in Example 6.1 is a short-term question. As another illustration, in Example 6.6 Kathy might want to know what the probability is that she hasnt lost any money after three games. Youll see how to answer both of these questions in this section. She probably also would like to know what the probability is that she will eventually wind up with $5. How to answer that question will be taken up in Section 6.4. Before going further with Markov Chains its necessary to establish the language that will be used. Although its assumed the set of outcomes or states is finite and remains the same from one trial to the next, the things that may constitute the states of a Markov Chain can vary greatly from one problem to another. For instance, in Example 6.2, the states are dominant, hybrid and recessive. In Example 6.3, the states are the rooms, i.e. room 1, room 2 and room 3. In Example 6.4, the states are excellent, good, fair, and poor, while in Example 6.5 the states are H and T. In Example 6.6 the states are $0, $1, $2, $3, $4, and $5. Its also necessary to know the probabilities of moving from a given state to another state on the next trial of the experiment. These probabilities are called transition probabilities. In the case of Example 6.3, theres enough information so the transition probabilities can be represented using tree diagrams, as is done below.
room 1
1/2

room 2
0

room 3
1/2

room 1
0

room 2
1/2

room 3
1/2

room 1
1/4

room 2
1/4

room 3
1/2

room 1

room 2

room 3

To make it easier to discuss transition probabilities and do computations with them, its helpful to number the states in the experiment as 1, 2, 3 and so forth. For instance in Example 6.2, dominant could be called state 1, hybrid state 2 and recessive state 3. In Example 6.3, the obvious thing to do is number each state the same number as the corresponding room. Once the states are numbered the transition probability can then be defined.

212

Chapter 6: Markov Chains

Definition: Transition Probability The transition probability pij is the probability of moving from state i (the current state) to the state j on the next trial.

You should note that the first subscript (i) represents the current state and the second subscript (j) represents the state into which the Markov Chain is moving. Thus in Example 6.3, the transition probability p32 represents the probability of moving from state 3 (in this instance room 3) to state 2 (room 2) when the bell is rung. As can be seen from the first tree diagram, p32 = 1/4. In fact, looking at the tree diagrams its clear that: p11 = 1/2 p12 = 0 p13 = 1/2 p23 =1/2 p33 = 1/2

p21 = 0 p22 = 1/2 p31 = 1/4

p32 = 1/4

Its convenient to organize these transition probabilities in a matrix which is called the transition matrix. Thus the transition matrix for Example 6.3 is
next state 1 2 3 1/2 0 1/2 0 1/2 1/2 1/4 1/4 1/2

current state

1 2 3

The transition matrix for Example 6.5 is

next state 1 2 1/2 1/2 1/2 1/2

current state

1 2

where state 1 is getting a head and state 2 is getting a tail. In general the states for a Markov Chain are either numbered or, as often happens, are simply labeled by some convenient name. For instance, in Example 6.6, there are six states which could be called states 1-6 or could be labeled $0, $1, $2, $3, $4, $5 depending on how much money Kathy has. Then the transition matrix could be written
$0 next state $1 $2 $3 $4 $5

Section 6.1: What is a Markov Chain?

213

$0 $1 $2 current state $3 $4 $5

1 1/2 0 0 0 0

0 0 1/2 0 0 0

0 1/2 0 1/2 0 0

0 0 1/2 0 1/2 0

0 0 0 1/2 0 0

0 0 0 0 1/2 1

In order to determine the transition matrices for Example 6.2 or Example 6.4 more information is needed because the examples as stated do not contain enough information to determine the transition probabilities. For instance, in Example 6.2, using the rules of inheritance as determined by the monk Gregor Mendel (excluding the possibility of mutations), the offspring of a dominant individual crossed with a hybrid are dominant 50% of the time and hybrid the other 50%. The offspring of a hybrid crossed with a hybrid are dominant 25%, hybrid 50% and recessive 25%, while the offspring of a recessive crossed with a hybrid are hybrid 50% and recessive 50%. So if the states are numbered as follows: state 1 = dominant state 2 = hybrid state 3 = recessive then the transition matrix for Example 6.2 would be 1 T =2 3 1 2 3 .5 .5 0 .25 .5 .25 . 0 .5 .5

However the transition matrix for Example 6.4 cant be determined without having access to data on the group of asthmatics in the study.

Definition: Transition Matrix

If a Markov Chain has n states, state 1, state 2, . . . , state n, then the transition matrix for the Markov Chain is an n n matrix T which has as entries the transition probabilities pij, i = 1, 2, . . . , n, j = 1, 2, . . . , n.

Notice that transition matrix T for a Markov Chain has the following properties: 1. T is square 2. 0 pij 1, i = 1, 2, . . . ,n, j = 1, 2, . . . , n 3. the sum of the entries in each row of T is 1. Property 1 is clearly true and its easy to see that property 2 is true since the entries

214

Chapter 6: Markov Chains

in T are probabilities. Property 3 is true since each row of T represents a possible starting state for the Markov Chain and the entries are the individual probabilities for all possible outcomes for the experiment. Those probabilities must sum to one since the probability of the sample space is always one. Moreover, for any matrix it is possible to determine whether or not it is a transition matrix for a Markov Chain based on whether or not it satisfies the above properties. Example 6.7. Which of the following matrices are transition matrices? 1 0 0 0 (a) 1/2 1/3 0 1/6 0 0 1 0 0 2 -1 (c) 1/2 1/2 0 1/3 2/3 0 1/2 1/4 1/4 (b) 0 2/3 1/3 3/4 0 1/4 1/2 2/3 (d) 1/2 1/3

Solution: (b) is the only transition matrix. (a) is not square. In (c), p12 = 2 which is greater than 1 (and p13 = 1 < 0), and in (d) the sum of row 1 is 1/2 + 2/3 = 7/6 1. The key to working with Markov Chain problems is finding the transition matrix since virtually all the questions youll be asked about a Markov Chain can be answered by doing computations using its transition matrix. Thus, assuming you have decided (or have been told) that an experiment can be modeled with a Markov Chain, the following procedure summarizes how to find the transition matrix: 1. Decide what the states of the Markov Chain are and number or label them. 2. Determine each transition probability, pij. 3. Arrange the transition probabilities in a matrix labeling the rows and columns with the appropriate numbers or names for the states. Now lets consider the mouse in a maze example (Example 6.3) further. Suppose the mouse is in room 1 and you want to know the probability it will be in room 1 after it has been given two opportunities to move. How could you determine that probability? One easy way would be by using tree diagrams.

Section 6.1: What is a Markov Chain?

room 1
1/2

215
room 3
1/2

room 2
0

room 3
1/2

room 1
0

room 2
1/2

room 1
1/4

room 2
1/4

room 3
1/2

room 1
0 1/2

room 2

room 3

1/2

room 1

Then the probability the mouse winds up in room 1 after 2 steps given that it started in room 1 is 1/2 1/2 + 0 0 + 1/2 1/4 = 3/8. This probability is denoted by p(2) 11 . Similarly, if you want the probability the mouse is in room 3 after 2 steps if it started in room 1 (which is denoted by p(2) 13 ), you can use the same tree diagram to get p(2) 13 = 1/2 1/2 + 0 1/2 + 1/2 1/2 = 1/2. You can also compute p(2) 12 = 1/2 0 + 0 1/2 + 1/2 1/4 = 1/8. But to compute the other 2 step transition probabilities, some more tree diagrams would have to be drawn, one for starting in state 2 and one for starting in state 3 and then computations similar to the ones done above would have to be done. As you can see, that would be quite tedious and, if you wanted to find transition probabilities for 3 or 4 steps later, it would quickly become painful. Keeping that in mind, the following computation is very interesting. If T is the transition matrix for the mouse problem, then TT= T2 1/2 0 1/2 1/2 0 1/2 = 0 1/2 1/2 0 1/2 1/2 1/4 1/4 1/2 1/4 1/4 1/2 3/8 1/8 1/2 = 1/8 3/8 1/2 . 1/4 1/4 1/2
(2) Not only do the entries in the first row have the same values as were found for p(2) 11 , p 12 2 and p(2) 13 respectively but the computations involved in finding the entries for T are precisely the same as those done to find the 2-step transition probabilities. For instance, you saw that

216

Chapter 6: Markov Chains p(2) 11 = 1/2 1/2 + 0 0 + 1/2 1/4.

But that computation is exactly what is done when the first row of T is multiplied by the first column of T to find the entry in the first row and first column of T2. Similarly, the computation done to find p(2) 12 is the same as the one done to find the entry in the first row and second column of T2. Its easily verified using the tree diagrams that p(2) ij has the same value as the entry in the ith row and jth column of T2, where i = 1, 2, 3 and j = 1, 2, 3. So, after this, rather than compute the 2-step transition probabilities by doing all the tree diagrams, you can simply compute T2. Since T 2 = T (2), the easy way to compute the 2-step transition probabilities is to multiply the transition matrix times itself to find T2.

Example 6.6 (continued). If Kathy has $3 what is the probability she has at least $3 after two more games? Solution:
1 1/2 0 = 0 0 0 0 0 1/2 0 0 0 0 1/2 0 1/2 0 0 0 0 1/2 0 1/2 0 $0 $0 $1 $2 $3 $4 $5 1 1/2 1/4 0 0 0 0 0 0 1/2 0 0 $1 0 1/4 0 1/4 0 0 0 0 0 0 1/2 1

T2

0 0 1/2 0 1/4 0

1 1/2 0 0 0 0 $3 0 1/4 0 1/2 0 0 $4

0 0 1/2 0 0 0 $5

0 1/2 0 1/2 0 0

0 0 1/2 0 1/2 0

0 0 0 1/2 0 0

0 0 0 0 1/2 1

$2

0 0 1/4 0 1/4 0

0 0 0 1/4 1/2 1

(2) (2) Thus p(2) 44 = 1/2, p 45 = 0 and p 46 = 1/4 so the probability Kathy has at least $3 after two games given she started with $3 is 3/4. (The subscripts may be confusing here. You should note that $3 is state 4, $4 is state 5, and so forth.)

Problems

Section 6.1: What is a Markov Chain? 1.

217

Determine which of the following matrices are transition matrices. If a matrix is not a transition matrix explain why not. 0 1 (a) 3/4 1/4 1 -1/2 1/2 (d) 0 1 0 2/3 1/3 0 1/2 1 (b) 1/2 0 .2 .5 .3 (e) .1 .7 .2 .7 .3 0 1/2 1/3 1/6 (c) 1/4 1/12 2/3

2.

0 x 1/3 Find the values of x, y and z in order for 0 0 y to be a transition matrix. 1/3 1/4 z 1/3 2/3 (2) (3) If T = 3/4 1/4 , find p(2) 12 , p 21 , and p 22 using (a) tree diagrams (b) matrix multiplication 0 1 (2) (3) If T = 3/4 1/4 find p(2) 12 , p 21 , and p 22 . .2 .5 .3 If T = .1 .7 .2 find p(2) 13 . .7 .3 0 Is the 6 6 identity matrix a transition matrix? The Chancellor of NCSU tells a friend A his decision on whether or not to accept a job at another university. A then tells B what the decision is, B tells C, etc., each time to a new person. Suppose each time the decision is relayed, a yes is changed to a no with probability .05 and a no is changed to a yes with probability .08. Let state 1 be the reply yes given at that time and state 2 be the reply no given at that time. (a) Find the transition matrix T. (b) If the Chancellor tells A yes he will accept the job, what is the probability C is told he will not accept the job? A mouse is put in the maze below. Each time period the doors in the maze are opened and it is allowed to move to another room. 50% of the time it decides to stay where it is but if it moves to another room, it chooses a door at random.

3.

4.

5. 6. 7.

8.

218

Chapter 6: Markov Chains

1 2

4 3

(a) Find the transition matrix T. (b) If the mouse is now in room 1, what is the probability it will be in room 2 after three time periods? 9. Two bowls, I and II, each contain 2 balls. Of the four balls, 2 are red and 2 are green. Each time period a ball is selected at random from each bowl. The ball from Bowl I is put in Bowl II and the ball from Bowl II is put in Bowl I. Take as state the number of red balls in Bowl I. (a) Find the transition matrix T for this Markov Chain. (b) Find T2 and T3.

10. Suppose in Exercise 9, Bowl I has three balls and Bowl II has two balls and of the five balls, three are red and two are green. Otherwise the situation is the same. Answer questions (a) and (b) for this Markov Chain. 11. John finds a bill on his desk. He either puts it on his wifes desk to be dealt with the next day or he leaves it on his own desk for the next day or he pays it immediately with probabilities .3, .6 and .1 respectively. Similarly, his wife Mary can keep it until the next day, put it on Johns desk or pay it immediately with probabilities .5, .2, and .3 respectively. Assume this is a Markov Chain process and set up the transition matrix. Find the probability a bill now on Johns desk will be paid within two days. 12. When Grace eats her evening meal she has tea, beer, wine or water. She only has one beverage with her meal. She never has alcoholic beverages twice in a row but if she has beer or wine one time she is twice as likely to have tea as water the next time. If she has tea or water one evening she has an alcoholic beverage the next time and is just as likely to choose beer as wine. Set up the transition matrix for this Markov Chain. 13. A baby crawls from room to room in a house described by the following diagram. Each time he moves from a room, he chooses a door at random. Assume this is a Markov Chain process and set up the transition matrix.

Section 6.1: What is a Markov Chain?

219

1 4 3
14. A junior college has freshmen and sophomore students. 80% of the freshmen successfully complete their year and go on to become sophomores, 10% drop out and 10% fail and must repeat their freshman year. Among the sophomores 85% graduate, 5% drop out and 10% fail and must repeat their sophomore year. Set up the transition matrix and find the probability an entering freshman graduates within 3 years. 15. The victims of a certain disease being treated at Wake Medical Center are classified annually as follows: cured, in temporary remission, sick, or dead from the disease. Once a victim is cured, he is permanently immune. Each year, those in remission get sick again with probability 1/4, are cured with probability 1/2, and stay in remission with probability 1/4. Those who are sick are cured, go into remission, or die from the disease with probability 1/3 each. (a) Find the transition matrix. (b) If a victim is now in remission, find the probability he is still alive in two years. 16. Set up the transition matrix for Example 6.1 and answer question 1.

6.2 Multi-Step Transition Probabilities and Distribution Vectors

You saw in the last section that the 2-step transition probabilities for a Markov Chain with transition matrix T can be found by computing T2. Similarly, the 3-step transition probabilities can be determined by finding T3 and, in general, Tk gives the kstep transition probabilities. This result and the notation used are summarized as:

Multi-step transition probabilities

If k is a positive integer, the k-step transition probability p(k) ij is the probability a Markov Chain is in state j after k steps given it started in state i. If Tk is computed then p(k) ij is the entry in the k ith row and jth column of T .

220

Chapter 6: Markov Chains

Example 6.8. A student has a class that meets on Monday, Wednesday and Friday. If he goes to class on one day, he goes to the next class with probability 1/2. If he doesnt go to class that day, he goes to the next class with probability 3/4. Set up the matrix T of transition probabilities and find the probability (a) he goes to class on Friday, if he didnt go to class the preceding Monday. (b) If he goes to class on Monday, find the probability hell show up for class the following Monday. Solution: There are 2 states in this problem: going to class, which will be numbered state 1, and not going to class, which will be numbered state 2. The transition matrix is then T=
1 2

1 2 1/2 1/2 3/4 1/4

(3) The answer to (a) is obtained by finding p(2) 21 and the answer to (b) by finding p 11 .

So its necessary to compute T2 and T3. 5/8 3/8 T2 = 9/16 7/16

(3) So p(2) 21 = 9/16 and p 11 = 19/32.

and

19/32 13/32 T3 = 39/64 25/64

You may have noticed that T2 and T3 both turn out to be transition matrices. In fact, if you think about it, it makes perfectly good sense that Tk, the matrix of k-step transition probabilities, ought to be a transition matrix. If T is a square matrix then its obvious that Tk is also a square matrix so property 1 is satisfied. The entries in Tk are probabilities, so property 2 (which required that the entries have values between 0 and 1) is satisfied. Also, for any row the sum of the entries in that row must be 1 since the entries in that row are the probabilities that, starting in the state represented by that row, the experiment winds up in state 1, state 2, ... , state n, respectively after k steps. Since these states are all the possible outcomes, the sum of the probabilities must be 1. So property 3 is satisfied. You have seen that if you know the state the system begins in, you can determine the probability the system will subsequently be in state j, for any j, j = 1,2, . . ., n, after any finite number of trials by looking at the appropriate entry of the right power of the transition matrix. What if you dont know the state in which the system begins? Its still possible to determine the probabilities if you know the initial probability distribution which is summarized in a row vector called the initial probability distribution vector.

Section 6.2: Multi-step Transition Probabilities and Distribution Vectors

221

Initial probability distribution vector

The initial probability distribution vector is p0 = (p1, p2, . . . ,pn) where pi = probability the system is in state i initially.

The next example shows how the initial probability distribution can be used: Example 6.8 (continued). Suppose the student in Example 6.8 attends the first class with probability .9. (a) What is the probability he attends the next class? (b) What is the probability he attends class on the third day? Solution: As before a tree diagram can be used to answer this question. Lets extend the tree diagram to the third day so both questions (a) and (b) can be answered. The probability he attends the first class is .9 but after that the Markov Chain process takes over so the tree diagram for the problem is:
attends doesnt 1/2 1/2 attends 3/4 doesnt 1/4 attends 1/2 attends 3/4 doesnt attend .9 doesnt 1/2 attends doesnt 3/4 1/4

attends 1/2 attends

doesnt attend 1/2

doesnt attend 1/4

.1

The answer to (a) is (.9)(1/2) + (.1)(3/4) = 21/40, and the answer to (b) is (.9)(1/2)(1/2) + (.9)(1/2)(3/4) + (.1)(3/4)(1/2) + (.1)(1/4)(3/4) = 99/160. However, its also possible to use matrix methods to solve this problem. Since the initial distribution vector is p0 = (.9 .1),the results obtained by using the tree diagram can easily be computed as: 1/2 1/2 p0T = (.9 .1) 3/4 1/4 = (21/40 19/40) = p1. where p1 is the distribution vector whose entries are the probabilities the student goes to

222

Chapter 6: Markov Chains

class or doesnt go to class on the second day. Similarly, to find the probabilities he does or doesnt attend class on the third day compute p2 = p0T2 = (p0T)T = p1T 1/2 1/2 = (21/40 19/40) 3/4 1/4 = (99/160 61/160). The first entry in p2 is the answer to (b). In general, to determine the probability the system is in state i after k steps, knowing the initial distribution vector, you need to find the kth distribution vector pk = p0Tk and take the ith entry in that vector. It should be noted that distribution vectors have the properties that the entries are all nonnegative and the sum of the entries are 1. Thats because the entries are again probabilities and represent all possible outcomes for the experiment. Now lets look at a few more examples. Example 6.2 (continued): In working with a particular gene for fruit flies, geneticists classify an individual fruit fly as dominant, hybrid or recessive. In running an experiment, an individual fruit fly is crossed with a hybrid, then the offspring is crossed with a hybrid and so forth. The offspring in each generation are recorded as dominant, hybrid or recessive. (a) What is the probability the third generation offspring is dominant given the first generation offspring is recessive? (b) If the population of fruit flies initially is 20% dominant, 50% hybrid and 30% recessive, what percentage of the population is dominant after 3 generations? Solution: As was seen earlier, the transition matrix for this problem is
1 2 3 1 2 3

T=

.5 .5 0 .25 .5 .25 0 .5 .5

where states 1, 2, and 3 are dominant, hybrid and recessive respectively. To answer (a) its necessary to compute T2 and take the entry in the first row and third column, i.e. find p(2) 13 . Thus T2 So p(2) 13 = 1/8. 1/2 1/2 0 1/2 1/2 0 3/8 1/2 1/8 1/4 1/2 1/4 1/4 1/2 1/4 = = 1/4 1/2 1/4 . 0 1/2 1/2 0 1/2 1/2 1/8 1/2 3/8

Section 6.2: Multi-step Transition Probabilities and Distribution Vectors The answer to (b) is found by computing p0T3, where p0 = (.2 .5 .3). Thus, 1/2 1/2 0 3 5/16 1/2 3/16 3 1/4 1/2 1/4 p0T = (.2 .5 .3 ) = (.2 .5 .3) 1/4 1/2 1/4 0 1/2 1/2 3/16 1/2 5/16 = (39/160 1/2 So the answer to (b) is 39/160. 41/160).

223

Example 6.9. Customers in a certain city are continually switching the brand of soap they buy. If a customer is now using brand A, the probability he will use brand A next week is .5, that he switches to brand B is .2 and that he switches to brand C is .3. If he now uses brand B, the probability he uses B next week is .6 and the probability that he switches to C is .4 . If he now uses brand C, the probability he uses C next week is .4, that he switches to A is .2 and to B is .4. Assume the process is a Markov Chain. (a) Find the probability a customer now using brand A will be using brand B in two weeks. (b) If the percentage of customers now using brand A is 30%, the percentage using brand B is 20% and the percentage using brand C is 50%, find the percentage of customers using brand C in three weeks. (c) Find the probability a customer now using brand A will be using brand B in 6 weeks. Solution: Let the states be using brand A, using brand B, and using brand C. Then the transition matrix T is
A B C

T=

A .5 0 .2

B .2 .6 .4

C .3 .4 .4

where the order of the states is as listed above.

2 (a) The answer to this question is p(2) 12 , so lets find T .

.5 .2 .3 2 .31 .34 .35 T2 = 0 .6 .4 = .08 .52 .40 .2 .4 .4 .18 .44 .38 Thus, p(2) 12 = .34. (b) Now, p0 = (.3 .2 .5 ) and, omitting the computations involved in finding p0T3, it turns out that: p0T3 = (.1745 .4454 .3801). So in three weeks the percentage of customers using brand C is about 38%.

224

Chapter 6: Markov Chains

6 (c) Here p(6) 12 is needed, so computing T gives

T6

.160599 .456266 .383135 = .150632 .464048 .38532 . .155002 .460636 .384362

Thus the probability a customer now using brand A will be using brand B in 6 weeks is p(6) 12 = .456266.

Problems
In Exercises 1-4, determine which of the vectors below are probability distribution vectors. 1. 3. [1/2 0 1/2] [1/2 -1/3 2/3 1/6] 2. 4. [0 0 1 0] [1/3 1/2 1/3]

In Exercises 5-8, if p0 and T are as given, find the probability distribution after 2 steps using (a) tree diagrams, (b) matrix multiplication 5. p0 = (.8 .2) .4 .6 T = .3 .7 1/3 2/3 0 T = 0 0 1 1/2 1/6 1/3 6. p0 = (1/3 2/3) 1/2 1/2 T = 3/4 1/4 1/4 1/4 1/2 T = 1 0 0 1/2 0 1/2

7.

p0 = (0 1/2 1/2)

8.

p0 = (1 0 0)

9.

p11 p12 If T = p21 p22 is a transition matrix and p0 = (p1 p2) is a distribution vector, show that p0T is a probability distribution vector.

10. A mouse is put in the maze below. Each time period the doors in the maze are opened and it is allowed to move to another room. 50% of the time it decides to stay where it is but if it moves to another room, it chooses a door at random.

1 2

4 3

If p0 = (1/4 1/2 1/8 1/8), find the probability distribution after 2 steps.

Section 6.2: Multi-step Transition Probabilities and Distribution Vectors

225

11. Two bowls, I and II, each contain 2 balls. Of the four balls, 2 are red and 2 are green. Each time period a ball is selected at random from each bowl. The ball from Bowl I is put in Bowl II and the ball from Bowl II is put in Bowl I. Take as state the number of red balls in Bowl I. If Bowl I contains 1 red and 1 green ball initially, find p1, p2, and p3 and interpret the results. 12. Suppose in the above problem, Bowl I has three balls and Bowl II has two balls and of the five balls, three are red and two are green. Otherwise the situation is the same. If Bowl I contains 2 red and 1 green ball initially, find p1, p2, and p3 and interpret the results. 13. A bead is located at one of the three points A, B or C on the wire drawn below. Each time period the bead moves clockwise to an adjacent point with probability 1/2, counterclockwise to an adjacent point with probability 1/3 or stays put with probability 1/6. (a) Set up the transition matrix T. (b) Find T2 and T3. (c) If the bead is initially at point A, find p1, p2, and p3.

C
14. A problem in the last section describes the following situation: John finds a bill on his desk. He either puts it on his wifes desk to be dealt with the next day or he leaves it on his own desk for the next day or he pays it immediately with probabilities .3, .6 and .1 respectively. Similarly, his wife Mary can keep it until the next day, put it on Johns desk or pay it immediately with probabilities .5, .2, and .3 respectively. If the bill is on Johns desk on Monday, what is the probability it will be paid by Friday? [Use the idea of an initial probability distribution vector in your solution.] 15. Nancy buys groceries once a week and during her shopping trip she always buys exactly one bag of candy, choosing from Jolly Ranchers, chocolate-covered mints and Skittles. If she chooses Jolly Ranchers one week, the next week she is equally likely to choose any of the three types of candy. If she picks chocolate-covered mints one week, she doesnt pick them the next week but is equally likely to choose Jolly Ranchers as Skittles. If she chooses Skittles one week, the next week she picks chocolate-covered minst half the time and otherwise is equally likely to choose Jolly Ranchers as Skittles.

226

Chapter 6: Markov Chains

If she chooses chocolate-covered mints one week, use the idea of an initial probability distribution vector to find the probability she buys Skittles 3 weeks later.

6.3 Regular Markov Chains

This section and the next one deals with the long term behavior of Markov Chains. The last section showed that k-step transition probabilities for a Markov Chain with transition matrix T can be found by simply computing Tk and looking at the appropriate entries of Tk. If you had a distribution vector p0 and wanted to find the kth distribution vector pk, you computed p0Tk. Determining long term behavior means finding, at least approximately, the entries of Tk and pk for k very large. However, while its possible to find Tk and pk for any k as long as its known what the value of k is, in practice it can be relatively difficult if the value of k is large. For example, suppose you wanted to find p25, where .8 .2 T = .4 .6 and p0 = (.3 .7) . Even though T is only a 2 2 matrix, doing the computations by hand is quite unpleasant. However, in many situations the problem isnt so much one of what is p8, or what is pk but rather is the problem of approximately what is pk, when k is large. In fact, if an approximation of Tk can be obtained, thats enough, since pk can then be found by computing pk = p0Tk For the T above, lets see if an approximation of Tk, for large k, can be found by computing various powers of T. .72 .28 T2 = .56 .44 .666672259 .333327741 T12 = .6666554819 .3333445181 T6
=

.668032 .331968 .663936 .336064

.6666670246 .3333329754 T15 = .6666659508 .3333340492

It looks like the matrices T12 and T15 can be approximated by a matrix S where 2/3 1/3 S = 2/3 1/3 . Note that the rows of S are identical. Moreover, when the following distribution vectors are computed, p2 = p0T2 = (.608
.392)

Section 6.3: Regular Markov Chains p6 = p0T6 = (.6651648 .3348352) p12 = p0T12 = (.666660515 .333339485) p15 = p0T15 = (.666666273 .333333727)

227

its easy to see that these vectors are approaching the vector p0S = s = (2/3 1/3) where s is a vector that has the same entries as a row in the matrix S. Now for this T it was possible to find a matrix S so that S Tk, for large k, (the symbol means is approximately equal to). However, you might ask if theres something special about this particular matrix T. It turns out that if T is a regular transition matrix then a matrix can always be found which approximates Tk. A regular transition matrix is defined as:

Definition: Regular transition matrix

T is a regular transition matrix if T is a transition matrix and if there is some power of T, say Tm, so that Tm has all positive entries.

The following theorem then describes what the above observations were all about.

Theorem
If T is a regular transition matrix then there is a matrix S, called the steady-state matrix, so that Tk S if k is large (The symbol means is approximately equal to.)

You might then ask: Are all transition matrices regular? Consider the following examples. 2/3 1/3 Example 6.10. T = 4/9 5/9

228

Chapter 6: Markov Chains

T is clearly regular, since all its entries are positive. (In this case, m = 1 in the definition.) 0 1 Example 6.11. T = 1/3 2/3 T is regular, since the entries of T2 are all positive. 1 0 0 Example 6.12. T = 0 1 0 0 0 1 T is not regular, since Tm = T for every m and T clearly has zero entries. In the above examples it was simple to find out whether or not the matrices were regular since it wasnt necessary to compute many powers of T to either get a matrix that had all positive entries or to see that all powers of T would contain a zero entry. But it can get rather messy if you have to compute several powers of T or if T is large or if T has difficult numbers to work with. An easier way to handle the problem of determining if T is regular is discussed at the beginning of the exercise set at the end of this section. In any case, once you have determined whether or not a transition matrix is regular and thus know it has a steady-state matrix, how do you find that steady-state matrix? You certainly dont want to have to compute Tk for large k and then eyeball S as was done above. That really defeats the purpose. Fortunately, the following theorem gives a simple way to compute S.

Theorem
Let T be a regular transition matrix. Then the following statements are true, where S is the steady-state matrix for T. (a) The rows of the matrix S are identical. Thus each row of S is a row vector (which is denoted by s and called the steady-state vector). Moreover, S is a transition matrix so the entries of s are nonnegative and the sum of the entries of s is 1. (c) If p0 is an initial probability distribution vector, then p0Tk approaches s if k is large and p0S = s. (d) To find s, you need to solve the equation sT = s and use the fact that the sum of the entries of s is 1.

Example 6.8 (continued). A student has a class that meets on Monday, Wednesday

Section 6.3: Regular Markov Chains

229

and Friday. If he goes to class on one day, he goes to the next class with probability 1/2. If he doesnt go to class that day, he goes to the next class with probability 3/4. In the long run, what fraction of the time does he goes to class? Solution: You saw earlier that the transition matrix for this problem is 1/2 1/2 T = 3/4 1/4 where state 1 represents attends class and state 2 represents doesnt attend class. To answer the question in this problem, you need to find the steady-state vector s which is done by solving the matrix equation sT = s, where s = (x y) together with x + y = 1. 1/2 1/2 Now, sT = s implies (x y) 3/4 1/4 = (x y), which gives the equations 1/2 x + 3/4 y = x 1/2 x + 1/4 y = y which simplify to 1/2 x + 3/4 y = 0 1/2 x 3/4 y = 0. The two equations have the same solution set, x = 3/2 y. Substituting this back into the equation x + y = 1 gives 3/2 y + y = 1 or y = 2/5. Thus, x = 3/5 and s = (3/5, 2/5). Therefore, in the long run the student attends class 3/5 of the time (and doesnt attend class 2/5 of the time). Example 6.13. Bob, Alice and Carol are playing frisbee. Bob always throws to Alice and Alice always throws to Carol. Carol throws to Bob 2/3 of the time and to Alice 1/3 of the time. In the long run what percentage of the time do each of the players have the frisbee? Solution: Letting the states be A, B, and C where state A is Alice has the frisbee, state B is Bob has the frisbee and state C is Carol has the frisbee, the transition matrix T is
A B C

T=

A B 0 0 1 0 1/3 2/3

C 1 0 0

Since T has several 0 entries, you first need to determine if T is regular. The

230

Chapter 6: Markov Chains

discussion at the beginning of the exercise set at the end of this section shows that all the entries of T5 are positive. Thus T is regular and the equation sT = s, where s = (x y z) must be solved, together with x + y + z = 1. Solving sT = s gives the system of equations y + 1/3 z = x 2/3 z = y x=z which reduces to -x + y + 1/3 z = 0 y + 2/3 z = 0 x z = 0. The second equation says y = 2/3 z while the third equation says x = z. Substituting these values for x and y into the first equation gives 0 = 0. However, s is a probability vector, so x + y + z = 1 and substituting the above values for x and y in terms of z into that equation gives z + 2/3 z + z = 1 Thus x = 3/8, y = 1/4 and z = 3/8 so Alice has the frisbee 3/8 of the time, Bob has it 1/4 of the time and Carol has it 3/8 of the time. Its useful to note that in both of these examples when the system of equations obtained from the matrix equation sT = s was simplified, the system ended up with one equation that was superfluous. That wasnt an accident. In fact, that should happen every time you solve sT = s, where T is a regular transition matrix and if it doesnt happen, youve made a mistake somewhere. As for the method you use in solving the system of equations, thats up to you. With more than two variables involved, you may want to go to the matrix methods which were studied in Chapter 1, but it generally depends on the complexity of the system of equations you have to solve. In both of the examples done above, it wasnt necessary to use row reduction to solve the system of equations since the systems were easily solved using other methods, but in many problems row reduction may be the preferred method. Consider the following example. or z = 3/8.

Section 6.3: Regular Markov Chains

231

Example 6.9 (continued). Customers in a certain city are continually switching the brand of soap they buy. If a customer is now using brand A, the probability he will use brand A next week is .5, that he switches to brand B is .2 and that he switches to brand C is .3. If he now uses brand B, the probability he uses B next week is .6, that he switches to C is .4, and he doesnt switch to A. If he now uses brand C, the probability he stays with C is .4, that he switches to A is .2 and to B is .4. Assuming the process is a Markov Chain, find the percentage of customers using each brand of soap in the long run. Solution: The transition matrix T for this problem is .5 .2 .3 T = 0 .6 .4 . .2 .4 .4 To answer the question in this problem its necessary to find s. Using sT = s, where s is given by s = (x, y, z), yields .5 .2 .3 (x y z) 0 .6 .4 = (x y z) .2 .4 .4 This is equivalent to the following system of equations: .5x + .2z = x .2x + .6y + .4z = y .3x + .4y + .4z = z which simplify to .5x + .2z = 0 .2x .4y + .4z = 0 .3x + .4y .6z = 0 Remember also that x + y + z = 1. This equation must be used in addition to the 3 listed above, for the system above does not have a unique solution. Inclusion of the equation x+y+z=1 does, however, guarantee a unique solution. These four equations may be solved using the techniques of Chapter 1. A good approach that tends to cut down on the computation is to use the augmented matrix for only the first 3 equations, and then come back to the equation x + y + z = 1 at the very end. Lets also multiply each of the original 3 equations by 10 so as to clear out the decimals: 5x + 2z = 0 2x 4y + 4z = 0 3x + 4y 6z = 0 The augmented matrix approach then might go like this:

232
R1 + 2R3

Chapter 6: Markov Chains

-5 0 2 0 2 -4 4 0 3 4 -6 0

1 8 -10 0 2 -4 4 0 3 4 -6 0

R2 2R1

R3 R2

1 8 -10 0 0 -20 24 0 0 -20 24 0

R3 3R1
1

1 8 -10 0 0 -20 24 0 0 0 0 0

20 R2

R1 8R2

1 8 -10 0 0 1 -6/5 0 0 0 0 0

1 0 -2/5 0 0 1 -6/5 0 0 0 0 0

The first and second rows now say x = 5 z and y = 5 z . Substituting this information into x + y + z = 1 gives z + 5 z + 5 z = 5 z = 1, so z = 13 , x = 13 , and y = 13 . Thus, in the long run, the proportion of customers using brand A is 2/13, and the percentage is 15.38% approximately. Similarly the percentage of customers using brand B is 46.15% and using brand C is 38.46% (approximately). You should compare these values with the entries obtained for T6 in Example 6.8 of the last section.
2 6 13 5 2 6 2 6

Problems
To determine if a transition matrix is regular the following technique can be used: (a) Replace all positive entries in T by *. (b) In finding Tk, if k is any positive integer, let * represent a positive entry of T. (Note: In checking for regularity, all thats important is whether there are any zero entries in a given power of T. The actual value of a given positive entry of T is irrelevant.)

Section 6.3: Regular Markov Chains

233

0 0 1 Example: Suppose T = 1 0 0 . Replacing positive entries of T by *s gives 1/3 2/3 0 0 0 * 0 0 * 0 0 * * * 0 2 * 0 0 * 0 0 * 0 0 T= . Then T = = 0 0 * , and * * 0 * * 0 * * 0 * 0 * * * 0 * * 0 * * * = 0 0 * 0 0 * = * 0 * . * 0 * * 0 * * * *

T4

T2

T2

* * * 0 0 * * * * T5 = T4 T = * 0 * * 0 0 = * * * . The purpose of this * * * * * 0 * * * calculation is to demonstrate that all the entries of T5 are positive. 1. Use the technique described above to determine which of the following matrices are regular. 0 1 (a) 1/3 2/3 2/3 1/3 (d) 0 1 0 1 0 (g) 1 0 0 1/2 1/4 1/4 1 0 (b) 1/4 3/4 1 0 (e) 0 1 1/2 1/2 (c) 1 0 0 1 (f) 1 0

(h)

0 0 1 2/3
0 1/4 0 0 0

1/5 4/5 0 0 1 0 0 0 0 0 0 1/3

(i)

1/3 1/2 1/6 0 1 0 1/2 1/2 0

(j)

1 0 0 0 0 3/4 0 0 1/2 0 1/2 0 0 3/4 0 1/4 0 0 1 0

2.

For each of the following matrices, verify that the given row vector is the steadystate vector for the regular transition matrix. 0 1 (a) 1/4 3/4 , s = (1/5 4/5) .3 .7 (b) .6 .4 , s = (6/13 7/13)

234 0 1/2 1/2 (c) 1/3 1/3 1/3 , s = (8/35 15/35 12/35) 1/4 1/2 1/4 3.

Chapter 6: Markov Chains

For each of the following matrices verify that the given row vector is the steady-state vector for the regular transition matrix. 2/3 1/3 (a) 1/2 1/2 , s = (3/5,2/5) .1 .9 (b) .6 .4 , s = (.4 .6)

.2 .3 .5 (c) .4 .4 .2 , s = (14/45 19/45 12/45) .3 .6 .1 In Exercises 4-13, find the steady-state vector. 4. 4/7 3/7 1/6 5/6 .7 .3 5. .6 .4 .9 .1 6. .7 .3 1/7 6/7 7. 5/7 2/7

.6 .2 .2 8. .4 .3 .3 0 .9 .1

3/5 1/5 1/5 9. 1/10 4/5 1/10 0 1/5 4/5

1/2 1/5 3/10 10. 2/5 2/5 1/5 3/10 1/10 3/5

1/2 1/2 0 11. 1/3 1/3 1/3 1/2 0 1/2

1/4 1/4 1/2 12. 1/2 0 1/2 0 1 0

.6 .2 .2 13. .1 .7 .2 .4 .2 .4

0 1 14. Show that T = 1 0 has a unique vector s = (1/2 1/2) so that sT = s but that 1/2 1/2 Tn does not converge to S = 1/2 1/2 as n gets larger and larger. 1 0 0 15. (a) Show that if T = 1/4 1/2 1/4 there is more than one s such that sT = s. 0 0 1 (b) Find a steady-state matrix S so that Tn S. Are the rows of S identical? 16. In a group of registered voters, 80% of those who voted in the last election will vote in the next election and 30% of those who didnt vote in the last election will vote in the next election. In the long run, what percentage of the voters are expected to vote in a given election? 17. In a group of registered voters, 60% of those who voted Democratic in the last election will vote Democratic in the next election, 20% will vote Republican and

Section 6.3: Regular Markov Chains

235

20% will fail to vote. 70% of those who voted Republican will vote Republican in the next election, 10% will vote Democratic and 20% will fail to vote. Of those who didnt vote last time, 20% will vote Democratic, 10% will vote Republican and 70% will fail to vote. In the long run, what percentage vote Democratic? 18. The Cola Bottling Company is considering purchasing one of two types of vending machines A and B. On a month-to-month basis a machine can be in one of two states W = working properly N = not working properly The transition matrices for each type of machine are:
W W N N W N W N

.77 .23 .68 .32 A

.75 .25 .81 .19 B

Based on long-term performance, which machine should Cola Bottling Company buy? 19. Washington, D.C. has two airports, Washington National and Dulles International. A car rental agency rents cars at both airports and the cars can be returned to either airport. If a car is rented at Washington National the probability is .6 that it will be returned to Washington National. If a car is rented at Dulles the probability is .7 that it is returned to Dulles. (a) If a car starts out at Dulles, what is the probability it is returned to Dulles after 2 rentals? (b) What percentage of the cars owned by the agency wind up at Dulles? 20. Answer questions 2 and 3 in Example 6.1. 21. A woman gets her daily exercise by running, swimming or biking. She never runs or bikes two days in a row. If she runs one day, she is equally likely to swim or bike the next day. If she bikes then the next day she is three times as likely to swim as run. If she swims one day, then half the time she swims the next day and otherwise she is equally likely to run or bike. In the long run, what portion of her time is spent on each of the activities? 22. A shelf in a toy store is stocked with 4 teddy bears. Each hour a teddy bear is sold with probability 1/3. As soon as all the teddy bears are sold, the shelf is restocked with 4 more bears. Set up the transition matrix for this Markov Chain process, assuming the states are the number of teddy bears on the shelf at any time. Show the matrix is regular, find the steady-state matrix and interpret the entries. 23. Nancy buys groceries once a week and during her shopping trip she always buys exactly one bag of candy, choosing from Jolly Ranchers, chocolate-covered mints

236

Chapter 6: Markov Chains and Skittles. If she chooses Jolly Ranchers one week, the next week she is equally likely to choose any of the three types of candy. If she picks chocolate-covered mints one week, she doesnt pick them the next week but is equally likely to choose Jolly Ranchers as Skittles. If she chooses Skittles one week, the next week she picks chocolate-covered minst half the time and otherwise is equally likely to choose Jolly Ranchers as Skittles. In the long run, what fraction of the time does she buy each time of candy?

6.4 Absorbing Markov Chains

An absorbing state in a Markov Chain is a state from which it is impossible to leave. Once you hit an absorbing state, youre stuck there forever. An absorbing Markov Chain is one which has absorbing states, in which it is possible to reach an absorbing state from any nonabsorbing state. While this concept of an absorbing state may seem a bit curious at first, its actually very useful and fits several situations that have already been examined.

Definition: Absorbing Markov Chain

A state in a Markov Chain is absorbing if it is impossible to leave the state. The Chain is an absorbing Markov Chain if the following two properties are satisfied: (1) the Markov Chain has at least one absorbing state (2) from each nonabsorbing state it is possible to go to an absorbing state (perhaps in more than one step).

In other words, a state in a Markov Chain is absorbing if the probability is 1 that once in the state, the process remains in that state (pii = 1). So, an easy way to check to see if a Markov Chain has absorbing states and to identify those states is to look down the main diagonal of the transition matrix and see if there are any 1s. If there are, the states associated with those 1s are the absorbing states. Once its been determined that the Markov Chain has absorbing states, property 2 must be checked for each nonabsorbing state. Example 6.14. Identify the absorbing states in each of the following transition matrices. Then determine which are absorbing Markov Chains.

1/2 0 (a) 3/4 1/3

1/4 0 1/4 1 0 0 0 1/4 0 1/3 1/3 0

(b)

1/3 1/8 1/2 2/5

0 2/3 0 1/4 3/8 1/4 0 0 1/2 1/5 1/10 3/10

Section 6.4: Absorbing Markov Chains

237

3/4 0 (c) 1/3 0 0

0 1/4 0 0 1 0 0 0 0 2/3 0 0 0 0 1 0 1/3 0 1/2 1/6

Solution: The absorbing state in (a) is state 2, while (b) has no absorbing states and (c) has states 2 and 4 as absorbing states. However, (a) is the only absorbing Markov Chain. In (a) it is possible to go from each of the states 1 and 4 to state 2 in one step and its possible to go from state 3 to state 2 in two steps. (b) is not an absorbing Markov Chain since it has no absorbing states, while (c) is not absorbing since it is not possible to get to any absorbing state from either state 1 or state 3. The long-term behavior of an absorbing Markov Chain has several interesting aspects. For example,

Theorem
Starting from any state in an absorbing Markov Chain, the probability is 1 that the process will wind up in an absorbing state.

However, even though the above theorem is useful, it raises more questions than it answers. For instance, how long does it take for the process to get absorbed? And if there is more than one absorbing state in the Markov Chain, in which state is the process most likely to get absorbed? And how long and in which nonabsorbing states is the process going to spend time before being absorbed? To understand why it might be worthwhile to know the answers to these questions lets look at the following example. Example 6.15. A rat is placed in the maze of the figure below. In room 1 is a cat and in room 4 is a piece of cheese. If the rat enters either of these rooms he does not leave it. If he is in one of the other rooms, each time period he chooses at random one of the doors of the room he is in and moves into another room.

238

Chapter 6: Markov Chains

1 3 4

1 1 2 room 3 4 1 1/3 1/2 0

room 2 3

So T =

0 0 0 0 1/3 1/3 1/2 0 0 0 0 1

Questions of vital importance to the rat are: Whats the probability I wind up in state 4 as opposed to state 1? Does it make a difference which state I start in? Depending on which state I start in, how long is it on average before Im absorbed ? (Here absorbed means absorbing (cheese) or being absorbed (by cat)) On the average, how much time do I spend in each of the rooms before absorption? So how do you go about trying to answer these questions? In the last section you saw that questions on long term behavior of a regular transition matrix could be answered by determining its steady-state matrix. It turns out that the transition matrix for an absorbing Markov Chain also has a steady-state matrix, i.e. if T is the transition matrix then there is a matrix S so that Tk S for large k. However, in doing the computations necessary to determining a steady-state matrix for an absorbing Markov Chain it turns out to be more convenient to rewrite the transition matrix so the absorbing states are listed first, followed by the nonabsorbing states. Thus the matrix ends up having the following form, called the canonical form:

Section 6.4: Absorbing Markov Chains

absorbing states absorbing states nonabsorbing states nonabsorbing states

239

I R

0 Q

If the Markov Chain has m absorbing states then I is an identity matrix of size m x m. If there are n states in the process, then there are n m nonabsorbing states so Q is also a square matrix and has size (n m) (n m). The zero matrix in the upper right hand corner has size m (n m) and R has size (n m) m. Example 6.15 (continued). To put the transition matrix into canonical form, the matrix needs to be rearranged so that the absorbing states, corresponding to rooms 1 and 4, are listed first. Thus the canonical form of the transition matrix is:
room 4 2

1 1 4 room 2 3

T=

1 0 1/3 1/2

0 0 0 1 0 0 1/3 0 1/3 0 1/2 0

In rewriting the matrix make sure that its rearranged so that the states are in the same order for both the row labels and the column labels. In T above, the rows are labeled in order as rooms 1, 4, 2,3 so the columns have to be labeled in the same order. In any event, in the canonical form for T, the matrices R and Q are
room 1 4 1/3 1/3 1/2 0 room 2 3 0 1/3 1/2 0

2 R = room 3

2 and Q = room 3

Example 6.16. Put the following transition matrices for absorbing Markov Chains in canonical form . Then find R and Q for each of the matrices.
1 1 2 3 4 2 3 4 1 2 3 1 0 0 0 4

(a)

1/2 0 0 1/3

0 1/4 1/4 1 0 0 0 1 0 1/3 0 1/3

(b)

1 2 3 4

0 0 0 1/2

0 0 1 0 1 0 0 1/2

Solution: (a) First notice that states 2 and 3 are absorbing states. Then the canonical form of the transition matrix is:
2 3 1 4

240
2 3 1 4

Chapter 6: Markov Chains

T=

1 0 0 1/3

0 0 0 1 0 0 1/4 1/2 1/4 0 1/3 13

1 4 1/2 1/4 1/3 1/3

1 1 with R = 4 and Q = 4 (b) Here state 3 is the only absorbing state. The canonical form is: 3 3 1 2 4 3 1 0 0 0 1/2 2 4 0 0 1 0 0 0 0 1/2

2 3 0 1/4 1/3 0

T=

1 0 1 0

1 2 4 0 1 0 0 0 0 1/2 0 1/2

with R =

1 2 4

0 1 0

and Q =

1 2 4

Once the transition matrix has been put in canonical form, the following theorem can be used:

Theorem
If T is the transition matrix for an absorbing Markov Chain and T is in canonical form, then when k is large:

! I Tk S = # " NR

0 $ 0 & %

where N = (I Q)-1 and S is the steady-state matrix. If there are n states in the Markov Chain and m of them are absorbing then I is the m m identity matrix, the size of N is then (n m) (n m), and NR has size (n m) m.

The fact that the last n m columns of the steady-state matrix are all zeroes simply says again that, in the long run, the process will end in an absorbing state no matter which state the process started in. Since NR is the matrix that gives the steady-state probabilities for ending in any absorbing state given that the process started in a non-

Section 6.4: Absorbing Markov Chains

241

absorbing state, all thats needed is to look at the appropriate entry of NR to find the probability that if the process started in a given nonabsorbing state then it ends in a particular absorbing state. Lets see how it works for the rat in a maze problem. Example 6.15 (continued). Since
room 1 4 1/3 1/3 1/2 0 room 2 3 0 1/3 1/2 0

2 R = room 3

2 and Q = room 3

then 1 -1/3 6/5 2/5 I Q = -1/2 1 and N = (I Q)-1 = 3/5 6/5 so 6/5 2/5 1/3 1/3 3/5 2/5 NR = 3/5 6/5 1/2 0 = 4/5 1/5 Notice that the matrix NR occupies the same block in Tk in the limit theorem above that the matrix R occupies in T. This means that the rows and columns of NR correspond to the same states as those of R. So the rows and columns of NR are labeled in the same way as the rows and columns of R are labeled. Thus:
room 1 4 3/5 2/5 4/5 1/5

2 NR = room 3

So if the rat starts out in room 2 the probability he winds up in room 1 is 3/5 while the probability he ends up in room 4 is 2/5. On the other hand, if he starts in room 3, the probability he winds up in room 1 is 4/5 and the probability he ends up in room 4 is 1/5. The matrix N (which is called the fundamental matrix) also has important properties of its own. Since N = (I Q)-1, if row and column labels are to be supplied to N they should be the same as those used with Q. In this example that would mean writing
room 2 3 6/5 2/5 3/5 6/5

2 N = (I Q)-1 = room 3

242

Chapter 6: Markov Chains

Properties of the fundamental matrix N

1. The entries of N give the average (or expected value) of the number of times the process is in each nonabsorbing state for each possible nonabsorbing starting state. 2. The sum of a row of N is the average (or expected value) of the number of steps before the process is absorbed assuming the process started in the state represented by the row. 3. NR is the matrix whose entries represent the probabilities that the process ends up in a particular absorbing state for each possible nonabsorbing starting state.

Example 6.15 (continued). Since

room 2 3 6/5 2/5 3/5 6/5

2 N = (I Q)-1 = room 3

property 1 above says that the average number of times the rat is in room 2 given it started in room 2 is 6/5, while the average number of times it goes to room 3 is 2/5 (before absorption). The average number of times spent in room 2 given it started in room 3 is 3/5 and the average number of times spent in room 3 if it started in room 3 is 6/5. If the rat starts in room 2 the average number of steps before absorption is 8/5, while if it starts in room 3 the average number of steps before absorption is 9/5. Lets look at a few more examples to give you some more practice setting up and interpreting problems of this sort. Example 6.17. Suppose Kathy and Melissa repeatedly play a game in which each time they play Kathy has probability .6 of winning. If they each start out with $2 and each bets $1 each time they play, and if they play until one person has lost all her money, determine: (a) the probability Kathy ends up with $4 (b) the average number of times Kathy has $2 in the course of the game. (c) the average number of times Kathy plays the game. Solution: Taking as the states the amount of money Kathy has at any time during the game, the states are $0, $1, $2, $3, $4. The game ends when Kathy has $0 or $4, so these are the absorbing states. Putting the transition matrix in canonical form gives
$0 $4 $1 $2 $3

Section 6.4: Absorbing Markov Chains

$0 $4 $1 $2 $3

243

T=

1 0 .4 0 0

0 1 0 0 .6

0 0 0 .4 0

0 0 .6 0 .4

0 0 0 .6 0

$1 $1 0 Then Q = $2 .4 $3 0

$2 .6 0 .4

$3 0 .6 0

and so I Q =

$1 $2 $3 $1 1 -.6 0 $2 -.4 1 -.6 $3 0 -.4 1

Computing the inverse of I Q gives

$2 $3 19/13 15/13 9/13 10/13 25/13 15/13 4/13 10/13 19/13

$1

N = (I

Q)-1

$1 $2 $3

Since Kathy started with $2, the answer to (b) is 25/13. To answer (c) look at the row sums. The entries in the second row of N add up to 50/13, so on the average the number of rounds they would play before Kathy either loses all her money or wins all of Melissas money is 50/13. The reason for looking at the second row is that it is the row that is labeled $2, and thats the amount she started with. If Kathy starts with $3 and Melissa with $1, then the average number of times they would play until someone goes bankrupt would be 33/13 times, the sum of the third row. (Do you see intuitively why the game might be expected to end quicker in this case than it would if they started out with equal amounts?) To answer (a) its necessary to find the matrix 19/13 15/13 9/13 .4 0 NR = 10/13 25/13 15/13 0 0 4/13 10/13 19/13 0 .6
$1 $2 $3

$0 $4 38/65 27/65 4/13 9/13 8/65 57/65

(Notice again that the same labels are used for the matrix NR as are used for R.) Thus, the probability Kathy ends up with $4 is 9/13 (since she started with $2.) If she had started with $3 and Melissa had started with $1 then the probability Kathy would have wound up with $4 is 57/65. Example 6.18. Jim and Sally are playing catch but neither of them is very good at

244

Chapter 6: Markov Chains

catching the ball. When Jim throws to Sally, 1/3 of the time she gets the ball, 1/6 of the time Jim retrieves it, 1/6 of the time the dog runs off with it and 1/3 of the time it rolls down the storm sewer. When Sally throws to Jim, 1/3 of the time he gets it, 1/3 of the time Sally retrieves it, 1/6 of the time the dog runs off with it and 1/6 of the time it rolls down the storm sewer. Use as the states who or what has the ball and assume the dog and the storm sewer are absorbing states. (a) If Jim has the ball now, how many times on average will Sally have the ball before its lost to the dog or the sewer? (b) If Sally has the ball now, how many times, on average, will the ball get thrown before its lost? (c) If Sally has the ball now, what is the probability the ball winds up in the storm sewer? Solution: Since the dog and the storm sewer are absorbing states, they are listed first. The canonical form for the transition matrix is:
D D SS J S SS J S

T=

1 0 1/6 1/6

0 0 0 1 0 0 1/3 1/6 1/3 1/6 1/3 1/3

and

Q= Then

J S

J S 1/6 1/3 1/3 1/3

and N = (I Q)-1 =
D SS

J S

J S 3/2 3/4 3/4 15/8

NR =

J S

3/8 5/8 7/16 9/16

The answer to (a) is obtained by looking at the entry in the first row and second column of N so the average number of times Sally has the ball before absorption is 3/4. (This is the average number of times Sally has the ball before it goes into the storm sewer or the dog gets it.) The answer to (b) is found by adding up the numbers in the second row of N, so the average number of times the ball is thrown (until it goes into the storm sewer or the dog gets it) is 21/8. The answer to (c) is 9/16 which is obtained from the entry in the second row and second column of NR.

Section 6.4: Absorbing Markov Chains

245

Troubleshooting
There are several things you can watch for in doing computations on absorbing Markov Chains that will tell you that youve made a mistake somewhere in your computations: (1) The entries in N and NR should all be nonnegative. (2) Each row of NR should sum to 1. (Since the entries in NR are probabilities which give the probability of winding up in each absorbing state for a given nonabsorbing state and since the process must end in an absorbing state, the probabilities must sum to 1.) (3) The entries along the main diagonal of N should be 1. The entry in the ith row and the ith column of N is the average number of times the process is in the ith state assuming it started in the ith state. But that number of times includes that initial time and so the number must be 1.

Problems
In Exercises 1-7, determine if the given matrix is a transition matrix for an absorbing Markov Chain. 1. 1/3 2/3 0 1 0 1/2 1/2 0 1 0 1/2 1/4 1/4 2. 0 1 1/3 2/3

3.

4.

1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0

5.

1/3 0 0 3/4

0 1 0 0

0 2/3 0 0 1 0 0 1/4

6.

2/3 1/2 1/6 0 0 1 1 0 0

246
0 1/4 0 0 0 1 0 0 0 0 3/4 0 0 1/2 0 1/2 0 0 3/4 0 1/4 0 0 1 0

Chapter 6: Markov Chains

7.

In Exercises 8-13, each of the matrices is a transition matrix for an absorbing Markov Chain. Rewrite the matrices in canonical form and then identify the R and Q matrices.
1 2 3 1/3 1/12 7/12 2/3 1/6 1/6 0 0 1 1 1 2 3 4 5 1 2/3 0 0 0 1 1 2 3 4 5 6 2 3 4 1 2 1 2 3 3 2/3 0 1/3 1/2 1/2 0 0 0 1 1 2 3

8.

1 2 3

9.

1 2

10.

1 2 3

1 0 0 1/4 1/2 1/4 0 0 1

3 4 5

11.

0 0 0 0 0 1/3 0 0 2/3 0 1/3 0 0 2/3 0 1/3 0 0 0 1 2 3 4 5

12.

1 2 3 4 5

1/2 3/7 0 0 0

0 1/2 0 0 4/7 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0

13.

1/2 0 0 0 0 0

0 1/4 0 0 1/4 1 0 0 0 0 0 1/3 1/3 1/3 0 0 0 1 0 0 1/5 2/5 0 0 2/5 0 0 0 0 1

In Exercises 14-21, find N and then determine the steady-state matrix for each of the following transition matrices for absorbing Markov Chains.
1 2 1 0 .33 .67 1 2 3 1 0 0 1/3 1/2 1/6 0 0 1 1 2 3

14.

1 2

15.

1 2 3

16.

1 2 3

1 2 3 1/4 1/4 1/2 0 1 0 1/2 1/4 1/4

17.

1 2 3 4

1/2 0 0 0

1/4 1/4 0 1 0 0 0 1 0 1/3 1/3 1/3

Section 6.4: Absorbing Markov Chains

1 1 2 3 4 2 3 4 1 2 0 1 0 3/4 2 1/3 1 0 0 0 3 4 1 0 0 0 0 1 0 1/4 3 4

247

18.

1/2 0 1/4 1/3

1 1 1/4 0 0 1/3

0 1/2 0 1 0 0 1/2 1/4 0 0 1/3 1/3 2 3 4

19.

1 2 3 4

0 0 0 0
1

20.

1 2 3 4 5

0 0 0 0 1/4 0 0 1/2 0 1/3 1/3 1/3 0 0 1 0 1/3 0 1/3 0

21.

1 2 3 4 5

0 0 0 0 1/2

0 1/3 1/3 0 0 0 0 3/4 1/4 0 1 0 0 0 1/2

22. Answer question 4 in Example 6.1. 23. A mouse is put into the maze of the following figure. Each time period it chooses at random one of the doors in the room it is in and moves to another room. From room 1 the mouse can escape to the outside (state 5) but in room 3 is a (Havahart) mouse trap.

4 3 2

1 5 (outside the maze)

(a) Set up the process as a Markov Chain. (b) Find N and NR. (c) If the mouse starts in room 4, what is the average number of rooms he will visit before he escapes or is caught? (d) If he starts in room 4, what is the average number of times he visits room 1? (e) If he starts in room 2, what is the probability he escapes? 24. A junior college has freshmen and sophomore students. 80% of the freshmen successfully complete their year and go on to become sophomores, 10% drop out and 10% fail and must repeat their freshman year. Among the sophomores 85% graduate, 5% drop out and 10% fail and must repeat their sophomore year. Set up the transition matrix and find (a) the probability a freshman eventually graduates. (b) the average number of years an entering freshman spends at the junior college.

248

Chapter 6: Markov Chains

25. The victims of a certain disease being treated at Wake Medical Center are classified annually as follows: cured, in temporary remission, sick, or dead from the disease. Once a victim is cured, he is permanently immune. Each year, those in remission get sick again with probability 1/4, are cured with probability 1/2, and stay in remission with probability 1/4. Those who are sick are cured, go into remission, or die from the disease with probability 1/3 each. Determine (a) the probability of being cured if the victim is now in remission. (b) the average number of years before a victim currently in remission is either cured or dies. 26. Sally and Becky are playing tennis. When deuce is reached, the player winning the next point has advantage. On the following point, the player either wins the game or the game returns to deuce. Suppose that at deuce, Sally has probability 2/3 of winning the next point and Becky has 1/3 probability of winning the point. When Sally has advantage she has probability 3/4 of winning the next point and when Becky has advantage she has probability 1/2 of winning the next point. Set this up as a Markov Chain with states: Sally wins the game, Becky wins the game, Sallys advantage, Beckys advantage, deuce. (a) If the game is at deuce, find how long the game is expected to last and the probability that Becky wins. (b) If Sally has advantage, what is the probability she eventually wins the game? 27. John has $750 and needs $1000 for his vacation. He decides to go to the track and bet his money until he either loses all of it or makes $1000. Suppose each time he bets, he wins with probability 2/5 and loses with probability 3/5. Also suppose that each time he bets, he either bets as much as he has or as much as he needs to get his $1000, whichever is smaller. (In other words, if he has $250, he bets $250, if he has $500 he bets $500, and if he has $750 he bets $250.) (a) Set up the transition matrix. (b) Find N and NR. (c) Find the expected number of bets he makes. (d) Find the probability he gets to go on his vacation. 28. Andy, Bill and Carl are playing Laser Tag. Suppose Andy has probability 1/2 of hitting his opponent any time he fires, Bill has probability 1/3 of hitting his opponent and Carl has probability 1/6 of hitting his opponent. Assume the boys fire simultaneously each round with each boy firing at his strongest opponent and also assume that a boy is out of the game if he is hit. Treat this as a Markov Chain with the states being the boys left in the game after any one round. (a) Find the transition matrix. (b) Find N and NR. (c) What is the probability Andy wins the game? What is the probability no one wins the game? (d) If Carl and Bill are left after a round, how many more rounds is the game

Section 6.4: Absorbing Markov Chains expected to last?

249

29. Suppose instead of following the strategy in Exercise 27, John simply bets $250 each time. Answer questions (a), (b), (c), and (d) for this new strategy. Which strategy is the best one for him to follow if he wants to go on his vacation?

Chapter 6 Review Problems

1. Determine which of the following matrices are transition matrices. For those which are transition matrices, classify them as regular or absorbing or neither. For those which are regular or absorbing, find the steady-state matrix and interpret the entries.
1 2 3 0 1 0 1/2 1/4 1/4 1/3 1/2 1/3 1 2 3 4 1 2 3 4 1 2 3 0 1 0 1/4 1/4 1/2 0 2/5 3/5 1 2 3 4 0 0 0 0 3

(a)

1 2 3

(b)

1 2 3

(c)

0 0 0 0
1

1 0 1 1 2

0 1 0 0

4 5

(d)

1 2 3 4

0 1 0 0
1 1 1/4 0 0 0

0 0 0 1 2

1 0 0 0

0 0 1 0 3

4 5

(e)

1 2 3 4 5

1/4 0 0 0 0
1

1/4 1/4 0 1/4 1/3 0 1/3 1/3 0 1/3 1/3 1/3 0 0 1 0 0 0 0 1 2 3 4

(f)

1 2 3 4 5

0 0 0 0 0 3/4 0 0 1/2 0 1/2 0 0 3/4 0 1/4 0 0 0 1

(g)

1 2 3 4

1/3 1 1 1

1/12 1/6 1/2 0 0 0 0 0 0 0 0 0

2.

For Exercises 7, 10, 11, 12, and 13 in Section 6.1, determine if the transition matrix is regular, absorbing or neither. Then for those which are regular or absorbing, find the steady-state matrix and interpret the entries. Each day Andy eats at Two Cousins or Fat Mamas. If he eats at Two Cousins one day, there is a 50% chance he will return there the next day. If he eats at Fat Mamas

3.

250

Chapter 6: Markov Chains one day, there is a 75% chance he will go to Two Cousins the next day. Consider this a 2 state Markov Chain with state 1= eating at Two Cousins and state 2 = eating at Fat Mamas. (a) Find the transition matrix. (b) If Andy eats at Two Cousins on Monday, what is the probability he will eat at Fat Mamas on Thursday? (c) In the long run, what fraction of the time does he eat at Two Cousins?

4.

A company has stores in Boston and Chicago and sells items to men, women and children. Sometimes items that do not sell well are transferred from one store to another. Each week at the Boston store, 10% of the items are sold to men, 10% are sold to women, 20% are sold to children, 20% are shipped to Chicago, and the remaining 40% are kept in Boston. The Chicago store sells 10% to men, 20% to women, 30% to children, ships 10% to Boston, and keeps the remaining 30%. (a) Treat this as a 5-state Markov chain with men, women, and children as absorbing states. Write down the transition matrix. (b) What is the probability that an item in the Boston store will eventually be sold to a woman? (c) What is the probability that an item in the Chicago store will eventually be sold to a child? A banker has three different suits she wears to work, a navy blue one, a gray one and a beige one. She never wears the same suit two days in a row. If she wears the navy blue suit one day she always wears the gray one the next day. If she wears either the gray or beige suits one day she is twice as likely to wear the navy blue one rather than the other one the next day. In the long run what fraction of the time does she wear each suit?

5.