Rejection sampling is a basic technique used to generate observations from a distribution. [Wikipedia]
From Wikipedia:
Rejection sampling is a basic technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or "accept-reject algorithm" and is a type of Monte Carlo method. The method works for any distribution in $\mathbb R^m$ with a density.
Rejection sampling is based on the observation that to sample a random variable one can sample uniformly from the region under the graph of its density function [(Neal, 2003; Bishop, 2006)]...
As a simple geometric example, suppose it is desired to generate a random point within the unit circle. Generate a candidate point $(x,y)$ where $x$ and $y$ are independent uniformly distributed between −1 and 1. If it so happens that $x^2+y^2\le1$ 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...
Rejection sampling can lead to a lot of unwanted samples being taken if the function being sampled is highly concentrated in a certain region, for example a function that has a spike at some location. For many distributions, this problem can be solved using an adaptive extension (see adaptive rejection sampling). In addition, as the dimensions of the problem get larger, the ratio of the embedded volume to the "corners" of the embedding volume tends towards zero, thus a lot of rejections can take place before a useful sample is generated, thus making the algorithm inefficient and impractical. See curse of dimensionality. In high dimensions, it is necessary to use a different approach, typically a Markov chain Monte Carlo method such as Metropolis sampling or Gibbs sampling.
References
- Bishop, C. (2006). 11.4: Slice sampling. Pattern Recognition and Machine Learning. Springer.
- Neal, R. M. (2003). Slice sampling. Annals of Statistics, 31(3), 705–767. Retrieved from http://people.ee.duke.edu/~lcarin/slice.pdf.
