Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 36 ยท Stationary Distributions and Mixing

Reversibility and Detailed Balance

Learn detailed balance and reversible Markov chains: a shortcut for stationary distributions, birth-death chains and the Metropolis algorithm, checked in Python.

Solving ฯ€ P = ฯ€ for a big chain means solving a big linear system. For many important chains there is a shortcut: a stronger condition, called detailed balance, that is easy to check and that implies stationarity. It also explains why some chains look the same when you play the movie backwards, and it is the engine of the Metropolis algorithm that powers much of modern statistics.

Detailed balance

A probability vector ฯ€ and a transition matrix P satisfy detailed balance if

Text
ฯ€_i p_ij = ฯ€_j p_ji      for all states i, j

Interpretation: in equilibrium, the probability flow from i to j equals the flow from j back to i. Not just the total flow into each state balances (that is ฯ€ P = ฯ€), but the flow between every pair of states balances.

Detailed balance implies stationarity. Sum the equation over i:

Text
ฮฃ_i ฯ€_i p_ij = ฮฃ_i ฯ€_j p_ji = ฯ€_j ฮฃ_i p_ji = ฯ€_j

which is ฯ€ P = ฯ€. A chain with such a ฯ€ is called reversible: if it starts from ฯ€, then the sequence X_0, X_1, ..., X_n has the same distribution as X_n, ..., X_1, X_0. Run the movie backwards and you cannot tell.

The converse is false: a chain can have a stationary distribution without detailed balance. The weather chain is an example. Its stationary distribution is (21, 13, 12)/46, but ฯ€_S p_SC = 21 ร— 0.2 / 46 differs from ฯ€_C p_CS = 13 ร— 0.3 / 46.

Python Test detailed balance

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.

Birth-death chains are always reversible

A birth-death chain moves only to a neighboring state: from i to i + 1 with probability p_i, to i - 1 with probability q_i, or stays. Queues (arrivals and departures), populations and the gambler's fortune are of this type. Because the only transitions are between neighbors, detailed balance only involves neighboring pairs, and it gives a recursion:

Text
ฯ€_(i+1) = ฯ€_i ร— p_i / q_(i+1)

So ฯ€_i โˆ (p_0 p_1 ... p_(i-1)) / (q_1 q_2 ... q_i): multiply the ratios and normalize.

flowchart LR
    s0((0)) -->|"p0"| s1((1))
    s1 -->|"q1"| s0
    s1 -->|"p1"| s2((2))
    s2 -->|"q2"| s1
    s2 -->|"p2"| s3((3))
    s3 -->|"q3"| s2

A birth-death chain: only neighboring moves, so flow balance holds edge by edge.

Python Stationary distribution of a birth-death chain by the product formula

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 queue is short most of the time: since down-moves are more likely than up-moves, ฯ€_i decays geometrically.

The Metropolis algorithm: building a chain with a chosen ฯ€

Reversibility lets us run the problem backwards: given a target distribution ฯ€, design a chain that has it as stationary distribution. This is the idea of Markov chain Monte Carlo (MCMC). The Metropolis rule:

  1. From state i, propose a neighbor j using a symmetric rule (proposal(i โ†’ j) = proposal(j โ†’ i)).
  2. Accept the move with probability a_ij = min(1, ฯ€_j / ฯ€_i); otherwise stay at i.

Then ฯ€_i p_ij = ฯ€_i ร— prop ร— min(1, ฯ€_j / ฯ€_i) = prop ร— min(ฯ€_i, ฯ€_j), which is symmetric in i and j. Detailed balance holds, so ฯ€ is stationary. Note that you only need ฯ€ up to a constant, since the ratio ฯ€_j / ฯ€_i cancels it. That is why MCMC works for distributions whose normalizing constant is unknown.

Python Metropolis chain for the target (1, 2, 3, 4, 5) / 15

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 chain only ever used ratios of target weights, yet the frequencies reproduce the target distribution.

Time reversal in general

Even if a chain is not reversible, its time reversal under stationarity is another Markov chain with matrix p*_ij = ฯ€_j p_ji / ฯ€_i. A chain is reversible exactly when P* = P. This shows that detailed balance is the statement that the chain is equal to its own reversal.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Detailed balance says...

    The equilibrium flow from i to j equals the flow from j to i, for every pair.
  2. 2. If ฯ€ satisfies detailed balance with P, then...

    Summing detailed balance over i gives ฮฃ_i ฯ€_i p_ij = ฯ€_j, i.e. ฯ€ P = ฯ€.
  3. 3. In a birth-death chain, how does ฯ€_(i+1) relate to ฯ€_i?

    Detailed balance for neighbors: ฯ€_i p_i = ฯ€_(i+1) q_(i+1).
  4. 4. Why does the Metropolis algorithm only need the target distribution up to a constant?

    The acceptance probability min(1, ฯ€_j/ฯ€_i) uses only ratios, so unknown normalizing constants cancel.

Summary

  • Detailed balance ฯ€_i p_ij = ฯ€_j p_ji implies ฯ€ P = ฯ€; chains with it are reversible.
  • Reversible stationary processes look the same forward and backward in time.
  • Birth-death chains are always reversible: ฯ€_(i+1) = ฯ€_i p_i / q_(i+1).
  • The Metropolis rule builds a reversible chain with any desired target distribution; this is the basis of MCMC.

Next: The Poisson Process: Counting Random Events in Time