Markov Chains Mixing Times

Exercises - Part 2

Ori Gurel-Gurevich  Ariel Yadin

December 16, 2007

Please take some time to go over the last lesson and think about the exercises. Some of the exercises may require knowledge outside the scope of this course. Exercises marked with an asterisk are harder.

Exercise 1. Prove that irreducibility of the Markov chain and strong-connectivity of the corresponding directed graph are equivalent.

Exercise 2. Prove that if the directed graph of a Markov chain is one-way-connected, (i.e. for any two vertices there’s a directed path from one of them to the other), then any harmonic function is constant.

Exercise 3. Prove that x↔y (there’s a directed path from x to y and from y to x) is an equivalent relation.

Exercise 4. Prove that the equivalent classes of this relation constitute a Directed Acyclic graph.