A Generalization of the maximal-spacings in several
dimensions and a convexity test.
Catherine Aarona , Alejandro Cholaquidisb , Ricardo Fraimanb
a

Université Blaise-Pascal Clermont II.

b

Universidad de la República.

arXiv:1411.2482v2 [] 5 May 2016

Abstract
The notion of maximal-spacing in several dimensions was introduced and studied
by Deheuvels (1983) for data uniformly distributed on the unit cube. Later on,
Janson (1987) extended the results to data uniformly distributed on any bounded
set, and obtained a very fine result, namely, he derived the asymptotic distribution
of different maximal-spacings notions. These results have been very useful in many
statistical applications.
We extend Janson’s results to the case where the data are generated from
a Hölder continuous density that is bounded from below and whose support is
bounded. As an application, we develop a convexity test for the support of a distribution.

Key words:maximal spacing, convexity test, non-parametric density estimation.

1

Introduction

The notion of spacings, which for one dimensional data are just the differences between
two consecutive order statistics, have been extensively studied in the one dimensional
setting; see, e.g., the review papers [18, 19]. Many important applications to testing
and estimation problems have been derived from the study of the asymptotic behaviour
of the spacings. Applications to testing problems date back to [20], who address the
asymptotic theory of a class of tests for Increasing Failure Rate. For estimation problems,
[21] propose the maximum spacing estimation method to estimate the parameters of a
univariate statistical model.
In the multidimensional case, several different notions of maximal-spacing have been
proposed. Most of them are based on the nearest-neighbors balls (see for instance [14]
or [2]) or on the Voronoi tessellation [16], (a comparison can be found in [22]), but they
do not capture the key idea of ‘largest set missing the observations’. In contrast, this is
the case with the different and global notion proposed in [7], and generalized in [12].
In [7], the notion of maximal-spacing is defined and studied
Q for iid data uniformly
distributed in [0, 1]d as the maximal length a of a cube C = [xi , xi + a], included in
[0, 1]d that does not contain any of the observations. This notion has been extended in
[12], in which the uniformity assumption remains but the support of the distribution is
no longer assumed to be [0, 1]d but may be any compactum S. Moreover, C is allowed
to be any compact and convex set. Finally, while in [7] only bounds are given, in [12]
the asymptotic distribution for the maximal spacing is provided.
The notion of maximal multivariate spacing, and in particular Janson’s result, has
been used to solve different statistical problems. In set estimation (see, for instance, [3]
1

and [4] ), it is used to prove the optimality of the rates of convergence.
The aim of this paper is to extend Janson’s result to Hölder continuous densities,
and develop, using that extension, a test to decide whether the support is convex or not.
It is organized as follows: Section 2 is devoted to the extension of Janson’s results. A
new definition (which includes Janson’s as a particular case) is given and the associated
theoretical results are presented. The proofs of these results are given in Appendix
A. Section 3 is dedicated to the problem of testing the convexity of the support. The
corresponding proofs are given in Appendix B. Just to mention some application of this
test, let us recall that when dealing with support estimation, if the support is known
to be convex, the convex hull of the observations provides a consistent and well studied
(see for instance [23],[24] and [27]) estimator of S which does not require any smoothing
parameter. Also, a convexity test can be used to, a posteriori, select a tuning parameter.
In [6] a test for convexity is also proposed, and applied to choose the parameter of the
ISOMAP (see [26]) method for dimensionality reduction. The convexity test based on
Janson’s extension allows us to provide an estimation of the p-value, whereas, in [6], it
has to be estimated via the Monte Carlo method.

2

Main definitions and results

We start by fixing some notation that will be used throughout the paper.
Given a set S ⊂ Rd , we denote by ∂S, S̊, S, diam(S), |S|, and H(S), the boundary,
interior, closure, diameter, Lebesgue measure, and convex hull of S, respectively. We
denote by k · k and h·, ·i the euclidean norm and the inner product respectively. We
write N (S, ε) for the inner covering number of S (i.e.: the minimum number of balls
of radius ε and centred in S required to cover S). Recall that if S is compact, there
exists CS such that N (S, ε) ≤ CS ε−d . We denote by B(x, ε) the closed ball in Rd ,
of radius ε, centered at x. We set ωd = |B(0, 1)|. Given λ ∈ R, A, C ⊂ Rd , we set
λA = {λa : a ∈ A}, A ⊕ C = {a + c : a ∈ A, c ∈ C}, and A C = {x : {x} ⊕ C ⊂ A}. For
the sake of simplicity, we use the notation x + C, instead of {x} ⊕ C. If λ ≥ 0, we set
Aλ = A ⊕ λB(0, 1) and A−λ = A λB(0, 1). Given A, C ⊂ Rd two non-empty compact
sets, the Hausdorff (or Pompeiu–Hausdorff) distance between them is given by


dH (A, C) = max max d(a, C), max d(c, A) ,
a∈A

c∈C

where d(a, C) = inf{ka − ck : c ∈ C}.
Let A ⊂ Rd be a compact convex set with |A| = 1, let v be a vector of Rd , and let
αA (v) be the constant defined in equation (2.4) of [12]:
Z
Z
d
1
αA (v) =
...
Det n(yi ) i=1 dω(y1 ) . . . dω(yd ),
(1)
d!
where ω denotes the d − 1 dimensional Hausdorff measure, and for y ∈ ∂A, n(y) denotes
the exterior unit normal vector to A at y. The integral in (1) is over all y1 , . . . , yd ∈ ∂A
2

such that v is a linear combination of n(y1 ), . . . , n(yd ) with positive coefficients, and
Det(n(yi ))di=1 is the determinant of the vectors n(yi ) in an orthonormal basis. Corollary
7.4 in [13] proves that αA (v) is almost everywhere independent of v, so that there can
be defined an αA such that αA (v) = αA almost everywhere.
If A is the unit cube, then αA = 1; while if B is the unit ball, then
1
αB =
d!

√

πΓ
Γ

d
2 +1

d+1
2

 !d−1
.


Lastly, let U be a random variable such that P(U ≤ t) = exp − exp(−t) .

2.1

Janson’s result and its extension

Let S ⊂ Rd be a bounded set with |S| = 1 and |∂S| = 0. Let ℵn = {X1 , . . . , Xn } be iid
random vectors uniformly distributed on S, and A a bounded convex set. In [12], the
maximal-spacing is defined as
n
o
∆∗ (ℵn ) = sup r : ∃x such that x + rA ⊂ S \ ℵn .
To generalize the results of [12] to the non-uniform case, we need to extend the
definition of maximal-spacing. When the sample is drawn according to a probability
measure PX , we consider the probability measure of the largest set λA missing ℵn . If
|A| = 1, ∆∗ (ℵn )d is the Lebesgue measure of the largest set x + rA ⊂ S \ ℵn . When
the sample is drawn from a non-uniform probability measure, is natural to use the
same definition, replacing the Lebesgue measure by the true underling distribution PX .
If PX has continuous density f , then PX (x + rA) ∼ f (x)rd for sufficiently small r,
so one can define the maximal-spacing as the largest r such that there exists x with
x + f (x)r 1/d A ⊂ S \ ℵn .
Definition 1. Let ℵn = {X1 , . . . , Xn } be an iid random sample of points in Rd , drawn
according to a density f with bounded support S. Let A ⊂ Rd be a convex and compact
set such that |A| = 1 and its barycentre is the origin of Rd . We define
n
o
r
∆(ℵn ) = sup r : ∃x such that x +
A
⊂
S
\
ℵ
,
n
f (x)1/d
V (ℵn ) = ∆d (ℵn ),
and

U (ℵn ) = n∆d (ℵn ) − log(n) − (d − 1) log log(n) − log(αA ).
The following result can be found in [12].
Theorem 1. Let S ⊂ Rd be a bounded set such that |S| = 1 and |∂S| = 0. Let
ℵn = {X1 , . . . , Xn } be iid random vectors uniformly distributed on S. Then,

3

i)
L

U (ℵn ) −→ U

when n → ∞,

ii)
lim inf

n→+∞

nV (ℵn ) − log(n)
= d − 1 a.s.,
log(log(n))

iii)
lim sup
n→+∞

nV (ℵn ) − log(n)
= d + 1 a.s.
log(log(n))

A rescaling extends these results to the case where |S| =
6 1.
Corollary 1. Let S ⊂ Rd be a bounded set such that |∂S| = 0 and |S| > 0. Let
ℵn = {X1 , . . . , Xn } be iid random vectors uniformly distributed on S. Then,
i)
L

U (ℵn ) −→ U

when n → ∞,

ii)
lim inf

n→+∞

nV (ℵn ) − log(n)
= d − 1 a.s.,
log(log(n))

iii)
lim sup
n→+∞

nV (ℵn ) − log(n)
= d + 1 a.s.
log(log(n))

Janson’s result does not require any condition on the shape of the support S, while in
our extension it will be required that the inside covering number of ∂S is such that there
exists C∂S > 0 and κ < d satisfying N (∂S, ) ≤ C∂S −κ . Note that this is a very mild
hypothesis: if ∂S is smooth enough (for instance, a C1 (d − 1)−dimensional manifold), it
is fulfilled for κ = d − 1. More generally, it also holds for any set S with finite Minkowski
content of the boundary, for κ = d − 1 (see, for instance [15]). With respect to the
distribution of the sample, we require that the density is Hölder continuous on S (i.e.
there exists Kf and β ∈ (0, 1] such that for all x, y ∈ S, |f (x) − f (y)| ≤ Kf kx − ykβ )
and bounded from below on it support, by a positive constant f0 .
This is stated in our main theorem, given below.
Theorem 2. Let ℵn = {X1 , . . . , Xn } be iid random vectors distributed according to a
distribution PX whose density f with respect to Lebesgue measure is Hölder continuous
and bounded from below on its support S. Let us assume that S is compact, and there
exists κ < d and C∂S > 0 such that N (∂S, ε) ≤ C∂S ε−κ Then, we have that
L

U (ℵn ) −→ U

lim inf

n→+∞

when n → ∞,

nV (ℵn ) − log(n)
≥ d − 1 a.s.,
log(log(n))
4

(2)

(3)

lim sup
n→+∞

nV (ℵn ) − log(n)
≤ d + 1 a.s.
log(log(n))

(4)

The proof is given in Appendix A.

3
3.1

A new test for convexity
The semi-parametric case

In this section we propose, using the concept of maximal-spacing defined in Section 2,
a consistent hypothesis test based on an iid sample {X1 , . . . , Xn } uniformly distributed
on a compact set S, to decide whether S is convex or not.
The main idea is the following: if S is convex and the sample is uniformly distributed on S, then H(ℵn ) is a good approximation to S and |H(ℵn )|−1 IH(ℵn ) is a good
approximation of the uniform law. As a result,
n
o
˜ n ) = sup r : ∃x such that x + r|H(ℵn )|1/d B(0, 1) ⊂ H(ℵn ) \ ℵn
∆(ℵ
is a plug-in estimator of the maximal spacing and should converge to 0. On the other
˜ n ) is expected to converge to a positive constant (that
hand, if S is not convex, ∆(ℵ
depends on the shape of S). In order to unify notation, let us first define the maximal
inner radius.
Definition 2. Let S ⊂ Rd be a bounded set satisfying S̊ 6= ∅. We define the maximal
inner radius of S as

R(S) = sup r : ∃x ∈ S such that B(x, r) ⊂ S .
1/d
˜ n ) = R(H(ℵn )\ℵn )ω 1/d |H(ℵn )|1/d .
Remark 1. We have ∆(ℵn ) = R(S\ℵn )ωd |S|1/d and ∆(ℵ
d

˜ n ), we
When testing the convexity of the support using a test statistic based on ∆(ℵ
only obtain, in general, an upper asymptotic bound on the test level. However, if the
boundary of the support is smooth enough, we have a converging estimation of the level.
The regularity condition is the following.
Condition (P): For all x ∈ ∂S there exists a unique vector ξ = ξ(x) with kξk = 1,
such that hy, ξi ≤ hx, ξi for all y ∈ S, and
kξ(x) − ξ(y)k ≤ lkx − yk

∀ x, y ∈ ∂S,

where l is a constant. We will denote by CP the class of convex subsets that satisfy
condition (P).
The convexity test and its asymptotic behaviour is given in the following theorem.

5

Theorem 3. Let S ⊂ Rd be compact with non-empty interior. Let ℵn = {X1 , . . . , Xn }
be a set of iid random vectors uniformly distributed on S. For the following decision
problem,
(
H0 : the set S is convex
(5)
H1 : the set S is not convex,
d
the test based on the statistic Ṽn = |H(ℵn )|ωd R H(ℵn ) \ ℵn with critical region given
by

RC = Ṽn > cn,γ ,
where
cn,γ =




1
− log − log(1 − γ) + log(n) + (d − 1) log log(n) + log(αB ) ,
n

and αB is the constant defined in (1), is asymptotically of level less than or equal to γ.
Moreover, if S ∈ CP , the asymptotic level is γ. If S is not convex, the test has power
one for all sufficiently large n.
The proof of Theorem 3 is given in Appendix B.

3.2

The non-parametric case

We now assume that we have a sample ℵn = {X1 , . . . , Xn } of iid random vectors in Rd
drawn according to an unknown density f . As in the semi-parametric case, the idea is
to estimate the maximal-spacing and use this estimation as a test statistic. As before,
H(ℵn ) is proposed as an estimator of S. To ensure that the test proposed in Theorem 3
allows determining whether the support is convex or not, the density estimator should
have a non-conventional behaviour: it is expected to converge toward the unknown
density when the support is convex, but not when the support is not convex. That is
why we propose the following density estimator.

Definition 3. Let Vor(Xi ) be the Voronoi cell of the point Xi (i.e. Vor(X
R i) = x :
K is a kernel function (i.e. K ≥ 0, K = 1 and
kx
R − Xi k = miny∈ℵn kx − yk ). 1 IfP
uK(u)du = 0) and fn (x) = nhd
K((x − Xi )/hn ) denotes the usual kernel density
n
estimator, we define
fˆn (x) =
max
fn (Xi )Ix∈H(ℵn ) .
(6)
i:x∈Vor(Xi )
We propose to test the convexity using the following plug-in estimator of ∆(ℵn ):



r
δ̂ H(ℵn ) \ ℵn = sup r : ∃x such that x +
A ⊂ H(ℵn ) \ ℵn ,
fˆn (x)1/d
−1/d

with A = ωd B(0, 1), and reject H0 (the support is convex) if δ̂(H(ℵn ) \ ℵn ) is sufficiently large.
The proof of Theorem 4 makes use of Theorem 2.3 in [11]. In order to apply that
result, we will introduce some technical hypotheses on the kernel function.
6

Definition 4. Let K be the set of kernel functions K(u) = φ(p(u)), where p is a
polynomial
and φ a is bounded real function of bounded variation, such that cK =
R
kukK(u)du < ∞, K ≥ 0 and there exists rK and c0K > 0 such that K(x) ≥ c0K
for all x ∈ B(0, rK ).
Note that, for example, the Gaussian and the uniform kernel are in K.
Definition 5. A set S is standard if there exist positive numbers r0 , cS such that
|B(x, r) ∩ S| ≥ cS ωd rd for all r ≤ r0 . We write C for the class of compact convex
sets with non-empty interior, and A for the class of all compact standard sets.
Finally it is also necessary to impose some conditions on the density.
Condition (B): A density f with support S fulfils condition B if its restriction to S
is Lipschitz continuous (i.e. there exists kf such that ∀x, y ∈ S, |f (x)−f (y)| ≤ kf kx−yk)
and there exists f0 > 0 such that f (x) ≥ f0 for all x ∈ S. We denote f1 = maxx∈S f (x).
Remark 2. The condition f (x) ≥ f0 > 0 for all x ∈ S is a necessary condition to test
convexity, as indeed is mentioned in [6]: ‘...an assumption like the density being bounded
away from zero on its support is necessary for consistent decision rules.’
Theorem 4. Let K ∈ K, and let fˆn be as defined in (3). Assume that hn = O(n−β ) for
some 0 < β < 1/d. Assume also that the unknown density fulfils condition B. For the
following decision problem,
(
H0 : S ∈ C
(7)
H1 : S ∈
/ C,
a) the test based on the statistic V̂n = δ̂ H(ℵn )\ℵn
cn,γ }, where
cn,γ =

d

with critical region RC = {V̂n ≥


1
− log(− log(1 − γ)) + log(n) + (d − 1) log(log(n)) + log(αB ) ,
n

has an asymptotic level less than γ.
b) Moreover, if S ∈ A is not convex, the power is 1 for sufficiently large n.
Remark 3. Notice that the ‘optimal’ kernel sequence size, hn = h0 n1/(d+4) , satisfies the
hypothesis of our theorem, so that any bandwidth selection method should be suitable for
testing for convexity.
However, in the semi-parametric case it is possible to derive the asymptotic behaviour
for the level under regularity conditions on the support. In this more general setup, we
will not have a convergent level estimation but only a bound for the level (the price to
pay for estimating the density). The proof of Theorem 4 is given in Appendix B.

7

3.3

Simulations

We have performed two simulation studies to assess the behaviour of our test in the
scenarios described in Sections 3.1 and 3.2. For the first study, the data were drawn
uniformly from sets S ⊂ R2 , and we will perform the test defined in Section 3.1 to
obtain estimations of the power and the level. In the second study, the non-parametric
case, the data can be not uniformly drawn drawn, and we estimate the density using the
estimator given by (6). In this case, we consider the same sets and density as in [6].
3.3.1

Semi-Parametric case

The data were generated uniformly from the sets Sϕ = [0, 1]2 \ Tϕ , where Tϕ is the
isosceles triangle with height 1/2 (see Figure 1) whose angle at the vertex (1/2, 1/2)
is equal to ϕ. If we have a random sample from Sϕ , it is clear that as ϕ increases, it
should be easier to detect the non-convexity of the set. The results of the simulations
are summarized in Table 1.
ϕ = π/4
n
β̂
100
.4
130 .636
160 .835
200 .946
300 .997

ϕ = π/6
n
β̂
200 .565
250 .787
300 .926
400 .996
500
1

ϕ = π/8
n
β̂
300 .543
350 .679
400 .846
500 .976
600 .997

Table 1: Power estimated over 1000 replications, for different values of ϕ, when the
sample is uniformly distributed on [0, 1]2 \ Tϕ , where Tϕ is an isosceles triangle, (see
Figure 1).

φ

Figure 1: [0, 1]2 \ Tϕ where Tϕ is an isosceles triangle with height 1/2.

3.3.2

Non-parametric case

We performed a simulation study for the same sets used in [6]. Consider the curves
γR,θ = R(cos(θ), sin(θ)) with θ ∈ [ 3π(R−1)
, 32 π] and the reflections of those curves along
2R
the y axis (which will be denoted by ζR,θ ). We consider ΓR = T(0,R) (γR,θ ) ∪ T(0,−R) (ζR,θ )
with θ ∈ [ 3π(R−1)
, 23 π], where Tv is the translation along the vector v. It is easy to
2R
8

see that the length of every ΓR is 32 π. We will consider, for different values of R, the
S-shaped sets (see the first row in Figure 2)

SR = T(0,R) 


[



γr,θ  ∪ T(0,−R) 

R−0.6≤r≤R+0.6


[

ζr,θ  .

R−0.6≤r≤R+0.6

Observe that when R approaches infinity, the sets S converge to a rectangle (which
corresponds to the convex case). We have generated the data according to two different
densities. The first one is the same as that considered in [6]: that is, along the orthogonal
direction of ΓR , we choose a random variable with normal density (with zero mean and
standard deviation σ = 0.15) truncated to 0.6 (the truncation is performed to ensure
that we obtain a point in the set SR ). In the second case, we consider a random variable
along the orthogonal direction of ΓR but uniformly distributed on [−0.6, 0.6]. In Tables
2 and 3, we have summarized the results of the simulations, for different sample sizes
(we performed the test B = 100 times). The results are quite encouraging and slightly
better that those obtained in [6] since the non-convexity is better detected (see Fig. 7 in
[6] for comparison) with no need for the decision rule to be calibrated.
R
1
1.5
3
6
12
24
∞

N=100
np unif
.13
.44
.98
1
.38
.24
.08
.09
.01
.05
0
.07
0
.04

N=250
np unif
.55
.99
1
1
1
1
.41
.66
.02
.08
.01
.05
0
.09

N=500
np unif
1
1
1
1
1
1
1
1
.39
.68
0
.09
0
.04

N=1000
np unif
1
1
1
1
1
1
1
1
.98
1
.07
.48
.01
.05

Table 2: Power estimated over B replications, for different values of R, when the sample
is uniformly distributed along the orthogonal direction of ΓR .
R
1
1.5
3
6
12
24
∞

N=100
np unif
1
1
1
1
1
.99
.67
.41
.25
.19
.1
.30
0
.33

N=250
np unif
1
1
1
1
1
1
.99
1
.62
.98
.30
.92
.04
.92

N=500
np unif
1
1
1
1
1
1
1
1
.85
1
.38
1
.06
1

N=1000
np unif
1
1
1
1
1
1
1
1
.94
1
.48
1
.04
1

Table 3: Power estimated over B replications, for different values of R, when the sample
is drawn according to a truncated normal distribution along the orthogonal direction of
ΓR .

9

Figure 2: SR for different values of R together with the sample drawn with a uniform
radial noise (top) and with a truncated Gaussian noise (bottom)
.

4

Appendix A

In Appendix A we proof the main result on the generalization of the maximal-spacing,
given in Theorem 2. First we settle some preliminary lemmas, then we prove a weaker
version of Theorem 2, for the case of piecewise constant densities on disjoint sets. We
continue by considering piecewise constant densities, and finally we prove the result for
Hölder continuous densities.

4.1

Preliminary Lemmas

As we mentioned before, the proof of Corollary 1 follows from a simple rescaling in the
lemmas stated in [12], used to prove Theorem 1. In particular the following rescaled
lemma will be used in this section.
Lemma 1. Let S ⊂ Rd be a bounded set, |S| > 0, |∂S| = 0, and ℵn = {X1 , . . . , Xn }
iid random vectors with uniform distribution on S. Then, there exists aS− = aS− (w, n),
aS+ = aS+ (w, n) such that aS− → αA and aS+ → αA as w → ∞ and w/n → 0, such that if
n d−1 −w
γ = |S|
w e ,

exp(−γaS+ |S|) ≤ P nV (ℵn ) < w ≤ exp(−γaS− |S|).
(8)
The functions aS+ and aS− only depend on the “shape” of S (i.e. are invariant by similarity
transformations). Without loss of generality they can be chosen such that, for all w0 ≥ w
and n0 ≥ n: aS+ (w0 , n0 ) ≤ a+ (w, n) and aS( − w0 , n0 ) ≥ a− (w, n).
Next we settle two lemmas whose proofs are quite similar. The first one (Lemma
2) gives a first rough upper bound for the maximal spacing. The second one (Lemma
3) bounds a sort “constrained” maximal-spacing (the centre x of the largest set x + rA
missing the observation is constrained to be in a “small” subset of the support).
Recall first (see [1]) that, since A is convex, there exist ε0 > 0 such that,
for all ε ≤ ε0 , A−ε 6= ∅ and |A−ε | = |A| − ε|∂A|d−1 + o(ε).
10

(9)

It can also be proved easily that,
for all r > 0, and for all x ∈ B(0, ε0 /r), x + (rA)−kxk ⊂ rA.

(10)

Lemma 2. Let ℵn = {X1 , . . . , Xn } be iid random vectors in Rd , with common density
f . Assume that f has bounded support S and there exist 0 < f0 < f1 < ∞ such that
f0 ≤ f (x) ≤ f1 for all x ∈ S. Then, for all rf > 0 such that rfd > 2f1 /f0 we have,

∆(ℵn ) ≤ rf

log(n)
n

1/d
eventually almost surely.

Proof. First observe that S can be covered with N (S, n−1/d ) ≤ CS n balls of radius n−1/d
1/d

with rfd > 2f1 /f0 .
centered at some points {x1 , . . . , xνn } ⊂ S. Denote wn = rf log(n)
n
First observe that ∆(ℵn ) ≥ wn ⇔ ∃x ∈ S, such that x + wn f (x)−1/d A ⊂ S \ ℵn , then
−1/d
∆(ℵn ) ≥ wn ⇒ ∃x ∈ S, such that x+wn f1
A ⊂ S \ℵn . Applying (10), for sufficiently
large n (that is possible because n−1/d  wn ) we get
−1/d

∆(ℵn ) ≥ wn ⇒ ∃xi such that xi + (wn f1

1/d

A)−1/n

⊂ S \ ℵn .

(11)

Next notice that,


−1/d

P xi + wn f1

A

−1/n1/d



⊂ S \ ℵn =
≤
≤

1 − PX



−1/d −1/n1/d
wn f1
A

1 − f0
1−


−1/d −1/n1/d
xi + wn f1
A

f

0

f1

wnd

−

f0
d−1

!n

!n

wnd−1 n−1/d (1


+ o(1))

f1 d

The last inequality is obtained using (9). Since wn  n−1/d , we finally get
n

 
f0 d
−1/d −1/n1/d
P xi + wn f1
A
⊂ S \ ℵn ≤ 1 − wn (1 + o(1)) .
f1
From this inequality and (11) it follows that,


n
1/d 
f0
P ∆(ℵn ) ≥ rf log(n)n/n
≤ N (S, n−1/d ) 1 − wnd (1 + o(1))
f1
 f

0
≤ CS n exp − nwnd (1 + o(1)) ,
f1
and therefore,


d
P ∆(ℵn ) ≥ rf (log(n)/n)1/d ≤ CS n1−rf f0 /f1 +o(1) .
11

!n
.


P
Finally, since rfd > 2f1 /f0 we have
P ∆(ℵn ) ≥ rf (log(n)/n)1/d < ∞. Thus, the
Borel-Cantelli Lemma entails that ∆(ℵn ) ≤ rf (log(n)/n)1/d eventually almost surely.
Lemma 3. Let ℵn = {X1 , . . . , Xn } be iid random vectors in Rd with common distribution
distribution PX supported on a compact set S and density f continuous on S. Assume
that there exists f0 > 0 such that f (x) ≥ f0 ∀x ∈ S. Let Gn be a sequence of sets included
in S, with the following property: there exist C such that N (Gn , n−1/d ) ≤ Cn1−a (log(n))b
for some a > 0 and b > 0. Let A be a compact and convex set with |A| = 1 such that its
barycenter is the origin of Rd . Let us denote
n
o
r
∆(ℵn , Gn ) = sup r : ∃x ∈ Gn such that x +
A
⊂
S
\
ℵ
,
n
f (x)1/d
V (ℵn , Gn ) = ∆d (ℵn , Gn ),
U (ℵn , Gn ) = nV (ℵn , Gn ) − log(n) − (d − 1) log(log(n)) − log(αA ).

Then, P U (ℵn , Gn ) ≥ − log(log(n)) → 0.
Proof. Let us first cover Gn with νn = N (Gn , n−1/d ) balls of radius n−1/d , centred at
A ) 1/d
)
some points {x1 , . . . , xνn } belonging to S, and choose wn = ( log(n)+(d−2) log(log(n))+log(α
n
(observe that wn  (1/n)1/d ). As in the proof of Lemma 2 we have,
∆(ℵn ) ≥ wn ⇔ ∃x ∈ Gn , such that x + wn f (x)−1/d A ⊂ S \ ℵn .
which implies,
∆(ℵn ) ≥ wn ⇒ ∃xi ∃x ∈ B(xi , n−1/d ), such that xi + (wn f (x)−1/d A)−1/n

1/d

⊂ S \ ℵn .

Therefore,


P xi + (wn f (x)−1/d A)

−1/n1/d



⊂ S \ ℵn =

1 − PX



−(1/n1/d ) 
xi + wn f (x)−1/d A

!n
.

With rough bounds on the density,

−1/n1/d  mint∈S∩(xi +wn f1−1/d A) f (t) d
PX xi + wn f (x)−1/d A
≥
w (1 + o(1)).
maxt∈S∩B(xi ,n−1/d ) f (t) n
Since f is uniformly continuous on S, A is bounded, wn → 0 and n−1/d → 0, for all
c < 1 there exist nc such that for all n ≥ nc

 
n
1/d
P xi + (wn f (x)−1/d A)−1/n ⊂ S \ ℵn ≤ 1 − cwnd (1 + o(1)) ,
then,

P ∆(ℵn , Gn ) ≥ wn ≤ Cn1−a (log n)b (1 − cwnd (1 + o(1)))n .
12

Taking c = 1 − a/2, we finally get that

−1+a/2 −a/2
P U (ℵn , Gn ) ≥ − log(log(n)) ≤ CαA
n
(log(n))b−(1−a/2)(d−2) (1 + o(1)) → 0.

The next lemma relates the behaviour of the maximal-spacing for two different densities having the same support.
Lemma 4. Let us consider f and h, two densities with compact support S such that,
h(x) > h0 for all x ∈ S and maxx∈S |f (x) − h(x)| ≤ εh0 for a given ε ∈ (0, 1/2). Denote
by n0 = bn(1 − 2ε)c and n1 = dn(1 + 2ε)e the floor and ceiling of n(1 − 2ε) and n(1 + 2ε)
−1 )
respectively. For any w ∈ R, let us define wn,0 = w(1−2ε−n
and wn,1 = w(1−ε)
1+2ε . Then,
(1+ε)
P n0 V (Yn0 ) ≤ wn,0
and



1−


1 − ε
≤ P nV (ℵn ) ≤ w ,
nε



1 + 2ε + n−1 −1
,
P nV (ℵn ) ≤ w ≤ P n1 V (Yn1 ) ≤ wn,1 1 −
(nε + 1)(1 + ε)

(12)

(13)

where Yn0 = {Y1 , . . . , Yn0 } and Yn1 = {Y1 , . . . , Yn1 } are iid random vectors on Rd , with
density h, and ℵn = {X1 , . . . , Xn } are iid random vectors with density f .
Proof. We first prove (12). Observe that X can be generated from the following mixture:
with probability p = 1 − ε, X is drawn with density h, and, with probability 1 − p, X
IS (x). Let us denote
is drawn with the law given by the density g(x) = f (x)−h(x)(1−ε)
ε
∗
by N0 the number of points drawn according to h on S and ℵN0 = {Y1 , . . . , YN0 } the
associated sample. Let us recall that
o
n
r
A
⊂
S
\
ℵ
.
∆(ℵn ) = sup r : ∃x such that x +
n
f (x)1/d
Observe that
sup h0 |f (x)/h(x) − 1| ≤ sup h(x)|f (x)/h(x) − 1| ≤ h0 ε,
x

x

so f (x)/h(x) ≤ 1 + ε. Then we have,
n
∆(ℵn ) ≤ (1 + ε)1/d sup r : ∃x such that x +
From the inclusion ℵ∗N0 ⊂ ℵn we get
n
1/d
∆(ℵn ) ≤ (1 + ε) sup r : ∃x such that x +

o
r
A
⊂
S
\
ℵ
.
n
h(x)1/d

o
r
∗
A ⊂ S \ ℵ N0 ,
h(x)1/d

and therefore ∆(ℵn ) ≤ (1 + ε)1/d ∆(ℵ∗N0 ), which entails that V (ℵn ) ≤ (1 + ε)V (ℵ∗N0 ).
Then, for all w > 0,


P nV (ℵn ) ≤ w ≥ P (1 + ε)nV (ℵ∗N0 ) ≤ w ,
13

and





P nV (ℵn ) ≤ w ≥ P (1 + ε)nV (ℵ∗N0 ) ≤ w ∩ N0 ≥ n0 .

For N0 ≥ n0 , let us denote by Yn0 = {Y1 , . . . , Yn0 } the n0 first values of ℵ∗N0 . Clearly
we have V (ℵ∗N0 ) ≤ V (Yn0 ) so,



PN0 ≥n0 (1 + ε)nV (ℵ∗N0 ) ≤ w ≥ P (1 + ε)nV (Yn0 ) ≤ w ,
where PN0 ≥n0 denotes the conditional probability given N0 ≥ n0 . Therefore,


wn0 
P nV (ℵn ) ≤ w ≥ P n0 V (Yn0 ) ≤
P(N0 ≥ n0 ).
(1 + ε)n
On the other hand, since N0 ∼ Bin(n, 1 − ε), we obtain,


P(N0 < n0 ) = P N0 − (1 − ε)n < n0 − (1 − ε)n ≤ P(N0 − (1 − ε)n ≤ −εn).
Since n0 = bn(1 − 2ε)c, n0 − n(1 − ε) ≤ −εn, which together with Chebyshev’s inequality
entails that
nε(1 − ε)
(1 − ε)
=
,
P(N0 < n0 ) ≤
2
2
n ε
nε
and then,
(1 − ε)
P(N0 ≥ n0 ) ≥ 1 −
.
nε
−1 )

Let us denote by wn,0 = w(1−2ε−n
(1+ε)
from where it follows that


. Since n(1 − 2ε) − 1 ≤ n0 we have wn,0 ≤


P nV (ℵn ) ≤ w ≥ P n0 V (Yn0 ) ≤ wn,0



1−ε
1−
nε

wn0
(1+ε)n ,


.

Equation (13) is proved in the same way. We just provide a sketch of the proof. The
key point for the proof of (12) was to think the law of a random variable Y drawn with the
1
density h as the following mixture: with probability p = 1+ε
, Y as a random variable with
(x)
density f , and, with probability 1−p, Y is drawn with density g(x) = h(x)(1+ε)−f
IS (x).
ε
Next, we consider a sample Yn1 = {Y1 , . . . , Yn1 } of iid copies of Y , (that follows a law
given by h). Denote by N the number of the points that drawn according to the density
f and Y∗N = {X1 , . . . XN } these points. The rest of the proof follows using the same
argument to prove (12).

4.2

Uniform mixture on disjoint supports

Proposition 1. Let E1 , . . . , Ek be subsets of Rd such that for all i 6= j ⇒ Ei ∩ Ej = ∅,
and 0 < |Ei | < ∞ for all i. Let ℵn = {X1 , . . . , Xn } be iid random vectors in S = ∪i Ei
with density
k
X
f (x) =
pi IEi (x),
i=1

14

where p1 , . . . , pk are positive real numbers. Then,
L

U (ℵn ) −→ U

when n → ∞.

Proof. First let us introduce some notation, for i = 1, . . . , k
• Ni = #{ℵn ∩ Ei } denotes the number of data points in Ei . Notice that Ni ∼
Bin(n, pi |Ei |).
• ℵiNi = {Xi1 , . . . , XiNi } denotes the subsample of ℵn that falls in Ei . Observe that
they all are uniformly distributed.
P
• ai = P
pi |Ei | for i = 1, . . . , k, that fulfils
ai = 1, a0 = mini ai , A0 = maxi ai and
1−ai
C=
.
ai
• εn,i =

Ni −ai n
nai .

Since the support of f is ∪i Ei , and by assumption i 6= j ⇒ Ei ∩ Ej = ∅, we have
n
o
r
∆(ℵn ) = sup r : ∃x∃i such that x + 1/d A ⊂ Ei \ ℵn ,
pi
so

while

o
n
r|Ei |1/d
i
∆(ℵn ) = max sup r : ∃x such that x +
A
⊂
E
\
ℵ
i
Ni ,
i
(|Ei |pi )1/d

(14)

o
n
∆(ℵiNi ) = sup r0 : ∃x ∈ Ei such that x + r0 |Ei |1/d A ⊂ Ei \ ℵiNi .

(15)

From (14) and (15) we derive that
n
o
n
o
∆(ℵn ) = max (|Ei |pi )1/d ∆(ℵiNi ) and V (ℵn ) = max |Ei |pi V (ℵiNi ) ,
i

i

which entails that

Y 
wNi
i
P(nV (ℵn ) ≤ w) =
P Ni V (ℵNi ) ≤
.
ai n
i

−
→

Let P n (A) = P(A|N1 = n1 , . . . , Nk = nk ) stand for the conditional probability given the
number of points that fall in each Ei . We have that,
P

−
→
n



nV (ℵn ) ≤ w =

k
Y

P

−
→
n

n|Ei |pi V

(ℵini )



≤w =

i=1

Now, taking wn,i =

exp

−

k
X

wni
n|Ei |pi ,

k
Y


P
ni V (ℵini ) ≤
−
→
n

i=1

γn,i =


i
γn,i aE
+ |Ei |

d−1 −wn,i
ni wn,i
e
|Ei |

−
→
n

≤P

and applying Lemma 1 we obtain,


nV (ℵn ) ≤ w ≤ exp

i=1


−

k
X
i=1

15

wni
n|Ei |pi


.

i
γn,i aE
− |Ei |


.

On the other hand,
k
X

i
γn,i aE
+ |Ei |

=

i=1

=

k
X
i=1
k
X


ni

wni
n|Ei |pi

d−1



wni
i
aE
exp −
+
n|Ei |pi

i
ni wd−1 (1 + εi )d−1 exp(−w(1 + εi ))aE
+ (wn,i , ni ).

i=1
E

Let εn = maxi |εn,i | and εa+ = maxi
k
X

|a+i (wn,i ,ni )−αA |
,
αA

then we have

d−1
i
γn,i aE
exp(−w)αA (1 + εn )d−1 exp(wε)(1 + εa+ ).
+ |Ei | ≤ nw

i=1

Taking w = wn = x + log(n) + (d − 1) log(log(n)) + log(αA ), we obtain that nV ≤ w ⇔
U ≤ x, which implies that



−
→
P n U (ℵn ) ≤ x ≥ exp −e−x (1 + ε)d−1 exp(log(n)εn )(1 + εa+ )(1 + on (1)) .
In the same way it can be proved,



−
→
P n U (ℵn ) ≤ x ≤ exp −e−x (1 − εn )d−1 exp(− log(n)εn )(1 − εa− )(1 + on (1)) .
Ei
(wn,i ,ni )−α

|a

|

A
where we denoted εa− = maxi −
.
αA
2
Suppose that εn = max |εn,i | ≤ 1/ log(n) , then, if n ≥ 5, a0 n/2 ≤ Ni ≤ n for all
i, which imply that for all i,wn,i ≥ log(n)a0 /(2A0 ) → ∞ and wn,i /n ≤ x + log(n) +
(d − 1) log(log(n)) + log(αA ) /(na0 ) → 0. Then εa− and εa+ converges to 0, according
to Lemma 4. Therefore

2
Pεn ≤1/ log(n) U (ℵn ) ≤ x → exp(− exp(−x)) when n → ∞.
(16)

Since

P max |εn,i | ≥
i

k

[
1  X 
1 
1 
=
P
|ε
|
≥
≤
P
|ε
|
≥
,
n,i
n,i
log(n)2
log(n)2
log(n)2
i

i=1

from Chebyshev’s inequality we obtain

1 
P |εn,i | ≥
≤ log(n)4 V(ε2n,i )
log(n)2
and therefore

where

V(ε2n,i ) =

4
log(n)
1 
≤C
.
P εn ≥
log(n)2
n


Finally, from equations (16) and (17) we get,

P U (ℵn ) ≤ x → exp(− exp(−x)) when n → ∞,
which concludes the proof.
16

1 − ai
,
nai

(17)

4.3

Uniform mixture

Proposition 2. Let E1 , . . . , Ek be subsets of Rd such that,
1) i 6= j ⇒ |Ei ∩ Ej | = 0.
2) 0 < |Ei | < ∞ for i = 1, . . . , k.
3) There exists a constant C > 0 such that, for all i, for all ε > 0, N (∂Ei , ε) ≤
Cε−d+1 .
Let ℵn = {X1 , . . . , Xn } be iid random vectors with density
f (x) =

k
X

pi IE̊i ,

i=1

where p1 , . . . , pk are positive real numbers. If there exist constants r0 > 0 and c > 1−1/d
such that, for all r ≤ r0 and all x ∈ ∪i E̊i ,
mint∈S∩B(x,r) f (t)
≥ c,
maxt∈S∩B(x,r) f (t)
then,
L

U (ℵn ) −→ U

when

n → ∞.

Proof. We start by introducing some definitions and notation.
n
o
r
˚ n ) = sup r : ∃x∃i, such that x +
∆(ℵ
A
⊂
E̊
\
ℵ
,
i
n
f (x)1/d
˚ d (ℵn ),
V̊ (ℵn ) = ∆

Ů (ℵn ) = nV̊ (ℵn ) − log(n) − (d − 1) log log(n) − log(αA )
With the same ideas used to prove Proposition 1 (and the fact that |Ei | = |E̊i |) it
 L



follows that Ů ℵn −→ U . Let Fn (x) = P Ů ℵn ≤ x . Clearly U (ℵn ) ≥ Ů ℵn , and
therefore

P U (ℵn ) ≤ x ≤ Fn (x) → exp(− exp(−x)).
(18)
In order to prove the other inequality let us define

S
• G = i,j Ei ∩ Ej .
• p0 = mini pi .
• ρA = maxx∈A kxk.
1/d
1/d
1/d
with rf such that ∆(ℵn ) ≤ rf log(n)/n
even• ρn = (rf ρA /p0 ) log(n)/n
tually almost surely (whose existence follows from Lemma 2). Notice that condition
3) ensures that N (Gρn , n−1/d ) = O(n1−1/d (log(n))1/d ).
17

o
r
A
⊂
S
\
ℵ
.
n
f (x)1/d
o
r
such that x +
A
⊂
S
\
ℵ
n .
f (x)1/d

n

• ∆ ℵn , S \ Gρn = sup r : ∃x ∈ S \ Gρn such that x +
n

• ∆ ℵn , Gρn = sup r : ∃x ∈ Gρn
Clearly we have that,

n

o
∆(ℵn ) = max ∆ ℵn , S \ Gρn , ∆ ℵn , Gρn .

(19)

For the chosen ρn , we are going to prove that,


˚ ℵn ≥ ∆ ℵn , S \ Gρn eventually almost surely.
∆
(20)

Let us suppose first that ∆ ℵn , S \ Gρn ≤ rf (log(n)/n)1/d (which holds, e.a.s., due to
Lemma 2) then

∆ ℵn , S \ Gρn − ε
ρn
for all ε > 0 there exists xε ∈ S \ G such that xε +
A ⊂ S \ ℵn ,
f (xε )1/d
and



∆ ℵ n , S \ Gρ n − ε
rf (log(n)/n)1/d − ε
xε +
A ⊂ B xε , ρA
⊂ B(xε , ρn ).
1/d
f (xε )1/d
p
0



S
∆ ℵn ,S\Gρn −ε
A ⊂ i E̊i \ ℵn . Then, for all ε > 0,
From d(xε , G) ≥ ρn we get xε +
f (xε )1/d


˚ ℵn ≥ ∆ ℵn , S \ Gρn − ε e.a.s., which concludes the proof of (20).
∆
By (19), introducing U (ℵn , Gρn ) = n∆(ℵn , Gρn )d − log(n) − (d − 1) log(log(n)) −
log(αA ), one can bound P(U (ℵn ) ≥ x) for all x, as follows:

P(U (ℵn ) ≥ x) ≤ P(Ů (ℵn ) ≥ x) + P(U (ℵn , Gρn ) ≥ − log(log(n))) if x ≥ − log(log(n))
P(U (ℵn ) ≥ x) ≤ 1
if x ≤ − log(log(n))
By Lemma 3 we obtain:

P(U (ℵn ) ≤ x) ≥ Fn (x) + o(1)
P(U (ℵn ) ≤ x) ≥ 0

if x ≥ − log(log(n))
(21)
if x ≤ − log(log(n)).

Finally using (18), (21) and that P U ≤ − log(log(n)) = 1/n → 0 we conclude the
proof.

Proof of Theorem 2
1

Let cn = (log(n)/n) 3d . Take a “mesh” of Rd with small squares of side cn ,
d h
i
Y
ki cn , (ki + 1)cn
i=1

18

with ki ∈ N,

and denote by mn ≤ |S|c−d
n the number of these squares {C1 , . . . , Cmn } that are included
in S.
Like in the proof of Proposition 2 let us denote,
n
o
r
˚ n ) = sup r : ∃x∃i, such that x +
∆(ℵ
A
⊂
C̊
\
ℵ
,
i
n
f (x)1/d
˚ d (ℵn ),
V̊ (ℵn ) = ∆

Ů (ℵn ) = nV̊ (ℵn ) − log(n) − (d − 1) log log(n) − log(αA ).



S n
From the inclusion m
C̊
⊂
S
it
follows
that,
P
U
(ℵ
)
≤
x
≤
P
Ů
(ℵ
)
≤
x
.
i
n
n
i=1
Like in the proof of Proposition 1 let us denote, for i = 1, . . . , mn .
• Ni = #{ℵn ∩ Ci },
R
P 1−ai
• ai = Ci f (t)dt; a0 = mini ai ; A0 = maxi ai and C =
ai . Observe that
P
d
ai = 1 and a0 ≥ f0 cn .
• ℵiNi = {Xi1 , . . . , XiNi }, the subsample of ℵn that belongs to Ci . Observe that Xij

for j = 1, . . . , Ni has density fi (x) = f (x)/ai ICi (x).
• εn,i =

Ni −ai n
nai ,

εn = maxi εi .

We start with some asymptotic properties about εn,i and εn . If we bound |ai | ≥ f0 |cn |d
and apply Hoeffding’s inequality we get


P(log(n)|εn,i | ≥ t) ≤ 2 exp − 2t2 f02 (log(n))−4/3 n1/3 ,
and,
P(log(n)|εn | ≥ t) ≤



2|S|n1/3
2 2
−4/3 1/3
.
exp
−
2t
f
(log(n))
n
0
(log n)1/3
a.s.

Borel-Cantelli Lemma entails (log(n))εn → 0. Then, with probability 1, for n large
enough,
f0
(log n)1/3 n2/3 ≤ Ni ≤ 2f1 (log n)1/3 n2/3 for i = 1, . . . , mn .
2
In what follows n is large enough so that (22) is fulfilled.
Proceeding exactly as in the proof of Proposition 1 we can derive that
n
˚ n ) = max sup r : ∃x such that x +
∆(ℵ
i

1/d

o
rai
i
A
⊂
C̊
\
ℵ
i
Ni ,
(ai fi (x))1/d

and therefore
n
o
˚ n ) = max a1/d ∆(ℵiN )
∆(ℵ
i
i
i

and

19

n
o
V (ℵn ) = max ai V (ℵiNi ) .
i

(22)

First we to bound P(Un (ℵn ) ≥ x) from above. As in Proposition 1

mn 

 Y
wn Ni
d
P nV (ℵn ) ≤ wn ≤ P nV̊ (ℵn ) ≤ wn =
P Ni ∆ (ℵNi ) ≤
.
ai n

(23)

i=1

At any of the small squares Ci , by Hölder continuity, the density is close to the
uniform density, that will allow us to apply Lemma 4 with h = 1/|Ci |ICi . More precisely:
for all i an for all y ∈ Ci ,
Z
Z
Z
1
f (y)
1
|Ci | − 1 =
fi (y)|Ci | − 1 =
f (y)dt −
f (t)dt ≤ Kf
|y − t|β dt.
ai
ai Ci
ai
Ci
Ci
√
Since |y − t| ≤ dcn , if we denote Af = Kf f0−1 dβ/2 we derive that
fi (y)|Ci | − 1 ≤

√ β
1
Kf d cd+β
≤ Af cβn
n
ai

Let Ni0 = dNi (1 + 2Af cβn )e, wn0 = wn

1−Af cβ
n
1+2Af cβ
n

∀y ∈ Ci .

and YNi0 a sample of Ni0 variables

uniformly drawn on Ci , then Lemma 4 implies that
!−1




1 + 2Af cβn + Ni−1
wn0 Ni0
wn Ni
0 d
d
≤ P Ni ∆ (YNi0 ) ≤
1−
.
P Ni ∆ (ℵNi ) ≤
ai n
ai n
(Ni Af cβn )(1 + Af cβn )
(24)
On the other hand, by (22), with probability one, for n large enough we have that,
!−1 
−1
1 + 2Af cβn + Ni−1
2
1
≤ 1−
1−
for all i,
f0 Af (log n)1/3+β/3d n2/3−β/3d (1 + o(1))
(Ni Af cβn )(1 + Af cβn )
(25)
and,
!−1 
−1
1 + 2Af cβn + Ni−1
1
1 + o(1)
1−
≥ 1−
for all i.
2f1 Af (log n)1/3+β/3d n2/3−β/3d
(Ni Af cβn )(1 + Af cβn )
(26)
Let us prove that,
!−1
mn
Y
1 + 2Af cβn + Ni−1
a.s.
1−
→ 1.
(27)
β
β
(Ni Af cn )(1 + Af cn )
i=1
Since the right hand side of (25) can be express, for n large enough, as


exp − C(log n)1/3+β/3d n2/3−β/3d (1 + o(1)) ,
being C a positive constant, we get, for n large enough,
!−1
mn


Y
1 + 2Af cβn + Ni−1
1/3+β/3d 2/3−β/3d
1−
≤
exp
−Cm
(log
n)
n
(1+o(1))
→ 1,
n
(Ni Af cβn )(1 + Af cβn )
i=1
20

where the limit follows from mn (log n)−1/3−β/3d n−2/3+β/3d ≤ (log n)−β/3d n−1/3+β/3d →
0. (27) is obtained doing the same with (26).

0 N0
Q n  0 d
wn
i
0
P
N
∆
(Y
)
≤
Now let us study the asymptotic behaviour of m
. If we
Ni
i
i=1
ai n
apply Lemma 1, (observe that the functions aS− only depends on the shape of S) we get,

 0 0 d−1

 0 0

!
mn
mn 
0 N0
0ω0
X
Y
d
N
ω
N
ω
w
N
[0,1]
i n
i n
Ni0
P Ni0 ∆d (YNi0 ) ≤ n i ≤ exp −
exp − i n a−
, Ni0
.
ai n
ai n
ai n
ai n
i=1

i=1

Let, ε0n,i =

0
Ni wn
ai n wn

0

n
− 1 for i = 1, . . . , mn . Observe that ε0n,i = (1 + εn,i ) w
wn − 1 =

a.s.
1−Af cβ
n
− 1 and ε0n = maxi |ε0n,i |. Since (log(n))εn → 0, ε0n fulfils
1+2Af cβ
n
all i, Ni0 ≥ Ni . The previous equation together with (23) entails,

(1 + εn,i )
and for

a.s.

log(n)ε0n → 0


 [0,1]d

P(nV (ℵn ) ≤ wn ) ≤ exp −nωnd−1 (1−ε0n )d−1 exp −wn (1+ε0n ) a− (min wn (1−ε0n ), min Ni ) .
i

(28)
If we choose wn = x + n log(n) + (d − 1) log(log(n)) + log(αA ) in (28) we get,
P(U (ℵn ) ≤ x) ≤ exp(− exp(−x)) + o(1).

(29)

In order to conclude the proof of (2) we have to bound P(U (ℵn ) ≤ x) from below. We
provide just a sketch of the proof since the arguments are similar to those in Proposition
2, using Lemma 4 as in the proof of (29). Let us denote,
• ρn =

rf ρA log(n) 1/d
1/d
n
f

with ρA = maxx∈A kxk.

0

n
• Gn = ∪m
i6=j (Ci ∩ Cj ).

cn
n
• Hn = S \ (∪m
i Ci ), notice that Hn ⊂ ∂S .

Proceeding as in Proposition 2 we have
n
o

U (ℵn ) ≤ max Ů ℵn , U (ℵn , Gρnn ), U (ℵn , Hn ) eventually almost surely,
and
P(Ů (ℵn ) ≤ x) ≥ exp(− exp(−x)) + o(1).
Then, reasoning as in Proposition 2 we get
P(U (ℵn ) ≤ x) ≥ exp(− exp(−x)) + o(1).
Finally, in order to conclude the proof of (2) it suffices to prove that Gρnn and Hn satisfies
the hypothesis of Lemma 3.
Gn is the union of less than mn 2d (d − 1)−dimensional cubes of size cn . Each
−d+1 balls of radius ρ (with a a positive
of them can be cover by less than a1 cd−1
n
1
n ρn
21

S
constant), centered at some points {xij }i,j . Since Gρnn ⊂ i,j B(xij , 2ρn ), and every
B(xij , 2ρn ) can be covered by a2 ρdn n balls of radius n−1/d , Gρnn can be covered by less
2

2

−d+1 a ρd n = O(n1− 3d (log n) 3d ) balls of radius n−1/d .
than νn = mn a1 cd−1
2 n
n ρn
d+κ
d+κ
In the same way it can be proved that Hn can be covered with O(n1− 3d log(n) 3d )
balls of radius n−1/d . Indeed, cover ∂S with O(c−κ
n ) balls of radius cn , apply triangular inequality
to
obtain
that
the
union
of
the
balls
with the same centre but with a
√
√
dc
n
radius cn d covers ∂S
and then covers Hn , finally cover every of these balls by
O((cn n1/d )−d ) balls of radius n−1/d .

Proof of (3)
In Equation (28), let
√ us choose wn = log(n) + c log(log(n)) with c < (d − 1) and introduce Nk = dexp( k)e, like in equation (3.12) in [12], we obtain for k large enough,
d−1−c
P(Nk V (ℵNk ) ≤ wNk ) ≤ exp(−αA k 2 /2) and, Borel-Cantelli Lemma implies that,
with probability one, for k large enough Nk V (ℵNk ) ≤ wNk . The rest of the proof is
exactly the same as in Lemma 5 in [12]
Proof of (4):
For any u > 0 let us introduce the sequence rn =
1
log(n) log(log(n)) .



log n+(d+1+u) log(log(n))
n

1/d

and εn =

−d
Cover S with νn ≤ CS ε−d
n rn balls of radius εn rn . Reasoning like in [12]

we get



n
nV (ℵn ) − log(n)
P
≥ d + 1 + u = P(∆n ≥ rn ) ≤ νn 1 − rnd (1 − εn )d (1 − 2Kf rn diam(A)) ,
log(log(n))
that implies,

nV (ℵn ) − log(n)
(log(log(n)))d
P
≥ d + 1 + u ≤ CS
.
log(log(n))
(log(n))2+u+o(1)
√
From Borel-Cantelli Lemma, taking Nk = dexp( k)e it follows that, with probability


Nk V (ℵNk )−log(Nk )
≤ d + 1 + u. Now
log(log(Nk ))
Nk V (ℵNk )−log(Nk )
≤ d + 1 + u. We have,
log(log(Nk ))

one, for k large enough
and suppose that

Nk+1
nV (ℵn ) ≤
V (ℵNk ) ≤ exp
Nk



take n ≥ Nk and n ≤ Nk+1


1
√ (1 + o(1)) (log(Nk ) + (d + 1 + u) log(log(Nk ))),
2 k

that entails,

nV (ℵn ) ≤ 1 +


1
(1 + o(1))) (log(n) + (d + 1 + u) log(log(n))).
2 log(n)

Finally for n large enough,
nV (ℵn ) ≤ log(n) + (d + 1 + u) log(log(n)) + 1,
22

so that

nV (ℵn ) − log(n)
1
≤d+1+u+
,
log(log(n))
log(log n)

which concludes the proof of (4).

5

Appendix B

5.1

Proof of Theorem 3

The proof make use of the following two propositions. The first one gives conditions
under which the maximal-spacing of two compact sets are close. The second one shows
that if the set S is not convex, then R(H(S) \ S) > 0.
Proposition 3. Let A and B be bounded and non-empty subsets of Rd . If dH (A, B) ≤ ε
and dH (∂A, ∂B) ≤ ε. Then R(A) − R(B) ≤ 2ε.

Proof. First we introduce A0 = x ∈ A : d(x, ∂A) > 2ε and prove that A0 ⊂ B by
contradiction. Suppose that there exists x ∈ A such that d(x, ∂A) > 2ε and x ∈
/ B.
Since dH (A, B) ≤ ε we have A ⊂ B ε , then x ∈ B ε \ B, so d(x, ∂B) ≤ ε. Now, as
dH (∂A, ∂B) ≤ ε, by the triangular inequality, d(x, ∂A) ≤ 2ε. which is a contradiction.
From A0 ⊂ B it follows that R(A0 ) ≤ R(B). Now for all r < R(A) there exist x ∈ A
such that B(x, r) ⊂ A so that B(x, r − 2ε) ⊂ A0 which entails R(A0 ) ≥ R(A) − 2ε and,
finally, R(B) ≥ R(A) − 2ε. Proceeding in the same way, we get R(A) ≥ R(B) − 2ε that
conclude the proof.
d
Proposition
 4. Let S ⊂ R be a non–convex, closed set with non-empty interior. Then,
R H(S) \ S > 0.

Proof. Since S is closed and non-convex there exists x ∈ H(S) \ S with d(x, S) = r > 0.
˚ so that, for all ε > 0, there exists
By Corollary 7.1 in [10] we know that H(S) = H(S)

xε and νε > 0 such that |xε − x| ≤ ε and B(xε , νε ) ⊂ H(S). Taking ε = r/2 and
ρ = min(νr/2 , r/2) > 0 we conclude that R H(S) \ S ≥ ρ > 0.
Now we can prove Theorem 3.


First observe that, if S is convex R H(ℵn ) \ ℵn ≤ R S \ ℵn and |H(ℵn )| ≤ |S| so

that V˜n ≤ V (ℵn ). Then, from Corollary 1 we obtain that P V˜n > cn,γ ≤ γ + o(1), and
the test is asymptotically of level smaller than γ.

Now we prove that if S ∈ CP , then PH0 Ṽn > cn,γ → γ. Recall that, if S ⊂ Rd is
convex and ℵn = {X1 , . . . , Xn } is an iid random sample, uniformly drawn on S ∈ CP , in

23

[9] it is proved that, almost surely:



2/(d+1) 

2/(d+1) 
dH H(ℵn ), S = O log(n)/n
and dH ∂H(ℵn ), ∂S = O log(n)/n
.
(30)



2/(d+1) 
Thus, by Proposition 3, we have that R H(ℵn )\ℵn −R S\ℵn = O log(n)/n
almost surely. Therefore

1/d 
2/(d+1) 
˜ n (ℵn ) = |H(ℵn )|
∆
∆(ℵ
)
+
O
log(n)/n
a.s.
n
|S|1/d

2/(d+1) 
The second equation in (30) also provides that |H(ℵn )| = |S|+O log(n)/n
almost surely. Finally we have,



2/(d+1) 
1+O
Ṽn = V (ℵn ) 1 + O log(n)/n

2/(d+1) !!d
log(n)/n
a.s.
∆(ℵn )

Observe that from Corollary 1 ii) and iii) ∆(ℵn ) = (log(n)/n)1/d (1 + o(1)) almost
surely, then

1+ d−1 
d(d+1)
a.s.
Ṽn = V (ℵn ) + O log(n)/n
This, together with cn,γ = O(log(n)/n) entails that P(Ṽn ≥ cn,γ ) → γ, as desired.
To conclude the proof of the theorem consider now that S is not convex. First we
prove that, if εn = dH (S, ℵn ), then dH (H(S), H(ℵn )) ≤ 2εn . Indeed, for all x ∈ H(S)
there exist x1 ∈ S, x2 ∈ S and λ ∈ [0, 1] such that x = λx1 + (1 − λ)x2 . Since εn =
dH (S, ℵn ) there exist Xi ∈ ℵn and Xj ∈ ℵn such that kx1 −Xi k ≤ εn and kx2 −Xj k ≤ εn
so that y = λXi +(1−λ)Xj belongs to H(ℵn ). By the triangular inequality kx−yk ≤ 2εn .
Since H(ℵn ) ⊂ H(S) we also have that dH (∂H(S), ∂H(ℵn )) ≤ 2εn , which implies that
kH(ℵn )|−|H(S)k ≤ O(εn ). On the other hand we have dH (H(S)\ℵn , H(ℵn )\ℵn ) ≤ 2εn
and dH (∂(H(S) \ ℵn ), ∂(H(ℵn ) \ ℵn )) ≤ 2εn . By Proposition 3 we get, R(H(ℵn ) \ ℵn ) ≥
R(H(S) \ ℵn ) − 2εn . Since H(S) \ S ⊂ H(S) \ ℵn it follows,
R(H(ℵn ) \ ℵn ) ≥ R(H(S) \ S) − 2εn .
a.s.

(31)

Since εn → 0 almost surely, |H(ℵn )| → |H(S)| and R(H(ℵn ) \ ℵn ) ≥ R(H(S) \ S)
eventually almost surely. Then, there exists CS a positive constant that depends on S
such that, Ṽn ≥ CS eventually almost surely. Finally, since cn,γ → 0 we conclude the
proof.

5.2

Proof of Theorem 4

The proof of Theorem 4 is based on the following lemma
24

Lemma 5. Assume that the unknown density f fulfils condition B and S ∈ A. Take
K ∈ K, and hn = O(n−β ) with β ∈ (0, 1/d).
Let fˆn (x) be the density estimator introduced in Definition 3. Then,
+
(i) there exists a sequence ε+
n such that log(n)εn → 0 and for all x ∈ S,

1−

ε+
n



f (x)
fˆn (x)

1/d

≥

e.a.s.

(ii) there exist a sequence ε−
n → 0 and a constant λ0 > 0 such that for all x ∈ H(ℵn ),
(fˆn (x))1/d ≥ λ0 − ε−
.
e.a.s.
n
Proof. We start the proof by establishing some useful preliminary results. First notice
that, for S ∈ A, with exactly the same kind of calculation we did to prove Lemma 2,

1/d
n
choosing ρn = f04clog
we have,
S ωd n
P(dH (ℵn , S) ≥ ρn ) ≤ CS n−2

for n large enough.

(32)

Notice that, since K ∈ K, S ∈ A, and K is bounded from below on a neighbourhood of
the origin, there exist c00K > 0 and rK > 0 such that,
Z
0
K((u − x)/r)du ≥ c00K rd for all x ∈ S and r ≤ rK
.
(33)
S

We have, for all x ∈ S,
Z
Efn (x) =

K(u)f (x + uhn )du.
{u:x+uhn ∈S}

Using that f is Lipschitz and
Z
Efn (x) ≤

R

Rd

K(u)du = 1, we get, for all x ∈ S

K(u) f (x) + kf kukhn du ≤ f (x) + kf hn cK .

(34)

{u:x+uhn ∈S}

From (33) and the condition f (x) > f0 for all x ∈ S, it follows that,
Efn (x) ≥ f0 c0K

for all x ∈ S.

We start by proving (i). The triangular inequality entails that,


max fˆn (x) − f (x) ≤ sup fˆn (x) − Efˆn (x) + sup Efˆn (x) − f (x) .
x∈S

(35)

(36)

x∈S

x∈S

In order to deal with the first term on the right hand side of (36), observe that, since
K ∈ K and hn = O(n−β ) with β ∈ (0, 1/d) we can apply Theorem 2.3 in [11]. Then,
there exists a constant C1 such that, with probability one, for n large enough,
s
nhdn
sup fn (x) − Efn (x) ≤ C1 .
− log(hn ) x∈Rd
25

Thus

s

nhdn
sup fn (x) − Efn (x) ≤ C1 ,
− log(hn ) x∈ℵn

and therefore,
s

nhdn
sup fˆn (x) − Efˆn (x) ≤ C1 .
− log(hn ) x∈S

(37)

Now let us bound supx∈S (Efˆn (x) − f (x)) from above. For all x ∈ S we have,
E(fˆn (x)) = E(fˆn (x)|dH (ℵn , S) ≤ ρn )P(dH (ℵn , S) ≤ ρn )+
E(fˆn (x)|dH (ℵn , S) > ρn )P(dH (ℵn , S) > ρn ). (38)
Since {(x, y) ∈ S 2 , kx − yk ≤ hn } is compact, the Lebesgue dominate convergence
theorem entails that there exist y0 ∈ S such that kx − y0 k ≤ ρn , and a sequence yk with
yk → y0 , kyk − y0 k ≤ ρn , such that for n large enough, with probability one

E(fˆn (x)|dH (S, ℵn ) ≤ ρn ) ≤ sup E
x∈S

lim sup


fn (y) =

y∈S:kx−yk≤ρn



sup E lim fn (yk ) = sup lim (E(fn (yk ))) ≤ sup
x∈S

yk →y0

x∈S yk →y0

sup

E(fn (y)).

x∈S y∈S:kx−yk≤ρn

Now applying (34) and the Lipschitz continuity of f we obtain,
E(fˆn (x)|dH (S, ℵn ) ≤ ρn ) ≤

max
y∈S,kx−yk≤ρn

{f (y) + kf hn cK } ≤ f (x) + kf ρn + kf hn cK .
(39)

With the same kind of argument it can be proved that,
E(fˆn (x)|dH (ℵn , S) ≥ ρn ) ≤ sup Efn (y) ≤ f1 + kf hn cK .

(40)

y∈S

From equations (38),(39),(40) and (32) we get,
sup(E(fˆn (x)) − f (x)) ≤ kf ρn + kf hn cK + (f1 + kf hn cK )CS n−2 .

(41)

x∈S


1/2
nhdn
Take now εn = kf ρn + kf hn cK + (f1 + kf hn cK )CS n−2 + C1 − log(h
. Which
n)
fulfils log(n)εn → 0. From equations (36), (37), (41), we obtain that, with probability
one, for n large enough,

max fˆn (x) − f (x) ≤ εn .
x∈S

Then, for all x ∈ S, fˆn (x) − f (x) ≤ f (x)εn /f0 , and thus,
lently,
!1/d 

εn −1/d
f (x)
≥ 1+
.
f0
fˆn (x)
26

fˆn (x)
f (x)

≤ 1+

εn
f0 ,

or equiva-

Finally, taking ε+
= (1 − (1 + εn /f0 )−1/d ) ∼ εn /(df0 ) (observe that we have ε+
n log(n) →
n
1/d
0) then maxx∈S ˆf (x)
≥ 1 − ε+
n eventually almost surely, which concludes the proof
fn (x)

of (i).
In order to prove (ii), observe that
min fˆn (x) ≥ min Efˆn (x) − max Efˆn (x) − fˆn (x) .

x∈Rd

x∈Rd

x∈Rd

Since we have already proved that maxx∈Rd Efˆn (x)− fˆn (x) → 0 a.s., it remains to prove
that minx∈Rd Efˆn (x) is bounded from below by a positive constant. From minx∈Rd Efˆn (x) =
minx∈ℵn Efn (x) and (35), we get
min Efˆn (x) ≥ min Efn (x) ≥ f0 c0K .
x∈S

x∈Rd

Now we are ready to prove Theorem 4 .

Proof of Theorem 4 a)
Recall that


δ̂ H(ℵn ) \ ℵn = sup r : ∃x such that x +




r
fˆn (x)1/d

A ⊂ H(ℵn ) \ ℵn ,

−1/d

with A the ball B(O, ωd ).
Under H0 (S is convex),


δ̂ H(ℵn ) \ ℵn ≤ sup r : ∃x such that x +


r
fˆn (x)1/d


A ⊂ S \ ℵn .

If we apply Lemma 5 (i), (notice that all convex sets are in A) we get,

r
+
(1 − εn )A ⊂ S \ ℵn .
δ̂ H(ℵn ) \ ℵn ≤ sup r : ∃x such that x +
f (x)1/d

Equivalently, ∆(ℵn ) ≥ (1−ε+
n )δ̂ H(ℵn )\ℵn , and therefore P(V̂n ≥ cn,γ ) ≤ P V (ℵn ) ≥

d
(1 − ε+
n ) cn,γ , from where it follows that P(V̂n ≥ cn,γ ) can be majorized by,




d
+ d
P U (ℵn ) ≥ −(1−ε+
n ) log −log(1−γ) + (1−εn ) −1 log(n)+(d−1) log(log(n))+log(αB ) .




Therefore, by Theorem 2, (using that log(n)ε+
n → 0) we get that,

P(V̂n ≥ cn,γ ) ≤ P U (ℵn ) ≥ − log(− log(1 − γ)) + o(1) → γ.
27

Proof of Theorem 4 b)
From Lemma 5 (ii), we have that


δ̂ H(ℵn ) \ ℵn ≥ (λ0 − ε−
n )R H(ℵn ) \ ℵn ,
where ε−
n → 0 a.s. Then, under H1 (S is not convex), from (31), we obtain



δ̂ H(ℵn ) \ ℵn ≥ (λ0 − ε−
n ) R H(S) \ S − 2dH (S, ℵn ) .

Since S ∈ A, dH (S, ℵn ) → 0 a.s. (see [4]), and R H(S) \ S > 0 (see Proposition 4) then
with probability one, for n large enough

 1
δ̂ H(ℵn ) \ ℵn ≥ λ0 R H(S) \ S ,
2
and Theorem 4 b) follows from the fact that cn,γ → 0.

References
[1] Ambrosio, L., Colesanti, A., and Villa, E. (2008). Outer Minkowski content for some
classes of closed sets. Math. Ann. 342, 727–748.
[2] Baryshnikov B.Y., Penrose, M., and Yukich, J.E. (2009) Gaussian limits for generalized spacing. Ann. Appl. Prob. 19(1) 158–185
[3] Cuevas, A., and Fraiman, R. (1997) A plug-in approach to support estimation. Ann.
Statist. 25, 2300–2312.
[4] Cuevas, A., and Rodriguez-Casal, A. (2004) On boundary estimation. Adv. Appl.
Probab. 36, 340–354.
[5] Cuevas, A., Fraiman, R., and Pateiro-Lopez, B. (2012) On statistical properties of
sets fulfilling rolling-type conditions. Adv. Appl. Probab. 44, 311–239.
[6] Delicado, P., Hernández, A., and Lugosi, G. (2014) Data-based decision rules about
the convexity of the support of a distribution. Electron. J. Statist. 8, 96–129.
[7] Deheuvels, P. (1983). Strong Bounds for Multidimensional Spacings. Probab. Theory
Related Fields 64 (4) 411–424
[8] Devroye, L. (1981). Laws of the iterated logarithm for order statistics of uniform
spacings. Ann. Probab. 9 860–867.
[9] Dümbgen L., and Walther, G. (1996) Rate of convergence for random approximation
of convex sets. Ann. Appl. Prob. 28 384–393
[10] Gallier, J. (2011). Geometric Methods and Applications: For Computer Science and
Engineering, 2nd Edition. Springer-Verlag.
28

[11] Giné, E., and Guillou, A. (2002). Rates of strong uniform consistency for multivariate kernel density estimators. Annales de l’Institut Henri Poincare (B). Probability
and Statistics 38(6) 907–921.
[12] Janson, S. (1987). Maximal spacings in several dimensions. Ann. Prob. 15 274–280.
[13] Janson, S. (1986). Random coverings in several dimensions. Acta Math. 156 82–118.
[14] Leonenko, N., Prozanto, L., and Savani, V. (2008) A class of Rényi information
estimators for multidimensional densities. Ann. Stat. 36(5) 2153–2182.
[15] Matilla, P. (1995) Geometry of sets and measures in Euclidean spaces, Cambridge
Univ. Press.
[16] Miller, E.G. (2003) A new class of entropy estimators for multi-dimensional densities. International Conference on Acoustics, Speech, and Signal Processing.
[17] Møller, J., and Waagepetersen R. P. (2004) Statistical inference and simulation for
spatial point processes. Chapman & Hall/CRC
[18] Pyke, R. (1965). Spacings. J. Roy. Statist. Soc. Ser. B 27 395–449.
[19] Pyke, R. (1972). Spacings revisited. Proc. Sixth Berkeley Symp. Math. Statist.
Probab. 1 417–427.
[20] Proschan, F. and Pyke, R. (1967). Tests for monotone failure rate. Proc. Fifth
Berkeley Symp. on Math. Statist. and Prob. 3 293–312.
[21] Ranneby, B. (1984). The maximal spacing method. An estimation method related
to maximum likelihood method. Scand. J. Statist. 11 93–112.
[22] Ranneby, B., Jammalamadaka, S.R., and Teterukovskiy, A. (2005) The maximum
spacing estimation for multivariate observations. Journal of Statistical Planning and
Inference 129 (1–2) 427–446.
[23] Rényi, A., and Sulanke, R. (1963) Uber die konvexe Hülle von n zufällig gewählten
Punkten. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete. 2, 75–84.
[24] Rényi, A., and Sulanke, R. (1964) Uber die konvexe Hülle von n zufällig gewählten
Punkten (II). Z. Wahrscheinlichkeitstheorie und Verw. Gebiete. 3, 138–147.
[25] Stevens, W. L. (1939) Solution to a geometrical problem in probability. Ann. Eugenics 9 315–320
[26] Tenenbaum, J.B., De Silva V., and Lanford, J.C. (2000) A global geometric framework for nonlinear dimensionality reduction. Science 290 2319–2323.
[27] Dümbgen, L., and Walther, G.(1996) Rates of convergence for random approximations of convex sets. Adv. Appl. Probab. 28 384–393.
29

