Markov Chain Monte Carlo

MCMC samples from complex distributions by building a Markov chain whose stationary distribution is the target.

The problem it solves

Bayesian posteriors and other high-dimensional distributions are often known only up to a normalizing constant, which is an intractable integral. Markov chain Monte Carlo (MCMC) draws samples from such a distribution without ever computing that constant, by constructing a Markov chain that converges to it.

Metropolis-Hastings

Kronos motion — monte carlo

The basic algorithm proposes a move from the current state, then accepts it with a probability that depends only on the ratio of target densities — so the unknown normalizing constant cancels. The acceptance rule enforces detailed balance, guaranteeing the target as the stationary distribution.

python

import math, random
def target(x):            # unnormalized: standard normal
    return math.exp(-x*x/2)
x = 0.0; samples = []
for _ in range(50000):
    xp = x + random.uniform(-1,1)
    if random.random() < min(1, target(xp)/target(x)):
        x = xp
    samples.append(x)
print(round(sum(samples)/len(samples),3))  # near 0

Burn-in and mixing

Early samples reflect the arbitrary starting point, so an initial burn-in stretch is discarded. Successive samples are correlated, which reduces the effective sample size; how quickly the chain explores the target is called mixing. Poor mixing means many draws carry little independent information.

Diagnostics

Trace plots should look like stationary noise, not drift.
Run several chains from different starts and check they agree (the R̂ statistic).
Autocorrelation and effective sample size gauge how much the samples are worth.

Variants

Gibbs sampling updates one variable at a time from its full conditional. Hamiltonian Monte Carlo uses gradient information to make long, efficient proposals, which is why modern probabilistic programming systems rely on it for high-dimensional posteriors.