View source for Acceptance-rejection method

Introduced by J. von Neumann [[#References|[a8]]], this is the most adaptable method for sampling from complicated distributions (cf. also [[Sample|Sample]]; [[Distribution|Distribution]]). It works as follows.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a1300801.png" /> be a given probability density (cf. also [[Density of a probability distribution|Density of a probability distribution]]), and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a1300802.png" /> be a function such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a1300803.png" /> within the range of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a1300804.png" />. If the integral of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a1300805.png" /> over this range is a finite number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a1300806.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a1300807.png" /> is a probability density function, and the following procedure is valid:

1) Take a random sample <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a1300808.png" /> from the distribution with probability density <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a1300809.png" />.

2) Generate a uniform random deviate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008010.png" /> between zero and one. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008011.png" />, accept <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008012.png" /> as a sample from the distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008013.png" />. Otherwise reject <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008014.png" /> and go back to Step 1.

The ease of the method depends on the following properties of the hat function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008015.png" />:

A) One has to select a hat function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008016.png" /> from which it is easy to sample. Examples are given below.

B) The parameters of the hat function have to be determined in such a way that the area <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008017.png" /> below <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008018.png" /> becomes minimal.

Optimal hat functions can be calculated by analytical methods. Assume that the hat function touches <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008019.png" /> at two points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008020.png" /> (left) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008021.png" /> (right), where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008022.png" />. Furthermore, suppose that the hat function depends on two parameters, called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008024.png" />. Thus

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008025.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008026.png" /> for all other <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008027.png" />. Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008029.png" /> are local maxima of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008030.png" />, one has the necessary conditions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008031.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>

and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008032.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008034.png" /> are uniquely determined, they should satisfy the sufficient conditions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008035.png" /></td> </tr></table>

Otherwise, the first derivative of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008036.png" /> has to be discussed in detail.

Equations (a1), (a2) and (a3) are four equations for the determination of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008038.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008039.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008040.png" />. Assuming that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008042.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008043.png" /> can be expressed as functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008044.png" />, one has to minimize

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008045.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>

This leads to the necessary conditions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008046.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008047.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008048.png" /></td> </tr></table>

The first expression in each line is zero, by (a2) and (a3). Solving both equations for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008049.png" />, and comparing, yields the fundamental relation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008050.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a5)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008051.png" /></td> </tr></table>

(a1), (a2), (a3) and (a5) contain five conditions for finding candidates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008053.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008055.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008056.png" />.

==Examples.==


===Triangular hat functions.===
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008057.png" /></td> </tr></table>

Samples may be obtained as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008058.png" />. The fundamental identity (a5) leads to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008059.png" />. With its help all constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008060.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008062.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008063.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008064.png" /> can be determined.

===Double exponential hat functions.===
The double exponential (or Laplace) distribution is given by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008065.png" /></td> </tr></table>

(See also [[Laplace distribution|Laplace distribution]].)

Samples are obtained as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008066.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008067.png" /> is a standard exponential deviate and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008068.png" /> a random sign <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008069.png" />. The fundamental identity (a5) leads to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008070.png" />.

===Student-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008071.png" /> hat functions.===
Its probability density function is given as

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008072.png" /></td> </tr></table>

for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008073.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008074.png" />, where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008075.png" /></td> </tr></table>

(See also [[Student distribution|Student distribution]].)

The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008076.png" />-family contains the [[Cauchy distribution|Cauchy distribution]] for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008077.png" /> and the [[Normal distribution|normal distribution]] for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008078.png" /> as extreme cases. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008079.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008080.png" /> special sampling methods are available: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008081.png" /> denotes a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008082.png" />-uniform random variable, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008083.png" /> samples from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008084.png" /> and values from the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008085.png" />-distribution can be generated efficiently by the ratio-of-uniforms method of A.J. Kinderman and J.F. Monahan [[#References|[a5]]], which will be discussed subsequently. The fundamental identity (a5) yields <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008086.png" />. As before, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008087.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008088.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008089.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008090.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008091.png" /> can be determined explicitly.

The ratio-of-uniforms method was introduced by Kinderman and Monahan for sampling from a density <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008092.png" />. First the table mountain-function is constructed: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008093.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008094.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008095.png" /> be real numbers and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008096.png" /> be equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008097.png" />, but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008098.png" /> might be another possible choice for some densities. Then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a13008099.png" /></td> </tr></table>

Samples from the area below the table mountain-function are obtained by the transformation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080100.png" /></td> </tr></table>

The table mountain-function is taken as a hat function for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080101.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080102.png" />. In this case the fundamental identity leads to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080103.png" /> for calculating optimal constants.

===Squeeze functions.===
Step 2 of the acceptance-rejection method can be improved if some lower bound

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080104.png" /></td> </tr></table>

is known and easy to calculate. Step 2 then changes to:

2') Generate a uniform random deviate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080105.png" /> between zero and one. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080106.png" />, accept <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080107.png" /> as a sample from the target distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080108.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080109.png" />, reject <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080110.png" /> and go back to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080111.png" />. Otherwise accept <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130080/a130080112.png" />.

Squeeze functions have been constructed in many procedures. See [[#References|[a4]]] for some theory.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.H. Ahrens,   U. Dieter,   "Computer methods for sampling from gamma, beta, Poisson and binomial distributions"  ''Computing'' , '''12'''  (1974)  pp. 223–246</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Devroye,   "Non-uniform random variate generation" , Springer  (1986)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  U. Dieter,   "Optimal acceptance-rejection methods for sampling from various distributions"  P.R. Nelson (ed.) , ''The Frontiers of Statistical Computation, Simulation, &amp; Modeling'' , ''Amer. Ser. Math. Management Sci.''  (1987)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  U. Dieter,   "Mathematical aspects of various methods for sampling from classical distributions" , ''Proc. 1989 Winter Simulation Conference''  (1989)  pp. 477–483</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A.J. Kinderman,   J.F. Monahan,   "Computer generation of random variables using the ratio of uniform deviates"  ''ACM Trans. Math. Software'' , '''3'''  (1977)  pp. 257–260</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  D.E. Knuth,   "The art of computer programming" , '''2: Seminumerical algorithms''' , Addison-Wesley  (1998)  (Edition: Third)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J. Leydold,   "Automatic sampling with the ratio-of-uniform method"  ''ACM Trans. Math. Software'' , '''26'''  (2000)  pp. 78–88</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J. von Neumann,   "Various techniques used in connection with random digits. Monte Carlo methods"  ''Nat. Bureau Standards'' , '''12'''  (1951)  pp. 36–38</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  E. Stadlober,   "Sampling from Poisson, binomial and hypergeometric distributions: Ratio of uniforms as a simple and fast alternative"  ''Math.–Statist. Sekt. 303 Forschungsgesellschaft Joanneum, Graz, Austria''  (1989)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  E. Stadlober,   "The ratio of uniforms approach for generating discrete random varates"  ''J. Comput. Appl. Math.'' , '''31''' :  1  (1990)  pp. 181–189</TD></TR></table>