Information Technology Reference
In-Depth Information
just to have one point near each corner of the hypercube. For quasi-Monte Carlo,
this is impractical. For RNGs, we can easily have more than 2
100
points in
Ψ
s
, but
the high-dimensional uniformity eventually breaks down as well for a larger
s
.
In QMC, we are saved by the fact that
f
is often well approximated by a sum
of low-dimensional functions, that depend only on a small number of coordinates
of
u
;thatis,
f
(
u
)
≈
f
u
(
u
)
,
(3)
u
⊆J
where each
f
u
:(0
,
1)
s
→
R
{
u
j
,j
∈
u
}
J
depends only on
,and
is a family of
. Then, to integrate
f
with small error, it
suces to integrate with small error the low-dimensional functions
f
u
making
up the approximation. For that, we only need high uniformity of the projections
P
n
(
{
1
,...,s
}
small-cardinality subsets of
. This suggests a
figure of merit defined as a weighted sum (or supremum) of discrepancy measures
computed over the sets
P
n
(
u
)of
P
n
over the low-dimensional sets of coordinates
u
∈J
u
)for
u
∈J
. The figures of merit used to select QMC
point sets are typically of that form.
This heuristic interpretation can be made rigorous via a functional ANOVA
decomposition of
f
[23,18,24]. When (3) holds for
for a
small
d
,wesaythat
f
has low effective dimension in the superposition sense,
while if it holds for
J
=
{
u
:
|
u
|≤
d
}
for a small
d
,wesaythat
f
has
low effective dimension in the
truncation sense
[25,18]. Low effective dimension
can often be achieved by redefining
f
without changing its expectation, via
a change of variables [26,25,27,28,14,29,30]. That is, we change the way the
uniforms (the coordinates of
u
) are transformed in the simulation. There are
important applications in computational finance, for example, where after such
a change of variable, the one- and two-dimensional functions
f
u
account for more
than 99% of the variability of
f
[14,30]. For these applications, it is important
that the one- and two-dimensional projections
P
n
(
J
=
{
u
⊆{
1
,...,d
}}
) have very good uniformity,
and there is no need to care much about the high-dimensional projections.
It makes sense that the figures of merit for the point sets
Ψ
s
produced by RNGs
also take the low-dimensional projections into account, as suggested in [3,31,17],
for example. In fact, the standardized figures of merit based on the spectral test,
as defined in [32,33,34] for example, already do this to a certain extent by giving
more weight to the low-dimensional projections in the truncation sense (where
u
u
=
{
1
,...,d
}
for small
d
).
2 Examples of Discrepancies for QMC
Discrepancies and the corresponding variations are often defined via reproduc-
ing kernel Hilbert spaces (RKHS). An RKHS is constructed by selecting a
kernel
K
:[0
,
1]
2
s
, which is a symmetric and positive semi-definite function. The
kernel determines in turn a set of basis functions and a scalar product, that
define a Hilbert space
→
R
H
[35]. For
f
∈H
and a point set
P
n
, (2) holds with
