Automatic Random Variate Generation for Simulation Input
We develop and evaluate algorithms for generating random variates
for simulation input. One group called automatic, or black-box
algorithms can be used to sample from distributions with known
density. They are based on the rejection principle. The hat function
is generated automatically in a setup step using the idea of
transformed density rejection. There the density is transformed into
a concave function and the minimum of several tangents is used
to construct the hat function. The resulting algorithms are
not too complicated and are quite fast. The principle is also applicable
to random vectors.
A second group of algorithms is presented that
generate random variates directly from a given sample by implicitly
estimating the unknown distribution.
The best of these algorithms are based on the idea of naive resampling
plus added noise. These algorithms can be interpreted as sampling from
the kernel density estimates.
This method can be also applied to random vectors. There it can be
interpreted as a mixture of naive resampling and
sampling from the multi-normal distribution that has the same
covariance matrix as the data.
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
random number generation, rejection method, log-concave density,
transformed density rejection, black-box algorithm,
universal method, kernel density estimation, smoothed bootstrap, simulation