Markov

Chapter 11

Markov Chains
11.1 Introduction

Most of our study of probability has dealt with independent trials processes. These processes are the basis of classical probability theory and much of statistics. We have discussed two of the principal theorems for these processes: the Law of Large Numbers and the Central Limit Theorem. We have seen that when a sequence of chance experimentsforms an independent trials process, the possible outcomes for each experiment are the same and occur with the same probability. Further, knowledge of the outcomes of the previous experiments does not influence our predictions for the outcomes of the next experiment. The distribution for the outcomes of a single experiment is sufficient to construct a tree and a tree measure for a sequence of nexperiments, and we can answer any probability question about these experiments by using this tree measure. Modern probability theory studies chance processes for which the knowledge of previous outcomes influences predictions for future experiments. In principle, when we observe a sequence of chance experiments, all of the past outcomes could influence our predictions for the next experiment. For example,this should be the case in predicting a student’s grades on a sequence of exams in a course. But to allow this much generality would make it very difficult to prove general results. In 1907, A. A. Markov began the study of an important new type of chance process. In this process, the outcome of a given experiment can affect the outcome of the next experiment. This type of process is called a Markovchain.

Specifying a Markov Chain
We describe a Markov chain as follows: We have a set of states, S = {s1 , s2 , . . . , sr }. The process starts in one of these states and moves successively from one state to another. Each move is called a step. If the chain is currently in state si , then it moves to state sj at the next step with a probability denoted by pij , and this probability does notdepend upon which states the chain was in before the current 405

406

CHAPTER 11. MARKOV CHAINS

state. The probabilities pij are called transition probabilities. The process can remain in the state it is in, and this occurs with probability pii . An initial probability distribution, defined on S, specifies the starting state. Usually this is done by specifying a particular state as thestarting state. R. A. Howard1 provides us with a picturesque description of a Markov chain as a frog jumping on a set of lily pads. The frog starts on one of the pads and then jumps from lily pad to lily pad with the appropriate transition probabilities. Example 11.1 According to Kemeny, Snell, and Thompson,2 the Land of Oz is blessed by many things, but not by good weather. They never have two nice daysin a row. If they have a nice day, they are just as likely to have snow as rain the next day. If they have snow or rain, they have an even chance of having the same the next day. If there is change from snow or rain, only half of the time is this a change to a nice day. With this information we form a Markov chain as follows. We take as states the kinds of weather R, N, and S. From the aboveinformation we determine the transition probabilities. These are most conveniently represented in a square array as R N S   R 1/2 1/4 1/4 P = N  1/2 0 1/2  . S 1/4 1/4 1/2 2

Transition Matrix
The entries in the first row of the matrix P in Example 11.1 represent the probabilities for the various kinds of weather following a rainy day. Similarly, the entries in the second and third rowsrepresent the probabilities for the various kinds of weather following nice and snowy days, respectively. Such a square array is called the matrix of transition probabilities, or the transition matrix . We consider the question of determining the probability that, given the chain is in state i today, it will be in state j two days from now. We denote this probability (2) by pij . In Example 11.1, we see...