Rejection Sampling - Algorithm

Algorithm

The algorithm (used by John von Neumann and dating back to Buffon and his needle) is as follows:

• Sample from and from (the uniform distribution over the unit interval)
• Check whether or not .
  • If this holds, accept as a realization of ;
  • if not, reject the value of and repeat the sampling step.

The validation of this method is the envelope principle: when simulating the pair, one produces a uniform simulation over the subgraph of . Accepting only pairs such that then produces pairs uniformly distributed over the subgraph of and thus, marginally, a simulation from .

This means that, with enough replicates, the algorithm generates a sample from the desired distribution . There are a number of extensions to this algorithm, such as the Metropolis algorithm.