Information Technology Reference
In-Depth Information
Do the discrepancies discussed in Section 2 have simplified expressions for
digital nets, as was the case for lattice rules? Those based on the kernel (5) do
not, but they do if we take a slightly different kernel, based on Walsh expansions
in base
b
instead of Fourier expansions. This can be exploited to develop practical
figures of merit analogous to those used for lattice rules.
The most widely used class of figures of merit, for both RNG and QMC
point sets, are those based on the notion of
equidistribution
, defined as follows.
For a vector of non-negative integers (
q
1
,...,q
s
), we partition the
j
th axis into
b
q
j
equal parts for each
j
. This partitions the hypercube [0
,
1)
s
into
b
q
1
+
···
+
q
s
rectangular boxes of the same size and shape. A point set
P
n
of cardinality
n
=
b
k
is (
q
1
,...,q
s
)
-equidistributed in base
b
if each box of this partition contains
exactly
b
t
points of
P
n
,where
t
=
k
−
q
1
−···−
q
s
. For a digital net in base
b
, this property holds if and only if the set of
k
+
q
t
rows that
comprise the first
q
j
rows of
C
j
,for
j
=1
,...,s
, is linearly independent in the
finite ring
R
[4].
The set
P
n
is a (
t, k, s
)
-net in base b
if it is (
q
1
,...,q
s
)-equidistributed when-
ever
q
1
+
−
q
=
q
1
+
···
···
+
q
s
≤
k
−
t
[4]. The smallest such
t
is the
t
-value
of the net. A digital
sequence
{
u
0
,
u
1
,...,
}
in
s
dimensions is a (
t, s
)
-sequence in base
b
if for all in-
{
u
i
:
i
=
νb
k
,...,
(
ν
+1)
b
k
tegers
k>
0and
ν
}
is a (
t, k, s
)-net in base
b
.The
t
-value is a widely used figure of merit for digital
nets. Ideally, we would like it to be zero, but there are theoretical lower bounds
on it. In particular, a (0
,k,s
)-net in base
b
can exist only if
b
≥
0, the point set
Q
(
k, ν
)=
−
1
≥
s
−
1, and a
(0
,t
)-sequence in base
b
can exist only if
b
t
. Lower bounds for general pairs
(
b, s
), together with the best values achieved by known constructions, are tabu-
lated in [62]. For example, for
b
=2,
k
= 16, and
s
= 20, the
t
-value cannot be
smaller than 9. A
t
-value of 9 in this case only guarantees equidistribution for
a partition in 2
7
= 128 boxes, which must contain 2
9
= 512 points each. For a
given partition, this is a weak requirement.
The problem is that a small
t
-value would require equidistribution for a very
rich family of partitions into rectangular boxes, and this becomes impossible
when
t
is too small. To get around this, we may restrict our consideration to a
smaller family of partitions; for example, only cubic boxes. We then want
P
n
to
be (
,...,
)-equidistributed for the largest possible
, which obviously cannot
exceed
≥
k/s
. We want to minimize the
resolution gap
δ
=
k/s
−
.
These definitions apply to the projections
P
n
(
u
) as well. Let
t
u
and
δ
u
denote
), and
t
|
u
|
the
t
-value and the resolution gap for
P
n
(
a theoretical lower bound
on
t
u
. Discrepancy measures for digital nets can be defined by
u
max
u
∈J
γ
u
δ
u
,
or
γ
u
δ
u
,
or
u
∈J
t
u
−
,
t
u
−
,
t
|
u
|
t
|
u
|
max
u
∈J
γ
u
or
γ
u
u
∈J
for some non-negative weights
γ
u
and a preselected class
J
of index sets
u
[58,13,59,63]. The choice of
J
is a matter of compromise. With a larger (richer)
J
, the criterion is more expensive to compute, and its best possible value is
