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 |
Acceptance-rejection method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Acceptance-rejection_method&oldid=18274