Information Technology Reference
In-Depth Information
are dicult to find. This is the main reason why most good RNGs used in
practice are based on linear recurrences [3,9]. Specific measures for linear RNGs
are discussed later in this paper. The choice generally depends on the type of
RNG, for computability reasons.
To construct a new RNG, one would usually specify a parameterized class of
(large-period) constructions (based on the availability of a fast implementation)
and a figure of merit, and then perform a computer search for the construction
with the largest figure of merit that can be found within that class. Then, the
selected RNG is implemented and tested empirically. There is a large variety of
empirical statistical tests
for testing the statistical behavior of RNGs [1,9].
1.2 Low-Discrepancy Sets and Sequences
In
quasi-Monte Carlo
(QMC) numerical integration, we want a set of
n
points,
P
n
=
{
u
0
,...,
u
n−
1
}
,thatcoverthe
s
-dimensional unit hypercube [0
,
1)
s
very
evenly. These points are used to approximate the integral of some function
f
:
[0
,
1)
s
→
R
,say
μ
=
[0
,
1)
s
f
(
u
)
d
u
,
by the average
n−
1
1
n
μ
n
=
f
(
u
i
)
.
(1)
i
=0
This
μ
can be interpreted as the mathematical expectation
μ
=
[
f
(
U
)], where
U
is a random vector uniformly distributed over [0
,
1)
s
. Here, the cardinality
n
of the point set is much smaller than for RNGs, because we need to evaluate
f
at each of these points. It rarely exceeds a million.
Again, a key question is: How do we measure the uniformity of the point set
P
n
? Standard practice is to use a figure of merit that measures the
discrepancy
between the empirical distribution of
P
n
and the uniform distribution over [0
,
1)
s
[11,12,13,14,4]. Many of these discrepancies are actually defined as the worst-
case integration error, with
P
n
, over all functions
f
whose
variation
V
(
f
)=
E
of functions
[11,15]. In this setting, the worst-case error can be bounded by the product of
the discrepancy
D
(
P
n
), that depends only on
P
n
, and the function's variation,
that depends only on
f
:
f
−
μ
does not exceed 1, in a given Banach (or Hilbert) space
H
|
μ
n
−
μ
|≤
D
(
P
n
)
V
(
f
)
(2)
for all
f
. This is a generalized form of the Koksma-Hlawka inequality [4].
Generally speaking, for a given point set, the more restricted (or smoother) the
class of functions
f
for which
V
(
f
)
∈H
1, the smaller will be the discrepancy,
and the faster min
P
n
D
(
P
n
) will converge to 0 as a function of
n
.Thatis,the
worst-case error bound for the best possible point set will converge to 0 more
quickly. Specific examples of discrepancies are mentioned in Section 2.
≤
