Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 36 ยท Stationary Distributions and Mixing

Irreducibility, Periodicity and Ergodicity

Learn why some chains never settle: the period of a state, aperiodic and ergodic chains, and a Python function that computes periods and tests ergodicity.

A stationary distribution exists for every finite chain, but the distribution of X_n does not always converge to it. A chain that flips deterministically between two states keeps oscillating forever. Convergence needs a condition that rules out such rhythm: aperiodicity. Together with irreducibility it defines the friendly class of ergodic chains.

A chain that never settles

Two states, and the chain always switches: P = [[0, 1], [1, 0]]. Starting at state 0, you are at 0 at even times and at 1 at odd times. The distribution ฮผ_n alternates between (1, 0) and (0, 1), so it has no limit. The stationary distribution is (1/2, 1/2), but the chain never approaches it.

Python A periodic chain oscillates

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 period of a state

The period of state i is

Text
d(i) = gcd { n >= 1 : p_ii^(n) > 0 }

the greatest common divisor of all possible return times. If no return is possible, the period is undefined. A state with d(i) = 1 is aperiodic.

Examples:

  • The flip chain: returns to a state are possible only after 2, 4, 6, ... steps, so d = 2.
  • A cycle 0 โ†’ 1 โ†’ 2 โ†’ 0: returns after 3, 6, 9, ... steps, so d = 3.
  • Any state with a self-loop (p_ii > 0) has d(i) = 1, because a return in 1 step is possible.

Period is a class property: all states in a communicating class share the same period. For an irreducible chain, we speak of "the period of the chain".

A useful sufficient condition: if an irreducible chain has any state with p_ii > 0, the chain is aperiodic.

flowchart LR
    A["Return times to state i"] --> B["gcd = 1<br/>aperiodic"]
    A --> C["gcd = d > 1<br/>periodic with period d"]

The period is the gcd of the possible return times.

Computing the period in Python

Check which n up to a bound have a positive return probability, then take the gcd.

Python Compute periods of four chains

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 mixed chain has return times 2 and 3, whose gcd is 1: it is aperiodic even though it has no self-loops. Different cycle lengths share only the divisor 1.

Ergodic chains

A finite chain is ergodic (some books say regular, which is equivalent in the finite case) if it is:

  1. irreducible: one communicating class, and
  2. aperiodic: period 1.

(For infinite chains, ergodic also requires positive recurrence.) An equivalent test for finite chains: some power P^m has all entries strictly positive. After m steps you can get from anywhere to anywhere.

Python Test ergodicity by looking for a strictly positive power

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 weather chain has all entries positive already at k = 1. The flip chain never gets there; the two-absorbing chain fails irreducibility.

Why bother?

For an ergodic chain, two big results hold, and you will prove or use them in the next lesson:

  • the distribution of X_n converges to the unique stationary distribution, whatever the starting state;
  • the long-run fraction of time spent in each state equals its stationary probability.

To make a periodic chain behave, make it lazy: at each step stay put with probability 1/2 and otherwise move as before. The lazy version (P + I)/2 has the same stationary distribution and is always aperiodic. Lazy chains are a standard trick in sampling algorithms.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the period of state i?

    The period is the greatest common divisor of all possible return times.
  2. 2. A state with a self-loop (p_ii > 0) has period...

    A return in one step is possible, and gcd(1, anything) = 1.
  3. 3. A finite chain is ergodic if it is...

    Ergodic = irreducible + aperiodic (+ positive recurrent, automatic in finite chains).
  4. 4. For the flip chain P = [[0,1],[1,0]], which statement is true?

    The chain is periodic with period 2, so its distribution oscillates even though the uniform distribution is stationary.

Summary

  • The period of a state is the gcd of its possible return times; aperiodic means period 1.
  • Period is a class property; a self-loop makes a state aperiodic.
  • Ergodic (finite) = irreducible and aperiodic; equivalently some power of P has all entries positive.
  • Periodic chains oscillate; lazy chains fix that.

Next: The Convergence Theorem and the Ergodic Theorem