Drawing from a simple distribution and keeping points that fall under the target one.Rejection sampling is a simple Monte Carlo method for generating samples from a target probability distribution when direct sampling is difficult. It works by sampling from a simpler proposal distribution that covers the target distribution, then accepting or rejecting each sample based on a random test. The accepted samples follow the target distribution exactly. It is a foundational algorithm in computational physics and statistics, often used as a building block for more sophisticated methods like Markov chain Monte Carlo.
The method was described by John von Neumann in 1951 in a paper on various techniques for random number generation, though similar ideas appeared earlier in the statistical literature.
Given a target distribution p(x) and a proposal distribution q(x) such that p(x) ≤ M·q(x) for some constant M, you draw a candidate x from q(x) and a uniform random number u in [0,1]. Accept x if u < p(x)/(M·q(x)), otherwise reject and try again. The accepted samples are distributed according to p(x). The efficiency depends on the ratio of the areas under p and M·q; if M is too large, many samples are rejected, wasting computation. The method works best when q is a good approximation to p.
Used in particle physics to generate random events according to complex differential cross-sections, and in Bayesian statistics to sample from posterior distributions when the normalizing constant is unknown.
Rejection sampling is also known as the 'accept-reject method' and is a key ingredient in the famous Metropolis-Hastings algorithm, which generalizes it to handle high-dimensional problems.
