Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 36 ยท MCMC and Sampling

Why MCMC? Sampling from Posteriors

Understand why Bayesian models need MCMC: Monte Carlo integration, rejection sampling, the curse of dimensionality and Markov chains with a stationary distribution, with Python.

Conjugate models are lovely, but most real models are not conjugate. A logistic regression, a hierarchical model with several levels, or a mixture has a posterior with no closed form, and its normalizing constant is an integral nobody can do by hand. The modern answer is to sample from the posterior instead of writing it down. This lesson explains why sampling works and builds up to Markov chain Monte Carlo (MCMC).

Monte Carlo: answers by counting

Suppose you can draw samples ฮธโ‚ โ€ฆ ฮธ_N from the posterior. Then:

  • The posterior mean is the average of the draws.
  • P(ฮธ > 0.5) is the fraction of draws above 0.5.
  • Quantiles and intervals come from sorted draws.
  • Any function of the parameters (a ratio, a difference) is the function applied to each draw.

The error of such an estimate shrinks like 1/โˆšN, regardless of how many parameters there are. That independence from dimension is what makes Monte Carlo attractive.

Python Monte Carlo estimates of a known posterior

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 estimates settle on the truth as N grows. We just need a way to produce the draws when the posterior is only known up to a constant.

The unnormalized target

Recall posterior โˆ likelihood ร— prior. We can always compute that right-hand side, called the unnormalized posterior (or its log). What we cannot easily compute is the normalizing integral. Good samplers only need the unnormalized density, because the unknown constant cancels in ratios.

Rejection sampling

A simple sampler: pick a proposal distribution q and a constant M with M q(ฮธ) โ‰ฅ target(ฮธ) everywhere. Draw ฮธ from q, then accept it with probability target(ฮธ) / (M q(ฮธ)). The accepted draws follow the target.

Python Rejection sampling from an unnormalized density

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 samples reproduce Beta(4, 3) without ever computing its normalizing constant. Rejection sampling works in one or two dimensions but fails in high dimensions: the proposal box becomes enormously larger than the region where the target has mass, so almost everything is rejected.

Python Why rejection fails in high dimensions

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 acceptance rate collapses exponentially with dimension. We need a smarter way to explore: stay near the probable region and wander through it.

Markov chains

A Markov chain is a sequence of values where each next value depends only on the current one, ฮธ_{t+1} ~ P(ยท | ฮธ_t). Under mild conditions, run it long enough and the fraction of time it spends in each region converges to a fixed stationary distribution, whatever the starting point.

The MCMC idea: design a chain whose stationary distribution is the posterior, then run it and treat the visited states as (correlated) draws from the posterior.

flowchart LR
    A["Start anywhere"] --> B["Propose a move"]
    B --> C{"Accept?"}
    C -->|"yes"| D["Move to new value"]
    C -->|"no"| E["Stay put"]
    D --> B
    E --> B

The core loop of every MCMC sampler; the rules for accepting decide the stationary distribution.

A chain that finds its stationary distribution

Here is a three-state weather chain, with transition probabilities in a matrix. Starting from "sunny" or from "rainy", it ends up spending the same fraction of time in each state.

Python Stationary distribution of a Markov chain

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.

All three give the same distribution: the starting state is forgotten. MCMC samplers are chains of this kind, built so that the long-run distribution is your posterior.

What to expect from MCMC

  • Correlated draws: consecutive samples are similar, so 10,000 draws carry less information than 10,000 independent ones (measured by the effective sample size).
  • Warm-up (burn-in): early draws still remember the starting point and are discarded.
  • Several chains: running chains from different starting points is how you detect a failure to converge.
  • Diagnostics are mandatory: you cannot see convergence in one number; you check it (MCMC Diagnostics).

The algorithms ahead

Algorithm Idea Lesson
Metropolis-Hastings Propose a random move, accept based on a density ratio next
Gibbs sampling Update one parameter at a time from its conditional Gibbs Sampling
Hamiltonian Monte Carlo / NUTS Use gradients to make long, informed moves used by PyMC and Stan

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does a Monte Carlo estimate get more accurate with more draws?

    Averages of N independent draws have standard error proportional to 1/sqrt(N).
  2. 2. What does a sampler need to know about the posterior?

    MCMC acceptance rules use density ratios, so the normalizing constant is never needed.
  3. 3. What is the stationary distribution of a Markov chain?

    After enough steps the chain's state distribution settles to a fixed distribution; MCMC makes this the posterior.
  4. 4. Why does rejection sampling fail in high dimensions?

    The acceptance rate falls exponentially with dimension.

Summary

  • Draws from the posterior turn integrals into averages; the error shrinks as 1/โˆšN independent of dimension.
  • Samplers need only the unnormalized posterior.
  • Rejection sampling is simple but breaks down in high dimensions.
  • A Markov chain forgets its start and converges to a stationary distribution; MCMC engineers that distribution to be the posterior.
  • MCMC draws are correlated, need warm-up, several chains and diagnostics.

Next: Metropolis-Hastings