Learn · Intermediate

Markov chain Monte Carlo: exploring a probability distribution one step at a time

Markov chain Monte Carlo is a family of methods for drawing approximate samples from a probability distribution when direct sampling is difficult. It builds a sequence of dependent samples whose long-run distribution is designed to match the distribution of interest, making otherwise intractable expectations and uncertainty estimates more practical.

Suppose a scientist wants to estimate the likely values of several model parameters after observing data. Bayes’ rule says the posterior distribution is proportional to the likelihood of the observations multiplied by the prior distribution. Often we can calculate that product for a proposed parameter setting but cannot calculate the normalizing constant that makes it integrate to one. In a high-dimensional model, even mapping the whole distribution on a grid can be prohibitively expensive. The Bayesian updating lesson explains the underlying posterior.

Imagine exploring a mountain landscape in fog. You cannot see the whole map, but you can compare the height of where you stand with that of a nearby candidate point. A carefully designed walk can spend more time in high-probability regions while still visiting low-probability regions sometimes. After enough exploration, the relative time spent in each region approximates its probability mass. A high peak is not automatically the whole story: a broad plateau can contain more total probability than a narrow summit.

The Markov part means that the next position depends on the current state, according to a fixed transition rule, rather than requiring the entire history. The Monte Carlo part means we estimate quantities using samples. The resulting samples are generally correlated, unlike independent draws. That dependence matters for the precision of an estimate.

A classic method is Metropolis sampling, introduced by Nicholas Metropolis and colleagues in their 1953 paper. Start from a current point, propose a nearby candidate, and compare their unnormalized target probabilities. With a symmetric proposal, accept a move to a higher-probability point; accept a move to a lower-probability point with probability equal to the ratio of candidate to current probability. Otherwise stay at the current point and count that repeated state as a sample. The normalizing constant cancels in the ratio.

For example, if the proposed point has half the unnormalized probability of the current point, accept it half the time. Allowing some downhill moves prevents the method from behaving like simple hill climbing. If the proposal is asymmetric, the more general Metropolis–Hastings rule also includes the reverse-to-forward proposal probability ratio. Omitting that correction can produce the wrong distribution. The desired stationary distribution is an invariant distribution of the transition rule; a particular finite run is not automatically representative of it.

After generating samples, estimate the posterior mean of a quantity by averaging it over the retained states. To estimate the probability that a parameter exceeds a threshold, count the fraction of samples above it. The method can approximate many different expectations from the same run, provided it has explored the relevant distribution well enough. It does not turn an incorrect likelihood, an inappropriate prior, or biased data into a trustworthy conclusion.

The difficult part is knowing whether the walk has explored enough. A chain initialized far from the typical region may spend an initial period moving toward it; practitioners often discard that initial warmup. There is no universally sufficient number of discarded steps. If the target has separated peaks, a local proposal may remain trapped near one peak and miss another entirely. A trace that looks stable within one region can still be misleading.

Multiple chains started from dispersed positions help reveal disagreement. Diagnostics such as split R-hat compare between-chain and within-chain behavior, while effective sample size estimates how much information remains after accounting for autocorrelation. These are warning tools, not proofs of convergence. Agreement among chains that all missed the same region is possible. Compare results across reasonable initializations and methods, inspect trace behavior, and use problem knowledge to check whether important regions were explored.

Proposal design creates a tradeoff. Tiny steps may be accepted frequently but move slowly across the space; enormous steps may be rejected so often that the chain barely moves. Other methods use different structure: Gibbs sampling updates variables from their conditional distributions when those are available, while Hamiltonian Monte Carlo uses gradients to propose longer moves. These are related techniques, not interchangeable guarantees of efficiency. Their suitability depends on the target’s geometry and the cost of each evaluation.

MCMC is useful for uncertainty in scientific models and Bayesian machine learning, but it is distinct from generating text by sampling a model’s next token. Both use random samples, yet MCMC specifically constructs a dependent chain designed to approach a target distribution. Its value lies in disciplined approximation: define the target, choose a valid transition, check exploration, quantify sampling error, and retain uncertainty about the underlying model itself.

Ground Truth. (2026, November 10). Markov chain Monte Carlo: exploring a probability distribution one step at a time. Ground Truth. https://groundtruth.day/learn/markov-chain-monte-carlo.html

@misc{groundtruth:markov-chain-monte-carlo,
  title  = {Markov chain Monte Carlo: exploring a probability distribution one step at a time},
  author = {{Ground Truth}},
  year   = {2026},
  month  = {nov},
  url    = {https://groundtruth.day/learn/markov-chain-monte-carlo.html}
}

Topics: statistics · bayesian-inference · sampling