Markov chain Monte Carlo and the random-walk Metropolis algorithm
Markov chain Monte Carlo draws samples from a posterior distribution that has no closed form. This article presents the random-walk Metropolis algorithm, the effect of the step size, and two convergence diagnostics: the effective sample size and the Gelman-Rubin statistic.
Bayes' rule is simple to state but usually impossible to compute in closed form. The posterior is the prior times the likelihood divided by a normalising integral, and for any model more interesting than a coin flip that integral has no formula.
A practical case shows why the integral matters. A regional health service compares the complication rate of one surgical procedure across twelve hospitals. Some hospitals perform hundreds of these operations a year and others a few dozen, so a sensible model lets each hospital's rate differ while sharing information between hospitals: two complications in thirty operations at a small hospital should not be judged on those thirty cases alone. The posterior of such a model has thirteen or more unknown quantities, and its normalising integral has no closed form. The questions the health service asks, such as the probability that a given hospital's rate exceeds the regional target, are averages over that posterior. MCMC answers them by producing a large sample of plausible values and counting: if 870 of 1,000 draws place the hospital above the target, the estimated probability is 0.87.
For decades this limited Bayesian methods to simple models. The change came when statisticians adopted an algorithm that physicists had used since 1953. The algorithm performs a random walk and decides at each step whether to move using only the ratio of the target density at the proposed and current positions. The normalising integral cancels in this ratio, and the visited positions, collected over time, form a sample from the target distribution.
Metropolis, the Rosenbluths and the Tellers (1953) introduced the algorithm to simulate the equation of state of interacting molecules on one of the first electronic computers. Hastings (1970) generalised it to asymmetric proposals and presented it to statisticians, giving the Metropolis-Hastings algorithm. It became mainstream after Gelfand and Smith (1990) showed how such methods compute Bayesian posteriors. Gelman and Rubin (1992) proposed running several chains from dispersed starting points and comparing them, the origin of the diagnostic. Roberts, Gelman and Gilks (1997) proved that in high dimensions the optimal random-walk acceptance rate is about 0.234; in one dimension it is about 0.44, as Roberts and Rosenthal (2001) review.
The algorithm
To sample from a density known up to a constant:
- Start somewhere, .
- Propose with .
- Accept with probability : set if accepted, otherwise .
- Repeat.
Uphill moves are always accepted; downhill moves sometimes. This rule makes the chain spend time in each region in proportion to its probability.
Choice of step size
The only tuning parameter is , and both extremes perform poorly.
- Too small: almost every proposal is accepted, but each moves a tiny distance. Consecutive draws are nearly identical, and the chain explores the distribution very slowly.
- Too large: proposals land far out in the tails, where the density is tiny, and are almost always refused. The chain sits still for long stretches.
Between the two lies an efficient range, which for a one-dimensional normal target is with an acceptance rate around 44%.
Convergence diagnostics
A chain's draws are correlated, so 1,000 draws contain less information than 1,000 independent ones. The effective sample size discounts for that: , with the autocorrelations of the chain. And because a single chain can look fine while missing half the distribution, Gelman and Rubin's compares several chains started far apart: if the variance between chains is large relative to the variance within them, they have not yet found the same distribution. Values close to 1, below about 1.01 to 1.05 depending on the guideline, suggest convergence.
These quantities decide whether the hospital comparison can be trusted. With 1,000 effectively independent draws, the estimate of 0.87 has a Monte Carlo standard error of about 0.01. With an effective sample size of 50, the same estimate has a standard error of about 0.05, enough to move a hospital close to the target from one side of a decision to the other.
The figure below runs four chains from dispersed starting points.
The small multiples are the four chains' traces; the histogram pools their later draws against the true target; the gauge and radar summarise the run's health.
Suggested settings:
- Efficient step size. With the normal target and step 2.4, acceptance settles near 44%, the four traces overlap within a few dozen steps, the histogram matches the curve and is about 1.00.
- Small step size. Set the step to 0.1. Acceptance rises above 90%, but the traces move slowly away from their starting points, the effective sample size falls sharply and remains well above 1.
- Large step size. Set the step to 20. Acceptance falls below 10%, the traces show long flat segments, and the effective sample size falls again, for the opposite reason.
- Bimodal target. Choose "Two peaks" with a step of 0.5. Each chain remains near its own mode; the pooled histogram may appear reasonable, but flags the disagreement. Raise the step to 5 or more and the chains begin to move between modes.
Stationarity of . A sufficient condition for to be the chain's stationary distribution is detailed balance: the probability flow from to equals the flow from to . With a symmetric proposal , the flow from to is , which is symmetric in and . Summing detailed balance over shows that if then . The normalising constant of appears in both numerator and denominator of the ratio, so it is never needed.
MCMC made Bayesian inference practical, and modern probabilistic programming languages still rely on it, usually with more efficient proposals than a random walk. The same rule applies to all variants: the diagnostics should be checked before the results are used, because a chain can appear to mix well while covering only part of the distribution. In the hospital example, such a chain would rank hospitals using only some of the explanations the data allow.
References
- N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller, "Equation of state calculations by fast computing machines", Journal of Chemical Physics, 21(6), 1087-1092, 1953.
- W. K. Hastings, "Monte Carlo sampling methods using Markov chains and their applications", Biometrika, 57(1), 97-109, 1970.
- A. E. Gelfand and A. F. M. Smith, "Sampling-based approaches to calculating marginal densities", Journal of the American Statistical Association, 85(410), 398-409, 1990.
- A. Gelman and D. B. Rubin, "Inference from iterative simulation using multiple sequences", Statistical Science, 7(4), 457-472, 1992.
- G. O. Roberts, A. Gelman and W. R. Gilks, "Weak convergence and optimal scaling of random walk Metropolis algorithms", Annals of Applied Probability, 7(1), 110-120, 1997.
- G. O. Roberts and J. S. Rosenthal, "Optimal scaling for various Metropolis-Hastings algorithms", Statistical Science, 16(4), 351-367, 2001.