Hamiltonian Monte Carlo and NUTS

Basic Metropolis-Hastings MCMC explores a posterior distribution by proposing a small random step and accepting or rejecting it — like a blindfolded person feeling their way around a room by shuffling randomly, only moving where the floor doesn't drop away. In low dimensions this eventually covers the space fine, but over, say, 20 correlated parameters, random shuffling wastes enormous numbers of steps wandering in place or getting rejected, since most random directions in high dimensions lead somewhere worse. Hamiltonian Monte Carlo (HMC) replaces the blind shuffle with something far more efficient: it uses the shape of the posterior (its gradient) to simulate a smooth trajectory that glides across high-probability regions the way a ball rolls across a landscape, using momentum instead of guesswork.

An analogy: a marble rolling on a hilly surface versus a blindfolded person groping around

Picture the negative log of the posterior density as a landscape of hills and valleys — low points are high-probability regions. A blind, random-shuffling sampler pokes around step by step, often stepping "uphill" into low-probability territory and getting rejected. HMC instead gives the sampler a marble and some momentum, simulating it physically rolling across the landscape according to the slope at every point — it naturally swoops through valleys and only slows climbing hills, covering long, sensible distances per move instead of tiny random hops. The No-U-Turn Sampler (NUTS) is a refinement that automatically decides how far to let the marble roll before it curves back on itself — exploring new territory and no longer, without a human hand-tuning trajectory length.

The maths, one symbol at a time

HMC augments the parameter $\theta$ (position) with an auxiliary momentum variable $p$, and simulates trajectories under Hamiltonian dynamics:

$$H(\theta, p) = -\log \pi(\theta) + \frac{1}{2} p^{\top} M^{-1} p$$

In words: $H$ (total "energy") sums a "potential energy" term, $-\log\pi(\theta)$, low where the posterior $\pi(\theta)$ is high (so the marble settles into high-probability valleys), plus a "kinetic energy" term from momentum $p$ that lets it carry speed through the landscape rather than crawling. The sampler alternates: draw a random momentum kick, simulate the marble's motion for several small steps by following the gradient of $\log\pi(\theta)$ (why HMC needs a differentiable model), then accept or reject the resulting $(\theta,p)$ based on how well energy was conserved along the path. NUTS automates the trajectory length, stopping once the path would start doubling back on itself (a "U-turn"), so both wasteful loops and wasteful short hops are avoided automatically.

Worked example 1: why gradient information beats random shuffling

Consider a posterior that's a narrow, elongated ridge — highly correlated parameters, like two regression coefficients that trade off against each other. A random-walk Metropolis sampler proposing isotropic steps will mostly propose points off the ridge (rejected), since "most directions" in a narrow ridge point off it; an accepted move traveling any meaningful distance along the ridge can take hundreds of wasted proposals. HMC's gradient-following trajectory naturally curves to follow the ridge's shape, since the gradient of $\log\pi$ points along the direction of highest density change — a single HMC trajectory can traverse a distance along the ridge that would take a random-walk sampler orders of magnitude more steps to cover.

Worked example 2: NUTS avoiding a wasted long trajectory

Suppose an analyst manually tunes plain HMC's trajectory length to 50 steps, but the posterior is fairly compact in one region — after only 15 steps the trajectory has already looped back near its starting point, and continuing another 35 steps just retraces explored territory, wasting three-fifths of the computation. NUTS detects the U-turn automatically around step 15 and stops there, then repeats this adaptively for every draw — using long trajectories where the posterior geometry calls for them and short ones where it doesn't, with no manual tuning.

The explorer above shows gradient-following steps crawling toward a minimum on a loss surface — HMC uses the same underlying gradient information, but adds momentum so the trajectory glides through the landscape rather than creeping toward it one small step at a time.

What this means in practice

HMC and NUTS are the default samplers behind modern Bayesian software (Stan, PyMC, NumPyro) precisely because they scale to the dozens or hundreds of correlated parameters typical of real factor models, hierarchical models, and Bayesian neural networks — where plain Metropolis-Hastings would need impractically many iterations to converge (see MCMC convergence diagnostics). The tradeoff: HMC needs a differentiable log-posterior, ruling out discrete parameters unless handled separately.