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 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/
Stephanie Glen. "Acceptance-Rejection Sampling: Plain English Definition / Overview" From StatisticsHowTo.com: Elementary Statistics for the rest of us! https://www.statisticshowto.com/acceptance-rejection-sampling/
Need help with a homework or test question? With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field. Your first 30 minutes with a Chegg tutor is free!
Comments? Need to post a correction? Please post a comment on our Facebook page.