Rejection sampling

From Free net encyclopedia

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>.

Rejection sampling is used in cases where <math>f(x)</math> is difficult to sample directly from. The difficult sampling problem can be avoided by sampling from an easy to sample envelope distribution <math>Mg(x)</math> instead, and probabilistically accepting or rejecting the samples.

The algorithm goes as follows:

  • Sample <math>x</math> from <math>g(x)</math> and <math>u</math> from <math>U(0,1)</math>
  • Check whether or not <math>u<f(x)/Mg(x)</math>.
    • If this holds, accept <math>x</math> as a realization of <math>f(x)</math>;
    • if not, reject the value of <math>x</math> and repeat the sampling step.

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<f(x)/Mg(x)</math> then produces pairs <math>(x,v)</math> uniformly distributed over the subgraph of <math>f(x)</math> and thus, marginally, a simulation from <math>f(x)</math>.

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>.

[edit]

Example

Image:Circle sampling.png As a simple geometric example, suppose it is desired to generate a random point within the unit circle. Generate a candidate point <math>(x,y)</math> where <math>x</math> and <math>y</math> are independent uniformly distributed between −1 and 1. If it so happens that <math>x^2+y^2 \leq 1</math> then the point is within the unit circle and should be accepted. If not then this point should be rejected and another candidate should be generated.

[edit]

References

  • Robert, C.P. and Casella, G. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.de:Verwerfungsmethode
Retrieved from "http://www.netipedia.com/index.php/Rejection_sampling"