Markov Chains Mixing Times

Ori Gurel-Gurevich  Ariel Yadin

December 16, 2007

1 stationary distribution

Definition.

π = πP

Example. SRW on graph. stationary dist = degree.

Frog example is a special case (even though it looks directed at first glance).

Example. SRW on directed graph. no formula for stationary dist. special case: if in-degree=out-degree then like former case. note: in these cases, distribution on edges is uniform. In particular, the uniform distribution on the deck of cards is stationary. A special case of RW on groups.

Note: any Markov Chain can be represented as a RW on a directed weighted graph. Vertices=States, Transitions=Edges.

Does a stationary distribution always exist? Is it unique? Does the distribution converges to a stationary distribution?

1.1 existence

Theorem. For any Markov chain P on a finite state space, a stationary distribution π exists - π = πP.

Note: not true for infinite state space, not even if we want a stationary measure. example: shift on ℕ.

There are many proofs: analytic, algebraic, probabilistic.

Proof. Brouwer fixed point theorem. P is a continuous (linear) function from the n-dimensional simplex to itself, and therefore has a fixed point. This is exactly the stationary distribution.

Maybe we’ll see another, more constructive proof later.

1.2 uniqueness

Obviously, sometimes the stationary distribution is not unique.

Trivial example: if the graph is disconnected then each of the stationary distributions of the components of the graph is stationary.

Definition. If it is possible to get from any state to any state then the chain is called irreducible. Equivalently, the directed graph associated with the chain is strongly connected. Equivalently, ∀x, v ∈ Ω∃n ∈ ℕ P^{n}(x, y) > 0.

Note that irreducibility is a property of the underlying graph, and is not affected by the actual probability ,as long as they’re positive.

Is irreducibility enough for uniqueness? Yes. But first let’s give a more constructive proof of the existence of a stationary distribution.

hitting time, τ_{x}.

return time, τ_{x}^{+}

E_{x}(τ_{x}^{+}) < ∞.

The hitting time is a special case of a stopping time, a very useful concept later on.

   Fix a vertex z. Let π(y) = E_{z}(# of visits to y before returning to z) =

∑_{t≥0} P_{z}(X_{t} = y, t < τ_{z}^{+}).

Theorem. πP = π.

Recall that our matrix is stochastic, i.e. P 1 = P Definition. a function is harmonic if h = P h, i.e. h(x) = ∑_{y∈Ω} P (x, y)h(y).

A constant function is harmonic. Theorem. A harmonic function of an irreducible Markov chain is constant. Proof.

Exercise: prove that one-way-connectivity is enough. Theorem. The stationary distribution of an irreducible Markov chain is unique. Proof. rank of P_{I} is n − 1 because the dimension of {h|(P − I)h = 0} is 1. Therefore the dimension of {π|π(P − I) = 0} must also be 1.

Again, one-way-connectivity is enough.

What happens if the chain is not irreducible? Definition. x→y if there is a directed path from x to y, i.e. ∃t ≥ 0P^{t}(x, y) > 0. Definition. x↔y if x→y and y→x. Exercise. prove that ↔ is an equivalent relation.

The chain is irreducible iff there only 1 equivalent class. Otherwise, we get a Directed Acyclic Graph (DAG) of equivalent classes, where C→D if there are x ∈ C and y ∈ D such that P (x, y) > 0. Alternative definition with x→y yields the corresponding transitive closure. This graph is called the communication graph (relation, classes, etc.). Exercise. prove it’s a DAG.

No matter where the chain is started, it will eventually find itself in one of the leaves of this DAG. Then, it will stay on this leaf forever, and will be an irreducible chain there. If there’s only 1 leaf then the stationary distribution there is the unique stationary distribution of the whole chain. If there’s more then one leaf, then there’s more then one stationary distribution, one for each leaf (and their convex combinations).

If we start the chain at some vertex, x, what is the probability it’ll end at a specific leaf? Denote this probability f(x). Note that this is a function of the state, not the communication class.

Theorem. f is an harmonic function.

Proof. straightforward.

So we see that harmonic functions are not just a technical tool, they represent something significant.