94-01-18.wh-der
The Transformed Rejection Method for Generation Random Variables,
an Alternative to the Ratio of Uniforms Method
Abstract
Theoretical considerations and empirical results show that the
one-dimensional quality of non-uniform random numbers is bad and the
discrepancy is high when they are generated by the
ratio of uniforms method combined with linear congruential generators.
This observation motivates the suggestion to replace the ratio of
uniforms method by transformed rejection (also called exact
approximation or almost exact inversion), as the above problem does
not occur for this method. Using the function $G(x) =\left(
\frac{a}{1-x}+b\right)x $
with appropriate $a$ and $b$ as approximation of the inverse
distribution function the transformed rejection method can be used for
the same distributions as the ratio of uniforms method. The resulting
algorithms for the normal, the exponential and the t-distribution are
short and easy to implement. Looking at the number of uniform deviates
required, at the code length and at the speed the suggested algorithms
are superior to the ratio of uniforms method
and compare well with other algorithms suggested in literature.
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 variate generation,
transformed rejection method, normal distribution, t-distribution
Download Preprint
Wolfgang.Hoermann@statistik.wu-wien.ac.at