Information Technology Reference
In-Depth Information
Comparison of Point Sets and Sequences for
Quasi-Monte Carlo and for Random Number
Generation
(Invited Paper)
Pierre L'Ecuyer
DIRO, CIRRELT, and GERAD,
Universit´edeMontreal, Canada
http://www.iro.umontreal.ca/~lecuyer
Abstract.
Algorithmic random number generators require recurring
sequences with very long periods and good multivariate uniformity prop-
erties. Point sets and sequences for quasi-Monte Carlo numerical integra-
tion need similar multivariate uniformity properties as well. It then comes
as no surprise that both types of applications share common (or similar)
construction methods. However, there are some differences in both the
measures of uniformity and the construction methods used in practice.
We briefly survey these methods and explain some of the reasons for the
differences.
1
Introduction
1.1 Random Number Generators
(Pseudo)Random number generators (RNGs) are typically defined by a (deter-
ministic) recurring sequence in a finite state space
, usually a finite field or
ring, and an output function mapping each state to an output value in
S
,which
is often either a real number in the interval (0
,
1) or an integer in some finite
range [1,2,3,4]. We shall assume here that each output is a real number in (0
,
1)
and that the purpose of the RNG is to mimic a sequence of independent
U
(0
,
1)
random variables (i.e., uniformly distributed over (0
,
1)). Of course, with such an
algorithmic construction, this can only be a fake. The quality of the fake should
be measured in a way that depends on the application.
One could argue that physical noise would provide a safer source of (true)
randomness. With careful design, it does, and it is appropriate for certain appli-
cations such as generating random keys in cryptology and for gaming machines,
for example, where unpredictability is a major requirement. In this paper, we
focus on RNGs for simulation applications, where fast algorithmic RNGs are
much more convenient than physical sources, because they are faster, they per-
mit one to replicate the same exact sequence several times (this is often needed in
