Sketch · 2026-08-31
Metropolis-Hastings, wandering a 2D target.
A random walker sits on the plane. At every step it proposes a small Gaussian jump. If the new spot is denser under the target it moves, otherwise it flips a biased coin. The sampler never sees the normalising constant. The amber trail that remains matches the target density up to it.
Warm-up of 200 rejected draws is discarded before the trace starts
The rule
The chain sits at a state x. Draw a proposal x' by adding a Gaussian nudge of scale σ. Compute the ratio of densities and accept with probability
α = min(1, p(x') / p(x))If a uniform draw beats α, stay put and record x again. Repeat. Detailed balance guarantees the chain is stationary under p, so after a burn-in the histogram of visits converges to p up to the constant you never had to compute. The Gaussian proposal is symmetric, which is why the ratio collapses to p(x')/p(x) with no proposal term.
Step size
σ trades exploration against acceptance. Too small and the chain crawls, staying close to itself and taking forever to reach the other lobe of the mixture. Too large and almost every proposal lands in low-density territory and gets rejected, so the chain barely moves either. The empirical sweet spot for a random-walk Metropolis on a smooth 2D target is roughly 20 to 45 percent acceptance; below that you are wasting draws, above it you are wasting reach.
What to try
Start on Mixture at σ = 0.35. The chain settles on the nearer lobe first, then jumps across when a lucky proposal lands. Drop σ to 0.05 and the crossing rarely happens on a human timescale. Switch to Banana and watch the walker slide along the curved ridge; a step too large gets rejected off the ridge, a step too small takes forever to reach the tails. Ring shows how quickly the trace covers a thin manifold once it finds it.
Sources
- Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. & Teller, E. (1953). Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21(6), 1087–1092. The algorithm.
- Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1), 97–109. The generalisation to asymmetric proposals.
- Roberts, G. O., Gelman, A. & Gilks, W. R. (1997). Weak convergence and optimal scaling of random walk Metropolis algorithms. Annals of Applied Probability, 7(1), 110–120. Where the 23.4 percent optimal acceptance number comes from in high dimensions.