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,
Previous Page Next Page