Markov Chain Monte Carlo

Markov chain Monte Carlo (MCMC) is a family of computational methods for sampling from a target probability distribution by constructing a Markov chain that has the target as its stationary distribution. Samples generated along the chain are used to approximate expectations and other distributional quantities. Unlike ordinary Monte Carlo sampling based on independent draws, MCMC usually produces dependent observations. It is particularly useful when direct sampling is difficult but the target density can be evaluated up to an unknown normalizing constant. (stat.umn.edu)

Mathematical foundations

A Markov chain satisfies the Markov property: conditional on its present state, the distribution of its next state does not depend on earlier states. An MCMC algorithm specifies a transition kernel $K(x,A)$ , the probability of moving from state $x$ into a set $A$ . Invariance of the target distribution $\pi$ means

\pi(A)=\int K(x,A)\,\pi(dx).

Thus, if a state already has distribution $\pi$ , applying the transition preserves that distribution. This does not mean that a chain initialized at an arbitrary point immediately samples from the target. (stat.umn.edu)

A common construction satisfies detailed balance, expressed on a discrete state space as

\pi(x)K(x,y)=\pi(y)K(y,x).

Detailed balance implies invariance, but is not necessary: nonreversible chains can also preserve the target. Appropriate accessibility and recurrence conditions are needed for consistent estimation; convergence of state distributions additionally requires conditions excluding persistent periodicity. Merely having the correct invariant distribution does not guarantee useful finite-run behavior. (stat.umn.edu)

For an integrable function $f$ , MCMC estimates its expected value using

\widehat{\mu}_N=\frac{1}{N}\sum_{t=1}^{N}f(X_t), \qquad \mu=\int f(x)\,\pi(dx).

Under suitable ergodicity conditions, a Markov-chain version of the law of large numbers makes this average converge to $\mu$ . The method therefore turns a potentially difficult integral into a simulation problem. (stat.umn.edu)

Principal algorithms

Metropolis–Hastings proposes a candidate $y$ from a proposal density $q(y\mid x)$ and accepts it with probability

\alpha(x,y)= \min\!\left( 1,\frac{\pi(y)q(x\mid y)} {\pi(x)q(y\mid x)} \right).

If rejected, the next state remains $x$ ; repeated states are part of the sample, not failed observations to be removed. The unknown normalizing constant of $\pi$ cancels from the ratio. For symmetric proposals, the proposal terms also cancel, giving the Metropolis acceptance rule. Random-walk proposals add a random perturbation to the current state, with their scale strongly affecting efficiency. (arxiv.org)

Gibbs sampling updates individual coordinates or blocks by drawing from their conditional distributions given the remaining coordinates. Each update preserves the joint target. Gibbs sampling is convenient when these conditional distributions are tractable, although strong dependence between coordinates can impede exploration. (arxiv.org)

Hamiltonian Monte Carlo (HMC) augments continuous parameters with auxiliary momentum variables and uses Hamiltonian dynamics to propose moves. Gradients of the log density guide trajectories, while a Metropolis correction accounts for numerical integration error. HMC can make long moves without the diffusive behavior characteristic of random-walk proposals. The No-U-Turn Sampler adaptively determines trajectory length. These methods require suitable differentiability and do not directly update discrete parameters. (mc-stan.org)

Statistical applications

In Bayesian inference, the posterior distribution satisfies

p(\theta\mid y)\propto p(y\mid\theta)\,p(\theta),

where $p(y\mid\theta)$ is the likelihood and $p(\theta)$ the prior. MCMC can sample this posterior without explicitly calculating its normalizing integral. Posterior draws support estimates of means, probabilities, and other summaries even when analytical integration is unavailable. The simulated sample size is distinct from the number of observed data points: more iterations improve computational precision, not the information supplied by the observations. (stat.umn.edu)

In statistical mechanics, related methods sample configurations of interacting particles and estimate equilibrium properties. The chain’s updates are computational devices and need not represent the system’s actual physical motion. (osti.gov)

Accuracy, diagnostics, and limitations

Dependence between draws changes estimation uncertainty. When an appropriate central limit theorem holds, the uncertainty of an estimated mean depends on both its variance under the target and correlations across iterations. For a stationary scalar sequence with summable autocorrelations $\rho_k$ , its effective sample size is conventionally expressed as

N_{\mathrm{eff}} =\frac{N}{1+2\sum_{k=1}^{\infty}\rho_k}.

Positive autocorrelation usually reduces effective sample size; negative autocorrelation can make it exceed the number of draws. Effective sample size is specific to the quantity being estimated, rather than a universal property of a run. Monte Carlo standard error measures simulation uncertainty, not uncertainty about parameters under the statistical model. (mc-stan.org)

An initial segment may be discarded as burn-in or warmup. Adaptive samplers also use warmup to tune transition parameters. Discarding initial draws does not itself establish convergence. Multiple-chain comparisons, including the $\widehat{R}$ diagnostic, and effective sample sizes provide evidence about sampling behavior but cannot certify that every important region has been explored. (stat.umn.edu)

Poorly scaled proposals, strongly dependent coordinates, or separated modes can produce slow exploration. A mathematically valid chain may consequently yield misleading estimates within a practical computing budget. High acceptance rates alone do not demonstrate efficiency: extremely small moves may be accepted frequently while exploring little of the target. (arxiv.org)

Historical development

The influential 1953 work of Nicholas Metropolis, Arianna Rosenbluth, Marshall Rosenbluth, Augusta Teller, and Edward Teller introduced a sampling procedure for calculations involving interacting particles. In 1970, W. K. Hastings published a generalization accommodating broader proposal mechanisms, together with theory and discussion of Monte Carlo error assessment. These developments underpin the algorithm now called Metropolis–Hastings. (osti.gov)