Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 36 · MCMC and Sampling

Metropolis-Hastings

Write the Metropolis-Hastings sampler from scratch in Python: proposals, acceptance ratios, tuning the step size, burn-in and sampling a two-parameter posterior.

The Metropolis algorithm, invented in 1953 and generalized by Hastings in 1970, is the ancestor of nearly every MCMC method. It is short enough to write in a dozen lines, and writing it yourself is the best way to understand what sampling software does.

The idea

You want draws from a posterior π(θ) that you can evaluate only up to a constant. Start somewhere and repeat:

  1. Propose a new value θ* near the current θ, for example θ* = θ + Normal(0, s) (a random walk).
  2. Compute the acceptance ratio r = π(θ*) / π(θ).
  3. Accept the move with probability min(1, r). Otherwise stay at θ (and record it again).

If the proposed point is more probable you always move; if it is less probable you sometimes move, with chance equal to the density ratio. The chain therefore climbs toward high-probability regions but still visits the tails in the right proportion. The unknown normalizing constant cancels in r, which is why we only need the unnormalized posterior.

In code we use logs: accept if log u < log π(θ*) − log π(θ) where u is Uniform(0, 1).

A first sampler

Target: the posterior for a success probability after 14 successes in 60 trials with a Beta(2, 2) prior. We know the exact answer, Beta(16, 48), so we can check the sampler.

Python Random-walk Metropolis

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 sampler reproduces the exact posterior mean and standard deviation closely. Notice the pieces: a log target, a proposal, an accept/reject test, and a record at every step even when the move is rejected.

Warm-up (burn-in)

The chain starts at an arbitrary point (0.5 here), possibly far from where the posterior has mass. Early draws reflect that start. Dropping the first part is called warm-up or burn-in. Try starting far away to see why.

Python Starting far from the mass

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 walks from 0.95 down to the neighborhood of 0.25 in the first part of the run. Those early steps are not draws from the posterior, so we discard them.

Tuning the step size

The proposal width s controls efficiency.

  • Too small: nearly every move is accepted but each is tiny, so the chain explores slowly (high autocorrelation).
  • Too large: most proposals land in low-probability areas and are rejected, so the chain sticks in place.
  • Just right: for random-walk Metropolis a good acceptance rate is about 20% to 40% (about 23% in high dimensions, near 44% for one parameter).
Python Step size and acceptance rate

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 tiny step has high acceptance but extreme autocorrelation (close to 1), and the huge step has low acceptance. The middle values balance the two. Lag-1 autocorrelation is the correlation between a draw and the next; lower is better.

The Hastings correction

If the proposal is symmetric, q(θ*|θ) = q(θ|θ*) (as the normal random walk is), the proposal terms cancel. With an asymmetric proposal, for example one that proposes on a log scale, the acceptance ratio gets a correction:

r = [π(θ*) q(θ|θ*)] / [π(θ) q(θ*|θ)]

Forgetting this correction is a classic bug. When in doubt, use a symmetric proposal.

Two parameters: mean and standard deviation

With more than one parameter, propose a move in every coordinate. Here we infer μ and σ for normal data, working with log σ so the sampler is free to move on the whole real line (this transformation needs the Hastings/Jacobian care we discuss next).

Python Metropolis for (mu, log sigma)

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 log_sigma term is the Jacobian of the change of variable σ = exp(log σ). When you sample a transformed parameter, add the log of the absolute derivative so you still target the right posterior. The result agrees with the earlier grid answer for these data: μ near 5.25 and σ around 0.87.

Strengths and weaknesses

  • Strengths: easy to write, needs no gradients, works for any target you can evaluate.
  • Weaknesses: random walks explore slowly in high dimensions and in correlated or curved posteriors. Hamiltonian Monte Carlo (used by Stan and PyMC) fixes much of this with gradient information.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In random-walk Metropolis, a proposal with a higher posterior density than the current point is...

    The acceptance probability is min(1, r), and r is greater than 1 for a more probable point.
  2. 2. When a proposal is rejected, what is recorded for that iteration?

    The chain stays at the current value, and that repeated value is part of the sample.
  3. 3. A very small step size gives...

    Tiny moves are almost always accepted but barely change the state, so successive draws are highly correlated.
  4. 4. Why sample log(sigma) instead of sigma, and what must you add?

    An unconstrained parameter avoids invalid proposals, and the Jacobian keeps the target distribution correct.

Summary

  • Metropolis proposes a move and accepts it with probability min(1, π(θ*)/π(θ)); rejections repeat the current value.
  • Work with log densities; only the unnormalized posterior is needed.
  • Discard warm-up draws; tune the step size for roughly 20% to 40% acceptance.
  • Asymmetric proposals need the Hastings correction; transformed parameters need a Jacobian.
  • Random walks struggle in high dimensions, motivating Gibbs and Hamiltonian methods.

Next: Gibbs Sampling