MCMC and Metropolis–Hastings

Suppose you want samples from some distribution, a Bayesian posterior, say, but you can only compute its density up to an unknown scaling constant. That is the usual situation: Bayes' theorem gives the posterior as (likelihood × prior) divided by a normalizing integral that is hopelessly hard to compute in more than a couple of dimensions. Markov chain Monte Carlo (MCMC) sidesteps the integral entirely. Instead of computing the distribution, it wanders through the space in a cleverly designed random walk whose long-run visiting frequencies match the target distribution exactly. Collect the places it visits and you have your samples.

The Metropolis–Hastings rule

The workhorse recipe is Metropolis–Hastings. From your current position $x$, do two things:

1. Propose a candidate $x'$ from some proposal distribution $q(x' \mid x)$, for example a small random step.
2. Accept or reject it. Accept the move with probability

$$a = \min\!\left(1, \ \frac{p(x')\, q(x \mid x')}{p(x)\, q(x' \mid x)}\right) ,$$

and if you reject, stay put and record $x$ again. Here $p(\cdot)$ is the target density (known only up to a constant) and $q(\cdot)$ is your proposal. When the proposal is symmetric, $q(x'\mid x) = q(x\mid x')$, this collapses to the simple Metropolis rule $a = \min(1, \ p(x')/p(x))$: always move uphill to higher density, and move downhill only sometimes, in proportion to how much lower the new spot is.

The magic is in that ratio $p(x')/p(x)$: the unknown normalizing constant appears in both the top and bottom and cancels. You never need it. That single fact is why MCMC can sample a posterior no one can integrate.

Worked example: one Metropolis step

Take a target proportional to $e^{-x^2/2}$ (a standard normal, up to the constant you do not know) with a symmetric random-walk proposal, so acceptance is $\min(1, \ p(x')/p(x)) = \min\!\big(1,\ e^{-(x'^2 - x^2)/2}\big)$.

• You are at $x = 0.5$ and propose $x' = 1.5$ (farther from the peak at $0$). The ratio is $e^{-(1.5^2 - 0.5^2)/2} = e^{-(2.25 - 0.25)/2} = e^{-1} \approx 0.37$. So you accept the move with probability $0.37$, draw a uniform random number, and move only if it comes up under $0.37$.
• Instead propose $x' = 0.2$ (closer to the peak). The ratio is $e^{-(0.04 - 0.25)/2} = e^{0.105} \approx 1.11$, capped at $1$, so you accept for certain.

Run this thousands of times and the histogram of visited $x$ values fills in a bell curve, without ever computing the normalizing $\sqrt{2\pi}$.

What to watch out for

• Burn-in. The chain starts wherever you put it, which may be far from the high-density region. Throw away the first stretch of samples so your estimates are not polluted by the walk-in period.
• Correlated samples. Consecutive draws are not independent, each is a small step from the last, so a thousand MCMC samples carry less information than a thousand independent ones. Summarize this with the effective sample size, and thin or run longer if it is low.
• Step size. Tiny proposals almost always accept but crawl; huge proposals almost always reject and get stuck. The sweet spot accepts roughly $20\%$–$50\%$ of moves; tune the proposal scale to land there.
• Multimodality. If the target has two far-apart peaks separated by a low-density valley, a random-walk chain can get trapped in one peak and never visit the other, silently missing half the distribution.

MCMC is what makes Bayesian inference work when conjugate priors do not apply, it is a Markov chain engineered to have the target as its stationary law, and it is a close cousin of other simulation tools like Monte Carlo integration and importance sampling. Modern samplers (Gibbs, Hamiltonian Monte Carlo, NUTS) are all descendants of this one accept-reject idea.