Sampling > Acceptance-Rejection sampling
Acceptance-Rejection sampling is a way to simulate random samples from an unknown (or difficult to sample from) distribution (called the target distribution) by using random samples from a similar, more convenient probability distribution. A random subset of the generated samples are rejected; the rest are accepted. The goal is for the accepted samples to be distributed as if they were from the target probability distribution.
Let’s say you wanted to sample from the inverse of a particular function, but an explicit inverse doesn’t exist. You could use a similar distribution—making sure that (Carroll & Hamrick, 2011):
- The two distributions look as similar as possible, and
- Both functions have the same support (i.e. both cumulative distribution functions vanish or don’t vanish over the same set of real numbers)
Acceptance-rejection sampling is is a Monte Carlo method that has largely been replaced by newer Markov Chain Monte Carlo methods. It’s usually only used when it’s challenging to sample individual distributions within a larger Markov chain (Christensen et al., 2011).
General Steps for Acceptance-Rejection Sampling
General steps for sampling from a probability distribution with cumulative distribution function f(x), using a second function g(x) (Dieter & Ahrens, 1974) are:
- Generate a sample x from a distribution that has a density proportional to g(x), where g(x) ≥ f(x) for all x.
- Generate a [0,1)-uniform random number u.
If u > f(x)/g(x) reject the sample and return to Step 1; Otherwise accept x as a sample.
Dieter and Ahrens note that although the procedure is fairly simple, some mathematical skill is needed to choose an appropriate function g(x).
Acceptance-Rejection sampling is also used for double sampling.
References
Christensen, R. et al., (2011). Bayesian Ideas and Data Analysis: An Introduction for Scientists and Statisticians. CRC Press.
Dieter, U. & Ahrens, J. (1974). Acceptance-Rejection techniques for sampling from the gamma and beta distributions. Office of Naval Research Technical Report No. 83. Retrieved December 9, 2017 from: https://statistics.stanford.edu/sites/default/files/CHE%20ONR%2083.pdf
Glasserman, P. (2004). Monte Carlo Methods in Financial Engineering. Springer Science & Business Media.
Carroll, R. & Hamrick, J. (2011). Wolfram Demonstrations Project. Acceptance/Rejection sampling. Retrieved December 9, 2017 from: http://demonstrations.wolfram.com/AcceptanceRejectionSampling/