Rejection Sampling

Rejection Sampling generates samples that are exactly distributed as the target $p(x)$ when direct sampling is hard: pick an easy-to-sample proposal $q(x)$ and a constant $M$ with $p(x) \le M q(x)$ for all $x$ (envelope condition). Loop: draw $X \sim q$, then $U \sim \text{Uniform}(0, 1)$; accept $X$ if $U \le p(X)/(M q(X))$, otherwise retry. Acceptance probability:

where $q(x)$ is the density of $X$ at $x$ and the factor in parentheses is the conditional acceptance probability at $x$; the expected number of trials is exactly $M$ — tighter envelopes ($M$ close to 1) are more efficient, and the result is independent of the normalization constant of $p$ (any constant factor is absorbed into the envelope).

targets known only up to a constant (e.g. Bayesian posteriors $\propto$ prior $\times$ likelihood) in low dimension; interviews often ask for the acceptance-rate derivation and "why it fails in high dimensions".

exact samples without inverting a CDF or normalizing the target — the simplest general exact sampler; but the acceptance rate $1/M$ decays exponentially with dimension $d$ ($M \propto c^d$) because of volume concentration, so nearly all proposals are rejected and one must switch to MCMC or importance sampling.

Test Your Knowledge: Practice Questions for "Rejection Sampling"

Single choice pitfall questions with instant feedback and mistake tracking.