Rejection Sampling

Rejection sampling draws exact samples from a target density by proposing from an easier envelope distribution and accepting each proposal with a probability proportional to the ratio of target to envelope, discarding the rest.

Definition

Rejection sampling is a Monte Carlo technique that generates a candidate from a proposal density dominating the target up to a constant, then accepts the candidate with probability equal to the target-to-bound density ratio, yielding accepted values distributed exactly as the target.

Scope

This topic covers the basic acceptance-rejection algorithm and its correctness, the role of the envelope and the bounding constant in determining efficiency, the squeeze technique for avoiding costly density evaluations, and adaptive constructions such as adaptive rejection sampling for log-concave densities. It connects to acceptance steps inside Markov chain methods.

Core questions

• Why are accepted candidates distributed exactly according to the target density?
• How does the bounding constant control the expected number of proposals per accepted draw?
• How do squeeze functions reduce the number of expensive density evaluations?
• How can the envelope be built and refined automatically for log-concave densities?

Key concepts

• Envelope distribution
• Bounding constant
• Acceptance probability
• Squeeze function
• Log-concavity

Key theories

Acceptance-rejection principle

If a proposal density times a constant dominates the target everywhere, accepting proposals with probability equal to the target-over-bound ratio produces exact target samples; the acceptance probability equals the reciprocal of the bounding constant.

Adaptive rejection sampling

For log-concave densities a piecewise-exponential envelope built from tangents and chords can be refined at each rejected point, driving the acceptance rate toward one without requiring the normalizing constant.

Clinical relevance

Rejection sampling generates variates from densities known only up to a constant, which arise constantly in Bayesian computation; adaptive rejection sampling in particular supplies the full-conditional draws inside many Gibbs samplers, making it a building block of practical posterior simulation.

History

Von Neumann described the acceptance-rejection idea in the early days of Monte Carlo computation; later work generalized the envelopes, added squeeze steps for efficiency, and developed adaptive schemes that automatically tighten the envelope for log-concave targets used in Bayesian sampling.

Key figures

• John von Neumann
• Luc Devroye
• Walter Gilks
• Christian P. Robert

Seminal works

• devroye1986
• gilks1992

Frequently asked questions

What makes rejection sampling efficient or inefficient?

Efficiency is governed by how tightly the scaled envelope hugs the target. A loose envelope means a large bounding constant and many rejected proposals; in high dimensions the acceptance rate can become impractically small.

Why is rejection sampling useful when the normalizing constant is unknown?

The method only needs the target density up to a multiplicative constant, because that constant is absorbed into the bounding constant. This is why it pairs naturally with Bayesian posteriors, which are typically known only up to their normalizer.