18 1. INTRODUCTION TO FINITE MARKOV CHAINS y ∈ C, whence π is supported on C. Consequently, for x ∈ C, π(x) = y∈Ω π(y)P (y, x) = y∈C π(y)P (y, x) = y∈C π(y)P|C(y, x), and π restricted to C is stationary for P|C . By uniqueness of the stationary distri- bution for P|C , it follows that π(x) = πC (x) for all x ∈ C. Therefore, π(x) = πC (x) if x ∈ C, 0 if x ∈ C, and the solution to π = πP is unique. Suppose there are distinct essential communicating classes for P , say C1 and C2. The restriction of P to each of these classes is irreducible. Thus for i = 1, 2, there exists a measure π supported on Ci which is stationary for P|Ci . Moreover, it is easily verified that each πi is stationary for P , and so P has more than one stationary distribution. Exercises Exercise 1.1. Let P be the transition matrix of random walk on the n-cycle, where n is odd. Find the smallest value of t such that P t(x, y) 0 for all states x and y. Exercise 1.2. A graph G is connected when, for two vertices x and y of G, there exists a sequence of vertices x0, x1, . . . , xk such that x0 = x, xk = y, and xi ∼ xi+1 for 0 ≤ i ≤ k − 1. Show that random walk on G is irreducible if and only if G is connected. Exercise 1.3. We define a graph to be a tree if it is connected but contains no cycles. Prove that the following statements about a graph T with n vertices and m edges are equivalent: (a) T is a tree. (b) T is connected and m = n − 1. (c) T has no cycles and m = n − 1. Exercise 1.4. Let T be a tree. A leaf is a vertex of degree 1. (a) Prove that T contains a leaf. (b) Prove that between any two vertices in T there is a unique simple path. (c) Prove that T has at least 2 leaves. Exercise 1.5. Let T be a tree. Show that the graph whose vertices are proper 3-colorings of T and whose edges are pairs of colorings which differ at only a single vertex is connected. Exercise 1.6. Let P be an irreducible transition matrix of period b. Show that Ω can be partitioned into b sets C1,C2, . . . , Cb in such a way that P (x, y) 0 only if x ∈ Ci and y ∈ Ci+1. (The addition i + 1 is modulo b.) Exercise 1.7. A transition matrix P is symmetric if P (x, y) = P (y, x) for all x, y ∈ Ω. Show that if P is symmetric, then the uniform distribution on Ω is stationary for P .

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.