The mean square discrepancy of randomized nets.
One popular family of low dicrepancy sets is the (t, m, s)-nets. Recently a randomization of these nets that preserves their net property has been introduced. In this article a formula for the mean square L2-discrepancy of (0, m, s)-nets in base b is derived. This formula has a computational complexity of only O(s log(N) + s2) for large N or s, where bm is the number of points. Moreover, the root mean square L2-discrepancy of (0, m, s)-nets is show to be O(N-1[log(N)](s-1)/2) as N tends to infinity, the same asymptotic order as the known lower bound for  the  L2-discrepancy of an arbitrary set.
INTRODUCTION
Multidimensional integrals over the s-dimensional unit cube C may be
approximated by the sample mean of the integrand evaluated on a point set, P ,
with N points. (Here, in contrast to ordinary sets, P may have multiple copies of
the same point [Niederreiter 1992, p. 14].) The quadrature error depends on how
uniformly the points in P are distributed on the unit cube and on how much the
integrand varies from a constant. For example, if D(P ) is the L 1 -star discrepancy
[Niederreiter 1992, Definition 2.1], and V (f) is the variation of f on
the sense of Hardy and Krause, then the Koksma-Hlawka inequality [Niederreiter
1992, Theorem 2.11] is
Z
This research was partially supported by a Hong Kong RGC grant 94-95/38 and HKBU FRG
grant 96-96/II-01.
Address: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong
Kong, E-mail: fred@hkbu.edu.hk, URL: http://www.math.hkbu.edu.hk/~fred
Permission to make digital or hard copies of part or all of this work for personal or classroom use is
granted without fee provided that copies are not made or distributed for profit or direct commercial
advantage and that copies show this notice on the first page or initial screen of a display along
with the full citation. Copyrights for components of this work owned by others than ACM must
be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on
servers, to redistribute to lists, or to use any component of this work in other works, requires prior
specific permission and/or a fee. Permissions may be requested from Publications Dept, ACM
Inc., 1515 Broadway, New York, NY 10036 USA, fax +1 (212) 869-0481, or permissions@acm.org.
ACM Transactions on Modeling and Computer Simululation, 1997
bounds of this form with other definitions of D(P ) and V (f) appear in the
literature as well. A good set P for quadrature is one that has a small discrepancy,
sets have been found that have smaller discrepancies
than simple random points. These sets are often called quasi-random points.
Calculating the L 1 -star discrepancy of a particular set is impractical unless
both N and s are small because it requires O(N s ) operations. Much effort has
been directed towards finding quasi-random sequences that have asymptotically
small discrepancies as N tends to infinity. The (t; m; s)-nets [Niederre-
iter 1992, Chapter 4] are one example. By comparison the L 2 -star discrepancy is
easier to compute, requiring only O(N 2 ) operations using a naive algorithm, or
O(N[log(N operations using the algorithm of Heinrich [1996].
Owen [1995, 1996a, 1996b] has proposed a randomization of (t; m; s)-nets that
preserves their net properties. His aim is to obtain probabilistic quadrature error
estimates in a similar manner as one would for simple Monte Carlo quadrature. In
this article a formula for the mean square L 2 -discrepancy of randomized (0; m; s)-
nets is derived which requires only O(s log(N) mathematical operations to
evaluate as N and/or s tend to infinity. The L 2 -discrepancy for these randomized
nets is shown to decay like O(N matching
the asymptotic lower bound obtained by Roth [1954].
In the remainder of this section we define (t; m; s)-nets and describe Owen's
randomization. Also, a generalized L 2 -discrepancy that arises in quadrature error
bounds recently derived by the author is defined. In Section 2 the mean square L 2 -
discrepancy is computed for simple random samples and randomized (0; m; s)-nets.
The asymptotic behavior of the L 2 -discrepancy is studied in Section 3. This article
concludes with some discussion.
Any point may be written in base b as
where the b-nary digits z ij range from 0 to b \Gamma 1. Let Z s
denote the space of
s-dimensional non-negative integer vectors. For any
. There are b k1 different ways to choose the first
b-nary digits of a point z:
z
being specified.) A (t; m; s)-net contains at least one
point with every possible choice of the first k digits, provided that oe(k) is small
enough.
Definition 1. Let t and m be non-negative integers with 0  t  m, and let s be
a positive integer. A (t; m; s)-net in base b is a set, P , containing
in C s . For any possible choice of the first k b-nary digits (1.2) there exist b m\Gammaoe(k)
points in P with these digits provided that t.
A smaller value of t tends to imply a net with better uniformity (smaller discrep-
ancy). Any any set is an
(m; m; s)-net. For a fuller discussion of (t; m; s)-nets see Niederreiter [1992, Chapter
4].
Owen randomizes the digits of the points in a given (t; m; s)-net P 0 to obtain
a new (t; m; s)-net P . For every digit index every coordinate index
obtains a random digit z ij that contributes to a
random point z 2 P . The randomized net, P satisfies the following assumptions:
Assumption 1.
a. For any z 2 P each digit z ij is uniformly distributed on the set 1g.
b. For any two points z; z the random vectors (z
s are
mutually independent.
c. For any two points be the corresponding points in the
randomized net. Suppose that y j and y 0
share the same first k j digits, but that
st digits are different. Then
ii. the random vector (z k j +1;j ; z 0
uniformly distributed on the set
are mutually independent for
are mutually independent.
Assumptions 1a and 1b imply that the marginal probability distribution of any
is uniform on C s and that the z are mutually inde-
pendent. Assumption 1c maintains the correlation between different points in P
that is necessary for retaining its net properties and thus a low discrepancy. For
a simple random sample Assumptions 1a and 1b are also satisfied, but instead of
Assumption 1c one has z 1j ; z
mutually independent for z 6= z 0 .
sg be the set of coordinate indices. For any u ' S let juj denote
the number of points in u. Let C denote the juj-dimensional unit cube
involving the coordinates in u, and likewise, let Z u
be the juj-dimensional non-negative
integer vectors. This notation allows us to distinguish spaces of the same
dimension in different coordinate directions.
The L p -star discrepancy is sometimes defined as the L p -norm of the difference
between the empirical distribution associated with the sample P and the uniform
distribution on the unit cube:
denotes the number of points in a set, and k k p denotes the L p -norm.
Although this definition is appropriate for does not admit an error bound
like (1.1) for other values of p. A more suitable definition [Hickernell 1997] is
1=p
where P u denotes the projection of the sample P into the cube C u . This means
that D
only one term in the definition of D
bound of the form (1.1) based on this definition was derived by Zaremba [1968] for
Hickernell [1997] for all p. The L p -star discrepancy is in general difficult
to compute, except in the case reduces to a double sum:
[D
s
Y
s
Y
Hickernell [1997] has derived a family of quadrature error bounds of form (1.1)
and L p -discrepancies, D p (P ), that include the star discrepancy as a special case.
The -discrepancy is the simplest to compute. Let fi be an arbitrary positive
constant and  be an arbitrary function on [0; 1) whose first derivative is essentially
bounded and that satisfies
Z 1' d
dx
The generalized L 2 -discrepancy defined in [Hickernell 1997] is
s
Y
s
Y
oe
denotes the quadratic Bernoulli polynomial [Abramowitz and Stegun
1964, Chapter 23]. The star discrepancy is obtained by choosing
Another choice of  and fi yields a discrepancy derived by Hickernell [1996] that is
similar to the figure of merit, P ff , used in the study of lattice rules [Sloan and Joe
1994, Eq. (4.8)]. Several different choices of  and fi are discussed by Hickernell
[1997].
The L 2 -discrepancy defined in (1.4) can also be written as
where
[D
Y
Y
\Theta
Choosing  and fi according to (1.5) and setting in the above equation yields
a formula for D
2;S of (1.3) originally derived by Warnock [1972]:
[D
\GammaN
s
Y
s
Y
Not only does the L 2 -discrepancy appear in worst-case quadrature error bounds,
such as (1.1), it also arises in average-case quadrature error analysis. Let E f denote
the expected value over some space of integrands. Then
where the choice of the space of integrands determines the specific form of the discrepancy
[Sacks and Ylvisacker 1970; Ritter 1995]. The case of the star discrepancy
has been studied by Wo'zniakowski [1991] and Morokoff and Caflisch [1994].
2. COMPUTING THE MEAN SQUARE L 2 -DISCREPANCY
Let E denote the expected value over a space of random sets P . In this section
we compute Ef[D 2 (P for simple random samples and for randomized (0; m; s)-
nets. Both kinds of samples satisfy Assumptions 1a and 1b. This allows a simple
treatment of terms in (1.4) involving only z j or only z 0
. The difficult term is jz
since its expected value depends on the correlation of z and z 0 .
Lemma 1. If P is a random set satisfying Assumptions 1a and 1b, then
Y
Proof. By Assumption 1a each z j is uniformly distributed on [0,1), so
By Assumption 1b, the components (z
s are mutually independent
so that the expectation of the product over j is the product of the expectations.
Combining these two results implies that (1.4) can be written as
s
Y
ae'
oe
Using the binomial theorem to rewrite the product completes the proof of this
lemma.
To simplify (2.1) further one must calculate
j. In the case where P is
a simple random sample it is straightforward to show that
(2.
Substituting this expression into (2.1) calculation leads to
oe
which after further simplification gives the following theorem:
Theorem 1. If P is a simple random sample, then
This formula serves as a benchmark for other (presumably superior) quasi-random
sets, P . Since the mean square generalized L 2 -discrepancy is O(N \Gamma1 ), the generalized
-discrepancy itself is typically O(N \Gamma1=2 ) for a simple random sample.
The mean square discrepancy of a randomized (0; m; s)-net is given by the following
theorem. Two major steps in the calculation are contained in Lemmas 2
and 3 below.
Theorem 2. Let P be a (0; m; s)-net randomized according to Assumption 1.
Let R(l; t) be defined as the partial binomial sum:
r
The mean square discrepancy of P is
l
\Theta
#)
The first step in the proof of this theorem is to calculate 3Ejz
randomized
net and obtain a formula analogous to (2.2).
Lemma 2. Suppose that P is a randomized (t; m; s)-net satisfying Assumption
1, and that z and z 0 are two points in P , such that the components z j and z 0
share
the same first k j digits, but no more. It follows that
Y
Proof. The j th components z j and z 0
share the same first k j digits, but have
different st digits, if and only if the original y j and y 0
j from which they came
have the same first k j digits but different k st digits. In this case Assumption
1c implies that
distributed according to Assumption 1cii, and where ffi
and ffi 0 are uniformly distributed on [0; 1). Then
To compute the mean square L 2 -discrepancy for a randomized net one must count
how many points share exactly the same first k j digits for all possible k u 2 Z u
. The
result for (0; m; s)-nets result is contained in the lemma below. It seems impossible
to extend this calculation to (t; m; s)-nets for t ? 0 because a (t; m; s)-net is not
defined precisely enough. For example, a (1; m; s)-net may also be a (0; m; s)-net.
Lemma 3. Suppose that P is any (0; m; s)-net (randomized or not). For any
fixed z let (k u ) denote the number of points z 0 2 P such that z j and z 0
share
exactly the same k j digits (but no more) for j 2 u. Then for finite k u
where
r
Proof. As a consequence of Definition 1 there are no points (other than z itself)
that have the same k u digits as z for oe(k holds in this
case. Now assume that (2.6) holds for all k u with oe(k u ) strictly greater than some
m. This is shown to imply that (2.6) holds for oe(k u
holds for all oe(k u ) by induction.
For any k 0
implies that there are b m\Gamma 0
points
z which have the same first k 0
(or more) digits as z. This can be written as
or
u means that k j  k 0
above represents z is assumed to be true for all oe(k
and since there are
different k u
u with oe(k u the sum over
u may be rewritten as
r
To simplify this double sum the index r is replaced by r  and the order of
summation is reversed:
An identity for binomial coefficients [Prudnikov et al. 1986, Section 4.2.5, Equation
47] simplifies the inner sum:
Substituting this formula for the sum back into
, which
completes the proof of (2.6).
Proof of Theorem 2. Combining the results of Lemmas 2 and 3 the sum over
in (2.1) can be written as:N 2
Y
ku2Z u
ku2Z u
For every are
with oe(k u
Y
Also, for any positive integer l, there are
l
distinct u ' S with
allows (2.1) to be written as:
l
\Theta
#)
thereby completing the proof.
From (2.4) it follows that
(2.
Therefore, only O(s 2 ) operations are required to calculate the O(s 2 ) nontrivial
values of R(l; s. The sums over l and  in (2.5) involve a
total of O(ms) terms, so the mean square L 2 -discrepancy of randomized (0; m; s)-
nets can be calculated in O(s log(N)+s 2 ) operations as N and/or s tend to infinity.
This order is much smaller than that required to compute the L 2 -discrepancy of an
arbitrary set P .
are quite similar. Thus,
the root mean square of D 2;u (P ) can be calculated using the same arguments as
for Theorems 1 and 2.
Theorem 3. If P is a simple random sample, then
Ef[D
Theorem 4. Let P be a (0; m; s)-net randomized according to Assumption 1 and
u be some non-empty subset of S. Then
Ef[D
l
6
\Theta
#)
3. ASYMPTOTICS
As N (or equivalently m) approaches infinity one would like to know how quickly
the mean squared L 2 -discrepancy tends to zero. This can be calculated by an
asymptotic analysis of the formulas in Theorems 2 and 4.
Theorem 5. Let P be a (0; m; s)-net randomized according to Assumption 1.
Then
Ef[D
Proof. The dependence on m in (2.5) and (2.9) lies in the term in square
brackets, which we call T (l). Its asymptotic form can be obtained by rewriting the
sum over  as an infinite sum. Since
it follows by (2.8) that
The definition of R(l; ) in (2.4) can be used to simplify this expression further:
r
r
which implies
r
For large m the binomial coefficient
\Delta is asymptotic to m
By reversing the order of the summation above one can
compute an asymptotic form for T (l):
r
r
=r
b \Gamma2
r
The asymptotic expected mean square discrepancy involves the sum of T (l) over
l. Because of the factor m above, the most significant term occurs when
Therefore,
which completes the proof of (3.1). A similar argument is used to prove (3.2).
Note that the asymptotic behavior of Ef[D 2 (P is independent of the function
and the constant M ; the asymptotic behavior of Ef[D 2;u (P is independent
of the constant fi as well. For prime power dimensions s there exist (0; m; s)-nets
with base [Niederreiter 1992, Theorem 4.54]). For this
case we have
where
For large s the coefficient A(s) tends to zero faster than exponentially. By Stirling's
as s !1:
4. DISCUSSION
The mean of the square of a random variable is equal to the square of it mean plus
the square of its standard deviation. In particular,
so
is an upper bound on both the mean and the standard deviation
of D 2 (P ). Thus, by Theorem 5
which is the same asymptotic order as a lower bound on D
derived by Roth
[1954]. Kuipers and Niederreiter [1974, p.102] refined this lower bound to give an
explicit constant (see also [Niederreiter 1978, Equation (3.10) and p. 972]):
where
12 \Gamma1=2 for
A lower bound on D
l
To compare the lower bound on the L 2 -star discrepancy for all P and the asymptotic
behavior for randomized (0; m; s)-nets, the coefficients A(s) and B(s) are
plotted in Figure 1. It is clear that B(s) tends to zero much faster than A(s) as
the dimension increases. The reason could be that i) the lower bound is not tight,
ii) the average discrepancy of (0; m; s)-nets is much worse than the discrepancies of
some especially good (0; m; s)-nets, or iii) the optimal discrepancy is only obtained
s
Coefficient

Figure

1. A comparison of A(s) (solid) and B(s) (dashed).
by some other kind of point set P . It is not clear to the author which reason is
more likely.
Given a lower bound, L, on D 2 (P ), such as zero or that above, one can derive
an upper bound on the likelihood that a randomized (0; m; s)-net has a large
discrepancy. For any non-negative y  L
that is,
Replacing y by a new constant ff 2 equal to the right hand side of this equation gives
ff
In particular, no more than 1% of randomized (0; m; s)-nets can have an L 2 -
discrepancy greater than 10
g.

Figure

2 shows the root mean square L 2 -star discrepancy for randomized (0; m; s)-
nets in base s plotted versus N from formula (2.5). The values of M and fi are given
in (1.5). The dimensions considered are the prime numbers 2 through 13, and N
runs up to 10 10 . For comparison, the root mean square asymptotic L 2 -discrepancy,
(3.1), the root mean square L 2 -star discrepancy of a simple random sample, (2.3),
and the lower bound on the L 2 -star discrepancy, (4.1), are also shown.

Figure

3 is similar to Figure 2 except that it shows the L 2 -symmetric discrepancy
defined in [Hickernell 1997]. In contrast to (1.5) the symmetric discrepancy is
defined by
Because (x) is invariant when x is replaced by 1 \Gamma x, the symmetric discrepancy
does not change when the P is reflected about any plane x 1=2. Like the star
discrepancy, the symmetric discrepancy has a geometric interpretation. For any
subset of coordinate indices u the planes passing through a point x u parallel to the
faces of the cube C u divide this cube into 2 juj intervals (rectangular solids). Each
interval consists of the points between a vertex of the cube and the point x u . These
intervals can be denoted as odd or even depending on the sum of the coordinates
of the corresponding vertex. For example, is an even interval, and
[x is even or odd according to whether juj is even or odd. Let J e
denote the union of the even intervals. The L 2 -symmetric discrepancy is defined as
In both Figures 2 and 3 the root mean square L 2 -discrepancies of the nets
approach their asymptotic behaviors - more quickly for lower dimensions. The
asymptotic values of the discrepancies increase with N initially because the term
increasing for N ! e (s\Gamma1)=2 .
The discrepancies of the nets decay to zero faster with increasing sample size
than the discrepancies of the simple random samples. The number of log(N) factors
in the asymptotic behavior of the discrepancy for nets increases with dimension
(see Theorem 5), thus reducing their advantage over simple random samples. This
effect is more pronounced for the symmetric discrepancy than the star discrepancy
because of the larger value of fi in the former. Formula (1.6) shows how [D 2 (P
is a sum of the [D 2;u (P )] 2 with weights fi 2juj . A larger value of fi accentuates
the importance of terms with large juj, that is, those terms that decay to zero
more slowly according to Theorem 5. A large or small value of fi is not inherently
better, but rather reflects a personal choice. Although decreasing fi decreases the
increases the variation (or norm) of the integrand in the corresponding
quadrature error bound. Thus, there is a trade-off. The effect of varying
fi is discussed further in [Hickernell 1997]. Our numerical experiments indicate that
root mean square discrepancy of a randomized (0; m; s)-net base s is never greater
than that of a simple random sample, regardless of the choice of  and fi. However,
this conjecture has not yet been proven.
Equations (1.1) and (3.1) imply that for randomized (0; m; s)-nets
sup
where the variation of the integrand, V (f ), is defined in [Hickernell 1997]. For a
fixed integrand f under similar smoothness conditions Owen [1996b] showed that
for randomized (0; m; s)-nets. The additional power of N \Gamma1 in the latter result
Discrepancy
Discrepancy
Discrepancy
Discrepancy
Discrepancy
Discrepancy

Figure

2. Root mean square L 2 -star discrepancy for randomized (0; m; s)-nets base s versus N
(ffi), asymptotic behavior (+), root mean square L 2 -star discrepancy of simple random sample
(solid), and lower bound on L 2 -star discrepancy (dashed).
Discrepancy
Discrepancy
Discrepancy
Discrepancy
Discrepancy
Discrepancy

Figure

3. Root mean square L 2 -symmetric discrepancy of randomized (0; m; s)-nets base s versus
N (ffi), asymptotic behavior (+), and root mean square L 2 -symmetric discrepancy of simple
random sample (solid).
is due to the integrand being fixed in advance of choosing a randomized net for
quadrature. In the former result the integrand is chosen pessimistically after picking
a specific randomized net.
One may wonder why we have computed the mean square L 2 -discrepancy and
not the mean L 2 -discrepancy itself or the mean L p -discrepancy in general. The
answer is convenience. Only the square L 2 -discrepancy appears to have a simple
enough form to allow its mean value to be computed.

ACKNOWLEDGMENTS

The author would like to thank Profs. Harald Niederreiter and Art Owen for their
valuable comments and suggestions.



--R

Handbook of Mathematical Functions with Formulas
Discr'epance de suites associ'ees 'a un syst'eme de num'eration (en dimension s).
Efficient algorithms for computing the L 2 discrepancy.
Quadrature error bounds with applications to lattice rules.
A generalized discrepancy and quadrature error bound.
Uniform Distribution of Sequences.



Random Number Generation and Quasi-Monte Carlo Methods
Equidistributed Latin hypercube samples.
Monte carlo variance of scrambled equidistribution quadrature.
Scrambled net variance for integrals of smooth functions.
Integrals and Series.
Average case analysis of numerical problems.
On irregularities of distribution.
Statistical design and integral approximation.
Lattice Methods for Multiple Integration.
Computational investigations of low discrepancy point sets.

Average case complexity of multivariate integration.

--TR
Random number generation and quasi-Monte Carlo methods
Quasi-random sequences and their discrepancies
Quadrature Error Bounds with Applications to Lattice Rules
Monte Carlo Variance of Scrambled Net Quadrature
A generalized discrepancy and quadrature error bound

--CTR
Friedrich Pillichshammer, On the root mean square weighted L
Stefan Heinrich , Fred J. Hickernell , Rong-Xian Yue, Optimal quadrature for Haar wavelet spaces, Mathematics of Computation, v.73 n.245, p.259-277, January 2004
Art B. Owen, Monto Carlo extension of quasi-Monte Carlo, Proceedings of the 30th conference on Winter simulation, p.571-578, December 13-16, 1998, Washington, D.C., United States
Shu Tezuka , Henri Faure, I-binomial scrambling of digital nets and sequences, Journal of Complexity, v.19 n.6, p.744-757, December
Michael G. Hilgers, Quasi-Monte Carlo methods in cash flow testing simulations, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
Fred J. Hickernell, My dream quadrature rule, Journal of Complexity, v.19 n.3, p.420-427, June
Dick , Friedrich Pillichshammer, Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces, Journal of Complexity, v.21 n.2, p.149-149, April 2005
Hee Sun Hong , Fred J. Hickernell, Algorithm 823: Implementing scrambled digital sequences, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.95-109, June
Art B. Owen, Variance with alternative scramblings of digital nets, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.4, p.363-378, October
Art B. Owen, Latin supercube sampling for very high-dimensional simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.71-102, Jan. 1998
quasi-random sets;multidimensional integration;quasi-Monte Carlo methods;quadrature;number-theoretic nets and sequences