Bounds for the average Lp-extreme and the
L∞-extreme discrepancy
Michael Gnewuch ∗
Mathematisches Seminar, Christian-Albrechts-Universit¨at Kiel
Christian-Albrechts-Platz 4, D-24098 Kiel, Germany
e-mail: mig@numerik.uni-kiel.de
Submitted: Jan 24, 2005; Accepted: Oct 18, 2005; Published: Oct 25, 2005
Mathematics Subject Classifications: 11K38
Abstract
The extreme or unanchored discrepancy is the geometric discrepancy of point
sets in the d-dimensional unit cube with respect to the set system of axis-parallel
boxes. For 2 ≤p<∞we provide upper bounds for the average Lp-extreme dis-
crepancy. With these bounds we are able to derive upper bounds for the inverse
of the L∞-extreme discrepancy with optimal dependence on the dimension dand
explicitly given constants.
1 Introduction
Let Rdbe the set of all half-open axis-parallel boxes in the d-dimensional unit ball with
respect to the maximum norm, i.e.,
Rd={[x, y)|x, y ∈[−1,1]d,x≤y},
where [x, y):=[x1,y
1)×...×[xd,y
d) and inequalities between vectors are meant component-
wise. It is convenient to identify Rdwith
Ω:={(x, x)∈R2d|−1≤x≤x≤1},
where for any real scalar awe put a:= (a,...,a)∈Rd.TheLp-extreme discrepancy of a
point set {t1,...,t
n}⊂[−1,1]dis given by
Dp(t1, ..., tn):=Z
Ω
d
Y
l=1
(xl−xl)−1
n
n
X
i=1
1[x,x)(ti)
pdω(x, x)1/p
,
∗Supported by the Deutsche Forschungsgemeinschaft under Grant SR7/10-1
the electronic journal of combinatorics 12 (2005), #R54 1
where 1[x,x)denotes the characteristic function of [x, x)anddω is the normalized Lebesgue
measure 2−ddx dx on Ω. The L∞-extreme discrepancy is
D∞(t1, ..., tn):= sup
(x,x)∈Ω
d
Y
l=1
(xl−xl)−1
n
n
X
i=1
1[x,x)(ti)
,
and the smallest possible L∞-extreme discrepancy of any n-point set is
D∞(n, d)= inf
t1,...,tn∈[−1,1]dD∞(t1, ..., tn).
Another quantity of interest is the inverse of D∞(n, d), namely
n∞(ε, d)=min{n∈N|D∞(n, d)≤ε}.
If we consider in the definitions above the set of all d-dimensional corners
Cd={[−1,y)|y∈[−1,1]d}
instead of Rd, we get the classical notion of star-discrepancy.
It is well known that the star-discrepancy is related to the error of multivariate inte-
gration of certain function classes (see, e.g., [2, 5, 8, 10, 12]). That this is also true for the
extreme discrepancy was pointed out by Novak and Wo´zniakowski in [12]. Therefore it is
of interest to derive upper bounds for the extreme discrepancy with a good dependence
on the dimension dand explicitly known constants.
Heinrich, Novak, Wasilkowski and Wo´zniakowski showed in [4] with probabilistic meth-
ods that for the inverse n∗
∞(ε, d) of the star-discrepancy we have n∗(ε, d)≤Cdε−2.The
drawback is here that the constant Cis not known. In the same paper a lower bound was
proved establishing the linear dependence of n∗
∞(ε, d)ond. This bound has recently been
improved by Aicke Hinrichs to n∗
∞(ε, d)≥cdε−1[6]. These results hold also for n∞(ε, d).
In [4], Heinrich et al. presented two additional bounds for n∗
∞(ε, d) with slightly worse
dependence on d, but explicitly known constants. The first one uses again a probabilistic
approach, employs Hoeffding’s inequality and leads to
n∗
∞(ε, d)≤Odε−2ln(d)+ln(ε−1).
The approach has been modified in more recent papers to improve this bound or to derive
similar results in different settings [1, 5, 9]. In particular, it has been implicitly shown
in the quite general Theorem 3.1 in [9] that the last bound holds also for the extreme
discrepancy (as pointed out in [3], this result can be improved by employing the methods
used in [1]).
The second bound was shown in the following way: The authors proved for even pan
upper bound for the average Lp-star discrepancy av∗
p(n, d):
av∗
p(n, d)≤32/325/2+d/pp(p+2)
−d/pn−1/2.
the electronic journal of combinatorics 12 (2005), #R54 2
(This analysis is quite elaborate, since av∗
p(n, d) is represented as an alternating sum of
weighted products of Stirling numbers of the first and second kind.) The bound was
used to derive upper bounds n∗
∞(ε, d)≤Ckd2ε−2−1/k for every k∈N. To improve the
dependence on d, Hinrichs suggested to use symmetrization. This approach was sketched
in [11] and leads to
av∗
p(n, d)≤21/2+d/pp1/2(p+2)
−d/pn−1/2
and n∗
∞(ε, d)≤Ckdε−2−1/k. (Actually there seems to be an error in the calculations in
[11], therefore we stated the results of our own calculations—see Remark 4 and 9).
In this paper we use the symmetrization approach to prove an upper bound for the
average Lp-extreme discrepancy avp(n, d) for 2 ≤p<∞. Our analysis does not need
Stirling numbers and uses rather simple combinatorial arguments. Similar as in [4], we
derive from this bound upper bounds for the inverse of the L∞-extreme discrepancy of
the form n∞(ε, d)≤Ckdε−2−1/k for all k∈N.
2 Bound for the average Lp-discrepancy
If x,xare vectors in Rdwith x≤x, we use the (non-standard) notation x:= (x−x)/2.
Let p∈Nbe even. For i=1, ..., n we define the Banach space valued random variable
Xi:[−1,1]nd →Lp(Ω,dω)byXi(t)(x, x)=1
[x,x)(ti). Then X1, ..., Xnare independent
and identically distributed. Note that Xiis Bochner integrable for all i∈[n]. If Edenotes
the expectation with respect to the normalized measure 2−nd dt,thenEXi∈Lp(Ω,dω)
and EXi(x, x)=x1...xdalmost everywhere. We obtain
avp(n, d)p=Z
[−1,1]nd
Dp(t1, ..., tn)p2−nd dt
=Z
[−1,1]nd
1
n
n
X
i=1
(Xi(t)−EXi)
p
Lp(Ω,dω)2−nd dt
=E
1
n
n
X
i=1
(Xi−EXi)
p
Lp(Ω,dω).
Let ε1, ..., εn:[−1,1]nd →{−1,+1}be symmetric Rademacher random variables, i.e.,
random variables taking the values ±1 with probability 1/2. We choose these variables
such that ε1, ..., εn,X
1, ..., Xnare independent. Then (see [7, §6.1])
avp(n, d)p≤E2p
1
n
n
X
i=1
εiXi
p
Lp(Ω,dω)
=2
npn
X
i1,...,ip=1 Z
[−1,1]nd
Z
Ω
p
Y
l=1 εil(t)1[x,x)(til)dω(x, x)2
−nd dt .
the electronic journal of combinatorics 12 (2005), #R54 3
Let us now consider (x, x)∈Ω, k∈[p], pairwise disjoint indices i1, ..., ikand j1, ..., jk∈[p]
with Pk
l=1 jl=p. According to Fubini’s Theorem
J:= Z
[−1,1]nd k
Y
l=1
εjl
il(t)Z
Ωk
Y
l=1
Xjl
il(t)(x, x)dω(x, x)2−nd dt
=k
Y
l=1 Z
[−1,1]nd
εjl
il(t)2
−nd dtZ
ΩZ
[−1,1]nd k
Y
l=1
1[x,x)(til)2−nd dt dω(x, x).
This yields J=RΩ(x1...xd)kdω(x, x)=2
d(k+1)
−d(k+2)
−dif every exponent jlis even,
and J= 0 if there exists at least one odd exponent jl.LetT(p, k, n)bethenumberof
tuples (i1, ..., ip)∈[n]pwith |{i1, ..., ip}| =kand |{l∈[p]|il=im}| even for each m∈[p].
Our last observation implies
avp(n, d)p≤2p+dn−p
p/2
X
k=1
T(p, k, n)
(k+1)
d(k+2)
d.
In the next step we shall estimate the numbers T(p, k, n). For that purpose we introduce
further notation. Let
M(p/2,k)=nν∈Nk
1≤ν1≤... ≤νk≤p/2,
k
X
i=1
νk=p/2o,
and for ν∈M(p/2,k)lete(ν, i)=|{j∈[k]|νj=i}|. With the standard notation for
multinomial coefficients we get
T(p, k, n)= X
ν∈M(p/2,k)p
2ν1, ..., 2νkn(n−1)...(n−k+1)
e(ν, 1)!...e(ν, p/2)! .
If ♯(p/2,k,n) denotes the number of tuples (i1, ..., ip/2)∈[n]p/2with |{i1, ..., ip/2}|
=k,then
♯(p/2,k,n)= X
ν∈M(p/2,k)p/2
ν1, ..., νkn(n−1)...(n−k+1)
e(ν, 1)!...e(ν, p/2)! .
We want to compare T(p, k, n)with♯(p/2,k,n) and are therefore interested in the quantity
Qp
k(ν):=p
2ν1, ..., 2νk p/2
ν1, ..., νk−1
.
To derive an upper bound for Qp
k(ν), we prove two auxiliary lemmas.
Lemma 1. Let f:N0→Rbe defined by f(r)=[2r(2r−1)...(r+ 1)](2r)−rfor r>0and
f(0) = 1. Then f(r+s)≤f(r)f(s)for all r,s∈N0.
the electronic journal of combinatorics 12 (2005), #R54 4
Proof. We prove the inequality for an arbitrary sby induction over r.Itisevidentifr=0.
So let the inequality hold for some r∈N0. The well known relations Γ(x+1)=xΓ(x)
and √πΓ(2x)=2
2x−1Γ(x)Γ(x+1/2) for the gamma function lead to
f(r)=2
2rπ−1/2Γ(r+1/2) exp(−rln(2r)) ,
with the convention 0 ·ln(0) = 0 when r=0,and
f(r+1+s)
f(r+1) =g(r)
g(r+s)
f(r+s)
f(r),
where g:[0,∞)→[0,∞) is defined by g(0) = 2 and
g(λ)=1+ 1
2λ+1exp(λln(1 + 1/λ))
for λ>0. The function gis continuous in 0 and its derivative is given by
g′(λ)=ln(1 + 1/λ)−2
2λ+1g(λ)
for λ>0. Since
d
dλln(1 + 1/λ)−2
2λ+1=−1
λ(λ+ 1)(2λ+1)
2<0
and
lim
λ→∞ ln(1 + 1/λ)−2
2λ+1
=0,
we obtain g′(λ)≥0. Therefore gis an increasing function. Thus
g(r)
g(r+s)≤1,which establishes f(r+1+s)
f(r+1) ≤f(r+s)
f(r)≤f(s).
Lemma 2. Let k∈N,a1, ..., ak∈[0,∞)and σ=Pk
i=1 ai. Then
σ
kσ≤
k
Y
i=1
aai
i.
Proof. Let σ>0, and consider the functions s:Rk→R,x7→ Pk
i=1 xiand
f:[0,∞)k→R,x7→
k
Y
i=1
xxi
i=
k
Y
i=1
exp(xiln(xi)) ,
where we use the convention 0 ·ln(0) = 0. Let M={x∈(0,∞)k|s(x)=σ}.Sincefis
continuous, there exists a point ξin the closure Mof Mwith f(ξ)=min{f(x)|x∈M}.
the electronic journal of combinatorics 12 (2005), #R54 5