Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 38 · Markov Chain Monte Carlo

The Metropolis-Hastings Algorithm

Build the Metropolis-Hastings sampler from scratch: proposals, the acceptance ratio, step-size tuning and a bimodal example you can run.

The Metropolis-Hastings (MH) algorithm is the workhorse of MCMC. Given any target density p(x) that you can evaluate up to a constant, it produces a Markov chain whose long-run distribution is p. It needs only three ingredients: a way to evaluate p̃(x) ∝ p(x), a proposal distribution to suggest moves, and a random number generator. You will implement it in about ten lines.

The algorithm

Start at some x. At each step:

  1. Propose a new point x′ from a proposal density q(x′ | x).
  2. Compute the acceptance probability:
Text
α = min( 1,  [ p̃(x′) · q(x | x′) ] / [ p̃(x) · q(x′ | x) ] )
  1. Accept with probability α: set the next state to x′. Otherwise reject: the next state is x again (the repeat is a real sample and must be kept).

If the proposal is symmetric, q(x′|x) = q(x|x′) (for example x′ = x + Normal(0, s²), called a random-walk Metropolis sampler), the q terms cancel and α = min(1, p̃(x′)/p̃(x)). Moves uphill are always accepted; moves downhill are accepted with probability equal to the density ratio.

Why does it work? The acceptance rule makes p̃(x) q(x′|x) α(x → x′) symmetric in x and x′, which is detailed balance (see Markov chains for sampling).

Work with log densities. Accept when log(u) < log p̃(x′) − log p̃(x) with u uniform. This avoids numerical underflow when densities are tiny.

A bimodal target

Our target is a mixture of two normals: weight 0.3 on N(−2, 0.7²) and weight 0.7 on N(2, 1²). We run 20,000 steps and overlay the histogram on the true density.

Python Random-walk Metropolis for a two-peak target

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.

We discarded the first 2,000 steps as burn-in, the stretch before the chain has reached the high-probability region. The sample mean should land near 0.8, the true mean of the mixture.

Tuning the step size

The proposal width s is the knob that matters:

  • Too small: nearly every proposal is accepted, but each move is tiny. The chain crawls and may never cross between the two peaks.
  • Too large: most proposals land in low-density areas and are rejected. The chain sticks in place.
  • Just right: a moderate acceptance rate and fast exploration.

A well-known guideline from theory for Gaussian-like targets: about 44% acceptance in one dimension, falling toward 23% in high dimensions. Treat these as rough targets, not laws.

Python Step size, acceptance rate and mixing

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 starts at −2, in the smaller peak. With a tiny step the acceptance rate is almost 1 and the lag-1 autocorrelation is almost 1: successive samples are nearly identical, and the chain crosses the valley between the peaks only by a slow random drift. Its estimate of the mean therefore depends heavily on the seed and on how long you run it. A high acceptance rate alone does not prove a chain is working; look at autocorrelation too. Very large steps fail the other way: the acceptance rate collapses and the chain sticks.

General proposals

For a non-symmetric proposal you must include the correction q(x|x′)/q(x′|x). A classic example is sampling a positive variable by proposing x′ = x · exp(s·Z); this is not symmetric in x, so the ratio of proposal densities does not cancel. Independence samplers (q does not depend on x) are a special case that looks like importance sampling with an accept/reject step.

Never throw away rejected proposals by skipping the step. A rejection means "stay where you are", and that repeated value must appear in the output. Dropping them biases the sample toward whichever areas are hard to leave.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In random-walk Metropolis the acceptance probability is:

    With a symmetric proposal the q terms cancel, leaving min(1, p~(x')/p~(x)).
  2. 2. What should the chain do when a proposal is rejected?

    A rejection means the chain stays put. The repeated value counts as a sample.
  3. 3. A very small step size produces:

    Tiny moves are almost always accepted but barely change the state, so the chain crawls.
  4. 4. Why is burn-in discarded?

    Until the chain reaches the target's high-probability region, its draws are not representative.

Summary

  • MH proposes x′ ~ q(·|x) and accepts with α = min(1, p̃(x′)q(x|x′) / (p̃(x)q(x′|x))); rejection repeats x.
  • Only an unnormalized density is needed, and symmetric proposals make the q terms cancel.
  • Use log densities, discard a burn-in, and tune the step size (rough targets: about 44% acceptance in 1-D, 23% in many dimensions).
  • A good-looking acceptance rate does not prove good mixing; check the trace and autocorrelation.

Next: Gibbs Sampling