MCMC & the Metropolis Algorithm

Imagine you want to know the average height of a mountain range — but you can only take measurements at random spots, and the range is so vast and jagged that you cannot compute the average analytically. You wander around, spending more time in the tall regions and less in the valleys, and eventually your sample reflects the shape of the terrain. That wandering is, in essence, Markov Chain Monte Carlo.

MCMC is a family of algorithms for sampling from a probability distribution when direct calculation is impossible. The workhorse is the Metropolis algorithm, invented in 1953 by Nicholas Metropolis, Arianna Rosenbluth, Marshall Rosenbluth, Augusta Teller, and Edward Teller while simulating the thermodynamics of hard-sphere molecules. Decades later it was recognized as one of the ten most important algorithms of the twentieth century.

The core insight is disarmingly simple: you do not need to know everything about a distribution to sample from it. You only need to compare relative probabilities — is the proposed next state more or less likely than the current one? That ratio is almost always easy to compute, even when the normalizing constant (the total area under the curve) is completely intractable.

This single trick unlocks Bayesian inference, statistical physics, molecular dynamics, and modern machine learning. It is solved algorithmically — the Metropolis–Hastings algorithm is proven to converge to the correct distribution in the limit — but the practical challenge of mixing time (how long the walk must run before its samples are trustworthy) remains an active research frontier.

The target distribution below has two peaks — a mixture of two Gaussians. A naive approach would require computing the normalizing constant; the Metropolis algorithm ignores it entirely.

Press Run to start the random walk. At each step a candidate position is proposed; if it is more likely than the current position it is always accepted; if less likely it is accepted with probability proportional to how much less likely it is. The histogram below the canvas shows where the walk has spent its time.

<div class="controls">
  <label>{{lbl_step_size}} <span id="stepVal">1.0</span>
    <input type="range" id="stepSize" min="0.1" max="4" step="0.1" value="1.0">
  </label>
  <button id="runBtn" type="button">{{btn_run}}</button>
  <button id="stepBtn" type="button">{{btn_step}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
  <span class="stat">{{lbl_samples}} <b id="nSamples">0</b> &nbsp; {{lbl_accept}} <b id="acceptRate">—</b></span>
</div>
<canvas id="canvas" width="560" height="200"></canvas>
<div id="histWrap"><canvas id="hist" width="560" height="120"></canvas></div>
<p class="hint">{{hint_text}}</p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem .8rem; margin-bottom: .5rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 90px; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stat { font-size: .83rem; color: #444; }
canvas { display: block; border-radius: 6px; background: #f4f7fa; width: 100%; height: auto; }
#histWrap { margin-top: 4px; }
.hint { font-size: .8rem; color: #555; margin: .4rem 0 0; line-height: 1.4; }

// Code not found

Notice how the walk occasionally tunnels from one peak to the other — hopping through the low-probability valley. The histogram converges toward the true target (shown as a curve). Too small a step size keeps the walk exploring only locally; too large a step size causes most proposals to overshoot low-probability regions and get rejected. Adjusting the step size slider reveals this tradeoff in real time.

The Metropolis algorithm is proven correct: run it long enough and the fraction of time spent near any point converges to that point's probability under the target distribution. This follows from the theory of ergodic Markov chains — chains that eventually reach every state and do not get trapped in cycles.

But "long enough" hides the difficulty:

• Mixing time is the number of steps needed before the chain's distribution is close (in total variation distance) to the stationary distribution. For well-behaved, unimodal distributions this is polynomial in the dimension. For multimodal distributions separated by low-probability barriers, mixing can take exponentially long — the chain is stuck in one peak for an astronomically long time before accidentally crossing the valley.
• Spectral gap: the speed of mixing is governed by the second-largest eigenvalue of the chain's transition matrix. A small spectral gap means slow mixing. Computing this gap is hard in general.
• Dimension curse: in high dimensions, typical random-walk proposals land in low-probability regions almost always, so acceptance rates collapse. Algorithms like Hamiltonian Monte Carlo (HMC) use gradient information to make smarter proposals, keeping acceptance rates healthy even in hundreds of dimensions. HMC underlies modern probabilistic programming systems like Stan and PyMC.
• No free lunch: there is no universal fast sampler. Deciding whether a given Markov chain mixes in polynomial time is related to questions about counting complexity (the #P class) and remains open in general.

The status is therefore nuanced: Metropolis–Hastings is solved as an algorithm (it converges), but efficient sampling from arbitrary distributions is not — it can require exponential time in the worst case, and proving that a specific chain mixes fast is often a hard open problem.

MCMC's ability to sample from any distribution whose unnormalized density can be evaluated makes it indispensable across science and engineering:

• Bayesian inference: posterior distributions in statistical models almost never have closed forms. MCMC is the standard engine for approximate Bayesian computation — from simple regressions to hierarchical models with thousands of parameters.
• Molecular dynamics and protein folding: simulating how atoms explore energy landscapes to find stable configurations. The original Metropolis paper was literally about molecules.
• Ising model and statistical physics: simulating phase transitions in magnets and lattice models — exactly the setting where the algorithm was born.
• Image reconstruction: in medical imaging (MRI, CT), reconstructing an image from noisy measurements is a Bayesian problem; MCMC explores the space of plausible images.
• Probabilistic machine learning: variational inference and Monte Carlo gradient estimators underpin modern deep learning. Even the training of diffusion models (the backbone of generative image AI) is intimately connected to Langevin dynamics — a continuous-time cousin of Metropolis.
• Phylogenetics: inferring evolutionary trees from DNA sequence data is done almost exclusively with MCMC (the MrBayes and BEAST programs).

In each case the pattern is the same: the space of possibilities is too vast to enumerate, but relative probabilities are easy to compute. The random walk does the rest.

The Metropolis algorithm is one of the great algorithmic ideas of the twentieth century: a random walk that needs only relative probabilities, yet provably converges to sample from any target distribution. It turned intractable integrals into tractable simulations overnight, and the applications have never stopped growing.

The catch is mixing time — the walk must wander long enough to explore the full distribution, and in the worst case that takes exponentially long. Modern variants like Hamiltonian Monte Carlo and Langevin dynamics add gradient information to speed the exploration, but the fundamental tension between correctness and efficiency remains unsolved in general.

If you have encountered Bayesian inference or wondered how generative AI models explore their parameter spaces, you have brushed against MCMC. The random walk is everywhere — and it still has secrets left to give up.