Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 38 ยท Markov Chain Monte Carlo

Markov Chains for Sampling

Understand transition matrices, stationary distributions and detailed balance, the ideas that let a Markov chain sample from any target distribution.

Every method so far drew independent samples. That works when you can sample directly from your target distribution, or can find a good proposal for importance sampling. But what if the target lives in 500 dimensions, or you know its density only up to an unknown constant? Then independent sampling is usually hopeless.

Markov chain Monte Carlo (MCMC) takes a different route. It builds a random walk, a Markov chain, that wanders through the space and spends time in each region in proportion to the target probability. The samples are dependent, but if the chain is built correctly, their long-run frequencies match the target. This lesson gives you the mathematics of that idea on a tiny example.

Markov chains and transition matrices

A Markov chain is a sequence of random states Xโ‚€, Xโ‚, Xโ‚‚, โ€ฆ where the next state depends only on the current one. For a finite set of states, all the rules fit in a transition matrix P, where P[i][j] is the probability of moving from state i to state j. Each row sums to 1.

If ฯ€ is a row vector of probabilities over the states, one step of the chain turns it into ฯ€P. A distribution is stationary when one step leaves it unchanged:

Text
ฯ€ P = ฯ€

A chain that is irreducible (every state can reach every other) and aperiodic (it does not cycle with a fixed period) has exactly one stationary distribution, and no matter where it starts, the distribution of Xโ‚™ converges to it. This is the ergodic theorem, and it also says that the fraction of time spent in each state converges to ฯ€.

flowchart LR
  A["State 1"] -->|0.3| B["State 2"]
  B -->|0.2| C["State 3"]
  C -->|0.3| B
  A -->|0.2| C
  B -->|0.2| A
  C -->|0.1| A

Part of a three-state chain; self-loops are not drawn.

Watching a chain find its stationary distribution

We simulate a three-state chain for 100,000 steps and compare the visit frequencies with the left eigenvector of P for eigenvalue 1.

Python Simulate a chain and compare with the eigenvector

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.

Notice that every row of Pโตโฐ is (almost exactly) the same vector, the stationary distribution: after many steps the starting state no longer matters.

Detailed balance: designing a chain for a target

For MCMC you do the reverse. You are given the target ฯ€ and must build a chain whose stationary distribution is ฯ€. Checking ฯ€P = ฯ€ directly is hard, but there is a simple sufficient condition, detailed balance (also called reversibility):

Text
ฯ€_i ยท P[i][j] = ฯ€_j ยท P[j][i]   for all i, j

In words: at equilibrium the flow of probability from i to j equals the flow from j to i. Summing over i gives ฯ€P = ฯ€, so any chain satisfying detailed balance has ฯ€ as a stationary distribution.

The Metropolis rule produces such a chain. From state i, propose a state j with a symmetric probability (Q[i][j] = Q[j][i]), then accept it with probability min(1, ฯ€_j / ฯ€_i); otherwise stay at i. Notice that only the ratio ฯ€_j/ฯ€_i is needed, so any unknown normalizing constant cancels. That is the whole secret of MCMC.

Python Build a Metropolis chain for a target and check 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.

You should see ฯ€P = ฯ€ and a symmetric flow matrix. The chain was built from the target and a simple proposal alone.

Detailed balance is sufficient, not necessary: some good samplers are not reversible. But almost all classic algorithms (Metropolis, Metropolis-Hastings, Gibbs with random scan) are.

What goes wrong

  • Not irreducible. If the proposal can never reach part of the space, the chain never visits it.
  • Slow mixing. The chain converges, but takes very long to forget its start or to cross between regions of high probability.
  • Dependence. Consecutive samples are correlated, so N draws carry less information than N independent ones. You will measure this in MCMC diagnostics.

The next lesson turns the Metropolis idea into the general Metropolis-Hastings algorithm for continuous targets.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A stationary distribution pi of a transition matrix P satisfies:

    Stationary means one step of the chain leaves the distribution unchanged: pi P = pi.
  2. 2. Detailed balance means:

    The flow from i to j equals the flow from j to i. It implies pi P = pi.
  3. 3. Why is the Metropolis rule useful when the target density has an unknown normalizing constant?

    The acceptance probability depends on pi_j / pi_i, where any common constant cancels.
  4. 4. Samples from an MCMC chain are:

    Each sample depends on the previous one; the ergodic theorem guarantees correct long-run averages.

Summary

  • A Markov chain moves according to a transition matrix; its stationary distribution ฯ€ satisfies ฯ€P = ฯ€.
  • Irreducible, aperiodic chains converge to a unique ฯ€ from any start (ergodic theorem).
  • Detailed balance ฯ€_i P_ij = ฯ€_j P_ji is an easy way to guarantee a chain has the target ฯ€.
  • The Metropolis rule builds such a chain from the ratio ฯ€_j/ฯ€_i, so the normalizing constant is never needed.

Next: Metropolis-Hastings