Rejection sampling - Ciallo Wiki

1 Introduction to rejection sampling

Rejection sampling is a Monte Carlo technique for producing random draws from a desired probability distribution when direct sampling is difficult. It combines two ingredients: an easier-to-sample proposal distribution and a criterion that decides whether each proposed draw is retained or discarded. Over many iterations, the retained values form samples that follow the target distribution.

1.1 Core idea and accept–reject mechanism

The method draws a candidate value from a proposal distribution and then compares how large the target density is at that value to a pre-specified upper bound on the target density. If the candidate lies in the “acceptable region,” it is kept; otherwise it is rejected. Conceptually, this corresponds to sampling uniformly under an envelope curve that dominates the target density and accepting points that fall beneath the target.

In practice, the accept–reject decision is implemented by computing an acceptance probability. A uniform random number is generated and compared with this probability. If the number is smaller, the candidate is accepted; otherwise, it is discarded.

1.2 When and why it is used

Rejection sampling is often used when:

The target distribution is known up to a multiplicative constant, yet sampling directly is not feasible.
A convenient proposal distribution can be constructed that roughly resembles the target.
The target is one-dimensional (or low-dimensional), where envelope construction and bounding are manageable.

It is also useful as a baseline method. Even when it is not the most computationally efficient option, it is conceptually straightforward and can serve as a reference for more advanced algorithms.

1.3 Relationship to Monte Carlo simulation

Rejection sampling produces i.i.d. samples from the target distribution (assuming independent proposal draws). These samples can then be used to approximate expectations, probabilities, and integrals via Monte Carlo estimators. Because each iteration either yields a sample or is discarded, the overall computational effort varies with the acceptance rate, but the statistical correctness of the accepted draws does not depend on the number of rejections.

2 Mathematical foundation

The correctness of rejection sampling relies on a bounding relationship between the target density and an envelope built from the proposal distribution. Once this relationship is in place, the acceptance rule ensures that the distribution of accepted points matches the target.

2.1 Target and proposal distributions

Let the target distribution have density (or mass) \(p(x)\) and the proposal distribution have density \(q(x)\), defined on the same support. The algorithm typically assumes that sampling from \(q\) is straightforward and that \(p(x)\) can be evaluated pointwise (even if only up to normalization).

2.1.1 Probability density and mass function considerations

For continuous targets, \(p(x)\) and \(q(x)\) are probability density functions. For discrete targets, they are probability mass functions. The acceptance–rejection logic is analogous, but the envelope relationship is expressed in terms of probabilities rather than densities. Many implementations treat both cases through a unified “evaluate-and-compare” structure.

2.1.2 Normalization and unnormalized densities

In many applications, the target density is known only up to a constant: \(p(x) \propto \tilde{p}(x)\). Rejection sampling can still be applied because acceptance probabilities depend on ratios in which the unknown constant cancels out, provided the envelope bound is established for the unnormalized form in a consistent way.

2.2 Envelope (bounding) condition

A key requirement is the existence of a constant \(M \ge 1\) such that the target density is everywhere bounded by a scaled version of the proposal density: \[ p(x) \le M\, q(x) \quad \text{for all } x \text{ in the support where } p(x) > 0. \] This ensures the envelope dominates the target across the relevant region.

2.2.1 Choosing the scaling constant

The constant \(M\) should be chosen so that the inequality holds globally (or at least on the region where the target has support). One may seek a tight bound to improve efficiency. If \(M\) is overly conservative, the envelope becomes much higher than needed and many proposals will be rejected.

In practice, \(M\) can be determined analytically for common families, estimated numerically, or derived using upper bounds for the ratio \(p(x)/q(x)\).

2.2.2 Validity constraints for correctness

Correctness depends on two conditions:

Dominance: The envelope must upper-bound the target: \(p(x) \le M q(x)\) wherever the target is positive.
Support overlap: Where \(p(x) > 0\), the proposal must satisfy \(q(x) > 0\) so that the ratio is well-defined and candidates can, in principle, land in the target’s support.

Violating dominance causes the acceptance rule to no longer correspond to a valid probability, undermining the target recovery guarantee. Lack of support overlap prevents the algorithm from producing values where the target assigns positive probability.

2.3 Acceptance probability derivation

Given the dominance condition, one can derive an acceptance probability that yields the correct target distribution among accepted samples.

2.3.1 Acceptance rule in density form

A standard acceptance probability is \[ \alpha(x) = \frac{p(x)}{M\, q(x)}. \] Operationally, after proposing \(x \sim q\), the algorithm accepts \(x\) with probability \(\alpha(x)\). Since \(p(x) \le M q(x)\), this ratio satisfies \(0 \le \alpha(x) \le 1\).

2.3.2 Proof sketch of target distribution recovery

A proof sketch proceeds by considering the joint behavior of a proposal and its acceptance decision. The density of accepted points is proportional to \(q(x)\alpha(x)\), since accepted samples occur with probability \(\alpha(x)\) given proposal \(x\). Substituting \(\alpha(x)=p(x)/(M q(x))\) gives \[ q(x)\alpha(x) = q(x)\frac{p(x)}{M q(x)} = \frac{p(x)}{M}, \] which is proportional to \(p(x)\). After normalization over the acceptance events, the distribution of accepted draws equals the target distribution.

3 Algorithmic procedure

This section describes the practical steps of rejection sampling and the implementation choices that affect robustness and correctness.

3.1 Step-by-step sampling algorithm

A typical continuous-case procedure is:

Choose a proposal distribution \(q(x)\) from which sampling is easy.
Find \(M\) such that \(p(x) \le M q(x)\) on the relevant support.
Repeat until the desired number of accepted samples is obtained:

Draw \(x \sim q\).
Compute \(\alpha(x)=p(x)/(M q(x))\).
Draw \(u \sim \text{Uniform}(0,1)\).
If \(u \le \alpha(x)\), accept \(x\); otherwise reject it.

For discrete distributions, “draw \(x\)” and “compute \(\alpha(x)\)” remain the same in structure, but \(p\) and \(q\) are mass functions and the envelope bound must be checked for probability values.

3.2 Practical implementation details

Numerical implementation requires careful treatment of evaluation of densities/masses and of boundary cases where the ratio may be unstable.

3.2.1 Handling discrete versus continuous cases

For discrete targets, candidate values come from a finite or countable set. The envelope inequality must hold pointwise on that set: \[ p(x_i) \le M q(x_i). \] For continuous targets, densities may be extremely small in regions of the space; evaluating \(p(x)\), \(q(x)\), and their ratio must be done with attention to floating-point underflow and rounding.

3.2.2 Numerical stability and edge cases

Common stability tactics include:

Log-domain computation: Compute \(\log p(x)\) and \(\log q(x)\) and form \(\log \alpha(x)=\log p(x) - \log q(x) - \log M\), converting back only if needed.
Clipping due to numerical error: If due to approximation one obtains \(\alpha(x)>1\) by a tiny margin, it may be clipped to 1; however, systematic overshooting suggests the envelope bound is incorrect.
Zero proposal density: If \(q(x)=0\) while \(p(x)>0\), the ratio cannot be evaluated and the proposal support is insufficient. In a correct setup, accepted candidates should not encounter this situation.

Edge cases also include targets with bounded support and proposals that place mass outside that support; in those regions the acceptance probability will be zero, which is safe but may reduce efficiency.

3.3 Estimating acceptance rate

The acceptance rate affects the number of proposal draws required per accepted sample.

3.3.1 Expected number of proposals per sample

If proposals are accepted with probability \(a\), then the number of proposals per accepted sample follows a geometric distribution with mean \(1/a\). Here, \(a\) is the average acceptance probability: \[ a = \mathbb{E}_{x\sim q}\left[\alpha(x)\right] = \int q(x)\frac{p(x)}{M q(x)}\,dx = \frac{1}{M}\int p(x)\,dx = \frac{1}{M}, \] assuming \(p\) is normalized. For unnormalized targets, the same relationship holds in terms of the bound constant used consistently with the normalization implied by the acceptance ratio.

3.3.2 Measuring inefficiency

A useful diagnostic is to monitor the empirical acceptance frequency during a run. If the observed acceptance rate is far below the theoretically predicted \(1/M\), possible causes include:

\(M\) being underestimated.
Numerical errors in density evaluation.
A mismatch between the implemented proposal and the proposal assumed in the bound.

4 Efficiency and performance

Efficiency in rejection sampling is dominated by how well the proposal and envelope approximate the target. While the method is unbiased under correct bounding, its runtime can vary substantially.

4.1 Factors affecting acceptance rate

The acceptance probability at \(x\) depends on \(p(x)/q(x)\). Efficiency improves when:

The proposal resembles the target in the regions where the target has mass.
The envelope constant \(M\) is close to the true supremum of \(p(x)/q(x)\).
The proposal does not allocate large probability to regions where the target is negligible.

Conversely, poor overlap yields many rejected candidates and increased computational expense per accepted draw.

4.2 Selecting a good proposal distribution

Constructing a strong proposal is often the central design step.

4.2.1 Tail matching and overlap considerations

A common failure mode occurs in the tails: if the target has heavier tails than the proposal, the envelope may require a large \(M\), since the ratio \(p(x)/q(x)\) can become large for extreme values. On the other hand, if the proposal has much heavier tails than the target, many samples will be proposed in low-probability regions under the target, again reducing acceptance.

Overlap is assessed by where \(p(x)\) is substantial. A proposal that concentrates mass in the same region as the target typically yields a higher acceptance rate.

4.2.2 Minimizing wasted area under the envelope

Geometrically, the envelope-based view compares the “area” under the target with the larger “area” under the scaled proposal. The expected acceptance rate corresponds to the fraction of the envelope under the target. Thus, tightening \(M\) and shaping \(q\) to hug the target reduces wasted area and speeds up sampling.

4.3 Computational cost analysis

Total cost includes:

Time to sample from \(q\).
Time to evaluate \(p(x)\) and \(q(x)\) (or their logs).
Additional bookkeeping for rejection and repeated draws.

Even if evaluation is cheap, low acceptance can dominate runtime. In scenarios where evaluations are expensive, it may be beneficial to spend effort improving the proposal so that fewer candidates must be tested.

5 Special cases and extensions

Rejection sampling adapts to targets with different support structures and can be extended using more sophisticated proposal strategies.

5.1 Bounded-support targets

If the target is supported on a finite interval, the envelope can be constructed over that interval only. One can choose proposals with the same bounded support, often reducing the envelope width and improving acceptance. In the bounded case, it is also easier to establish an accurate global bound \(M\).

5.2 Unbounded targets and practical bounding strategies

For targets on \((-\infty,\infty)\) or \([0,\infty)\), the envelope must handle potentially large ranges. Common strategies include:

Using proposals whose tails are at least as heavy as the target’s tails so that \(p(x)/(q(x))\) remains bounded.
Building bounds piecewise, using different proposals or analytic envelope forms in different regions.
Employing numerical optimization to approximate the supremum of \(p(x)/(q(x))\) for candidate values.

Unbounded targets make envelope tightness harder; inaccurate bounds can either break correctness (if too small) or reduce efficiency (if too large).

5.3 Mixture proposals

A proposal distribution can be constructed as a mixture \(q(x)=\sum_k w_k q_k(x)\). Mixtures can improve overlap by combining proposals tailored to different regions of the target. However, the acceptance ratio involves the mixture density, not the component density, so computing \(q(x)\) is required at each step.

Mixture proposals can reduce the required \(M\) when no single proposal family adequately matches the entire target shape.

5.4 Multiple-try and adaptive rejection concepts (high-level)

Beyond basic rejection sampling, there exist families of methods that:

Try multiple candidates per iteration and select among them in a way that reduces waste.
Adjust proposal parameters over time based on observed regions of high target density.

At a high level, these extensions aim to raise acceptance efficiency without sacrificing correctness, often by improving how the envelope approximates the target during the run.

6 Diagnostics and validation

Correct implementation should be validated both empirically and through consistency checks related to acceptance probabilities and bounding.

6.1 Checking sample fidelity to the target

If the target distribution has known moments or characteristic features, one can compare empirical estimates from accepted samples to their theoretical values. Another approach is to verify that the implemented envelope bound holds over a set of test points, ensuring that acceptance probabilities stay within \([0,1]\) up to numerical tolerances.

6.2 Comparing histograms and summary statistics

For one-dimensional problems, histogram overlays provide a quick qualitative check: the density shape of the accepted samples should align with the target curve. Summary statistics such as mean, variance, and quantiles can provide quantitative agreement, especially when the distribution has known reference values.

For continuous targets, careful choice of histogram binning and sufficient sample size are important to avoid misleading artifacts.

6.3 Convergence and variance considerations

Because accepted samples are drawn independently (in the basic rejection-sampling setup), Monte Carlo convergence follows typical i.i.d. behavior. Variance of estimators depends on both the variability of the target and the number of accepted samples achieved within a fixed runtime. Low acceptance effectively reduces the number of usable samples, increasing estimator uncertainty for a given computational budget.

Practically, it is often useful to track acceptance rate and then relate it to the effective sample size.

7 Worked examples

Worked examples illustrate how proposal selection, bounding, and acceptance rules apply in concrete settings.

7.1 Sampling from simple bounded targets

Consider a target distribution on a finite interval, such as a density with a known maximum on \([a,b]\). One may choose a uniform proposal on \([a,b]\). In that case, \(q(x)\) is constant and the envelope condition becomes finding \(M\) such that \(p(x)\le M q(x)\) for all \(x\in[a,b]\), which is equivalent to \(M\) matching the maximum ratio of \(p(x)\) to the uniform height. The acceptance probability is then proportional to the target density at the proposed \(x\).

This example highlights a common pattern: bounded support and a simple proposal often make the bound easy to compute, though efficiency may suffer if the target is sharply peaked.

7.2 Sampling with unnormalized target densities

Suppose the target is specified as \(p(x)\propto \tilde{p}(x)\), and \(\tilde{p}\) can be evaluated. If one can find an envelope bound for the ratio \(\tilde{p}(x)/q(x)\), then the acceptance probability can be implemented using \(\tilde{p}\) with the same constant \(M\) adjusted accordingly. The unknown normalization cancels in the ratio, so exact normalization of the target is not required for sampling correctness.

This is particularly useful in Bayesian contexts where posteriors are often available only up to a constant.

7.3 Choosing proposals in common scenarios

In practice, proposal choices depend on the target shape:

If the target resembles a log-concave distribution, choosing a distribution with similar curvature can improve overlap.
If the target has multiple modes, using a mixture proposal aligned with the modes can reduce the chance of repeatedly proposing from low-density regions.
If the target is heavy-tailed, selecting a proposal with comparable or heavier tails helps keep the ratio bounded without inflating \(M\).

Selecting a proposal is therefore an exercise in matching both central mass and tail behavior to maintain a reasonable acceptance rate.

8 Connections to other methods

Rejection sampling relates to several other Monte Carlo approaches through shared ideas such as weighting, proposals, and bounding.

8.1 Relation to importance sampling

Importance sampling uses a proposal distribution \(q\) to estimate expectations under the target \(p\) via weights proportional to \(p(x)/q(x)\). Rejection sampling can be viewed as a mechanism that converts the ratio \(p/q\) into an accept–reject probability, producing unweighted samples rather than weighted estimates. While importance sampling always yields proposals that contribute through weights, rejection sampling discards many candidates and instead produces directly target-distributed draws.

Both methods leverage the same fundamental quantity \(p(x)/q(x)\), but they use it differently.

8.2 Relation to Markov Chain Monte Carlo (conceptual contrast)

Markov Chain Monte Carlo constructs a dependent sequence whose stationary distribution is the target. In contrast, basic rejection sampling aims for independent accepted samples. MCMC methods can handle complex high-dimensional targets where constructing an envelope is challenging, but they require burn-in and dependence assessments. Rejection sampling avoids such dependence diagnostics when feasible, but the envelope construction becomes difficult as dimension grows.

8.3 Connections to envelope-based algorithms

Envelope-based algorithms share the concept of using an upper bound to control sampling. Rejection sampling uses a global or fixed envelope constant, while related envelope-based strategies may use piecewise bounds or adapt envelopes to better match the target. These variants aim to increase acceptance efficiency by tightening the bound in regions where the target is relatively high.

9 Common pitfalls

Most implementation failures trace back to incorrect bounds, inefficient proposals, or misunderstandings about discrete versus continuous formulations.

9.1 Incorrect bounding envelopes

If \(M\) is chosen too small, the acceptance ratio \(\alpha(x)\) can exceed 1 in some region. This breaks the probabilistic interpretation and invalidates correctness guarantees. Even if one clips \(\alpha(x)\) numerically to 1, that ad hoc fix may bias the output.

The reliable approach is to confirm the dominance condition analytically or with conservative validation aligned with the theoretical envelope requirement.

9.2 Poor proposal choices and low acceptance

A proposal that matches the target only loosely can lead to very low acceptance rates, making runs inefficient. Symptoms include:

Large numbers of rejections relative to accepted samples.
Empirical acceptance rates much smaller than expected based on the chosen \(M\).

Improving overlap—especially in tails and modes—typically yields the biggest efficiency gains.

9.3 Misinterpreting acceptance probability for discrete targets

Discrete targets require a pointwise probability bound rather than a density bound. Confusing the continuous formula with a discrete setting can lead to applying an envelope in the wrong units. Correct discrete implementations evaluate \(p(x_i)\) and \(q(x_i)\) as mass functions and ensure \(p(x_i)\le M q(x_i)\) for each point that might be proposed.

10 Applications and use cases

Rejection sampling appears in many contexts where sampling from a target distribution is necessary but direct methods are unavailable or impractical.

10.1 Generating samples for expectation estimation

Accepted samples can be used to estimate expectations of functions \(g(x)\) under the target: \[ \mathbb{E}_p[g(X)] \approx \frac{1}{N}\sum_{i=1}^N g(x_i), \] where \(x_i\) are accepted draws. This makes the method useful whenever integrals are easier to approximate via sampling than via analytic methods.

10.2 Use in Bayesian computation (general overview)

In Bayesian workflows, posterior distributions are often available up to a normalizing constant. Rejection sampling can sometimes be applied by choosing a proposal distribution that bounds the unnormalized posterior density. While it may be less common than specialized sampling algorithms for high-dimensional problems, it can be effective in low-dimensional settings, for pedagogical demonstrations, or as a component in larger pipelines.

10.3 Simulation workflows where direct sampling is unavailable

More broadly, rejection sampling can be used in simulation studies, reliability modeling, and any setting where:

The target distribution is defined by a known probability law or likelihood-like function.
Direct sampling from that law is not straightforward.
A reasonable proposal distribution and envelope bound can be constructed.