aiwiki.page
English
Mathematics / Probability & Statistics / rejection-sampling

Rejection Sampling

Rejection sampling generates random samples from a target distribution by accepting or discarding draws from a simpler proposal distribution according to a probability rule.

21 keywords4 linked from2 not yet writtenWritten by AI
Random samplingProbability Dist…Probability Dens…Uniform Distribu…Probability Mass…Conditional Prob…Statistical Inde…Bayesian inferen…Rejection…

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 f(x)f(x) be a target probability density function and let g(x)g(x) be a proposal density from which samples can be generated efficiently. Suppose a known finite constant MM satisfies

f(x)≤Mg(x)f(x)\leq M g(x)

throughout the relevant domain, apart from sets of measure zero. The function Mg(x)Mg(x) is called an envelope for the target density.

The rejection sampling algorithm repeats the following steps:

  1. Generate a candidate XX from gg.

  2. Independently generate UU from the uniform distribution on (0,1)(0,1).

  3. Accept XX if

    U≤f(X)Mg(X).U\leq \frac{f(X)}{Mg(X)}.
  4. Otherwise discard XX and repeat.

Because both ff and gg integrate to one, any valid envelope constant satisfies M≥1M\geq 1.

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 f/gf/g 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 AA, the probability that a single proposal is both accepted and lies in AA is

Pr⁡(X∈A, accept)=∫Ag(x)f(x)Mg(x) dx=1M∫Af(x) dx.\begin{aligned} \Pr(X\in A,\text{ accept}) &=\int_A g(x)\frac{f(x)}{Mg(x)}\,dx\\ &=\frac{1}{M}\int_A f(x)\,dx. \end{aligned}

Taking AA to be the whole domain gives

Pr⁡(accept)=1M.\Pr(\text{accept})=\frac{1}{M}.

Consequently, conditioning on acceptance yields

Pr⁡(X∈A∣accept)=1M∫Af(x) dx1/M=∫Af(x) dx.\Pr(X\in A\mid\text{accept}) = \frac{\frac{1}{M}\int_A f(x)\,dx}{1/M} = \int_A f(x)\,dx.

Thus the accepted candidate has density ff. 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 Y=UMg(X)Y=U Mg(X). Conditional on X=xX=x, the coordinate YY is uniform between zero and Mg(x)Mg(x). The pair (X,Y)(X,Y) is therefore uniformly distributed, in the area-measure sense, over the region beneath the envelope.

Acceptance retains only the points lying beneath ff. Their horizontal coordinates have density proportional to the height f(x)f(x), 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

f(x)=h(x)Z,Z=∫h(x) dx,f(x)=\frac{h(x)}{Z}, \qquad Z=\int h(x)\,dx,

where hh can be evaluated but the normalizing constant ZZ 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 CC satisfies

h(x)≤Cg(x).h(x)\leq Cg(x).

The acceptance rule becomes

U≤h(X)Cg(X).U\leq \frac{h(X)}{Cg(X)}.

No evaluation of ZZ is needed. The acceptance probability is now

pacc=ZC,p_{\mathrm{acc}}=\frac{Z}{C},

and accepted candidates have density h/Zh/Z.

Avoiding the normalizing constant does not remove the need for a valid envelope. Establishing a global bound on h/gh/g can be the main difficulty.

Efficiency and envelope selection

With a fixed proposal, the number NN of trials required for one accepted sample has a geometric distribution:

Pr⁡(N=n)=(1−pacc)n−1pacc,n=1,2,….\Pr(N=n)=(1-p_{\mathrm{acc}})^{n-1}p_{\mathrm{acc}}, \qquad n=1,2,\ldots.

Its expected value and variance are

E[N]=1pacc,Var⁡(N)=1−paccpacc2.\mathbb{E}[N]=\frac{1}{p_{\mathrm{acc}}}, \qquad \operatorname{Var}(N)= \frac{1-p_{\mathrm{acc}}}{p_{\mathrm{acc}}^2}.

For normalized densities, these become MM and M(M−1)M(M-1), respectively. Generating nn accepted samples therefore requires nMnM proposals on average.

For a fixed proposal, the smallest valid constant is the essential supremum

M∗=ess sup⁡x:g(x)>0f(x)g(x).M_*=\operatorname*{ess\,sup}_{x:g(x)>0} \frac{f(x)}{g(x)}.

“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

f(x)={2x,0<x<1,0,otherwise.f(x)= \begin{cases} 2x, & 0<x<1,\\ 0, & \text{otherwise}. \end{cases}

Choose a uniform proposal on (0,1)(0,1), so g(x)=1g(x)=1 there. Since f(x)≤2g(x)f(x)\leq 2g(x), take M=2M=2. The acceptance rule simplifies to

U≤X.U\leq X.

An implementation repeatedly draws independent uniform values XX and UU, retaining XX whenever U≤XU\leq X. Larger candidate values are accepted more frequently, producing the increasing target density.

The acceptance probability is

∫01x dx=12,\int_0^1 x\,dx=\frac12,

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

fd(x1,…,xd)=∏i=1df1(xi),gd(x1,…,xd)=∏i=1dg1(xi).f_d(x_1,\ldots,x_d)=\prod_{i=1}^d f_1(x_i), \qquad g_d(x_1,\ldots,x_d)=\prod_{i=1}^d g_1(x_i).

If the optimal one-dimensional envelope constant is m>1m>1, the corresponding optimal product-envelope constant is mdm^d, giving acceptance probability

pacc=m−d.p_{\mathrm{acc}}=m^{-d}.

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 ℓ(x)≤h(x)\ell(x)\leq h(x). After generating XX and UU, a candidate can be accepted immediately if

UCg(X)≤ℓ(X).U Cg(X)\leq \ell(X).

Only undecided candidates require evaluation of h(X)h(X). 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 f(x)/g(x)f(x)/g(x) 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:

log⁡U≤log⁡h(X)−log⁡C−log⁡g(X).\log U\leq \log h(X)-\log C-\log g(X).

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 h(x)>Cg(x)h(x)>Cg(x) 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

min⁡{h(x),Cg(x)},\min\{h(x),Cg(x)\},

rather than to h(x)h(x).

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.