Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 36 ยท Stationary Distributions and Mixing

Stationary Distributions

Find the stationary distribution of a Markov chain: the equation pi P = pi, three ways to solve it in Python, what it means and when it exists or is unique.

In the weather chain, the distribution of tomorrow's weather changed from day to day at first, but then settled down. After a week the probabilities barely moved. That limiting distribution is a stationary distribution: a probability vector that the chain does not change. Understanding it tells you what a chain does in the long run, and it is the foundation for algorithms such as PageRank and Markov chain Monte Carlo.

The definition

A probability vector ฯ€ = (ฯ€_1, ฯ€_2, ...) (non-negative entries summing to 1) is a stationary distribution (or invariant distribution) of the chain with matrix P if

Text
ฯ€ P = ฯ€

where ฯ€ is a row vector. If the chain starts with X_0 ~ ฯ€, then X_1 ~ ฯ€P = ฯ€, and X_2 ~ ฯ€ too, and so on. The chain is then a stationary process in the sense of Lesson 4: its distribution never changes with time.

In coordinates: ฯ€_j = ฮฃ_i ฯ€_i p_ij for every j. The probability flowing into j equals the probability already sitting at j. The equation is a balance equation.

Computing it: a worked example

For the weather chain with rows S = (0.7, 0.2, 0.1), C = (0.3, 0.4, 0.3), R = (0.2, 0.3, 0.5):

Text
ฯ€_S = 0.7 ฯ€_S + 0.3 ฯ€_C + 0.2 ฯ€_R
ฯ€_C = 0.2 ฯ€_S + 0.4 ฯ€_C + 0.3 ฯ€_R
ฯ€_R = 0.1 ฯ€_S + 0.3 ฯ€_C + 0.5 ฯ€_R
ฯ€_S + ฯ€_C + ฯ€_R = 1

The three balance equations are not independent (they add up to an identity), so you drop one and use the normalization ฮฃ ฯ€ = 1 instead. Solving by hand gives ฯ€ = (21, 13, 12) / 46, about (0.4565, 0.2826, 0.2609).

Three ways to get the same answer by computer:

  1. Solve the linear system ฯ€ (P - I) = 0 with the normalization.
  2. Find the left eigenvector of P for eigenvalue 1 (that is, an eigenvector of P^T), and scale to sum 1.
  3. Raise P to a large power: every row converges to ฯ€ (when the chain is nice, see the next lessons).
Python Three ways to find the stationary distribution

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.

What does it mean?

Two interpretations, both important:

  • Long-run proportion of time. For a well-behaved chain, ฯ€_i is the fraction of days the chain spends in state i over a very long time. In our weather chain, about 45.7 percent of days are sunny.
  • Equilibrium distribution. Start many independent chains with distribution ฯ€ and the proportions stay fixed, even though individual chains keep moving.
Python Time spent in each state converges to pi

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.

Existence and uniqueness

Chain type Stationary distribution
Finite, any chain at least one exists
Finite, irreducible exactly one, and ฯ€_i > 0 for all i
Finite with several closed classes several; any mix of the classes' own distributions works
Infinite, irreducible exists if and only if the chain is positive recurrent
Transient states ฯ€_i = 0 for every transient state

An example of non-uniqueness: take two absorbing states a and b. Then (1, 0) and (0, 1) are both stationary, and so is every mixture (w, 1 - w).

Python A chain with many stationary distributions

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.

A stationary distribution is not the same as a limiting distribution. A chain can have a unique stationary distribution but never converge to it (a periodic chain, see the next lesson). Stationary means "unchanged by one step"; limiting means "what ฮผ_n approaches".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A stationary distribution ฯ€ satisfies...

    ฯ€ is a row vector of probabilities with ฯ€P = ฯ€.
  2. 2. A finite irreducible chain has how many stationary distributions?

    Finite and irreducible guarantees existence and uniqueness, with every entry positive.
  3. 3. Why can you drop one balance equation when solving ฯ€ P = ฯ€?

    The columns of P - I add up to zero, so the equations are dependent; the normalization pins down the scale.
  4. 4. What is the stationary distribution of a chain with two absorbing states a and b and nothing else?

    Every mixture of the two point masses is unchanged by P.

Summary

  • ฯ€ is stationary if ฯ€ P = ฯ€, ฯ€_i >= 0 and ฮฃ ฯ€_i = 1.
  • Compute it by solving a linear system with normalization, by an eigenvector, or by a high matrix power.
  • It is the long-run fraction of time in each state for nice chains.
  • Finite irreducible chains have a unique stationary distribution; reducible chains can have many.

Next: Irreducibility, Periodicity and Ergodicity