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