Rejection sampling is a method for generating random samples from a target probability distribution by drawing candidates from a simpler distribution and accepting them with carefully chosen probabilities. The acceptance rule corrects the difference between the proposal and target distributions, so that accepted candidates have exactly the target distribution under ideal mathematical assumptions. The method can be used even when the target density is known only up to a multiplicative constant, provided a suitable upper bound is available.
Mathematical formulation
Let be a target probability density function and let be a proposal density from which samples can be generated efficiently. Suppose a known finite constant satisfies
throughout the relevant domain, apart from sets of measure zero. The function is called an envelope for the target density.
The rejection sampling algorithm repeats the following steps:
Generate a candidate from .
Independently generate from the uniform distribution on .
Accept if
Otherwise discard and repeat.
Because both and integrate to one, any valid envelope constant satisfies .
The proposal must cover the target: it cannot assign zero density to a region having positive target probability. This support condition alone is insufficient, however. The ratio must also admit a finite upper bound, except on negligible sets.
The same construction applies to discrete distributions by replacing densities with probability mass functions and integrals with sums. More generally, the two distributions may have densities relative to a common reference measure.
Why the method works
For any measurable set , the probability that a single proposal is both accepted and lies in is
Taking to be the whole domain gives
Consequently, conditioning on acceptance yields
Thus the accepted candidate has density . If every trial uses fresh independent randomness and the proposal and envelope are fixed, successive accepted values are independent and identically distributed.
Geometric interpretation
For a continuous target, define . Conditional on , the coordinate is uniform between zero and . The pair is therefore uniformly distributed, in the area-measure sense, over the region beneath the envelope.
Acceptance retains only the points lying beneath . Their horizontal coordinates have density proportional to the height , which gives the target density. This interpretation also works in higher dimensions using volume rather than area.
Unnormalized target densities
Frequently, the target is available only in the form
where can be evaluated but the normalizing constant is unknown. This is common in Bayesian inference, where a posterior density is proportional to the product of a likelihood and a prior density.
Suppose a known constant satisfies
The acceptance rule becomes
No evaluation of is needed. The acceptance probability is now
and accepted candidates have density .
Avoiding the normalizing constant does not remove the need for a valid envelope. Establishing a global bound on can be the main difficulty.
Efficiency and envelope selection
With a fixed proposal, the number of trials required for one accepted sample has a geometric distribution:
Its expected value and variance are
For normalized densities, these become and , respectively. Generating accepted samples therefore requires proposals on average.
For a fixed proposal, the smallest valid constant is the essential supremum
“Essential” means that violations confined to sets of measure zero do not affect the distributional argument. In practice, a pointwise upper bound is often used.
A useful proposal balances several requirements:
- It is inexpensive to sample.
- Its density is inexpensive to evaluate.
- It covers all regions with positive target probability.
- It permits a provable finite envelope.
- It follows the target closely enough to keep the acceptance rate useful.
Acceptance rate is not the only measure of efficiency. A complicated proposal may accept more often while taking longer per accepted sample.
Tail behavior
A finite envelope can fail to exist when the proposal has tails that decay too quickly. For example, a normal proposal cannot globally dominate a Cauchy target: the Cauchy density decays polynomially, whereas the normal density decays exponentially in the square of the argument. Their target-to-proposal ratio is unbounded.
Heavier proposal tails help avoid this problem but do not, by themselves, guarantee an efficient envelope.
Example: a triangular density
Consider
Choose a uniform proposal on , so there. Since , take . The acceptance rule simplifies to
An implementation repeatedly draws independent uniform values and , retaining whenever . Larger candidate values are accepted more frequently, producing the increasing target density.
The acceptance probability is
so two proposals are required per accepted sample on average.
High-dimensional limitations
Rejection sampling can become inefficient in high-dimensional spaces because a proposal may match the target poorly over much of its domain.
For example, consider product densities
If the optimal one-dimensional envelope constant is , the corresponding optimal product-envelope constant is , giving acceptance probability
Even a modest mismatch in each coordinate can therefore cause exponential deterioration. This illustrates the curse of dimensionality, rather than a universal impossibility result: a well-matched proposal can still work well in many dimensions.
When the target factorizes, sampling its coordinates separately can avoid the inefficiency of rejecting an entire vector whenever one coordinate fails its acceptance test.
Variants and improvements
Squeezing
A squeeze uses an inexpensive lower bound . After generating and , a candidate can be accepted immediately if
Only undecided candidates require evaluation of . An inexpensive upper bound may similarly allow early rejection. Valid bounds preserve the target distribution while reducing evaluation costs.
Adaptive rejection sampling
Adaptive rejection sampling updates an envelope using information from previously evaluated points. A standard construction applies to positive one-dimensional densities whose logarithm is concave.
For a differentiable log-concave density, tangent lines to the log density provide upper bounds. A piecewise-linear upper envelope in log space becomes a piecewise-exponential envelope in density space, which can be integrated and sampled.
Additional evaluation points can tighten the envelope and improve acceptance. Correctness requires every updated envelope to remain valid; an arbitrary fitted approximation is not sufficient. When each trial uses a valid envelope selected from past information and fresh randomness, its conditional accepted distribution remains the target.
Relationship to other sampling methods
Inverse transform sampling generates a uniform value and applies the inverse cumulative distribution function. It avoids discarded candidates but requires a usable inverse or numerical inversion procedure.
Importance sampling also draws from a proposal, but assigns weights proportional to rather than rejecting candidates. It is primarily used to estimate integrals or expectations. A finite global envelope is unnecessary, although unstable weights can produce poor estimates.
Markov chain Monte Carlo methods generate a dependent sequence whose stationary distribution is the target. A rejected Metropolis–Hastings proposal leaves the chain at its current state; rejection sampling instead discards the candidate and tries again. Fixed-envelope rejection sampling produces independent target draws without a convergence period.
Conditioning by rejection retains draws from a distribution only when they satisfy an event. The retained draws follow the corresponding conditional distribution. This is exact when the event has positive probability, but becomes inefficient when the event is rare.
Implementation and exactness
The mathematical guarantee assumes correct proposal generation, valid bounds, and exact acceptance comparisons. Actual implementations use pseudorandom numbers and floating-point arithmetic.
For very small densities, the test can be evaluated in logarithmic form:
This reduces underflow and overflow risks, though zero densities and boundary values still require careful handling.
A bound obtained only by checking a finite grid or a collection of random points is not generally a certified global bound. If on a set with positive proposal probability, the algorithm is invalid. Silently clipping the ratio at one does not fix it: the resulting accepted density is proportional to
rather than to .
With a positive acceptance probability, the algorithm terminates almost surely, but there is no finite deterministic upper bound on the number of trials. Imposing a fixed trial limit introduces a possible failure outcome; returning a rejected candidate when that limit is reached generally changes the output distribution.