In numerical analysis and computational statistics, 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 exact simulation method. The method works for any distribution in R m {\displaystyle \mathbb {R} ^{m}} with a density. Rejection sampling is based on the observation that to sample a random variable in one dimension, one can perform a uniformly random sampling of the two-dimensional Cartesian graph, and keep the samples in the region under the graph of its density function. Note that this property can be extended to N-dimension functions.
Algorithmic Definition The algorithm, which was used by John von Neumann and dates back to Buffon and his needle, draws a sample from a (target) probability density function f ( x ) {\displaystyle f(x)} , which is proportional to f ∝ ( x ) {\displaystyle f_{\varpropto }(x)} , using draws from a simpler (proposal) probability density g ( x ) {\displaystyle g(x)} as follows: Rejection Sampling
Input Target density f ( x ) = f ∝ ( x ) ∫ f ∝ ( y ) d y {\displaystyle f(x)={\frac {f_{\varpropto }(x)}{\int f_{\varpropto }(y)dy}}} , proposal density g ( x ) {\displaystyle g(x)} , constant M {\displaystyle M} such that f ∝ ( x ) ≤ M g ( x ) {\displaystyle f_{\varpropto }(x)\leq Mg(x)} for all x {\displaystyle x} . Algorithm
Sample X ∼ g ( x ) {\displaystyle X\sim g(x)}
Sample U ∼ U n i f ( 0 , 1 ) {\displaystyle U\sim \mathrm {Unif} (0,1)} , independently of X {\displaystyle X} . Compute likelihood ratio W = f ∝ ( X ) g ( X ) {\displaystyle W={\dfrac {f_{\varpropto }(X)}{g(X)}}} . If W < M × U {\displaystyle W<M\times U} , reject X {\displaystyle X} and repeat from step 1. Otherwise, accept and output X {\displaystyle X} . Output A sample X {\displaystyle X} drawn from f {\displaystyle f} . The algorithm will take an average of M ∫ f ∝ ( y ) d y {\displaystyle {\frac {M}{\int f_{\varpropto }(y)dy}}} rejections to obtain a sample.
Detailed Description To visualize the motivation behind rejection sampling, imagine graphing the probability density function (PDF) of a random variable onto a large rectangular board and throwing darts at it. Assume that the darts are uniformly distributed around the board. Now remove all of the darts that are outside the area under the curve. The remaining darts will be distributed uniformly within the area under the curve, and the x {\displaystyle x} ‑positions of these darts will be distributed according to the random variable's density. This is because there is the most room for the darts to land where the curve is highest and thus the probability density is greatest. The visualization just described is equivalent to a particular form of rejection sampling where the "proposal distribution" is uniform. Hence its graph is a rectangle. The general form of rejection sampling assumes that the board is not necessarily rectangular but is shaped according to the density of some proposal distribution (not necessarily normalized to 1 {\displaystyle 1} ) that we know how to sample from (for example, using inversion sampling). Its shape must be at least as high at every point as the distribution we want to sample from, so that the former completely encloses the latter. Otherwise, there would be parts of the curved area we want to sample from that could never be reached. Rejection sampling works as follows:
… excerpt ends here. Continue reading the full article.
