8 1. INTRODUCTION TO FINITE MARKOV CHAINS 1.3. Irreducibility and Aperiodicity We now make note of two simple properties possessed by most interesting chains. Both will turn out to be necessary for the Convergence Theorem (The- orem 4.9) to be true. A chain P is called irreducible if for any two states x, y there exists an integer t (possibly depending on x and y) such that P t(x, y) 0. This means that it is possible to get from any state to any other state using only transitions of positive probability. We will generally assume that the chains under discussion are irreducible. (Checking that specific chains are irreducible can be quite interesting see, for instance, Section 2.6 and Example B.5. See Section 1.7 for a discussion of all the ways in which a Markov chain can fail to be irreducible.) Let T (x) := {t 1 : P t(x, x) 0} be the set of times when it is possible for the chain to return to starting position x. The period of state x is defined to be the greatest common divisor of T (x). Lemma 1.6. If P is irreducible, then gcd T (x) = gcd T (y) for all x, y Ω. Proof. Fix two states x and y. There exist non-negative integers r and such that P r(x, y) 0 and P (y, x) 0. Letting m = r+ , we have m T (x)∩T (y) and T (x) T (y) m, whence gcd T (y) divides all elements of T (x). We conclude that gcd T (y) gcd T (x). By an entirely parallel argument, gcd T (x) gcd T (y). For an irreducible chain, the period of the chain is defined to be the period which is common to all states. The chain will be called aperiodic if all states have period 1. If a chain is not aperiodic, we call it periodic. Proposition 1.7. If P is aperiodic and irreducible, then there is an integer r such that P r(x, y) 0 for all x, y Ω. Proof. We use the following number-theoretic fact: any set of non-negative integers which is closed under addition and which has greatest common divisor 1 must contain all but finitely many of the non-negative integers. (See Lemma 1.27 in the Notes of this chapter for a proof.) For x Ω, recall that T (x) = {t 1 : P t(x, x) 0}. Since the chain is aperiodic, the gcd of T (x) is 1. The set T (x) is closed under addition: if s, t T (x), then P s+t(x, x) P s(x, x)P t(x, x) 0, and hence s + t T (x). Therefore there exists a t(x) such that t t(x) implies t T (x). By irreducibility we know that for any y there exists r = r(x, y) such that P r(x, y) 0. Therefore, for t t(x) + r, P t(x, y) P t−r(x, x)P r(x, y) 0. For t t (x) := t(x) + maxy∈Ω r(x, y), we have P t(x, y) 0 for all y Ω. Finally, if t maxx∈Ω t (x), then P t(x, y) 0 for all x, y Ω. Suppose that a chain is irreducible with period two, e.g. the simple random walk on a cycle of even length (see Figure 1.3). The state space can be partitioned into two classes, say even and odd, such that the chain makes transitions only between states in complementary classes. (Exercise 1.6 examines chains with period b.) Let P have period two, and suppose that x0 is an even state. The probability distribution of the chain after 2t steps, P 2t(x0, ·), is supported on even states, while the distribution of the chain after 2t + 1 steps is supported on odd states. It is evident that we cannot expect the distribution P t(x0, ·) to converge as t ∞.
Previous Page Next Page