Acceptance-Rejection Algorithm
Jump to navigation
Jump to search
See: Data Generation, Continuous Random Variable, Simulation.
References
2011
- http://en.wikipedia.org/wiki/Rejection_sampling
- QUOTE: In mathematics, rejection sampling is a basic pseudo-random number sampling technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or “accept-reject algorithm”. It generates sampling values from an arbitrary probability distribution function [math]\displaystyle{ f(x) }[/math] by using an instrumental distribution [math]\displaystyle{ g(x) }[/math], under the only restriction that [math]\displaystyle{ f(x)\lt M g(x) }[/math] where [math]\displaystyle{ M\gt 1 }[/math] is an appropriate bound on [math]\displaystyle{ f(x)/g(x) }[/math]. Rejection sampling is usually used in cases where the form of [math]\displaystyle{ f(x) }[/math] makes sampling difficult. Instead of sampling directly from the distribution [math]\displaystyle{ f(x) }[/math], we use an envelope distribution [math]\displaystyle{ Mg(x) }[/math] where sampling is easier. These samples from [math]\displaystyle{ Mg(x) }[/math] are probabilistically accepted or rejected. 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]\displaystyle{ f(x) }[/math]. It forms the basis for algorithms such as the Metropolis algorithm.
The algorithm (used by John von Neumann and dating back to Buffon and his needle) is as follows:
- Sample [math]\displaystyle{ x }[/math] from [math]\displaystyle{ g(x) }[/math] and [math]\displaystyle{ u }[/math] from [math]\displaystyle{ U(0,1) }[/math] (the uniform distribution over the unit interval)
- Check whether or not [math]\displaystyle{ u\lt f(x)/Mg(x) }[/math].
- If this holds, accept [math]\displaystyle{ x }[/math] as a realization of [math]\displaystyle{ f(x) }[/math];
- if not, reject the value of [math]\displaystyle{ x }[/math] and repeat the sampling step.
- QUOTE: In mathematics, rejection sampling is a basic pseudo-random number sampling technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or “accept-reject algorithm”. It generates sampling values from an arbitrary probability distribution function [math]\displaystyle{ f(x) }[/math] by using an instrumental distribution [math]\displaystyle{ g(x) }[/math], under the only restriction that [math]\displaystyle{ f(x)\lt M g(x) }[/math] where [math]\displaystyle{ M\gt 1 }[/math] is an appropriate bound on [math]\displaystyle{ f(x)/g(x) }[/math]. Rejection sampling is usually used in cases where the form of [math]\displaystyle{ f(x) }[/math] makes sampling difficult. Instead of sampling directly from the distribution [math]\displaystyle{ f(x) }[/math], we use an envelope distribution [math]\displaystyle{ Mg(x) }[/math] where sampling is easier. These samples from [math]\displaystyle{ Mg(x) }[/math] are probabilistically accepted or rejected. 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]\displaystyle{ f(x) }[/math]. It forms the basis for algorithms such as the Metropolis algorithm.
2008
- (Upton & Cook, 2008) ⇒ Graham Upton, and Ian Cook. (2008). “A Dictionary of Statistics, 2nd edition revised.” Oxford University Press. ISBN:0199541450