U -max-Statistics
W. Lao∗ and M. Mayer†
Abstract
In 1948, W. Hoeffding introduced a large class of unbiased estima-
tors called U -statistics, defined as the average value of a real-valued
k-variate function h calculated at all possible sets of k points from a
random sample. In the present paper we investigate the corresponding
extreme value analogue, which we shall call U -max-statistics. We are
concerned with the behavior of the largest value of such function h in-
stead of its average. Examples of U -max-statistics are the diameter or
the largest scalar product within a random sample. U -max-statistics
of higher degrees are given by triameters and other metric invariants.
Keywords: random diameter, triameter, spherical distance, extreme
value, U -statistics, Poisson approximation
1 Introduction
U -statistics form a very important class of unbiased estimators for distri-
butional properties such as moments or Spearman’s rank correlation. A
U -statistic of degree k with symmetric kernel h is a function of the form
U(ξ1, . . . , ξn) =
h(ξi1 , · · · , ξik),
where the sum stretches over J = {(i1, . . . , ik) : 1 ≤ i1 < · · · < ik ≤ n},
ξ1, . . . , ξn are random elements in a measurable space S and h is a real-valued
Borel function on Sk, symmetric in its k arguments. In his seminal paper,
Hoeffding [8] defined U -statistics for not necessarily symmetric kernels and for
∗Institute of Stochastics, University of Karlsruhe, Englerstrasse 2, Karlsruhe, 76128
Germany
†Department of Mathematical Statistics and Actuarial Science, University of Bern,
Sidlerstrasse 54, CH-3012 Bern, Switzerland. Supported by Swiss National Foundation
Grant No. 200021-103579
http://arxiv.org/abs/0704.1379v1
random points in d-dimensional Euclidean space Rd. Later the concept was
extended to arbitrary measurable spaces. Since 1948, most of the classical
asymptotic results for sums of i.i.d. random variables have been formulated
in the setting of U -statistics, such as central limit laws, strong laws of large
numbers, Berry-Esséen type bounds and laws of the iterated logarithm.
The purpose of this article is to investigate the extreme value analogue
of U -statistics, i.e.
Hn = max
h(ξi1, . . . , ξik).
A typical example of such U -max-statistic is the diameter of a sample of
points in a metric space, obtained by using the metric as kernel. Grove and
Markvorsen [6] introduced an infinite sequence of metric invariants general-
izing the notion of diameter to “triameter”, “quadrameter”, etc. on com-
pact metric spaces. Their k-extent is the maximal average distance between
k points, which is an example for a U -max-statistic of arbitrary degree k.
Other examples are the largest surface area or perimeter of a triangle formed
by point triplets, or the largest scalar product within a sample of points in
The key to our results is the observation that for all z ∈ R, the U -max-
statistic Hn does not exceed z if and only if Uz vanishes, where
1{h(ξi1, . . . , ξik) > z}.
The random variable Uz counts the number of exceedances of the threshold
z and is a normalized U -statistic in the usual sense. We approximate its
distribution with the help of a Poisson approximation result for the sum of
dissociated random indicator kernel functions by Barbour et al. [3], which
enables us to determine the distribution ofHn up to some known error. In or-
der to deduce the corresponding limit law for Hn, the behavior of the upper
tail of the distribution of h must be known, which often requires compli-
cated geometric computations. Denote by ‖ · ‖ the Euclidean norm. The
general results are used to derive limit theorems for the following settings:
largest interpoint distance and scalar product of a sample of points in the
d-dimensional closed unit ball Bd = {x ∈ Rd : ‖x‖ ≤ 1}, where the directions
of the points have a density on the surface Sd−1 of Bd and are independent of
the norms; smallest spherical distance of a sample of points with density on
d−1; largest perimeter of all triangles formed by point triplets in a sample
of uniformly distributed points on the unit circle S.
2 Poisson approximation for U-max-statistics
The following result is easily derived from Theorem 2.N for dissociated indi-
cator random variables from Barbour et al. [3]. We use the convention that
improper sums for k = 1 equal zero.
Theorem 2.1. Let ξ1, . . . , ξn be i.i.d. S-valued random elements and
h : Sk → R a symmetric Borel function. Putting
pn,z = P {h(ξ1, . . . , ξk) > z} ,
λn,z =
pn,z,
τn,z(r) = p
n,zP {h(ξ1, . . . , ξk) > z, h(ξ1+k−r, ξ2+k−r, . . . , ξ2k−r) > z} ,
we have, for any n ≥ k and any z ∈ R,
|P {Hn ≤ z} − exp{−λn,z}| (2.1)
≤ (1− exp{−λn,z})
k − r
τn,z(r)
Clearly the result can be reformulated as well for the minimum value of
the kernel by replacing h with −h. One of the main applications of this
theorem consists in determining a suitable sequence of transformations
zn : T → R with T ⊂ R, such that both the right hand side of (2.1) converges
to zero as n→ ∞ for all z = zn(t), t ∈ T , and the limits of exp{−λn,zn(t)}
are non-trivial for all t ∈ T . The usual choice is T = [0,∞). One way to
achieve this goal is based on the following two remarks and will eventually
lead to the well known Poisson limit theorem of Silverman and Brown [12],
originally proved by a suitable coupling.
Remark 1. As already Silverman and Brown [12] stated,
pn,z ≤ τn,z(1) ≤ · · · ≤ τn,z(k) = 1.
Remark 2. If the sample size n tends to infinity, then the error (2.1) is
asymptotically
pn,zn
k−1 +
τn,z(r)n
and for k > 1 the sum is dominating, see [3, p. 35].
Remark 3. The symmetry condition on h can be avoided if h is symmetrized
h∗(x1, . . . , xk) = max
j1,...,jk
h(xj1 , . . . , xjk),
where the maximum is taken over all permutations of 1, . . . , k.
The conditions stated in [12] suffice to ensure that Theorem 2.1 provides
a non-trivial Weibull limit law.
Corollary 2.2 (Silverman-Brown limit law [12]). In the setting of Theo-
rem 2.1, if for some sequence of transformations zn : T → R with T ⊂ R, the
conditions
λn,zn(t) = λt > 0 (2.2)
n2k−1pn,zn(t)τn,zn(t)(k − 1) = 0 (2.3)
hold for all t ∈ T , then
P {Hn ≤ zn(t)} = exp{−λt} (2.4)
for all t ∈ T .
Remark 4. Condition (2.2) implies pn,zn(t) = O(n−k) and by Remarks 1 and
2 we obtain for (2.4) the rate of convergence
n−1 +
n2k−rpn,zn(t)τn,zn(t)(r)
with upper bound
O(n2k−1pn,zn(t)τn,zn(t)(k − 1)). (2.5)
If k > 2, it is sometimes useful to replace (2.3) by the weaker requirement
n2k−rpn,zn(t)τn,zn(t)(r) = 0 (2.6)
for each r ∈ {1, . . . , k−1}, a fact that follows immediately from Theorem 2.1
and Remark 2.
Appel and Russo [2] obtained a Weibull limit law similar to Corollary 2.2
for bivariate h. They assume that the upper tail of the distribution of h(ξ1, x)
does not depend on x for almost all x ∈ S, which implies that (2.2) and (2.3)
hold. However, this condition is fulfilled only in very rare settings, e.g. for
uniformly distributed points on Sd−1.
3 Largest interpoint distance
The asymptotic behavior of the range of a univariate sample can be deter-
mined by classical extreme value theory, see e.g. [5, Sec. 2.9]. The largest
interpoint distance
Hn = max
1≤i<j≤n
‖ξi − ξj‖
within a sample of points in Rd is a natural and consistent generalization
of the range to spatial data. Matthews and Rukhin [10] derived its limiting
behavior for a normal sample, a work which has been generalized by Henze
and Klein [7] to a sample of points with symmetric Kotz distribution. Appel
et al. [1] found corresponding limit laws in the setting of uniformly distributed
points in 2-dimensional compact sets, which are not too smooth near the
endpoints of their largest axes. They also provided bounds for the limit
law of the diameter of uniformly distributed points in ellipses and the unit
disk. The exact limit distribution for the disk and in more general settings
was found independently by Lao [9] and Mayer and Molchanov [11]. Lao
[9] used Theorem A of [12] to obtain the exact limit law for the diameter
of a uniform sample in Bd. The results in [11] rely on a combination of
geometric considerations and blocking techniques and yield e.g. the special
case of Theorem 3.1 for spherically symmetric distributions.
In what follows, we denote by 〈·, ·〉 the scalar product, by µd−1 the (d−1)-
dimensional Hausdorff measure and by Γ and B the complete Gamma and
Beta functions.
Theorem 3.1. Let ξ1, ξ2, . . . be i.i.d. points in B
d, d ≥ 2, such that
ξi = ‖ξi‖Ui, i ≥ 1, where Ui and ‖ξi‖ are independent and Ui ∈ Sd−1. Assume
that the distribution function F of 1− ‖ξ1‖ satisfies
s−αF (s) = a ∈ (0,∞)
for some α ≥ 0. Further assume that U1 has a density f with respect to µd−1
and that
f(x)f(−x)µd−1(dx) ∈ (0,∞). Then
n2/γ(2−Hn) ≤ t
= 1− exp
for t > 0, where
γ = (d− 1)/2 + 2α
2 a2Γ2(α + 1)
Γ(d+1
+ 2α)
f(x)f(−x)µd−1(dx).
The rate of convergence for t < ∞ is O(n−
d−1+4α ).
Remark 5. Spherically symmetric distributed points have independent and
uniformly distributed directions and hence [11, Th. 4.2] follows immediately
from Theorem 3.1 with
f(x)f(−x)µd−1(dx) =
2πd/2
The special case α = 1 and a = d yields the limit law for the diameter of a
sample of uniformly distributed points in Bd, see [9] or [11].
Remark 6. If ‖ξi‖ = 1 almost surely, then α = 0 and a = 1. For instance, if
Ui are uniformly distributed on S
d−1, then for t > 0
n4/(d−1)(2−Hn) ≤ t
= 1− exp
2d−3Γ(d
2Γ(d+1
see [2] or [11]. Another example appears if Ui has the von Mises-Fisher
distribution of dimension d ≥ 2 with density
fF (x) = Cd(κ) exp {κ〈µ, x〉}
for x ∈ Sd−1, where µ ∈ Sd−1 represents the mean direction and κ > 0 is the
concentration parameter. The normalizing constant Cd(κ) is given by
Cd(κ) =
κd/2−1
(2π)d/2Id/2−1(κ)
where Iν denotes the modified Bessel function of the first kind of order ν.
fF (x)fF (−x)µd−1(dx) = C2d(κ)
2πd/2
the corresponding limit law follows immediately.
A key part of the proof of Theorem 3.1 is the asymptotic tail behavior of
the distribution of the distance between two i.i.d. points.
Lemma 3.2. If the conditions of Theorem 3.1 hold, then
s−γP {‖ξ1 − ξ2‖ ≥ 2− s} = σ1.
Proof. Let η1 and η2 be independent random variables with distribution F
and denote by βx the smaller central angle between U2 and x ∈ Sd−1. The
cosine theorem yields
P {‖ξ1 − ξ2‖ ≥ 2− s} = P
‖ξ1‖2 + ‖ξ2‖2 + 2‖ξ1‖‖ξ2‖ cos β−U1 ≥ (2− s)2
cos β−U1 ≥
(2− s)2 − (1− η1)2 − (1− η2)2
2(1− η1)(1− η2)
and by expansion of cos β−U1 about 0 we obtain for sufficiently small s
P {‖ξ1 − ξ2‖ ≥ 2− s} = P
|β−U1| ≤ 2(s̃− η1 − η2)
2 , η1 + η2 ≤ s̃
, (3.1)
where |s̃ − s| ≤ C1s2 for some finite C1, thus s̃/s → 1 as s ↓ 0. Lebesgue’s
differentiation theorem (see e.g. [4, Th. 2.9.5]) implies that
|β−x| ≤ 2(s̃− y)
(4(s̃− y)) d−12
= µd−1(B
d−1)f(−x) = π
Γ(d+1
f(−x) (3.2)
for µd−1-almost every x ∈ Sd−1 and any y ∈ [0, s̃]. Integration over all
x ∈ Sd−1 with respect to f yields
(s̃− y)−
|β−U1| ≤ 2(s̃− y)
where
Γ(d+1
f(x)f(−x)µd−1(dx),
and hence with (3.1)
P {‖ξ1 − ξ2‖ ≥ 2− s}
(s̃− η1 − η2)
2 1{η1 + η2 ≤ s̃}
) = c.
If α = 0, then P {ηi = 0} = a, i = 1, 2, and thus
s̃−γP {‖ξ1 − ξ2‖ ≥ 2− s} = ca2 = σ1.
If α > 0,
P {‖ξ1 − ξ2‖ ≥ 2− s}
∫ s̃−y1
(s̃− y1 − y2)
2 dF (y2)dF (y1)
and substituting vi = yi/s̃, i = 1, 2, yields
P {‖ξ1 − ξ2‖ ≥ 2− s}
= ca2α2
∫ 1−v1
(1− v1− v2)
2 (v1v2)
α−1dv2dv1.
By Dirichlet’s Formula, the double integral equals
Γ2(α)Γ(d+1
Γ(d+1
+ 2α)
and the proof is complete.
Proof of Theorem 3.1. Plugging the transformation zn(t) = 2− tn−2/γ , t > 0
into Corollary 2.2 and using the tail probabilities given in Lemma 3.2, we
P {‖ξ1 − ξ2‖ > zn(t)} =
tγ , t > 0.
Hence condition (2.2) holds for all t > 0. The more extensive part of the
proof aims to show that (2.3) holds. Let βx and β
x be the smaller central
angles between U2 and x ∈ Sd−1 and between U3 and x ∈ Sd−1. Further
let η1, η2 and η3 be independent random variables with distribution F . Put
sn = tn
−2/γ . Following the proof of Lemma 3.2
P {‖ξ1 − ξ2‖ > zn(t), ‖ξ1 − ξ3‖ > zn(t)}
|β−U1| ≤ 2s
n , |β ′−U1| ≤ 2s
n , ηi ≤ sn, i = 1, 2, 3
|β−x| ≤ 2s
f(x)µd−1(dx)1{ηi ≤ sn, i = 1, 2, 3}
≤ CE(sd−1n 1{ηi ≤ sn, i = 1, 2, 3}), (3.3)
where the last step follows from (3.2) and C is a suitable finite positive
constant. If α = 0, then P {ηi = 0} = a, i = 1, 2, 3, and we obtain
n3P {‖ξ1 − ξ2‖ > zn(t), ‖ξ1 − ξ3‖ > zn(t)}
≤ Ca3 lim
n3sd−1n = Ca
3td−1 lim
n−1 = 0.
If α > 0, we derive from (3.3) that
P {‖ξ1 − ξ2‖ > zn(t), ‖ξ1 − ξ3‖ > zn(t)}
sd−1n dF (y3)dF (y2)dF (y1)
and substituting vi = yi/sn, i = 1, 2, 3, yields
n3P {‖ξ1 − ξ2‖ > zn(t), ‖ξ1 − ξ3‖ > zn(t)}
≤ Ca3 lim
sd−1+3αn = Ca
3td−1+3α lim
d−1+4α = 0.
The rate of convergence is determined via (2.5).
4 Largest scalar product
Besides the Euclidean metric, the scalar product is another symmetric kernel
on Rd × Rd. The behavior of its largest value
Hn = max
1≤i<j≤n
〈ξi, ξj〉
within a sample of points in Bd is determined in the next result.
Theorem 4.1. Let ξ1, ξ2, . . . be i.i.d. points in B
d, d ≥ 2, such that
ξi = ‖ξi‖Ui, i ≥ 1, where Ui and ‖ξi‖ are independent and Ui ∈ Sd−1. Assume
that the distribution function F of 1− ‖ξ1‖ satisfies
s−αF (s) = a ∈ (0,∞)
for some α ≥ 0. Further assume that U1 has a square-integrable density f
on Sd−1 with respect to µd−1. Then
n2/γ(1−Hn) ≤ t
= 1− exp
for t > 0, where
γ = (d− 1)/2 + 2α
2 a2Γ2(α + 1)
Γ(d+1
+ 2α)
f 2(x)µd−1(dx).
The rate of convergence for t < ∞ is O(n−
d−1+4α ).
Lemma 4.2. If the conditions of Theorem 4.1 hold, then
s−γP {〈ξ1, ξ2〉 ≥ 1− s} = σ2.
Proof. If βx is the smaller central angle between U2 and x ∈ Sd−1 and η is
distributed as 1− ‖ξ1‖‖ξ2‖, then
P {〈ξ1, ξ2〉 ≥ 1− s} = P {cos βU1 ≥ (1− s)/(1− η), η ≤ s} .
Expanding cos βU1 about 0 yields for all sufficiently small s
P {〈ξ1, ξ2〉 ≥ 1− s} = P
|βU1| ≤ (2(s̃− η))
2 , η ≤ s̃
, (4.1)
where |s̃−s| ≤ C1s2 for some finite C1, and thus s̃/s → 1 as s ↓ 0. Lebesgue’s
differentiation theorem (see e.g. [4, Th. 2.9.5]) implies that
|βx| ≤ (2(s̃− y))
(2(s̃− y)) d−12
= µd−1(B
d−1)f(x) =
Γ(d+1
f(x). (4.2)
for µd−1-almost every x ∈ Sd−1 and any y ∈ [0, s̃]. Integration over all
x ∈ Sd−1 with respect to f yields
(s̃− y)−
|βU1| ≤ (2(s̃− y))
Γ(d+1
f 2(x)µd−1(dx),
and by (4.1) we obtain
P {〈ξ1, ξ2〉 ≥ 1− s}
(s̃− η)
2 1{η ≤ s̃}
If α = 0, then P {η = 0} = a2 and hence
s−γP {〈ξ1, ξ2〉 ≥ 1− s} = ca2 = σ2.
If α > 0, then P {〈ξ1, ξ2〉 ≥ 1− s} equals asymptotically, as s ↓ 0, to
(1−s̃)/y1
(s̃− 1 + y1y2)
2 dF (1− y2)dF (1− y1).
By substituting v1 = (1− y1)/s̃ and v2 = (1− y2)/(1− (1− s̃)/y1)) the last
expression equals asymptotically, as s ↓ 0, to
ca2α2
1− v1
1− s̃v1
s̃− 1 + (1− s̃v1)(1− s̃v2
1− v1
1− s̃v1
vα−11 v
2 dv2dv1.
Hence
s−γP {〈ξ1, ξ2〉 ≥ 1− s}
= ca2α2
(1− v1)
+αvα−11 dv1
(1− v2)
2 vα−12 dv2
= ca2α2B((d+ 1)/2 + α, α)B((d+ 1)/2, α) = σ2.
Proof of Theorem 4.1. An application of Corollary 2.2 yields, together with
the transformation zn = 1− tn−2/γ , t > 0, and Lemma 4.2 the limit
P {〈ξ1, ξ2〉 ≥ zn(t)} =
hence (2.2) holds for any t > 0 and it remains to check (2.3). Put sn = tn
and let βx and β
x be the smaller central angles between U2 and x ∈ Sd−1 and
between U3 and x. Following the proof of Lemma 4.2
P {〈ξ1, ξ2〉 ≥ zn(t), 〈ξ1, ξ3〉 ≥ zn(t)}
|βU1 | ≤ (2sn)
2 , |β ′U1| ≤ (2sn)
2 , ‖ξi‖ ≥ zn(t), i = 1, 2, 3
|βx| ≤ (2sn)
f(x)µd−1(dx)1{‖ξi‖ ≥ zn(t), i = 1, 2, 3}
≤ CE(sd−1n 1{‖ξi‖ ≥ zn(t), i = 1, 2, 3}), (4.3)
where the last step follows from (4.2) and C is a suitable finite positive
constant. If α = 0, then P {‖ξi‖ = 1} = α, i = 1, 2, 3, and hence
n3P {〈ξ1, ξ2〉 ≥ zn(t), 〈ξ1, ξ3〉 ≥ zn(t)}
≤ Ca3 lim
n3sd−1n = Ca
3td−1 lim
n−1 = 0.
If α > 0, then (4.3) is bounded from above by
sd−1n dF (y3)dF (y2)dF (y1)
and substituting vi = yi/sn, i = 1, 2, 3, yields finally
n3P {〈ξ1, ξ2〉 ≥ zn(t), 〈ξ1, ξ3〉 ≥ zn(t)}
≤ Ca3 lim
sd−1+3αn = Ca
3td−1+3α lim
d−1+4α = 0,
and the rate of convergence is determined via (2.5).
5 Smallest spherical distance
A nice application of Theorem 4.1 comes from the field of directional statis-
tics. The following theorem determines the limiting behavior of the smallest
spherical distance
Sn = min
1≤i<j≤n
within i.i.d. points U1, U2, . . . on S
d−1, where βi,j denotes the smaller of the
two central angles between Ui and Uj . In other words, Sn equals the smallest
central angle formed by point pairs within the sample.
Theorem 5.1. Let U1, U2 . . . be i.i.d. points on S
d−1, d ≥ 2, having square-
integrable density f on Sd−1 with respect to µd−1. Then
n2/(d−1)Sn ≤ t
= 1− exp
for any t > 0, where
Γ(d+1
f 2(x)µd−1(dx)
The rate of convergence is O(n− 12 ) for finite t.
If the points are uniformly distributed on Sd−1, then Theorem 5.1 applies
f 2(x)µd−1(dx) =
2πd/2
If the points on Sd−1 follow the von Mises-Fisher distribution as introduced
in Section 3, then
f 2F (x)µd−1(dx) = C
d(κ)/Cd(2κ).
In dimension 2, Sn equals the minimal spacing, i.e. the smallest arc length
between the “order” statistics.
Proof of Theorem 5.1. Clearly, the relation cos βi,j = 〈Ui, Uj〉 holds for all
pairs of i and j between 1 and n. Since the cosine function is continuous and
monotone strictly decreasing on (0, π) and by the fact that
2 arccos(1− s) =
it follows that
n2/(d−1)Sn ≤ t
= lim
1≤i<j≤n
βi,j ≤ tn−2/(d−1)
= lim
1≤i<j≤n
βi,j ≤ arccos
1− t2n−4/(d−1)/2
= lim
1≤i<j≤n
〈Ui, Uj〉 ≥ 1− t2n−4/(d−1)/2
Theorem 4.1 yields the proof with α = 0 and a = 1.
6 Largest perimeter
Finally we present a result for a U -max-statistic of degree 3, namely the limit
law for the largest value
1≤i<j<ℓ≤n
peri(Ui, Uj , Uℓ)
of the perimeter peri(Ui, Uj , Uℓ) of all triangles formed by triplets of indepen-
dent and uniformly distributed points U1, U2, . . . on the unit circle S. The
random triameter (see [6]) of the sample is the largest perimeter up to a
factor 3, hence the limit law for the triameter of U1, U2, . . . can be derived
immediately.
Theorem 6.1. If U1, U2, . . . are independent and uniformly distributed points
on S, then
3−Hn) ≤ t
= 1− exp
for all t > 0 and for finite t the rate of convergence is O(n− 12 ).
Lemma 6.2. If U1, U2, U3 are independent and uniformly distributed points
on S, then
peri(U1, U2, U3) ≥ 3
Proof. Clearly, peri(x1, x2, x3) is maximal for x1, x2, x3 being the vertices of
an equilateral triangle on S, which has perimeter 3
3. If β1 and β2 are the
angles (measured counter-clockwise) between U1 and U2 and between U2 and
U3 respectively. By rotational symmetry, β1 and β2 are independent and
uniformly distributed on [0, 2π]. The cosine theorem yields for sufficiently
small s
peri(U1, U2, U3) ≥ 3
(2− 2 cosβ1)
2 + (2− 2 cosβ2)
+ (2− 2 cos(2π − β1 − β2))
2 ≥ 3
3− s, β1, β2 ∈ [2π/3± cs]
, (6.1)
where cs = C1
s and C1 is a suitable finite positive constant. If η1 and η2 are
independent and uniformly distributed on [−cs, cs], then the last expression
equals
(2− 2 cos(2π/3 + η1))
2 + (2− 2 cos(2π/3 + η2))
+ (2− 2 cos(2π/3− η1 − η2))
2 ≥ 3
P {β1 ∈ [2π/3± cs]}2 .
By series expansion, (6.1) equals
2(cs/π)
η21 + η
2 + (η1 + η2)
2 ≤ 8s̃/
(6.2)
= 2(cs/π)
−η1/2± (4s̃/
3− 3η21/4)
= π−2
s̃/33/4
s̃/33/4
(4s̃/
3− 3y2/4)
2dy =
where |s̃ − s| ≤ C2s3/2 for some finite C2, and the proof follows by the fact
that s̃/s → 1 as s ↓ 0.
Proof of Theorem 6.1. Plugging into Corollary 2.2 the transformation
zn(t) = 3
3− tn−3 together with the result of Lemma 6.2 yields
P {peri(U1, U2, U3) > zn(t)} =
hence (2.2) is satisfied for all t > 0. Condition (2.3) does not hold, so we use
the weaker requirement (2.6) to replace (2.3), i.e. we need to show that
n5P {peri(U1, U2, U3) > zn(t), peri(U1, U4, U5) > zn(t)} = 0 (6.3)
n4P {peri(U1, U2, U3) > zn(t), peri(U1, U2, U4) > zn(t)} = 0. (6.4)
For (6.3), we follow the proof of Lemma 6.2. In addition, denote by β ′1 and β
the random angles between U1 and U4 and between U4 and U5 respectively.
It follows immediately by rotational symmetry, that β1, β2, β
1 and β
2 are in-
dependent and uniformly distributed on [0, 2π]. With the help of Lemma 6.2
we check (6.3) by
n5P {peri(U1, U2, U3) > zn(t), peri(U1, U2, U4) > zn(t)}
≤ C1 lim
n5P {peri(U1, U2, U3) > zn(t)}2 = C2t2 lim
n−1 = 0,
where C1 and C2 are suitable finite positive constants. To show (6.4) we
follow the proof of Lemma 6.2 and introduce the random variable η3, which is
independent of η1 and η2 and uniformly distributed on [−cs, cs]. For suitable
finite positive constants C3, C4 and C5
P {peri(U1, U2, U3) > zn(t), peri(U1, U2, U4) > zn(t)}
≤ C3c3sP
η2, η3 ∈
−η1/2± (4s̃/
3− 3η21/4)
= C4c
s̃/33/4
s̃/33/4
−y/2± (4s̃/
3− 3y2/4)
dy = C5s̃
and with s = tn−3 and s/s̃ → 1 as s → 0
n4P {peri(U1, U2, U3) > zn(t), peri(U1, U2, U4) > zn(t)}
≤ C5t3/2 lim
2 = 0.
Hence (6.4) holds and the rate of convergence is determined by Remark 2.
Acknowledgements
The authors would like to thank Prof. Dr. N. Henze and Prof. Dr. I. Molchanov
for their invaluable help concerning this and many other problems.
References
[1] M. J. B. Appel, C. A. Najim, and R. P. Russo. Limit laws for the
diameter of a random point set. Adv. Appl. Probab., 34:1–10, 2002.
[2] M. J. B. Appel and R. P. Russo. Limiting distributions for the maximum
of a symmetric function on a random point set. J. Theor. Probab.,
19:365–375, 2006.
[3] A. D. Barbour, L. Holst, and S. Janson. Poisson Approximation. Claren-
don Press, Oxford, 1992.
[4] H. Federer. Geometric Measure Theory. Springer, Berlin, 1969.
[5] J. Galambos. The Asymptotic Theory of Extreme Order Statistics. Wi-
ley, New York, 1978.
[6] K. Grove and S. Markvorsen. Curvature, triameter, and beyond. Bull.
Amer. Math. Soc., 27:261–265, 1992.
[7] N. Henze and T. Klein. The limit distribution of the largest interpoint
distance from a symmetric Kotz sample. J. Multiv. Anal., 57:228–239,
1996.
[8] W. Hoeffding. A class of statistics with asymptotically normal distribu-
tion. Ann. Math. Statist., 19:293–325, 1948.
[9] W. Lao. The limit law of the maximum distance of points in a sphere
in Rd. Technical report, University of Karlsruhe, Karlsruhe, Germany,
2006.
[10] P. C. Matthews and A. L. Rukhin. Asymptotic distribution of the normal
sample range. Ann. Appl. Probab., 13:454–466, 1993.
[11] M. Mayer and I. Molchanov. Limit theorems for the diameter of a
random sample in the unit ball. Extremes. To appear.
[12] B. W. Silverman and T. C. Brown. Short distances, flat triangles and
poisson limits. J. Appl. Probab., 15:815–825, 1978.
	Introduction
	Poisson approximation for U-max-statistics
	Largest interpoint distance
	Largest scalar product
	Smallest spherical distance
	Largest perimeter

  In 1948, W. Hoeffding introduced a large class of unbiased estimators called
U-statistics, defined as the average value of a real-valued k-variate function
h calculated at all possible sets of k points from a random sample. In the
present paper we investigate the corresponding extreme value analogue, which we
shall call U-max-statistics. We are concerned with the behavior of the largest
value of such function h instead of its average. Examples of U-max-statistics
are the diameter or the largest scalar product within a random sample.
U-max-statistics of higher degrees are given by triameters and other metric
invariants.

Introduction
U -statistics form a very important class of unbiased estimators for distri-
butional properties such as moments or Spearman’s rank correlation. A
U -statistic of degree k with symmetric kernel h is a function of the form
U(ξ1, . . . , ξn) =
h(ξi1 , · · · , ξik),
where the sum stretches over J = {(i1, . . . , ik) : 1 ≤ i1 < · · · < ik ≤ n},
ξ1, . . . , ξn are random elements in a measurable space S and h is a real-valued
Borel function on Sk, symmetric in its k arguments. In his seminal paper,
Hoeffding [8] defined U -statistics for not necessarily symmetric kernels and for
∗Institute of Stochastics, University of Karlsruhe, Englerstrasse 2, Karlsruhe, 76128
Germany
†Department of Mathematical Statistics and Actuarial Science, University of Bern,
Sidlerstrasse 54, CH-3012 Bern, Switzerland. Supported by Swiss National Foundation
Grant No. 200021-103579
http://arxiv.org/abs/0704.1379v1
random points in d-dimensional Euclidean space Rd. Later the concept was
extended to arbitrary measurable spaces. Since 1948, most of the classical
asymptotic results for sums of i.i.d. random variables have been formulated
in the setting of U -statistics, such as central limit laws, strong laws of large
numbers, Berry-Esséen type bounds and laws of the iterated logarithm.
The purpose of this article is to investigate the extreme value analogue
of U -statistics, i.e.
Hn = max
h(ξi1, . . . , ξik).
A typical example of such U -max-statistic is the diameter of a sample of
points in a metric space, obtained by using the metric as kernel. Grove and
Markvorsen [6] introduced an infinite sequence of metric invariants general-
izing the notion of diameter to “triameter”, “quadrameter”, etc. on com-
pact metric spaces. Their k-extent is the maximal average distance between
k points, which is an example for a U -max-statistic of arbitrary degree k.
Other examples are the largest surface area or perimeter of a triangle formed
by point triplets, or the largest scalar product within a sample of points in
The key to our results is the observation that for all z ∈ R, the U -max-
statistic Hn does not exceed z if and only if Uz vanishes, where
1{h(ξi1, . . . , ξik) > z}.
The random variable Uz counts the number of exceedances of the threshold
z and is a normalized U -statistic in the usual sense. We approximate its
distribution with the help of a Poisson approximation result for the sum of
dissociated random indicator kernel functions by Barbour et al. [3], which
enables us to determine the distribution ofHn up to some known error. In or-
der to deduce the corresponding limit law for Hn, the behavior of the upper
tail of the distribution of h must be known, which often requires compli-
cated geometric computations. Denote by ‖ · ‖ the Euclidean norm. The
general results are used to derive limit theorems for the following settings:
largest interpoint distance and scalar product of a sample of points in the
d-dimensional closed unit ball Bd = {x ∈ Rd : ‖x‖ ≤ 1}, where the directions
of the points have a density on the surface Sd−1 of Bd and are independent of
the norms; smallest spherical distance of a sample of points with density on
d−1; largest perimeter of all triangles formed by point triplets in a sample
of uniformly distributed points on the unit circle S.
2 Poisson approximation for U-max-statistics
The following result is easily derived from Theorem 2.N for dissociated indi-
cator random variables from Barbour et al. [3]. We use the convention that
improper sums for k = 1 equal zero.
Theorem 2.1. Let ξ1, . . . , ξn be i.i.d. S-valued random elements and
h : Sk → R a symmetric Borel function. Putting
pn,z = P {h(ξ1, . . . , ξk) > z} ,
λn,z =
pn,z,
τn,z(r) = p
n,zP {h(ξ1, . . . , ξk) > z, h(ξ1+k−r, ξ2+k−r, . . . , ξ2k−r) > z} ,
we have, for any n ≥ k and any z ∈ R,
|P {Hn ≤ z} − exp{−λn,z}| (2.1)
≤ (1− exp{−λn,z})
k − r
τn,z(r)
Clearly the result can be reformulated as well for the minimum value of
the kernel by replacing h with −h. One of the main applications of this
theorem consists in determining a suitable sequence of transformations
zn : T → R with T ⊂ R, such that both the right hand side of (2.1) converges
to zero as n→ ∞ for all z = zn(t), t ∈ T , and the limits of exp{−λn,zn(t)}
are non-trivial for all t ∈ T . The usual choice is T = [0,∞). One way to
achieve this goal is based on the following two remarks and will eventually
lead to the well known Poisson limit theorem of Silverman and Brown [12],
originally proved by a suitable coupling.
Remark 1. As already Silverman and Brown [12] stated,
pn,z ≤ τn,z(1) ≤ · · · ≤ τn,z(k) = 1.
Remark 2. If the sample size n tends to infinity, then the error (2.1) is
asymptotically
pn,zn
k−1 +
τn,z(r)n
and for k > 1 the sum is dominating, see [3, p. 35].
Remark 3. The symmetry condition on h can be avoided if h is symmetrized
h∗(x1, . . . , xk) = max
j1,...,jk
h(xj1 , . . . , xjk),
where the maximum is taken over all permutations of 1, . . . , k.
The conditions stated in [12] suffice to ensure that Theorem 2.1 provides
a non-trivial Weibull limit law.
Corollary 2.2 (Silverman-Brown limit law [12]). In the setting of Theo-
rem 2.1, if for some sequence of transformations zn : T → R with T ⊂ R, the
conditions
λn,zn(t) = λt > 0 (2.2)
n2k−1pn,zn(t)τn,zn(t)(k − 1) = 0 (2.3)
hold for all t ∈ T , then
P {Hn ≤ zn(t)} = exp{−λt} (2.4)
for all t ∈ T .
Remark 4. Condition (2.2) implies pn,zn(t) = O(n−k) and by Remarks 1 and
2 we obtain for (2.4) the rate of convergence
n−1 +
n2k−rpn,zn(t)τn,zn(t)(r)
with upper bound
O(n2k−1pn,zn(t)τn,zn(t)(k − 1)). (2.5)
If k > 2, it is sometimes useful to replace (2.3) by the weaker requirement
n2k−rpn,zn(t)τn,zn(t)(r) = 0 (2.6)
for each r ∈ {1, . . . , k−1}, a fact that follows immediately from Theorem 2.1
and Remark 2.
Appel and Russo [2] obtained a Weibull limit law similar to Corollary 2.2
for bivariate h. They assume that the upper tail of the distribution of h(ξ1, x)
does not depend on x for almost all x ∈ S, which implies that (2.2) and (2.3)
hold. However, this condition is fulfilled only in very rare settings, e.g. for
uniformly distributed points on Sd−1.
3 Largest interpoint distance
The asymptotic behavior of the range of a univariate sample can be deter-
mined by classical extreme value theory, see e.g. [5, Sec. 2.9]. The largest
interpoint distance
Hn = max
1≤i<j≤n
‖ξi − ξj‖
within a sample of points in Rd is a natural and consistent generalization
of the range to spatial data. Matthews and Rukhin [10] derived its limiting
behavior for a normal sample, a work which has been generalized by Henze
and Klein [7] to a sample of points with symmetric Kotz distribution. Appel
et al. [1] found corresponding limit laws in the setting of uniformly distributed
points in 2-dimensional compact sets, which are not too smooth near the
endpoints of their largest axes. They also provided bounds for the limit
law of the diameter of uniformly distributed points in ellipses and the unit
disk. The exact limit distribution for the disk and in more general settings
was found independently by Lao [9] and Mayer and Molchanov [11]. Lao
[9] used Theorem A of [12] to obtain the exact limit law for the diameter
of a uniform sample in Bd. The results in [11] rely on a combination of
geometric considerations and blocking techniques and yield e.g. the special
case of Theorem 3.1 for spherically symmetric distributions.
In what follows, we denote by 〈·, ·〉 the scalar product, by µd−1 the (d−1)-
dimensional Hausdorff measure and by Γ and B the complete Gamma and
Beta functions.
Theorem 3.1. Let ξ1, ξ2, . . . be i.i.d. points in B
d, d ≥ 2, such that
ξi = ‖ξi‖Ui, i ≥ 1, where Ui and ‖ξi‖ are independent and Ui ∈ Sd−1. Assume
that the distribution function F of 1− ‖ξ1‖ satisfies
s−αF (s) = a ∈ (0,∞)
for some α ≥ 0. Further assume that U1 has a density f with respect to µd−1
and that
f(x)f(−x)µd−1(dx) ∈ (0,∞). Then
n2/γ(2−Hn) ≤ t
= 1− exp
for t > 0, where
γ = (d− 1)/2 + 2α
2 a2Γ2(α + 1)
Γ(d+1
+ 2α)
f(x)f(−x)µd−1(dx).
The rate of convergence for t < ∞ is O(n−
d−1+4α ).
Remark 5. Spherically symmetric distributed points have independent and
uniformly distributed directions and hence [11, Th. 4.2] follows immediately
from Theorem 3.1 with
f(x)f(−x)µd−1(dx) =
2πd/2
The special case α = 1 and a = d yields the limit law for the diameter of a
sample of uniformly distributed points in Bd, see [9] or [11].
Remark 6. If ‖ξi‖ = 1 almost surely, then α = 0 and a = 1. For instance, if
Ui are uniformly distributed on S
d−1, then for t > 0
n4/(d−1)(2−Hn) ≤ t
= 1− exp
2d−3Γ(d
2Γ(d+1
see [2] or [11]. Another example appears if Ui has the von Mises-Fisher
distribution of dimension d ≥ 2 with density
fF (x) = Cd(κ) exp {κ〈µ, x〉}
for x ∈ Sd−1, where µ ∈ Sd−1 represents the mean direction and κ > 0 is the
concentration parameter. The normalizing constant Cd(κ) is given by
Cd(κ) =
κd/2−1
(2π)d/2Id/2−1(κ)
where Iν denotes the modified Bessel function of the first kind of order ν.
fF (x)fF (−x)µd−1(dx) = C2d(κ)
2πd/2
the corresponding limit law follows immediately.
A key part of the proof of Theorem 3.1 is the asymptotic tail behavior of
the distribution of the distance between two i.i.d. points.
Lemma 3.2. If the conditions of Theorem 3.1 hold, then
s−γP {‖ξ1 − ξ2‖ ≥ 2− s} = σ1.
Proof. Let η1 and η2 be independent random variables with distribution F
and denote by βx the smaller central angle between U2 and x ∈ Sd−1. The
cosine theorem yields
P {‖ξ1 − ξ2‖ ≥ 2− s} = P
‖ξ1‖2 + ‖ξ2‖2 + 2‖ξ1‖‖ξ2‖ cos β−U1 ≥ (2− s)2
cos β−U1 ≥
(2− s)2 − (1− η1)2 − (1− η2)2
2(1− η1)(1− η2)
and by expansion of cos β−U1 about 0 we obtain for sufficiently small s
P {‖ξ1 − ξ2‖ ≥ 2− s} = P
|β−U1| ≤ 2(s̃− η1 − η2)
2 , η1 + η2 ≤ s̃
, (3.1)
where |s̃ − s| ≤ C1s2 for some finite C1, thus s̃/s → 1 as s ↓ 0. Lebesgue’s
differentiation theorem (see e.g. [4, Th. 2.9.5]) implies that
|β−x| ≤ 2(s̃− y)
(4(s̃− y)) d−12
= µd−1(B
d−1)f(−x) = π
Γ(d+1
f(−x) (3.2)
for µd−1-almost every x ∈ Sd−1 and any y ∈ [0, s̃]. Integration over all
x ∈ Sd−1 with respect to f yields
(s̃− y)−
|β−U1| ≤ 2(s̃− y)
where
Γ(d+1
f(x)f(−x)µd−1(dx),
and hence with (3.1)
P {‖ξ1 − ξ2‖ ≥ 2− s}
(s̃− η1 − η2)
2 1{η1 + η2 ≤ s̃}
) = c.
If α = 0, then P {ηi = 0} = a, i = 1, 2, and thus
s̃−γP {‖ξ1 − ξ2‖ ≥ 2− s} = ca2 = σ1.
If α > 0,
P {‖ξ1 − ξ2‖ ≥ 2− s}
∫ s̃−y1
(s̃− y1 − y2)
2 dF (y2)dF (y1)
and substituting vi = yi/s̃, i = 1, 2, yields
P {‖ξ1 − ξ2‖ ≥ 2− s}
= ca2α2
∫ 1−v1
(1− v1− v2)
2 (v1v2)
α−1dv2dv1.
By Dirichlet’s Formula, the double integral equals
Γ2(α)Γ(d+1
Γ(d+1
+ 2α)
and the proof is complete.
Proof of Theorem 3.1. Plugging the transformation zn(t) = 2− tn−2/γ , t > 0
into Corollary 2.2 and using the tail probabilities given in Lemma 3.2, we
P {‖ξ1 − ξ2‖ > zn(t)} =
tγ , t > 0.
Hence condition (2.2) holds for all t > 0. The more extensive part of the
proof aims to show that (2.3) holds. Let βx and β
x be the smaller central
angles between U2 and x ∈ Sd−1 and between U3 and x ∈ Sd−1. Further
let η1, η2 and η3 be independent random variables with distribution F . Put
sn = tn
−2/γ . Following the proof of Lemma 3.2
P {‖ξ1 − ξ2‖ > zn(t), ‖ξ1 − ξ3‖ > zn(t)}
|β−U1| ≤ 2s
n , |β ′−U1| ≤ 2s
n , ηi ≤ sn, i = 1, 2, 3
|β−x| ≤ 2s
f(x)µd−1(dx)1{ηi ≤ sn, i = 1, 2, 3}
≤ CE(sd−1n 1{ηi ≤ sn, i = 1, 2, 3}), (3.3)
where the last step follows from (3.2) and C is a suitable finite positive
constant. If α = 0, then P {ηi = 0} = a, i = 1, 2, 3, and we obtain
n3P {‖ξ1 − ξ2‖ > zn(t), ‖ξ1 − ξ3‖ > zn(t)}
≤ Ca3 lim
n3sd−1n = Ca
3td−1 lim
n−1 = 0.
If α > 0, we derive from (3.3) that
P {‖ξ1 − ξ2‖ > zn(t), ‖ξ1 − ξ3‖ > zn(t)}
sd−1n dF (y3)dF (y2)dF (y1)
and substituting vi = yi/sn, i = 1, 2, 3, yields
n3P {‖ξ1 − ξ2‖ > zn(t), ‖ξ1 − ξ3‖ > zn(t)}
≤ Ca3 lim
sd−1+3αn = Ca
3td−1+3α lim
d−1+4α = 0.
The rate of convergence is determined via (2.5).
4 Largest scalar product
Besides the Euclidean metric, the scalar product is another symmetric kernel
on Rd × Rd. The behavior of its largest value
Hn = max
1≤i<j≤n
〈ξi, ξj〉
within a sample of points in Bd is determined in the next result.
Theorem 4.1. Let ξ1, ξ2, . . . be i.i.d. points in B
d, d ≥ 2, such that
ξi = ‖ξi‖Ui, i ≥ 1, where Ui and ‖ξi‖ are independent and Ui ∈ Sd−1. Assume
that the distribution function F of 1− ‖ξ1‖ satisfies
s−αF (s) = a ∈ (0,∞)
for some α ≥ 0. Further assume that U1 has a square-integrable density f
on Sd−1 with respect to µd−1. Then
n2/γ(1−Hn) ≤ t
= 1− exp
for t > 0, where
γ = (d− 1)/2 + 2α
2 a2Γ2(α + 1)
Γ(d+1
+ 2α)
f 2(x)µd−1(dx).
The rate of convergence for t < ∞ is O(n−
d−1+4α ).
Lemma 4.2. If the conditions of Theorem 4.1 hold, then
s−γP {〈ξ1, ξ2〉 ≥ 1− s} = σ2.
Proof. If βx is the smaller central angle between U2 and x ∈ Sd−1 and η is
distributed as 1− ‖ξ1‖‖ξ2‖, then
P {〈ξ1, ξ2〉 ≥ 1− s} = P {cos βU1 ≥ (1− s)/(1− η), η ≤ s} .
Expanding cos βU1 about 0 yields for all sufficiently small s
P {〈ξ1, ξ2〉 ≥ 1− s} = P
|βU1| ≤ (2(s̃− η))
2 , η ≤ s̃
, (4.1)
where |s̃−s| ≤ C1s2 for some finite C1, and thus s̃/s → 1 as s ↓ 0. Lebesgue’s
differentiation theorem (see e.g. [4, Th. 2.9.5]) implies that
|βx| ≤ (2(s̃− y))
(2(s̃− y)) d−12
= µd−1(B
d−1)f(x) =
Γ(d+1
f(x). (4.2)
for µd−1-almost every x ∈ Sd−1 and any y ∈ [0, s̃]. Integration over all
x ∈ Sd−1 with respect to f yields
(s̃− y)−
|βU1| ≤ (2(s̃− y))
Γ(d+1
f 2(x)µd−1(dx),
and by (4.1) we obtain
P {〈ξ1, ξ2〉 ≥ 1− s}
(s̃− η)
2 1{η ≤ s̃}
If α = 0, then P {η = 0} = a2 and hence
s−γP {〈ξ1, ξ2〉 ≥ 1− s} = ca2 = σ2.
If α > 0, then P {〈ξ1, ξ2〉 ≥ 1− s} equals asymptotically, as s ↓ 0, to
(1−s̃)/y1
(s̃− 1 + y1y2)
2 dF (1− y2)dF (1− y1).
By substituting v1 = (1− y1)/s̃ and v2 = (1− y2)/(1− (1− s̃)/y1)) the last
expression equals asymptotically, as s ↓ 0, to
ca2α2
1− v1
1− s̃v1
s̃− 1 + (1− s̃v1)(1− s̃v2
1− v1
1− s̃v1
vα−11 v
2 dv2dv1.
Hence
s−γP {〈ξ1, ξ2〉 ≥ 1− s}
= ca2α2
(1− v1)
+αvα−11 dv1
(1− v2)
2 vα−12 dv2
= ca2α2B((d+ 1)/2 + α, α)B((d+ 1)/2, α) = σ2.
Proof of Theorem 4.1. An application of Corollary 2.2 yields, together with
the transformation zn = 1− tn−2/γ , t > 0, and Lemma 4.2 the limit
P {〈ξ1, ξ2〉 ≥ zn(t)} =
hence (2.2) holds for any t > 0 and it remains to check (2.3). Put sn = tn
and let βx and β
x be the smaller central angles between U2 and x ∈ Sd−1 and
between U3 and x. Following the proof of Lemma 4.2
P {〈ξ1, ξ2〉 ≥ zn(t), 〈ξ1, ξ3〉 ≥ zn(t)}
|βU1 | ≤ (2sn)
2 , |β ′U1| ≤ (2sn)
2 , ‖ξi‖ ≥ zn(t), i = 1, 2, 3
|βx| ≤ (2sn)
f(x)µd−1(dx)1{‖ξi‖ ≥ zn(t), i = 1, 2, 3}
≤ CE(sd−1n 1{‖ξi‖ ≥ zn(t), i = 1, 2, 3}), (4.3)
where the last step follows from (4.2) and C is a suitable finite positive
constant. If α = 0, then P {‖ξi‖ = 1} = α, i = 1, 2, 3, and hence
n3P {〈ξ1, ξ2〉 ≥ zn(t), 〈ξ1, ξ3〉 ≥ zn(t)}
≤ Ca3 lim
n3sd−1n = Ca
3td−1 lim
n−1 = 0.
If α > 0, then (4.3) is bounded from above by
sd−1n dF (y3)dF (y2)dF (y1)
and substituting vi = yi/sn, i = 1, 2, 3, yields finally
n3P {〈ξ1, ξ2〉 ≥ zn(t), 〈ξ1, ξ3〉 ≥ zn(t)}
≤ Ca3 lim
sd−1+3αn = Ca
3td−1+3α lim
d−1+4α = 0,
and the rate of convergence is determined via (2.5).
5 Smallest spherical distance
A nice application of Theorem 4.1 comes from the field of directional statis-
tics. The following theorem determines the limiting behavior of the smallest
spherical distance
Sn = min
1≤i<j≤n
within i.i.d. points U1, U2, . . . on S
d−1, where βi,j denotes the smaller of the
two central angles between Ui and Uj . In other words, Sn equals the smallest
central angle formed by point pairs within the sample.
Theorem 5.1. Let U1, U2 . . . be i.i.d. points on S
d−1, d ≥ 2, having square-
integrable density f on Sd−1 with respect to µd−1. Then
n2/(d−1)Sn ≤ t
= 1− exp
for any t > 0, where
Γ(d+1
f 2(x)µd−1(dx)
The rate of convergence is O(n− 12 ) for finite t.
If the points are uniformly distributed on Sd−1, then Theorem 5.1 applies
f 2(x)µd−1(dx) =
2πd/2
If the points on Sd−1 follow the von Mises-Fisher distribution as introduced
in Section 3, then
f 2F (x)µd−1(dx) = C
d(κ)/Cd(2κ).
In dimension 2, Sn equals the minimal spacing, i.e. the smallest arc length
between the “order” statistics.
Proof of Theorem 5.1. Clearly, the relation cos βi,j = 〈Ui, Uj〉 holds for all
pairs of i and j between 1 and n. Since the cosine function is continuous and
monotone strictly decreasing on (0, π) and by the fact that
2 arccos(1− s) =
it follows that
n2/(d−1)Sn ≤ t
= lim
1≤i<j≤n
βi,j ≤ tn−2/(d−1)
= lim
1≤i<j≤n
βi,j ≤ arccos
1− t2n−4/(d−1)/2
= lim
1≤i<j≤n
〈Ui, Uj〉 ≥ 1− t2n−4/(d−1)/2
Theorem 4.1 yields the proof with α = 0 and a = 1.
6 Largest perimeter
Finally we present a result for a U -max-statistic of degree 3, namely the limit
law for the largest value
1≤i<j<ℓ≤n
peri(Ui, Uj , Uℓ)
of the perimeter peri(Ui, Uj , Uℓ) of all triangles formed by triplets of indepen-
dent and uniformly distributed points U1, U2, . . . on the unit circle S. The
random triameter (see [6]) of the sample is the largest perimeter up to a
factor 3, hence the limit law for the triameter of U1, U2, . . . can be derived
immediately.
Theorem 6.1. If U1, U2, . . . are independent and uniformly distributed points
on S, then
3−Hn) ≤ t
= 1− exp
for all t > 0 and for finite t the rate of convergence is O(n− 12 ).
Lemma 6.2. If U1, U2, U3 are independent and uniformly distributed points
on S, then
peri(U1, U2, U3) ≥ 3
Proof. Clearly, peri(x1, x2, x3) is maximal for x1, x2, x3 being the vertices of
an equilateral triangle on S, which has perimeter 3
3. If β1 and β2 are the
angles (measured counter-clockwise) between U1 and U2 and between U2 and
U3 respectively. By rotational symmetry, β1 and β2 are independent and
uniformly distributed on [0, 2π]. The cosine theorem yields for sufficiently
small s
peri(U1, U2, U3) ≥ 3
(2− 2 cosβ1)
2 + (2− 2 cosβ2)
+ (2− 2 cos(2π − β1 − β2))
2 ≥ 3
3− s, β1, β2 ∈ [2π/3± cs]
, (6.1)
where cs = C1
s and C1 is a suitable finite positive constant. If η1 and η2 are
independent and uniformly distributed on [−cs, cs], then the last expression
equals
(2− 2 cos(2π/3 + η1))
2 + (2− 2 cos(2π/3 + η2))
+ (2− 2 cos(2π/3− η1 − η2))
2 ≥ 3
P {β1 ∈ [2π/3± cs]}2 .
By series expansion, (6.1) equals
2(cs/π)
η21 + η
2 + (η1 + η2)
2 ≤ 8s̃/
(6.2)
= 2(cs/π)
−η1/2± (4s̃/
3− 3η21/4)
= π−2
s̃/33/4
s̃/33/4
(4s̃/
3− 3y2/4)
2dy =
where |s̃ − s| ≤ C2s3/2 for some finite C2, and the proof follows by the fact
that s̃/s → 1 as s ↓ 0.
Proof of Theorem 6.1. Plugging into Corollary 2.2 the transformation
zn(t) = 3
3− tn−3 together with the result of Lemma 6.2 yields
P {peri(U1, U2, U3) > zn(t)} =
hence (2.2) is satisfied for all t > 0. Condition (2.3) does not hold, so we use
the weaker requirement (2.6) to replace (2.3), i.e. we need to show that
n5P {peri(U1, U2, U3) > zn(t), peri(U1, U4, U5) > zn(t)} = 0 (6.3)
n4P {peri(U1, U2, U3) > zn(t), peri(U1, U2, U4) > zn(t)} = 0. (6.4)
For (6.3), we follow the proof of Lemma 6.2. In addition, denote by β ′1 and β
the random angles between U1 and U4 and between U4 and U5 respectively.
It follows immediately by rotational symmetry, that β1, β2, β
1 and β
2 are in-
dependent and uniformly distributed on [0, 2π]. With the help of Lemma 6.2
we check (6.3) by
n5P {peri(U1, U2, U3) > zn(t), peri(U1, U2, U4) > zn(t)}
≤ C1 lim
n5P {peri(U1, U2, U3) > zn(t)}2 = C2t2 lim
n−1 = 0,
where C1 and C2 are suitable finite positive constants. To show (6.4) we
follow the proof of Lemma 6.2 and introduce the random variable η3, which is
independent of η1 and η2 and uniformly distributed on [−cs, cs]. For suitable
finite positive constants C3, C4 and C5
P {peri(U1, U2, U3) > zn(t), peri(U1, U2, U4) > zn(t)}
≤ C3c3sP
η2, η3 ∈
−η1/2± (4s̃/
3− 3η21/4)
= C4c
s̃/33/4
s̃/33/4
−y/2± (4s̃/
3− 3y2/4)
dy = C5s̃
and with s = tn−3 and s/s̃ → 1 as s → 0
n4P {peri(U1, U2, U3) > zn(t), peri(U1, U2, U4) > zn(t)}
≤ C5t3/2 lim
2 = 0.
Hence (6.4) holds and the rate of convergence is determined by Remark 2.
Acknowledgements
The authors would like to thank Prof. Dr. N. Henze and Prof. Dr. I. Molchanov
for their invaluable help concerning this and many other problems.
References
[1] M. J. B. Appel, C. A. Najim, and R. P. Russo. Limit laws for the
diameter of a random point set. Adv. Appl. Probab., 34:1–10, 2002.
[2] M. J. B. Appel and R. P. Russo. Limiting distributions for the maximum
of a symmetric function on a random point set. J. Theor. Probab.,
19:365–375, 2006.
[3] A. D. Barbour, L. Holst, and S. Janson. Poisson Approximation. Claren-
don Press, Oxford, 1992.
[4] H. Federer. Geometric Measure Theory. Springer, Berlin, 1969.
[5] J. Galambos. The Asymptotic Theory of Extreme Order Statistics. Wi-
ley, New York, 1978.
[6] K. Grove and S. Markvorsen. Curvature, triameter, and beyond. Bull.
Amer. Math. Soc., 27:261–265, 1992.
[7] N. Henze and T. Klein. The limit distribution of the largest interpoint
distance from a symmetric Kotz sample. J. Multiv. Anal., 57:228–239,
1996.
[8] W. Hoeffding. A class of statistics with asymptotically normal distribu-
tion. Ann. Math. Statist., 19:293–325, 1948.
[9] W. Lao. The limit law of the maximum distance of points in a sphere
in Rd. Technical report, University of Karlsruhe, Karlsruhe, Germany,
2006.
[10] P. C. Matthews and A. L. Rukhin. Asymptotic distribution of the normal
sample range. Ann. Appl. Probab., 13:454–466, 1993.
[11] M. Mayer and I. Molchanov. Limit theorems for the diameter of a
random sample in the unit ball. Extremes. To appear.
[12] B. W. Silverman and T. C. Brown. Short distances, flat triangles and
poisson limits. J. Appl. Probab., 15:815–825, 1978.
	Introduction
	Poisson approximation for U-max-statistics
	Largest interpoint distance
	Largest scalar product
	Smallest spherical distance
	Largest perimeter
