Markov Chains Mixing Times

Ori Gurel-Gurevich  Ariel Yadin

December 27, 2007

1 convergence to stationary distribution

Assume the chain is irreducible, so we have a stationary distribution, π. Does μ_{0}P^{t} = μ_{t}→π for any μ_{0}?

What exactly do we mean by → here? There are several notions of convergence, the simplest is pointwise, i.e. μ_{t}(x)→π(x) for any x ∈ Ω. In other words, convergence as a vector in ℝ^{Ω}.

However, sometimes we want to be more specific about how close are we to stationarity. So we want to define what is the distance between distributions. We can consider known norms on ℝ^{n}.

L_{∞}: d_{∞}(μ, ν) = max_{x∈Ω} |μ(x) − ν(x)| L_{2}: d_{2}(μ, ν) = \sqrt{∑_{x∈Ω}(μ(x) − ν(x))^{2}} L_{1}: d_{1}(μ, ν) = ∑_{x∈Ω} |μ(x) − ν(x)| and more They are all equivalent w.r.t. convergence, but may be different when

considering mixing times.

Obvious inequalities:

d_{∞} ≤ d_{1} ≤ \sqrt{n}d_{2} ≤ nd_{∞}

One may consider more ”exotic” distances:

d(μ, ν) = max_{x∈Ω} | log μ(x) − log ν(x)|

What do they all mean? We will work mainly with the L_{1} distance, which has a very natural probabilistic interpretation.

Suppose that we have μ and ν and we know d_{1}(μ, ν). Given an event A, if we know μ(A) what does this tells us about ν(A)?

Exercise. d_{1}(μ, ν) = 2 max_{A⊂Ω} |μ(A) − ν(A)|

L_{1} is also called total variation norm.

Periodic example for non-convergence.

SRW on a bipartite graph.

These examples have a period - all the times for which P^{t}(x, x) > 0 are divisible by some m > 1.

Definition. A Markov chain is aperiodic if ∀x ∈ Ω gcd{t|P^{t}(x, x) > 0} = 1. It is called periodic otherwise.

Like irreducibility, this is a property of the underlying graph, not of the specific probabilities.

Exercise. Show that a SRW on a non-bipartite graph is aperiodic.

Lemma. If P is irreducible and aperiodic, exists r such that for all x, y ∈ Ω, P^{r}(x, y) > 0.

Proof. First we prove that for all x ∈ Omega we have P^{r}(x, x) > 0 for all large enough r. Since the gcd is 1, we have a finite number of loops with lengths with gcd = 1. If these lengths are n_{i} then there are integers a_{i} such that ∑ a_{i}n_{i} = 1. Let A = − min{a_{i}} then any number greater then A ∏ n_{i} can be expressed as a linear combination of the n_{i}’s with natural coefficients.

Now the same is true for also for paths from x to y. Since Ω is finite, the proof is concluded.

Exercise. 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.

Theorem. If a chain is irreducible and aperiodic then μP^{t}→π. More specifically, there exists α < 1 such that |μP^{t} − π| ≤ α^{t}, for any distribution μ on Ω.

Proof. Assume P (x, y) > 0 for all x, y ∈ Ω. Since Ω is finite, there is β > 0 such that P (x, y) > βπ(y). This implies that for any distribution μ, one can decompose μP = βπ +αν, for alpha = 1−β and ν some probability measure depending on μ.

Fix μ_{0} and let mu_{t} = μ_{0}P^{t}. Then μ_{1} = βπ + αν_{1}. Decomposing ν_{1}P we get ν_{1}P = βπ + αν_{2}. Therefore,

μ_{2} = βπ + α(βπ + αν_{2}) = (1 − α^{2})π + α^{2}ν_{2}

By induction we see that

μ_{t} = (1 − α^{t})π + α^{t}ν_{t}

Thus,

∥π − μ_{t}∥_{1} = ∥α^{t}(π − ν_{t})∥ ≤ 2α^{t}

Do we really need irreducibility? Recalling our discussion of the communication graph and the stationary distributions on the irreducible components, it is easy to see that the theorem holds with π replaced by some stationary distribution, dependent on μ.

Exercise. prove that.