EXERCISES 19 Exercise 1.8. Let P be a transition matrix which is reversible with respect to the probability distribution π on Ω. Show that the transition matrix P 2 corre- sponding to two steps of the chain is also reversible with respect to π. Exercise 1.9. Let π be a stationary distribution for an irreducible transition matrix P . Prove that π(x) 0 for all x ∈ Ω, without using the explicit formula (1.25). Exercise 1.10. Check carefully that equation (1.19) is true. Exercise 1.11. Here we outline another proof, more analytic, of the existence of stationary distributions. Let P be the transition matrix of a Markov chain on a finite state space Ω. For an arbitrary initial distribution µ on Ω and n 0, define the distribution νn by νn = 1 n ( µ + µP + ··· + µP n−1 ) . (a) Show that for any x ∈ Ω and n 0, |νnP (x) − νn(x)| ≤ 2 n . (b) Show that there exists a subsequence (νnk )k≥0 such that limk →∞ νnk (x) exists for every x ∈ Ω. (c) For x ∈ Ω, define ν(x) = limk →∞ νnk (x). Show that ν is a stationary distri- bution for P . Exercise 1.12. Let P be the transition matrix of an irreducible Markov chain with state space Ω. Let B ⊂ Ω be a non-empty subset of the state space, and assume h : Ω → R is a function harmonic at all states x ∈ B. Prove that if h is non-constant and h(y) = maxx∈Ω h(x), then y ∈ B. (This is a discrete version of the maximum principle.) Exercise 1.13. Give a direct proof that the stationary distribution for an irreducible chain is unique. Hint: Given stationary distributions π1 and π2, consider the state x that min- imizes π1(x)/π2(x) and show that all y with P (x, y) 0 have π1(y)/π2(y) = π1(x)/π2(x). Exercise 1.14. Show that any stationary measure π of an irreducible chain must be strictly positive. Hint: Show that if π(x) = 0, then π(y) = 0 whenever P (x, y) 0. Exercise 1.15. For a subset A ⊂ Ω, define f(x) = Ex(τA). Show that (a) f(x) = 0 for x ∈ A. (1.35) (b) f(x) = 1 + y∈Ω P (x, y)f(y) for x ∈ A. (1.36) (c) f is uniquely determined by (1.35) and (1.36). The following exercises concern the material in Section 1.7. Exercise 1.16. Show that ↔ is an equivalence relation on Ω. Exercise 1.17. Show that the set of stationary measures for a transition matrix forms a polyhedron with one vertex for each essential communicating class.

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.