Gibbs Sampling

Imagine you want to draw random samples from a distribution over many variables — say, the joint state of all pixels in an image, or the topic assignments for every word in a document. Writing down the full distribution is one thing; drawing from it is quite another.

In high dimensions, the joint density is almost never something you can sample directly. Integration is intractable, and rejection sampling wastes nearly every candidate. You need a cleverer way in.

Gibbs sampling offers a surprising answer: instead of tackling the whole distribution at once, fix all variables but one and sample that one from its conditional. Then move to the next variable, and the next, cycling endlessly. The resulting sequence of states forms a Markov chain, and — under mild conditions — its long-run distribution converges to exactly the joint distribution you wanted.

Named for physicist J. Willard Gibbs and introduced into statistical computation by Stuart Geman and Donald Geman in 1984 in the context of image restoration, Gibbs sampling became the workhorse of Bayesian statistics and probabilistic machine learning. It is one of the clearest examples of how a hard global problem dissolves into a sequence of easy local ones.

Below is a correlated 2D Gaussian — a distribution where x and y are linked. Direct sampling would need the joint density; Gibbs sampling only ever needs the two conditionals: x given y, and y given x.

<div class="controls">
  <label>{{lbl_correlation}} <span id="rho-val">0.85</span>
    <input type="range" id="rho" min="-0.99" max="0.99" step="0.01" value="0.85">
  </label>
  <div class="btns">
    <button id="step-btn" type="button">{{btn_step}}</button>
    <button id="run-btn" type="button">{{btn_run}}</button>
    <button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<canvas id="canvas" width="420" height="300"></canvas>
<div class="info" id="info">{{msg_press_start}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .6rem; margin-bottom: .5rem; font-size: .9rem; }
label { display: flex; flex-direction: column; gap: .2rem; }
input[type=range] { width: 140px; cursor: pointer; }
.btns { display: flex; gap: .4rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f8fafc; display: block; }
.info { font-size: .85rem; color: #444; margin-top: .4rem; min-height: 1.3em; }

// Code not found

Press Step to take one Gibbs update (alternating x then y). Press Run to let it go. Each new dot is drawn from a 1D conditional — no joint density ever computed. Watch how the elongated cloud builds up from scratch, with early samples (lighter) leading the chain toward the dense region.

The burn-in phase (the chain wandering to the high-probability region) and mixing (how quickly the chain explores the full distribution) are the two central concerns of any MCMC method. Adjust the correlation slider to make sampling harder and watch mixing slow down.

Why does endlessly cycling one variable at a time actually converge to the right distribution? The answer comes from Markov chain theory.

• Detailed balance. Each Gibbs update satisfies a condition called detailed balance: transitions between any two states are balanced so that the target joint distribution is the stationary distribution of the chain. The chain is guaranteed to end up there.
• Ergodicity. If the chain can reach every part of the distribution from anywhere (irreducibility) and returns to states regularly (aperiodicity), convergence is guaranteed — these conditions usually hold when the conditionals have full support.
• Mixing time. Convergence is guaranteed, but speed is not. When variables are highly correlated, a single-coordinate update barely moves the chain — each step changes only one dimension while the other holds it back. This is called slow mixing. Near-deterministic relationships between variables can trap the chain for exponentially many steps.
• Block Gibbs. A classic fix is to group correlated variables and sample them jointly in one block, eliminating the internal bottleneck. The trade-off is that sampling the block may itself be hard.

Gibbs sampling has no formal NP-hard barrier of its own — the per-step cost is polynomial as long as the conditionals are easy to sample. But mixing can be exponentially slow, and distinguishing "converged" from "just stuck" is undecidable in general. In practice, practitioners run multiple chains from different starting points and look for agreement as the main convergence diagnostic.

Gibbs sampling sits alongside other MCMC methods like Metropolis–Hastings in the landscape of Bayesian inference. Where Metropolis–Hastings accepts or rejects proposed moves, Gibbs always accepts — its proposals are already drawn from the exact conditional.

"Sample from the conditional, one variable at a time" turns out to be useful almost everywhere probabilistic models live:

• Bayesian inference: the engine behind Bayesian hierarchical models and posterior computation in statistics packages like BUGS, Stan, and PyMC.
• Latent Dirichlet Allocation (LDA): the topic model that assigns each word to a topic is trained by cycling through every word and resampling its topic from the conditional given all other assignments — pure collapsed Gibbs sampling.
• Image restoration: Geman & Geman's original 1984 paper used Gibbs sampling to reconstruct noisy images by iteratively updating each pixel's label given its neighbors' current labels.
• Boltzmann machines: training the early neural energy models relied on Gibbs sampling to estimate expectations under the model distribution.
• Statistical genetics: genome-wide association studies use Gibbs samplers to impute missing genotype data and estimate haplotype frequencies.
• Natural language processing: word alignment models in machine translation and coreference resolution both use Gibbs as a core inference engine.

Wherever you have a probabilistic model with many interdependent variables and tractable conditionals, Gibbs sampling turns the problem of global inference into a loop of local coin flips — the same theme as Bayesian inference and k-means clustering.

Gibbs sampling encodes a beautiful insight: a joint distribution that is impossible to sample directly becomes approachable if you are willing to be patient and sequential. Fix everything, update one variable, repeat.

The mathematics guarantees correctness. The practice demands vigilance about mixing — slow-mixing chains produce convincing-looking but wrong samples. And the applications span a remarkable range, from image pixels to document topics to human genomes.

Next time you see a probabilistic model with dozens of latent variables, remember that somewhere underneath it, a Gibbs sampler is probably cycling through them one by one — and that this humble loop is doing the work that no closed-form formula could.