2002-03.wh-ley
Continuous Random Variate Generation by Fast Numerical Inversion
Abstract
The inversion method for generating non-uniform random variates has
some advantages compared to other generation methods, since it
monotonically transforms uniform random numbers into non-uniform
random variates. Hence it is the method of choice in the simulation
literature. However, except for some simple cases where the
inverse of the cumulative distribution function is a simple
function we need numerical methods. Often inversion by ``brute
force'' is used, applying either very slow iterative methods
or linear interpolation of the CDF and huge tables.
But then the user has to
accept unnecessarily large errors or excessive memory requirements,
that slow down the
algorithm. In this paper we demonstrate that with Hermite
interpolation of the inverse CDF we can obtain very small error bounds
close to machine precision.
Using our adaptive interval splitting method this accuracy
is reached with moderately sized tables that allow for a
fast and simple generation procedure.
The algorithms described in this paper
have been implemented in ANSI C in a library called
UNURAN which is
available via anonymous ftp.
Mathematics Subject Classification:
65C10 (Random Number Generation)
CR Categories and Subject Descriptors:
G.3 [Probability and Statistics]: Random number generation
General Terms:
Algorithms
Key Words:
random number generation,
inversion method,
Hermite interpolation,
approximation,
black-box algorithm,
universal method,
simulation
Download Preprint
© ACM, (2003). This is the author's version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in
Trans. Model. Comput. Simul. 13(4), 347-362
http://doi.acm.org/10.1145/945511.945517
Paper
Josef.Leydold@statistik.wu-wien.ac.at