6 1. INTRODUCTION TO FINITE MARKOV CHAINS Figure 1.3. Random walk on Z10 is periodic, since every step goes from an even state to an odd state, or vice-versa. Random walk on Z9 is aperiodic. That is, the probability of moving in t steps from x to y is given by the (x, y)-th entry of P t. We call these entries the t-step transition probabilities. Notation. A probability distribution µ on Ω will be identified with a row vector. For any event A ⊂ Ω, we write π(A) = x∈A µ(x). For x ∈ Ω, the row of P indexed by x will be denoted by P (x, ·). Remark 1.3. The way we constructed the matrix P has forced us to treat distributions as row vectors. In general, if the chain has distribution µ at time t, then it has distribution µP at time t + 1. Multiplying a row vector by P on the right takes you from today’s distribution to tomorrow’s distribution. What if we multiply a column vector f by P on the left? Think of f as a function on the state space Ω (for the frog of Example 1.1, we might take f(x) to be the area of the lily pad x). Consider the x-th entry of the resulting vector: P f(x) = y P (x, y)f(y) = y f(y)Px{X1 = y} = Ex(f(X1)). That is, the x-th entry of P f tells us the expected value of the function f at tomorrow’s state, given that we are at state x today. Multiplying a column vector by P on the left takes us from a function on the state space to the expected value of that function tomorrow. 1.2. Random Mapping Representation We begin this section with an example. Example 1.4 (Random walk on the n-cycle). Let Ω = Zn = {0, 1, . . . , n − 1}, the set of remainders modulo n. Consider the transition matrix P (j, k) = ⎧ ⎪1/2 ⎨ ⎪ ⎩ if k ≡ j + 1 (mod n), 1/2 if k ≡ j − 1 (mod n), 0 otherwise. (1.11) The associated Markov chain (Xt) is called random walk on the n-cycle. The states can be envisioned as equally spaced dots arranged in a circle (see Figure 1.3).

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.