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).
Previous Page Next Page