Acceptance-Rejection Sampling

Inverse transform sampling needs a closed-form inverse CDF, and most distributions that show up in practice — a fitted return distribution with fat tails, a posterior density in a Bayesian model, a shape read off a histogram — simply don't have one. Acceptance-rejection sampling sidesteps this entirely: it never inverts anything. Instead it samples from a distribution that is easy to draw from, and throws away exactly the right proportion of draws so that what's left follows the hard target distribution.

An analogy: darts under a curve

Draw the target density as a curve over a rectangle, and imagine throwing darts uniformly at random across the whole rectangle. Keep only the darts that land underneath the curve; throw away the ones that land above it. The x-coordinates of the surviving darts are distributed exactly according to the target density, because the curve is taller where the density is higher, so more of the rectangle's area under the curve — and more surviving darts — sits there. You never had to invert anything; you just needed a rectangle (or, more generally, an easy "envelope" shape) that fully covers the curve.

The method, one symbol at a time

Let $f(x)$ be the target density (possibly known only up to a scaling constant) and $g(x)$ a proposal density that's easy to sample from and covers $f$ in the sense that $f(x) \le M \cdot g(x)$ for all $x$, for some constant $M \ge 1$. The algorithm: draw $X \sim g$, draw $U$ uniform on $(0,1)$ independently, and accept $X$ if $U \le f(X) / (M \cdot g(X))$; otherwise reject and try again. Accepted draws follow exactly the density $f$. In plain terms, $M \cdot g(x)$ is the "envelope" — a scaled-up version of the easy proposal density guaranteed to sit on top of the target everywhere — and the acceptance test keeps a point with probability equal to how close the envelope is to the target at that exact $x$, which thins out the proposal wherever it's puffed up above the target and leaves it alone wherever the two nearly touch.

Worked example 1: sampling a triangular density with a uniform envelope

Suppose the target is a simple triangular density on $[0,1]$, $f(x) = 2x$ (rising linearly from 0 to a peak of 2 at $x=1$), and we use the uniform proposal $g(x) = 1$ on $[0,1]$. Since $f(x) \le 2$ everywhere, take $M = 2$, so the envelope is $M \cdot g(x) = 2$. Draw $X = 0.7$ from the uniform proposal and $U = 0.6$. Acceptance test: accept if $U \le f(X)/(M g(X)) = (2 \times 0.7)/2 = 0.7$. Since $0.6 \le 0.7$, accept $X = 0.7$. Now try $X = 0.2, U = 0.5$: threshold is $(2 \times 0.2)/2 = 0.2$, and $0.5 > 0.2$, so reject. Notice small $x$ values, where the target density is low, get rejected far more often — exactly correcting the uniform proposal's over-representation of small $x$.

Worked example 2: efficiency of the envelope

The average acceptance rate equals $1/M$, because the total area under the envelope $M \cdot g$ is $M$ (since $g$ integrates to 1) while the area under the true density $f$ is 1 — the fraction of thrown darts landing under $f$ is $1/M$. With $M=2$ as above, roughly half of all draws get rejected on average. If a worse-fitting proposal required $M = 10$ to cover the same target, only 10% of draws would be accepted, meaning ten times more random draws are needed for the same number of usable samples — a concrete, computable cost of choosing a proposal that doesn't hug the target closely.

Picture the curve above as the target density's rough shape and a flat horizontal line above its peak as the envelope: the gap between the curve and the line at each point is exactly the region where darts are rejected.

What this means in practice

Acceptance-rejection sampling is the fallback whenever a distribution can't be inverted analytically — sampling from fitted fat-tailed return distributions, custom posterior shapes in calibration, or truncated/conditional distributions where the CDF is awkward. Its practical cost is entirely governed by $M$: a tight-fitting proposal accepts often and runs fast, while a loose one wastes most draws. In high dimensions this problem compounds badly, since a proposal that covers a target reasonably well in one dimension often requires an enormous $M$ in many dimensions, which is why more sophisticated samplers (MCMC, particle filters) take over there.