Sampling Methods: Inverse Transform, Rejection & Importance Sampling
Most quantities in probabilistic ML are expectations — a predictive average, a marginal likelihood, an expected reward. When the integral has no closed form, we estimate it by drawing samples and averaging. The catch: how do you sample from when all you have is a uniform random number generator and a formula for the density? This page covers the foundational answers. (For resampling data see the bootstrap; for sampling correlated chains from intractable posteriors see MCMC — both linked below.)
Everything starts from one primitive: rng.random(), a draw from .
Inverse transform sampling
If you can write down and invert the CDF , sampling is exact and one-shot:
- Draw .
- Return .
Why it works: is itself uniform on (the probability integral transform), so pushing a uniform back through reproduces the target. For the exponential distribution , inverting gives the well-known generator .
Limitation: it requires a tractable inverse CDF. For the Gaussian, has no elementary form (hence dedicated tricks like Box–Muller); for most multivariate or unnormalized densities there is no inverse to invert. That is where the next two methods come in.
Rejection sampling
When you can evaluate the target (even unnormalized) but can't invert it, sample from an easy proposal and throw away the samples that don't fit. Pick a constant such that everywhere, then:
- Draw a candidate .
- Draw .
- Accept if ; otherwise reject and repeat.
Accepted samples are distributed exactly as . Geometrically: throw darts uniformly under the curve and keep only those that also land under .
The acceptance rate is 1/M — and M explodes in high dimensions
The fraction of proposals accepted is , so a loose envelope wastes most draws. Worse, the smallest valid grows roughly exponentially with dimension when doesn't closely match — in 100-D, rejection sampling can accept essentially nothing. This curse of dimensionality is precisely why MCMC, which doesn't reject its way to the target, dominates for high-dimensional posteriors.
Importance sampling
Sometimes you don't need samples from at all — you only need an expectation under , and sampling directly is hard (or you want to reuse samples from a different distribution). Importance sampling rewrites the expectation as one under a tractable proposal :
Draw and average . The importance weights correct for sampling from the wrong distribution. When is known only up to a constant (the usual Bayesian case), use self-normalized importance sampling, dividing by .
Choosing is everything. Variance is minimized when — you should sample more where the integrand is large. The classic application is estimating rare events: to estimate for a standard normal, sampling from almost never lands in the tail, but a shifted proposal puts samples exactly where they count, then reweights.
A heavy-tailed proposal is safer than a light-tailed one
If has thinner tails than , the ratio blows up in the tails and a single sample can dominate the estimate — the variance can even become infinite while the estimate looks deceptively stable. Rule of thumb: pick a proposal at least as heavy-tailed as the target, and always inspect the distribution of weights (a few weights carrying all the mass is the warning sign).
Variance reduction
The Monte Carlo error of an estimate shrinks like . These tricks reduce the constant in front, buying accuracy without more samples:
- Antithetic variates: pair each draw with its mirror . For a monotone the two are negatively correlated, so their average has lower variance than two independent draws.
- Stratified sampling: partition the domain into strata and sample a fixed quota from each, eliminating the "clumping" of pure random sampling. (Latin hypercube sampling generalizes this to many dimensions.)
- Control variates: subtract a correlated quantity with known mean to cancel part of the noise.
Choosing a method
| You have… | You want… | Use |
|---|---|---|
| Invertible CDF | exact samples | inverse transform |
| Evaluable density + good proposal, low-D | exact samples | rejection sampling |
| Tractable proposal; only need an expectation | an estimate (incl. rare events) | importance sampling |
| Unnormalized high-D density (e.g. a posterior) | samples | MCMC (see below) |
Related concepts
- Probability Distributions: the CDFs and densities these methods sample from
- Generative Models: learned samplers; the same accept/reweight ideas appear in their training and inference
- MCMC Sampling: when rejection and importance sampling break in high dimensions, build a Markov chain whose stationary distribution is the target
- The Bootstrap: resampling observed data rather than generating from a parametric distribution