Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 36 · Stationary Distributions and Mixing

Mixing Time and Total Variation Distance

Measure how fast a Markov chain forgets its start: total variation distance, mixing time, the second eigenvalue and the cycle walk example, computed in Python.

The convergence theorem says a chain reaches equilibrium eventually. In practice "eventually" is not enough: you want to know how long. A shuffled deck of cards, a sampling algorithm and a model of a population all need the number of steps after which the distribution is close to stationary. This number is the mixing time.

Measuring distance between distributions

For two probability distributions μ and ν on the same finite state space, the total variation distance is

Text
TV(μ, ν) = (1/2) Σ_i |μ_i - ν_i|  =  max over events A of |μ(A) - ν(A)|

It is a number between 0 (identical) and 1 (completely disjoint supports). The second form gives meaning: TV is the largest possible difference in the probability that any event happens, so if TV < 0.01, no question about the outcome can be answered with more than 1 percent difference.

Python Total variation distance in a few lines

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The distance to stationarity and mixing time

Let P^n(i, ·) be the distribution of X_n started at i. Define the worst-case distance at time n:

Text
d(n) = max_i TV( P^n(i, ·), π )

For an ergodic chain, d(n) decreases to 0. The mixing time with tolerance ε is

Text
t_mix(ε) = min { n : d(n) <= ε }

The convention ε = 1/4 is common, because getting from 1/4 to any smaller ε costs only a factor of about log(1/ε): roughly t_mix(ε) <= ⌈log2(1/ε)⌉ t_mix(1/4).

Python Mixing time of the weather chain

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On a log scale the curve is nearly a straight line: the error shrinks by a constant factor each step.

The role of eigenvalues

The transition matrix has eigenvalues 1 = λ_1 > |λ_2| >= |λ_3| >= ... for an ergodic chain. The eigenvalue 1 belongs to the stationary part; every other eigenvalue's power dies away. So P^n approaches its limit at the rate of the next largest eigenvalue modulus:

Text
d(n)  behaves like  C |λ_2|^n     for large n

The spectral gap is 1 - |λ_2|; a bigger gap means faster mixing. For reversible chains (next lesson) the relaxation time 1 / (1 - |λ_2|) is the natural time scale and bounds the mixing time from both sides up to a logarithmic factor.

Python Compare |lambda_2|^n with the measured distance

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After a few steps the ratio of successive distances settles near |λ_2|.

Slow and fast mixing: random walk on a cycle

Place m points on a circle. At each step the walker stays put with probability 1/2 (to avoid periodicity) and moves one point clockwise or counter-clockwise with probability 1/4 each. The stationary distribution is uniform, 1/m per point. How does the mixing time grow with m?

Python Mixing time of a lazy walk on a cycle

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Doubling the size of the circle multiplies the mixing time by about 4, so it grows like m². This matches the idea from the random walk: to forget its start, the walker must travel a distance of order m, and a random walk needs about m² steps to cover a distance m.

flowchart LR
    A["large spectral gap<br/>(small |λ_2|)"] --> B["fast mixing"]
    C["small gap<br/>(|λ_2| near 1)"] --> D["slow mixing<br/>(bottlenecks, long cycles)"]

Bottlenecks in the state diagram make |λ_2| close to 1.

Some chains show a cutoff: the distance stays near 1 for a long time, then drops to near 0 within a short window. Shuffling a deck of cards by riffle shuffles is the famous example. Mixing times tell you where that drop happens.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. TV(μ, ν) = (1/2) Σ |μ_i - ν_i| equals 1 when...

    Completely separate distributions are as far apart as possible, distance 1.
  2. 2. The mixing time t_mix(ε) is...

    It is the smallest time at which the worst-case total variation distance to π is at most ε.
  3. 3. A larger spectral gap 1 - |λ_2| means...

    The error shrinks like |λ_2|^n, so a smaller |λ_2| (larger gap) means faster decay.
  4. 4. For the lazy walk on a cycle of m points, doubling m multiplies the mixing time by about...

    Mixing time scales like m², so doubling m gives a factor of 4.

Summary

  • TV(μ, ν) = (1/2) Σ |μ_i - ν_i| measures how well two distributions can be told apart.
  • d(n) = max_i TV(P^n(i, ·), π); mixing time t_mix(ε) is the first n with d(n) <= ε.
  • Asymptotically d(n) decays like |λ_2|^n; the spectral gap measures speed.
  • A lazy random walk on a cycle of m points mixes in order m² steps.

Next: Reversibility and Detailed Balance