Markov Chain Monte Carlo
Markov chain Monte Carlo (MCMC) is a family of algorithms that draw samples from a probability distribution, often one known only up to a normalizing constant, by constructing a Markov chain whose long-run behavior matches that distribution; averages over the chain's states then approximate expectations, probabilities and quantiles that cannot be computed in closed form. It is the engine that made applied bayesian-inference feasible for realistic models, because a posterior-probability is typically a high-dimensional density whose normalizing integral is intractable, yet MCMC needs only the unnormalized product of prior and likelihood. The idea began in physics: Nicholas Metropolis, Arianna Rosenbluth, Marshall Rosenbluth, Augusta Teller and Edward Teller published "Equation of State Calculations by Fast Computing Machines" in 1953, and W. K. Hastings generalized it in a 1970 Biometrika paper.
The Metropolis–Hastings algorithm is the template: propose a move from the current state, compute the ratio of the target density at the proposed and current points, and accept the move with that probability (or always, if the ratio exceeds one). Because only a ratio of densities is used, the unknown normalizing constant cancels, which is the whole trick; and because acceptance obeys detailed balance, the chain's stationary distribution is the target. Hastings's extension allowed asymmetric proposals by adding a correction factor. The cost of the generality is that the samples are autocorrelated rather than independent: a proposal that is too small produces a slow random walk with high acceptance, while one that is too large is mostly rejected, and the usual rule of thumb for random-walk Metropolis aims at an acceptance rate of about 0.234 in high dimensions, a result from Roberts, Gelman and Gilks in 1997.
Gibbs sampling is the special case that exploits structure: when each variable's conditional distribution given all the others is easy to sample, cycle through the variables and sample each in turn, with no accept-reject step. The name comes from Stuart and Donald Geman's 1984 paper on image restoration, where the target was a Gibbs distribution from statistical physics, and Alan Gelfand and Adrian Smith's 1990 paper "Sampling-Based Approaches to Calculating Marginal Densities" showed statisticians how broadly it applied, setting off the Bayesian computational revolution; the BUGS software (from 1989) and later JAGS packaged it for users. Gibbs works beautifully for conjugate hierarchical models but mixes slowly when variables are strongly correlated, since each update can only move along one axis at a time.
Hamiltonian Monte Carlo (HMC) addresses that weakness by using the gradient of the log-density: it introduces auxiliary momentum variables and simulates Hamiltonian dynamics, so the proposed point can be far from the current one while still being accepted with high probability. It was introduced by Duane, Kennedy, Pendleton and Roweth in 1987 as "hybrid Monte Carlo" for lattice field theory, and Radford Neal's 2011 handbook chapter introduced it to statisticians. Tuning the path length and step size was the practical barrier until Hoffman and Gelman's No-U-Turn Sampler (NUTS, 2014) adapted them automatically. NUTS is the default in Stan (described by Carpenter and colleagues in the Journal of Statistical Software, 2017), and in PyMC, NumPyro and Turing.jl; because HMC needs gradients, these systems rely on automatic differentiation. Divergent transitions, which HMC reports when it detects trouble, are a diagnostic of difficult posterior geometry, such as the "funnel" of hierarchical models, and a standard remedy is reparameterization.
The most dangerous misconceptions are that MCMC draws are independent, that a chain that looks stable has converged, and that more samples fix a bad model. The chain starts wherever it is initialized and takes time to find the high-probability region, so early draws are discarded as warmup; the remaining draws are correlated, so the effective sample size can be much smaller than the number of iterations. Gelman and Rubin's 1992 diagnostic, now used in an improved rank-normalized version (R-hat), compares variation within and between multiple chains; no diagnostic can prove convergence, only fail to detect problems, and multimodal targets can trap a chain in one mode, which is why several dispersed chains are essential. MCMC also gives answers only for the model written down, so it cannot repair a misspecified likelihood, and it is expensive relative to variational inference, which trades accuracy for speed on very large models. MCMC samples are also the representation behind quantities like the credible intervals in the posterior entry.
Read Markov chain Monte Carlo as a patient random walk designed so that the time it spends in each region is proportional to that region's probability, turning an impossible integral into an average over draws, with the sampler choice and the diagnostics deciding whether the average can be believed.