Markov Chain Monte Carlo (MCMC) is a class of algorithms that generate samples from a target probability distribution $\pi$ by simulating a Markov chain whose stationary distribution is $\pi$. The samples are correlated, not i.i.d., but long-run averages still converge to expectations under $\pi$ by the ergodic theorem. MCMC solves the core computational problem of Bayesian inference: how to compute posterior expectations, quantiles, and marginal densities when the posterior $\pi (\theta \mid y)\propto p(\theta )p(y\mid \theta )$ has no closed form and its normalizing constant $\int p(\theta )p(y\mid \theta )d\theta$ is intractable.

The common structure across MCMC algorithms is the detailed-balance construction: propose a move from the current state $\theta$ to a candidate ${\theta }^{\prime }$ using a proposal distribution $Q$, then accept or reject the move to enforce $\pi (\theta )P(\theta ,{\theta }^{\prime })=\pi ({\theta }^{\prime })P({\theta }^{\prime },\theta )$. This single mechanism produces Random Walk Metropolis, Metropolis-Hastings, Gibbs sampling, MALA, and HMC — the difference is entirely in how $Q$ is chosen and what accept-reject rule implements balance.

Prerequisites

• 5.1 Markov Chains — time-homogeneous chains, transition kernels.
• 5.3 Distribution of Markov Chains — stationary distributions, ergodic theorem.
• 5.4 Reversibility — detailed balance and its equivalence to stationarity under irreducibility.
• 3.1 Bayesian Framework — why Bayesian inference produces unnormalized posteriors in the first place.

Contents

• 3.11.1 Metropolis-Hastings — general accept/reject Markov transition with arbitrary proposal.
• 3.11.2 Gibbs Sampling — coordinate-wise update from full conditional distributions.
• 3.11.3 MALA — Metropolis-adjusted Langevin algorithm; gradient-informed proposals.
• 3.11.4 Hamiltonian Monte Carlo — leapfrog-integrated momentum; efficient in high dimensions.
• 3.11.5 EM Algorithm — deterministic analog of Gibbs, used for maximum a posteriori rather than full posterior sampling.

Shared Concepts

(Acceptance Rate) Fraction of proposals accepted; measures how well the proposal matches the target.

Too-small proposal scales produce high acceptance rates (near $1$) but tiny moves, yielding strong autocorrelation and slow exploration. Too-large proposal scales produce most moves into low-density regions and few acceptances, yielding a chain that rarely moves. For high-dimensional Gaussian-like targets, theory suggests tuning to roughly $0.234$; $0.2$–$0.4$ is a practical working range.

(Burn-in) Early iterates depend on the starting point and are discarded.

The ergodic theorem guarantees convergence as $N\to \infty$, but for finite $N$ the estimate $\frac{1}{N}\sum g({\theta }^{(t)})$ is biased by the starting point. Standard practice is to discard the first $B$ iterates and use only ${\theta }^{(B+1)},\dots ,{\theta }^{(N)}$ for averages. Initializing at the MLE or MAP (via Newton’s method or the Laplace approximation) minimizes burn-in.

(Trace Plots) Plot each coordinate of ${\theta }^{(t)}$ against iteration $t$ to diagnose mixing.

A well-mixed chain looks like stationary noise around a stable mean. A poorly-mixed chain drifts for many iterations (still in burn-in), stays stuck at constant values (acceptance rate too low), or explores visibly different modes at different times (bimodal target with poor transition).

(Effective Sample Size) Correlated samples carry less information than i.i.d. ones.

If ${\theta }^{(1)},\dots ,{\theta }^{(N)}$ have autocorrelation ${\rho }_k$ at lag $k$, the effective sample size is approximately $N_{\text{eff}}=N/(1+2{\sum }_{k=1}^{\infty }{\rho }_k)$. An MCMC run of $N=10,000$ iterations with $N_{\text{eff}}=500$ is worth about $500$ i.i.d. samples, not $10,000$. Low $N_{\text{eff}}/N$ is the single most common sign of a poorly-tuned chain.

(Convergence Diagnostics) No single test proves convergence; use multiple chains and visual checks.

The Gelman-Rubin statistic $\hat{R}$ compares within-chain and between-chain variance from multiple independently-initialized chains; $\hat{R}\approx 1$ is consistent with convergence, $\hat{R}>1.1$ is a warning. Running $4$–$8$ chains from overdispersed starting points and checking that they overlap in the trace plots is the practical version of this diagnostic.

(Choice of Proposal) Algorithm correctness does not depend on $Q$; efficiency does.

Any proposal $Q$ that is irreducible with respect to $\pi$ eventually samples from $\pi$. The engineering challenge is choosing $Q$ so the chain mixes quickly. A proposal matched to the local curvature of $\pi$ — typically via a Laplace approximation at the MAP — dramatically outperforms isotropic random-walk proposals in high dimensions. Gradient-informed proposals (MALA, HMC) go further by using $\nabla \log \pi$.

See Also

• 7.4.2. Rejection Sampling — i.i.d. sampling alternative that requires a uniformly dominating proposal.
• 3. Bayesian Statistics — parent index.