Acceptance-rejection method

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

Let be a given probability density (cf. also Density of a probability distribution), and let be a function such that within the range of . If the integral of over this range is a finite number , then is a probability density function, and the following procedure is valid:

1) Take a random sample from the distribution with probability density .

2) Generate a uniform random deviate between zero and one. If , accept as a sample from the distribution . Otherwise reject and go back to Step 1.

The ease of the method depends on the following properties of the hat function :

A) One has to select a hat function 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 below becomes minimal.

Optimal hat functions can be calculated by analytical methods. Assume that the hat function touches at two points (left) and (right), where . Furthermore, suppose that the hat function depends on two parameters, called and . Thus

(a1)

and for all other . Since and are local maxima of , one has the necessary conditions

(a2)

and

(a3)

If and are uniquely determined, they should satisfy the sufficient conditions

Otherwise, the first derivative of has to be discussed in detail.

Equations (a1), (a2) and (a3) are four equations for the determination of , , , and . Assuming that , and can be expressed as functions of , one has to minimize

(a4)

This leads to the necessary conditions

The first expression in each line is zero, by (a2) and (a3). Solving both equations for , and comparing, yields the fundamental relation

(a5)

(a1), (a2), (a3) and (a5) contain five conditions for finding candidates , , , and .

Examples.

Triangular hat functions.

Samples may be obtained as . The fundamental identity (a5) leads to . With its help all constants , , , , and can be determined.

Double exponential hat functions.

The double exponential (or Laplace) distribution is given by

(See also Laplace distribution.)

Samples are obtained as , where is a standard exponential deviate and a random sign . The fundamental identity (a5) leads to .

Student- hat functions.

Its probability density function is given as

for , , where

(See also Student distribution.)

The -family contains the Cauchy distribution for and the normal distribution for as extreme cases. For and special sampling methods are available: If denotes a -uniform random variable, then samples from and values from the -distribution can be generated efficiently by the ratio-of-uniforms method of A.J. Kinderman and J.F. Monahan [a5], which will be discussed subsequently. The fundamental identity (a5) yields . As before, , , , , and can be determined explicitly.

The ratio-of-uniforms method was introduced by Kinderman and Monahan for sampling from a density . First the table mountain-function is constructed: Let , and be real numbers and let be equal to , but might be another possible choice for some densities. Then

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

The table mountain-function is taken as a hat function for , where . In this case the fundamental identity leads to for calculating optimal constants.

Squeeze functions.

Step 2 of the acceptance-rejection method can be improved if some lower bound

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

2') Generate a uniform random deviate between zero and one. If , accept as a sample from the target distribution . If , reject and go back to . Otherwise accept .

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

References

[a1]	J.H. Ahrens, U. Dieter, "Computer methods for sampling from gamma, beta, Poisson and binomial distributions" Computing , 12 (1974) pp. 223–246
[a2]	L. Devroye, "Non-uniform random variate generation" , Springer (1986)
[a3]	U. Dieter, "Optimal acceptance-rejection methods for sampling from various distributions" P.R. Nelson (ed.) , The Frontiers of Statistical Computation, Simulation, & Modeling , Amer. Ser. Math. Management Sci. (1987)
[a4]	U. Dieter, "Mathematical aspects of various methods for sampling from classical distributions" , Proc. 1989 Winter Simulation Conference (1989) pp. 477–483
[a5]	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
[a6]	D.E. Knuth, "The art of computer programming" , 2: Seminumerical algorithms , Addison-Wesley (1998) (Edition: Third)
[a7]	J. Leydold, "Automatic sampling with the ratio-of-uniform method" ACM Trans. Math. Software , 26 (2000) pp. 78–88
[a8]	J. von Neumann, "Various techniques used in connection with random digits. Monte Carlo methods" Nat. Bureau Standards , 12 (1951) pp. 36–38
[a9]	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)
[a10]	E. Stadlober, "The ratio of uniforms approach for generating discrete random varates" J. Comput. Appl. Math. , 31 : 1 (1990) pp. 181–189