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 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 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
- 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).
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/
Confused and have questions? Head over to Chegg and use code “CS5OFFBTS18” (exp. 11/30/2018) to get $5 off your first month of Chegg Study, so you can understand any concept by asking a subject expert and getting an in-depth explanation online 24/7.
Comments? Need to post a correction? Please post a comment on our Facebook page.