1 Consider the Markov chain with transition matrix Find the

1. Consider the Markov chain with transition matrix. Find the probability that, starting from 1, it hits 2 before 3.

2. Consider the Markov chain with transition matrix. Find the probability that, starting from 2, it hits 1 before 3.

Solution

Markov Chains

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 experiments forms 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 n experiments, 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 Markov chain.

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 not depend upon which states the chain was in before the current 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 the starting 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.

Where do Markov chains come from

At each time we apply some new ‘randomness’ to determine the next step, in a way that is a function only of the current state. We might take U1, U2, . . . as some i.i.d. random variables taking values in a set E and a function F : I × E I. Take i I. Set X0 = i and define recursively Xn+1 = F(Xn, Un+1), n 0. Then (Xn)n0 is Markov(i , P) where pij = P(F(i, U) = j).

How can we simulate them

Use a computer to simulate U1, U2, . . . as i.i.d. U[0, 1]. Define F(U, i) = J by the rules U [0, pi1) = J = 1 U hPj1 k=1 pik, Pj k=1 pik , j 2 = J = j

The n-step transition matrix

Let A be an event. A convenient notation is Pi(A) = P(A | X0 = i). For example Pi(X1 = j) = pij . Given the initial distribution , let us treat it as a row vector. Then P(X1 = j) = X iI iPi(X1 = j) = X iI ipij . Similarly, Pi(X2 = j) = X k Pi(X1 = k, X2 = j) = X k pikpkj = (P 2 )ij P(X2 = j) = X i,k iPi(X1 = k, X2 = j) = X i,k ipikpkj = (P2 )j . Continuing in this way, Pi(Xn = j) = (iP n )j = (P n )ij = p (n) ij P(Xn = j) = X i0,...,in1 i0 pi0i1 · · · pin1j = (P n )j . Thus P (n) = (p (n) ij ), the n-step transition matrix, is simply P n (P raised to power n). Also, for all i, j and n, m 0, the (obvious) Chapman-Kolmogorov equations hold: p (n+m) ij = X kI p (n) ik p (m) kj 3 named for their independent formulation by Chapman (a Trinity College graduate, 1880-1970), and Kolmogorov (1903-1987).