Sampling Methods: Inverse Transform, Rejection & Importance SamplingOpen in Colab

Sampling Methods: Inverse Transform, Rejection & Importance Sampling

Most quantities in probabilistic ML are expectations Ep[f(x)]=∫f(x) p(x) dx\mathbb{E}_{p}[f(x)] = \int f(x)\,p(x)\,dx — a predictive average, a marginal likelihood, an expected reward. When the integral has no closed form, we estimate it by drawing samples x(i)∼px^{(i)} \sim p and averaging. The catch: how do you sample from pp 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 Uniform(0,1)\text{Uniform}(0,1).

Inverse transform sampling

If you can write down and invert the CDF F(x)=P(X≤x)F(x) = P(X \le x), sampling is exact and one-shot:

  1. Draw u∼Uniform(0,1)u \sim \text{Uniform}(0,1).
  2. Return x=F−1(u)x = F^{-1}(u).

Why it works: F(X)F(X) is itself uniform on (0,1)(0,1) (the probability integral transform), so pushing a uniform back through F−1F^{-1} reproduces the target. For the exponential distribution F(x)=1−e−λxF(x) = 1 - e^{-\lambda x}, inverting gives the well-known generator x=−1λln⁡(1−u)x = -\frac{1}{\lambda}\ln(1-u).

Limitation: it requires a tractable inverse CDF. For the Gaussian, F−1F^{-1} 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 p(x)p(x) (even unnormalized) but can't invert it, sample from an easy proposal q(x)q(x) and throw away the samples that don't fit. Pick a constant MM such that p(x)≤M q(x)p(x) \le M\,q(x) everywhere, then:

  1. Draw a candidate x∼qx \sim q.
  2. Draw u∼Uniform(0,1)u \sim \text{Uniform}(0,1).
  3. Accept xx if u≤p(x)M q(x)u \le \dfrac{p(x)}{M\,q(x)}; otherwise reject and repeat.

Accepted samples are distributed exactly as pp. Geometrically: throw darts uniformly under the curve Mq(x)M q(x) and keep only those that also land under p(x)p(x).

The acceptance rate is 1/M — and M explodes in high dimensions

The fraction of proposals accepted is 1/M1/M, so a loose envelope wastes most draws. Worse, the smallest valid MM grows roughly exponentially with dimension when qq doesn't closely match pp — 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 pp at all — you only need an expectation under pp, and sampling pp directly is hard (or you want to reuse samples from a different distribution). Importance sampling rewrites the expectation as one under a tractable proposal qq:

Ep[f(x)]=∫f(x) p(x)q(x) q(x) dx=Eq ⁣[f(x) w(x)],w(x)=p(x)q(x)\mathbb{E}_{p}[f(x)] = \int f(x)\,\frac{p(x)}{q(x)}\,q(x)\,dx = \mathbb{E}_{q}\!\left[f(x)\,w(x)\right], \quad w(x) = \frac{p(x)}{q(x)}

Draw x(i)∼qx^{(i)} \sim q and average f(x(i)) w(x(i))f(x^{(i)})\,w(x^{(i)}). The importance weights ww correct for sampling from the wrong distribution. When pp is known only up to a constant (the usual Bayesian case), use self-normalized importance sampling, dividing by ∑iw(x(i))\sum_i w(x^{(i)}).

Choosing qq is everything. Variance is minimized when q(x)∝∣f(x)∣ p(x)q(x) \propto |f(x)|\,p(x) — you should sample more where the integrand is large. The classic application is estimating rare events: to estimate P(X>10)P(X > 10) for a standard normal, sampling from N(0,1)\mathcal{N}(0,1) almost never lands in the tail, but a shifted proposal N(10,1)\mathcal{N}(10, 1) puts samples exactly where they count, then reweights.

A heavy-tailed proposal is safer than a light-tailed one

If qq has thinner tails than pp, the ratio w=p/qw = p/q 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 1/N1/\sqrt{N}. These tricks reduce the constant in front, buying accuracy without more samples:

  • Antithetic variates: pair each draw uu with its mirror 1−u1-u. For a monotone ff 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 CDFexact samplesinverse transform
Evaluable density + good proposal, low-Dexact samplesrejection sampling
Tractable proposal; only need an expectationan estimate (incl. rare events)importance sampling
Unnormalized high-D density (e.g. a posterior)samplesMCMC (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

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
Sampling Methods: Inverse Transfo…Probability Distributions…MCMC Sampling: Metropolis…The Bootstrap: Resampling…Probability DistributionsWhat Are Generative Model…