Rejection sampling

For sampling values from an arbitrary probability distribution function <math>f(x)<math> by using an instrumental distribution <math>g(x)<math> under the only restriction that <math>f(x)< Mg(x)<math> where <math>M>1<math> is an appropriate bound on <math>f(x)/g(x)<math>. The algorithm goes as follows: sample <math>x<math> from <math>g(x)<math> and <math>u<math> from <math>U(0,1)<math> and check whether or not <math>u

The validation of this method is the envelope principle: when simulating the pair <math>(x,v=u*Mg(x))<math>, one produces a uniform simulation over the subgraph of <math>Mg(x)<math>. Accepting only pairs such that <math>u

Also called the acceptance-rejection method or "accept-reject algorithm", this method relates to the general field of Monte Carlo techniques, including Markov chain Monte Carlo algorithms that also use a proxy distribution to achieve simulation from the target distribution <math>f(x)<math>.

References

• Robert, C.P. and Casella, G. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.