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