1.1. FINITE MARKOV CHAINS 5 which implies (after a little algebra) that π(e) = q p + q , π(w) = p p + q . If we define ∆t = µt(e) − q p + q for all t ≥ 0, then by the definition of µt+1 the sequence (∆t) satisfies ∆t+1 = µt(e)(1 − p) + (1 − µt(e))(q) − q p + q = (1 − p − q)∆t. (1.8) We conclude that when 0 p 1 and 0 q 1, lim t→∞ µt(e) = q p + q and lim t→∞ µt(w) = p p + q (1.9) for any initial distribution µ0. As we suspected, µt approaches π as t → ∞. Remark 1.2. The traditional theory of finite Markov chains is concerned with convergence statements of the type seen in (1.9), that is, with the rate of conver- gence as t → ∞ for a fixed chain. Note that 1 − p − q is an eigenvalue of the frog’s transition matrix P . Note also that this eigenvalue determines the rate of convergence in (1.9), since by (1.8) we have ∆t = (1 − p − q)t∆0. The computations we just did for a two-state chain generalize to any finite Markov chain. In particular, the distribution at time t can be found by matrix multiplication. Let (X0, X1, . . . ) be a finite Markov chain with state space Ω and transition matrix P , and let the row vector µt be the distribution of Xt: µt(x) = P{Xt = x} for all x ∈ Ω. By conditioning on the possible predecessors of the (t + 1)-st state, we see that µt+1(y) = x∈Ω P{Xt = x}P (x, y) = x∈Ω µt(x)P (x, y) for all y ∈ Ω. Rewriting this in vector form gives µt+1 = µtP for t ≥ 0 and hence µt = µ0P t for t ≥ 0. (1.10) Since we will often consider Markov chains with the same transition matrix but different starting distributions, we introduce the notation Pµ and Eµ for probabil- ities and expectations given that µ0 = µ. Most often, the initial distribution will be concentrated at a single definite starting state x. We denote this distribution by δx: δx(y) = 1 if y = x, 0 if y = x. We write simply Px and Ex for Pδx and Eδx , respectively. These definitions and (1.10) together imply that Px{Xt = y} = (δxP t)(y) = P t(x, y).

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.