2005-03.derf-wh
Asymptotically Optimal Design Points for Rejection Algorithms
Abstract
Very fast automatic rejection algorithms were developed
recently which allow to generate random variates from large
classes of unimodal distributions. They require the choice
of several design points which decompose the domain of the distribution
into small sub-intervals. The optimal choice of these points is
an important but unsolved problem. So we present an approach that allows
to characterize optimal design points in the asymptotic case (when their number
tends to infinity) under mild regularity conditions.
We describe a short algorithm
to calculate these asymptotically optimal points in practice.
Numerical experiments indicate that they are very close
to optimal even when only six or seven design points are calculated.
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:
nonuniform random variate generation,
universal algorithm,
transformed density rejection,
optimal design points
Download Preprint
[ Postscript | PDF ]
Josef.Leydold@statistik.wu-wien.ac.at