Information Technology Reference
In-Depth Information
Such combinations provide ecient ways of implementing RNGs with larger
state spaces [45,46,31].
5 Lattice Rules for QMC
s
, it is called an
integration lattice
,and
the QMC approximation (1) with
P
n
=
L
s
∩
When a lattice
L
s
as in (12) contains
Z
[0
,
1)
s
is a
lattice rule
[4,20]. The
most frequently used lattice rules are of rank 1: we have
v
1
=
a
1
/n
where
a
1
=(
a
1
,...,a
s
), and
v
j
=
e
j
(the
j
th unit vector) for
j
2. A special case is
when
P
n
is the point set
Ψ
s
that correspond to a LCG; we then have a Korobov
lattice rule.
Integration lattices are usually randomized by a random shift modulo 1. The
shift preserves the lattice structure. It turns out that the variance of the corre-
sponding RQMC estimator can be written explicitly as
≥
0
=
h
∈L
s
|
f
(
h
)
2
,
Var[
μ
n,
rqmc
]=
|
(14)
where the
f
(
h
) are the coecients in the Fourier expansion of the function
f
[17]. Assuming that we want to minimize the variance, (14) gives the ultimate
discrepancy measure of a lattice point set to integrate a given function
f
.The
square Fourier coecients are generally unknown, but they can be replaced by
weights
w
(
h
) that try to approximate their expected behavior for a given class
of functions of interest. It might be dicult to obtain such an approximation.
Another problem is that computing (14) with the weights
w
(
h
), and searching
for lattices that minimize its value, may be dicult unless the weights have a
special form. In [17], the authors argue that since the Fourier coecients for the
short vectors
h
represent the main trends of the function's behavior, they are
likely to be those having the most impact on the variance, so we should try to
keep them out of the dual lattice to eliminate them from the sum in (14). If
we do this for a selected class of low-dimensional projections of
L
s
,andweight
these projections, this leads to the same criterion as in (13). Specific Korobov
lattice parameters found on the basis of this criterion are given in [17].
In these criteria, the Euclidean length of
h
could also be replaced by other
notions of length; for example, the
L
1
length, as discussed earlier, of the product
length
j
=1
max(1
,
), for which the length of the shortest vector in
L
s
is
called the
Zaremba index
[20].
For lattice rules, discrepancies based on kernels of the general form (5) admit
simplified formulas, thanks to the fact that
n−
1
|
h
j
|
i
=0
e
2
πι
h
t
u
i
=
n
for
h
∈ L
s
,
and 0 otherwise [20]. In particular, the square discrepancy for the kernel (7)
simplifies to
1+
γ
j
(
B
2
α
(
u
j
)
/
2
,
n−
1
s
4
π
2
)
α
(2
α
)!
1+
1
n
−
D
2
(
P
n
)=
−
(15)
i
=0
j
=1
