Sampling with Metropolis-Hastings

Draw samples from a distribution you can only evaluate up to a constant, using a random walk with an accept-reject rule.

The problem it solves

Often you know a probability density p(x) only up to normalization - you can compute p(x) but not the integral that scales it. Metropolis-Hastings builds a Markov chain whose stationary distribution is exactly p, using only ratios where the unknown constant cancels.

The algorithm

• Propose a move x' from the current x (e.g. a Gaussian step).
• Compute the acceptance ratio a = p(x')/p(x) (for a symmetric proposal).
• Accept x' with probability min(1,a); otherwise stay at x.
• Record the current state and repeat.

import numpy as np
target=lambda x: np.exp(-0.5*x*x)     # unnormalized N(0,1)
x=0.0; samples=[]
for i in range(100000):
    xp=x+np.random.randn()*1.0
    if np.random.rand()<target(xp)/target(x): x=xp
    samples.append(x)
s=np.array(samples[1000:])            # drop burn-in
print(round(s.mean(),3), round(s.std(),3))  # ~0, ~1

Practical concerns

The step size must be tuned: too small and the chain crawls with high autocorrelation; too large and most proposals are rejected. An acceptance rate near 0.234 is a rule of thumb for high-dimensional targets. Early samples are discarded as burn-in while the chain forgets its starting point.

Where it matters

Metropolis-Hastings underpins Bayesian inference, statistical mechanics simulations, and any setting where the posterior or Boltzmann distribution is known only up to a constant. Modern samplers like Hamiltonian Monte Carlo refine the proposal to explore faster, but the accept-reject core is the same.