Information Technology Reference
In-Depth Information
Slight variations of this discrepancy have interesting geometric interpretations.
For example, if we replace
B
2
α
((
u
j
−
v
j
)
mod
1) in (7) by an appropriate (simple)
polynomial in
u
j
and
v
j
,weobtainaweighted
L
2
-unanchored discrepancy
whose
interpretation is the following [11,12]. For each subset
u
of coordinates and any
u
,
v
∈
[0
,
1]
|
u
|
,let
D
(
P
n
(
u
)
,
u
,
v
) be the absolute difference between the volume
|
u
|
of the
-dimensional box with opposite corners at
u
and
v
,andthefractionof
the points of
P
n
that fall in that box. The square discrepancy is then defined as
⎛
⎝
j∈
u
⎞
⎠
[
D
2
(
P
n
)]
2
=
D
2
(
P
n
(
γ
j
u
)
,
u
,
v
)
d
u
d
v
.
(9)
[0
,
1]
|
u
|
[
0
,
v
]
φ
=
u
⊆S
Other similarly defined RKHSs contain non-periodic functions
f
. For exam-
ple, by taking again the appropriate (simple) function in place of
B
2
α
((
u
j
−
v
j
)
mod
1) in (7), we obtain a weighted
L
2
-star discrepancy
, whose square can
be written as
⎛
⎝
j∈
u
⎞
⎠
[
D
2
(
P
n
)]
2
=
D
2
(
P
n
(
γ
j
u
)
,
0
,
v
)
d
v
(10)
[0
,
1]
|
u
|
φ
=
u
⊆S
and the square variation is
⎛
⎝
j∈
u
⎞
f
u
(
u
u
)
2
V
2
(
f
)=
φ
∂
|
u
|
∂
u
u
⎠
γ
−
1
j
d
u
u
[0
,
1]
|
u
|
=
u
⊆S
(see [11,12]). All these discrepancies can be computed in
O
(
n
2
s
) time for general
point sets.
It is known that there exists point sets
P
n
for which the discrepancy based
on (7) converges as as
O
(
n
−α
+
δ
) for any
δ>
0, and point sets for which the
discrepancy (10) converges as
O
(
n
−
1+
δ
).
3 RNGs Based on Linear Recurrences Modulo a Large
Integer
m
An important (and widely used) class of RNGs is based on the general linear
recurrence
x
i
=(
a
1
x
i−
1
+
···
+
a
k
x
i−k
)
mod
m,
(11)
where
k
and
m
are positive integers,
a
1
,...,a
k
∈{
=
0. The state at step
i
is
s
i
=
x
i
=(
x
i−k
+1
,...,x
i
). Suppose the output is
u
i
=
x
i
/m
(in practice it is slightly modified to make sure that 0
<u
i
<
1).
This RNG is called a
multiple recursive generator
.For
k
=1,itisknownasa
linear congruential generator
(LCG). For prime
m
and well-chosen coecients,
the period length can reach
m
k
0
,
1
,...,m
−
1
}
,and
a
k
−
1 [1], which can be made arbitrarily large by
