Markov Chains Mixing Times

Exercises - Part 2

Ori Gurel-Gurevich  Ariel Yadin

December 27, 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 the L_{1} and the total variation distance are the same, e.e. ∑_{x∈Ω} |μ(x) − ν(x)| = 2 max_{A⊂Ω} |μ(A) − ν(A)|.

Exercise 2. Show that a simple random walk on a non-bipartite graph is aperiodic.

Exercise 3. Prove that if P is irreducible then gcd{t|P^{t}(x, x) > 0} is the same for all choices of x ∈ Ω. Conclude that if gcd{t|∃y ∈ ΩP^{t}(y, y) > 0} = 1 then the chain is aperiodic.

Exercise 4 (*). Prove that for any μ and any aperiodic P, μP^{t} converges to some stationary distribution, even if P is not irreducible.