Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 36 ยท Stationary Distributions and Mixing

The Convergence Theorem and the Ergodic Theorem

Why ergodic chains forget their start: the convergence theorem, the ergodic theorem for time averages and the mean return time 1/pi, tested in Python.

Now the payoff. For an ergodic chain (irreducible and aperiodic) two things hold. The distribution of X_n converges to the stationary distribution ฯ€, no matter where the chain started. And the fraction of time the chain spends in each state converges to ฯ€ as well. One theorem is about snapshots, the other about a long movie. Together they justify using stationary distributions as predictions.

The convergence theorem

Theorem. Let P be the transition matrix of a finite ergodic chain with stationary distribution ฯ€. Then for every pair of states i, j,

Text
p_ij^(n) โ†’ ฯ€_j      as n โ†’ โˆž

In matrix terms, P^n converges to a matrix whose every row equals ฯ€. The chain forgets its starting state. Moreover the convergence is geometric: the error shrinks like c r^n for some r < 1 (the next lesson shows r is the second-largest eigenvalue modulus).

Python Different starting states, same limit

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 largest error drops by roughly a constant factor each step. That is geometric convergence. By n = 30 all three rows agree with ฯ€ to many decimals.

The theorem needs aperiodicity. The flip chain is irreducible with stationary distribution (1/2, 1/2), but P^n alternates between the identity and the flip matrix forever. It needs irreducibility too: with two closed classes, the limit depends on the start.

The ergodic theorem

The convergence theorem speaks about the probability at one fixed large time. The ergodic theorem concerns a single long trajectory. Let V_j(n) be the number of visits to j up to time n. For an irreducible positive-recurrent chain, with probability 1,

Text
V_j(n) / n โ†’ ฯ€_j      as n โ†’ โˆž

More generally, for any function f on the states,

Text
(1/n) ฮฃ_(k=0)^(n-1) f(X_k) โ†’ ฮฃ_i ฯ€_i f(i)      with probability 1

The time average along one path equals the space average over ฯ€. Notice that this does not require aperiodicity: even a periodic irreducible chain spends the right fraction of time in each state. This is the Markov chain version of the law of large numbers.

An example: long-run average reward

Suppose a stall earns 10 dollars on sunny days, 5 on cloudy days and 0 on rainy days. The long-run average daily income is

Text
ฮฃ_i ฯ€_i f(i) = (21 ร— 10 + 13 ร— 5 + 12 ร— 0) / 46 = 275 / 46 โ‰ˆ 5.978 dollars per day
Python Time average of a reward along one long path

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.

Mean return times

How long does it take, on average, to come back to a state? If the chain is in state j now, the expected number of steps until its next visit to j is the mean return time m_j. The surprising and beautiful link:

Text
m_j = 1 / ฯ€_j

This makes sense: if the chain is in state j a fraction ฯ€_j of the time, then visits to j come on average every 1/ฯ€_j steps. For the weather chain, m_R = 46/12 โ‰ˆ 3.83 days between rainy days (counting from a rainy day to the next one).

Python Check m_j = 1 / pi_j by simulation

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.

Putting it together

flowchart TD
    A["Finite chain"] --> B{"irreducible?"}
    B -- no --> C["limit depends on the start;<br/>classify classes first"]
    B -- yes --> D["unique stationary pi<br/>time averages โ†’ pi"]
    D --> E{"aperiodic?"}
    E -- no --> F["distribution oscillates"]
    E -- yes --> G["distribution of X_n โ†’ pi<br/>(ergodic)"]

What each property buys you.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. For a finite ergodic chain, p_ij^(n) converges (as n grows) to...

    Every row of P^n converges to ฯ€, so the limit depends only on the target state j.
  2. 2. The ergodic theorem says (1/n) ฮฃ f(X_k) converges to...

    Time averages along a path converge to the average of f under the stationary distribution.
  3. 3. If ฯ€_j = 0.25, the mean return time to state j is...

    m_j = 1/ฯ€_j = 4.
  4. 4. Which condition is NOT needed for the distribution of X_n to converge to ฯ€?

    The limit is the same for every starting state; that is the point of the theorem.

Summary

  • Convergence theorem: finite ergodic chains have P^n โ†’ 1ฯ€ (every row ฯ€), geometrically fast.
  • Ergodic theorem: time averages along one path converge to ฮฃ ฯ€_i f(i), which also needs only irreducibility.
  • Mean return time to state j is 1/ฯ€_j.
  • Periodicity breaks convergence of ฮผ_n but not time averages.

Next: Mixing Time and Total Variation Distance