4 1. INTRODUCTION TO FINITE MARKOV CHAINS 0 10 20 0.25 0.5 0.75 1 0 10 20 0.25 0.5 0.75 1 0 10 20 0.25 0.5 0.75 1 (a) (b) (c) Figure 1.2. The probability of being on the east pad (started from the east pad) plotted versus time for (a) p = q = 1/2, (b) p = 0.2 and q = 0.1, (c) p = 0.95 and q = 0.7. The long-term limiting probabilities are 1/2, 1/3, and 14/33 ≈ 0.42, respectively. heads up, while the coin on the west pad has probability q of landing heads up. The frog’s rules for jumping imply that if we set P = P (e, e) P (e, w) P (w, e) P (w, w) = 1 − p p q 1 − q , (1.2) then (X0, X1, . . . ) is a Markov chain with transition matrix P . Note that the first row of P is the conditional distribution of Xt+1 given that Xt = e, while the second row is the conditional distribution of Xt+1 given that Xt = w. Assume that the frog spends Sunday on the east pad. When he awakens Mon- day, he has probability p of moving to the west pad and probability 1 − p of staying on the east pad. That is, P{X1 = e | X0 = e} = 1 − p, P{X1 = w | X0 = e} = p. (1.3) What happens Tuesday? By considering the two possibilities for X1, we see that P{X2 = e | X0 = e} = (1 − p)(1 − p) + pq (1.4) and P{X2 = w | X0 = e} = (1 − p)p + p(1 − q). (1.5) While we could keep writing out formulas like (1.4) and (1.5), there is a more systematic approach. We can store our distribution information in a row vector µt := (P{Xt = e | X0 = e}, P{Xt = w | X0 = e}) . Our assumption that the frog starts on the east pad can now be written as µ0 = (1, 0), while (1.3) becomes µ1 = µ0P . Multiplying by P on the right updates the distribution by another step: µt = µt−1P for all t ≥ 1. (1.6) Indeed, for any initial distribution µ0, µt = µ0P t for all t ≥ 0. (1.7) How does the distribution µt behave in the long term? Figure 1.2 suggests that µt has a limit π (whose value depends on p and q) as t → ∞. Any such limit distribution π must satisfy π = πP,

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.