Markov Chain Monte Carlo

Markov Chain Monte Carlo (MCMC) is a family of computational algorithms that generate samples from an arbitrary target probability distribution by constructing a Markov chain whose stationary distribution equals the target, enabling tractable approximate Bayesian inference and numerical integration over high-dimensional parameter spaces that are intractable by exact analytical methods. Foundational algorithms include Metropolis-Hastings, Gibbs sampling, Hamiltonian Monte Carlo (HMC), and the No-U-Turn Sampler (NUTS). MCMC is the standard tool for posterior inference in probabilistic programming and Bayesian statistical modelling across science, engineering, and machine learning.

Overview

• MCMC solves the fundamental problem of drawing samples from a probability distribution $\pi (\theta )$ that cannot be sampled directly — typically a Bayesian posterior $\pi (\theta \mid \mathbf{x})\propto p(\mathbf{x}\mid \theta )\pi (\theta )$.
• The core idea is to design a Markov chain over the parameter space such that its unique stationary distribution is the target $\pi$. Running the chain long enough guarantees samples approximate draws from $\pi$.
• Once the chain reaches stationarity (after a burn-in phase), collected samples are used to compute posterior summaries: means, variances, credible intervals, and predictive distributions.
• MCMC enables exact Bayesian computation (in the limit of infinite samples) in contrast to the approximations of Variational Inference or Normalising Flows, making it the gold standard for accuracy-critical applications.
• Convergence Diagnostics such as the Gelman-Rubin $\hat{R}$ statistic and Effective Sample Size (ESS) assess whether multiple chains have mixed and are sampling reliably.

Key Algorithms

• Metropolis-Hastings — the foundational MCMC algorithm (Metropolis 1953, Hastings 1970). A proposal distribution $q({\theta }^{\prime }\mid \theta )$ generates candidates accepted with probability $\min \left(1,\frac{\pi ({\theta }^{\prime })q(\theta \mid {\theta }^{\prime })}{\pi (\theta )q({\theta }^{\prime }\mid \theta )}\right)$, guaranteeing Detailed Balance with respect to $\pi$.
• Gibbs Sampling — samples each parameter in turn from its conditional distribution $p({\theta }_i\mid {\theta }_{-i},\mathbf{x})$. Requires tractable conditionals; naturally extends to hierarchical models. Introduced by Geman & Geman (1984) and popularised for Bayesian statistics by Gelfand & Smith (1990).
• Hamiltonian Monte Carlo (HMC) — augments the parameter space with auxiliary momentum variables and evolves proposals using Hamiltonian Dynamics (via leapfrog integration). Gradient information from $\log \pi$ enables distant, high-acceptance proposals, reducing random-walk behaviour. Introduced by Duane et al. (1987); adapted to Bayesian computation by Neal (1994).
• No-U-Turn Sampler (NUTS) — adaptively tunes HMC’s trajectory length using a no-U-turn criterion, eliminating manual tuning. Published by Hoffman & Gelman (2014); the default sampler in Stan and PyMC.
• Sequential Monte Carlo (Particle MCMC) — combines particle filtering with MCMC kernels for state-space and time-series models; handles non-stationary targets and model comparison.
• Riemannian HMC — uses the Fisher information metric to adapt proposals to local geometry of the parameter space, improving efficiency in curved posteriors.
• Langevin Monte Carlo (MALA) — a gradient-based first-order method using the stochastic gradient of $\log \pi$ to propose moves; computationally cheaper than full HMC but less efficient per sample.

Theoretical Foundations

• Ergodicity — MCMC correctness requires the chain be ergodic: irreducible (every state reachable from every other) and aperiodic. Ergodicity guarantees the empirical sample average converges to the true expectation under $\pi$.
• Detailed Balance — a sufficient (though not necessary) condition for $\pi$ to be stationary: $\pi (\theta )T({\theta }^{\prime }\mid \theta )=\pi ({\theta }^{\prime })T(\theta \mid {\theta }^{\prime })$. Metropolis-Hastings is constructed to satisfy this.
• Mixing Time — the number of steps before the chain distribution is close to stationarity. Poor mixing (slow diffusion, high autocorrelation) inflates variance of estimates and requires longer runs.
• Burn-in and Thinning — early samples (burn-in) are discarded to remove dependence on the starting state. Thinning (keeping every $k$-th sample) can reduce autocorrelation but is generally inefficient compared to using all post-burn-in samples.
• Central Limit Theorem for Markov Chains — under regularity conditions, sample averages from ergodic chains satisfy a CLT, enabling asymptotically valid uncertainty quantification.

Applications

• Bayesian Inference in statistics — fitting hierarchical models, mixed-effects models, and latent variable models in clinical trials, epidemiology, and social science.
• Probabilistic Programming — frameworks such as Stan, PyMC, Pyro, NumPyro, and Turing.jl use MCMC (primarily NUTS) as their core inference engine, exposing posterior computation to practitioners via model specification languages.
• Bayesian Neural Networks — MCMC provides exact posterior inference over network weights, enabling calibrated uncertainty in deep learning; computationally expensive but increasingly feasible via Stochastic Gradient MCMC.
• Gaussian Process regression and classification — MCMC is used for hyperparameter marginalisation and latent function inference in GP models.
• Astrophysics and cosmology — parameter estimation for cosmological models (e.g. CMB power spectrum fitting), exoplanet characterisation, and gravitational-wave source inference (LIGO uses MCMC extensively).
• Computational biology and bioinformatics — phylogenetic tree inference (MrBayes, BEAST), protein structure prediction, and molecular dynamics enhanced sampling.
• Statistical physics — simulation of lattice models (Ising model), computation of partition functions, and free-energy estimation.
• Finance and actuarial science — Bayesian calibration of stochastic volatility models, option pricing, and risk quantification.
• Reinforcement learning — Bayesian model-based RL uses MCMC for posterior inference over environment dynamics.

Standards & Ecosystem

• Stan — a probabilistic programming language and MCMC platform with NUTS as default sampler, widely adopted in applied statistics and social sciences.
• PyMC (formerly PyMC3) — Python-based Bayesian modelling framework backed by Aesara/PyTensor; uses NUTS, with JAX backends for GPU acceleration.
• Pyro / NumPyro — deep probabilistic programming frameworks from Uber AI / Google DeepMind; NumPyro leverages JAX for vectorised MCMC.
• Turing.jl — Julia-based probabilistic programming language with composable MCMC samplers including HMC, NUTS, and particle MCMC.
• MrBayes / BEAST — domain-specific MCMC tools for Bayesian phylogenetics and molecular clock estimation.
• No single governing standards body; convergence and reporting practices are guided by community best practices (e.g. Andrew Gelman’s “Bayesian Workflow” recommendations and the BDA3 textbook).

Diagnostics & Best Practices

• Run multiple chains (typically 4) from dispersed starting points; divergence between chains signals non-convergence.
• Monitor $\hat{R}$ (R-hat): values $<1.01$ indicate convergence; values $>1.1$ indicate problems.
• Monitor Effective Sample Size (ESS): bulk and tail ESS $>100$ per chain per parameter recommended.
• Diagnose divergent transitions in HMC/NUTS (proposals that violate energy conservation), which indicate pathological geometry requiring reparameterisation.
• Use posterior predictive checks to validate model fit.
• Reparameterisation (e.g. non-centred parameterisations for hierarchical models) dramatically improves mixing in nested models.

Provenance