Markov Chain Monte Carlo (MCMC)

Why Does This Exist?

You fit a Bayesian model and want the posterior mean, a credible interval, a prediction average. The posterior has a form you can write down but cannot integrate. It lives in dozens of dimensions, its normalising constant is unknown, and direct sampling is out of reach.

That is the exact gap Monte Carlo methods leave open. Plain Monte Carlo assumes you can already draw from the target. When you cannot, you need a way to turn a rule for wandering around into samples from the right place. MCMC is that bridge.

This page covers the wandering rule and the keep-or-stay decision that makes it work. The chain itself is taught in Markov chains. The posterior setting that motivates most uses is in Bayesian inference. The efficient physics-based sequel is Hamiltonian Monte Carlo.

The one idea you need first

A Markov chain is a sequence where the next state depends only on the current one, through fixed transition probabilities. Given enough steps, many chains settle into a stationary distribution that they then keep sampling. MCMC designs a chain whose stationary distribution equals your target, so running the chain draws from the target. The full treatment is in Markov chains.

Think of It Like This

How It Actually Works

Call the target $p(x)$. You can evaluate an unnormalised version $\tilde{p}(x)$, so ratios $\tilde{p}(x') / \tilde{p}(x)$ equal true ratios $p(x') / p(x)$ because the unknown constant cancels. That cancellation is the whole trick. You never need the constant.

From current state $x$, propose $x'$ from a proposal $q(x' \mid x)$. In plain words: $q$ is your random step rule, such as adding Gaussian noise. Then accept with probability:

Here $\alpha$ is the acceptance probability, $\tilde{p}$ is the unnormalised target, and the $q$ ratio corrects for asymmetric steps. With a symmetric step such as Gaussian noise, the $q$ ratio equals 1 and the rule simplifies to $\min(1, \tilde{p}(x') / \tilde{p}(x))$. Moves uphill always win. Moves downhill win in proportion. On rejection you stay at $x$ and record it again, which is what keeps the time spent in each region proportional to its mass.

Gibbs sampling as a special case

Gibbs sampling cycles through coordinates and samples each one from its conditional given the rest. Each such move accepts with probability 1, so it is Metropolis-Hastings where the proposal was chosen to make $\alpha = 1$ always. Use it when those conditionals have a direct sampler. Otherwise use Metropolis-Hastings.

Worked example

Take a two-place target with $p(A) = 0.2$ and $p(B) = 0.8$, and a symmetric proposal that always suggests the other place. Only the ratio matters, and you can compute both directions by hand:

• From $A$, propose $B$: ratio $0.8 / 0.2 = 4$, so $\alpha = \min(1, 4) = 1$. You always move.
• From $B$, propose $A$: ratio $0.2 / 0.8 = 0.25$, so $\alpha = 0.25$. You move one time in four and stay the other three.

That asymmetry is the sampler. It leaves $B$ rarely and returns to $B$ always, so a long run spends about 80 percent of its steps at $B$ and 20 percent at $A$, matching $p$. Discard the first few dozen steps as burn-in, because the chain starts wherever you dropped it rather than from $p$.

Code

The point is the check: a tiny Metropolis loop on the two-place target should recover 0.8 and 0.2 without ever being told the normalising constant, since only ratios are used.

1import random2
3
4def run_mcmc(n: int = 20000, seed: int = 0) -> dict[str, int]:5    random.seed(seed)6    weights = {"A": 0.2, "B": 0.8}  # unnormalised is fine here7    cur = "A"8    counts = {"A": 0, "B": 0}9    for _ in range(n):10        prop = "B" if cur == "A" else "A"11        ratio = weights[prop] / weights[cur]  # constant cancels12        if random.random() < min(1.0, ratio):13            cur = prop14        counts[cur] += 115    return counts16
17
18counts = run_mcmc()19print(counts)  # -> {'A': 3965, 'B': 16035}20print(round(counts["B"] / 20000, 3))  # -> 0.802

The 0.802 matches the target 0.8 within sampling noise. Change the seed and the counts wobble but stay near 80 and 20, which is exactly the claim to test.

Watch Out For

The Quick Version

• MCMC draws from a distribution you cannot sample directly by running a chain designed to settle on it.
• You only need ratios of an unnormalised target, since the unknown constant cancels.
• Metropolis-Hastings proposes a random step and keeps it with probability $\min(1, \text{ratio})$. Uphill always wins, downhill wins in proportion.
• On rejection you stay put and count the current state again, which is what allocates time by mass.
• The two-place example gives acceptance 1 one way and 0.25 the other, so a long run spends 80 percent at $B$.
• Gibbs sampling is the special case where each conditional move accepts with probability 1.
• Throw away burn-in, run several chains from different starts, and distrust agreement that you have not checked.

What to Read Next

• Markov Chains
• Monte Carlo Methods
• Hamiltonian Monte Carlo