arXiv:1604.07104v1 [] 25 Apr 2016

The limit of finite sample breakdown point of
Tukey’s halfspace median for general data
Xiaohui Liua,b , Shihua Luoa,b , Yijun Zuoc
a

School of Statistics, Jiangxi University of Finance and Economics, Nanchang, Jiangxi 330013, China
b
Research Center of Applied Statistics, Jiangxi University of Finance and Economics, Nanchang,
Jiangxi 330013, China
c
Department of Statistics and Probability, Michigan State University, East Lansing, MI, 48823, USA

November 9, 2017

Summary
Under special conditions on data set and underlying distribution, the limit of finite sample
breakdown point of Tukey’s halfspace median ( 13 ) has been obtained in literature. In this paper,
we establish the result under weaker assumption imposed on underlying distribution (halfspace
symmetry) and on data set (not necessary in general position). The representation of Tukey’s
sample depth regions for data set not necessary in general position is also obtained, as a byproduct of our derivation.
Key words: Tukey’s halfspace median; Limit of finite sample breakdown point; Smooth condition;
Halfspace symmetry
2000 Mathematics Subject Classification Codes: 62F10; 62F40; 62F35

1

Introduction
To order multidimensional data, Tukey (1975) introduced the notion of halfspace depth. The

halfspace depth of a point x in Rd (d ≥ 1) is defined as
D(x , Fn ) =

inf

u ∈S d−1

Pn (u ⊤ X ≤ u ⊤ x ),

where S d−1 = {v ∈ Rd : kv k = 1} with k · k being the Euclidean distance, Fn denotes the
empirical distribution related to the random sample X n = {X1 , X2 , · · · , Xn } from X ∈ Rd , and
Pn is the corresponding empirical probability measure.
With this notion, a natural definition of multidimensional median is the point with maximum
halfspace depth, which is called Tukey’s halfspace median (HM ). To avoid the nonuniqueness,
HM (θ̂n ) is defined to be the average of all points lying in the median region M(X n ), i.e.,
θ̂n := T ∗ (X n ) = Ave {x : x ∈ M(X n )} ,
where M(X n ) = {x ∈ Rn : D(x , Fn ) = supz ∈Rd D(z , Fn )}, which is the inner-most region
among all τ -trimmed depth regions:
n
o
Dτ (X n ) = x ∈ Rd : D(x , Fn ) ≥ τ ,

for ∀τ ∈ (0, λ∗ ] with λ∗ = D(θ̂n , Fn ).

When d = 1, HM reduces to the ordinary univariate median, the latter has the most outstanding property, its best breakdown robustness. A nature question then is: will HM inherit
the best robustness of the univariate median?
Answers to this question have been given in the literature, e.g. Donoho and Gasko (1992),
Chen (1995) and Chen and Tyler (2002) and Adrover and Yohai (2002). The latter two obtained
the asymptotic breakdown point ( 13 ) under the maximum bias framework, whereas the former

1

two obtained the limit of finite sample breakdown point (as n → ∞) under the assumption of
absolute continuity and central or angular symmetry of underlying distribution.
Among many gauges of robustness of location estimators, finite sample breakdown point is
the most prevailing quantitative assessment. Formally, for a given sample X n of size n in Rd ,
the finite sample addition breakdown point of an location estimator T at X n is defined as:


m
n
m
n
n
: sup kT (X ∪ Y ) − T (X )k = ∞ ,
ε(T, X ) = min
1≤m≤n n + m Y m
where Y m denotes a data set of size m with arbitrary values, and X n ∪ Y m the contaminated
sample by adjoining Y m to X m .
Absolutely continuity guarantees the data set is in general position (no more than d sample
points lie on a (d − 1)-dimensional hyperplane (Mosler et al., 2009)) almost surely. In practice,
the data set X n is most likely not in general position. This is especially true when we are
considering the contaminated data set.
Unfortunately, most discussions in literature on finite sample breakdown point is under the
assumption of data set in general position. Dropping this unrealistic assumption is very much
desirable in the discussion. In this paper we achieve this. Furthermore, we also relax the
angular symmetry (Liu, 1988, 1990) assumption in Chen (1995) to a weaker version of symmetry:
halfspace symmetry (Zuo and Serfling, 2000). X ∈ Rd is halfspace symmetrical about θ0 if
P (X ∈ Hθ0 ) ≥ 1/2 for any halfspace Hθ0 containing θ0 . Minimum symmetry is required to
guarantee the uniqueness of underlying center θ in Rd .
Without the ‘in general position’ assumption, deriving the limit of finite sample breakdown
point of HM is quite challenging. We will consider this issue under the combination of halfspace
symmetry and a weak smooth condition (see Section 2 for details). Recently, Liu et al. (2015b)
have derived the exact finite sample breakdown point for fixed n. Their result nevertheless
depends on the assumption that X n is in general position and could not be directly utilized under
the current setting, because when the underlying F only satisfies the weak smooth condition,
the random sample X n generated from F may not be in general position in some scenarios.
Hence, we have to extend Liu et al. (2015b)’s results.
Our proofs in this paper heavily depend on the representation of halfspace median region
while the existing one in the literature is for the data set in general position. Hence, we have
to establish the representation of Tukey’s depth region (as the intersection of a finite set of
halfspaces) without in general position assumption, which is a byproduct of our proofs. We

2

only need X n to be of affine dimension d which is much weaker than the existing ones in
(Paindaveine and Šiman, 2011).
The rest paper is organized as follows. Section 2 presents a weak smooth condition and shows
it is weaker than the absolute continuity and the interconnection with other notions. Section
3 establishes the representation of Tukey’s sample depth regions without in-general-position
assumption. Section 4 derives the limiting breakdown point of HM. Concluding remarks end
the paper.

2

A weak smooth condition
In this section, we first present the definition of smooth condition (SC ), and then investigate

its relationship with some other conditions, i.e., absolute continuity and continuous support,
commonly assumed in the literature dealing with HM. The connection between SC and the
continuity of the population version of Tukey’s depth function D(x , F ) is also investigated.
Let P be the probability measure related to F . We say a probability distribution F in Rd of
a random vector X is smooth at x 0 ∈ Rd if P (X ∈ ∂H) = 0 for any halfspace H with x 0 on its
boundary ∂H. F is globally smooth over Rd if F is smooth at ∀x ∈ Rd .
Recall that a distribution F is absolutely continuous over Rd if for ∀ε > 0 there is a positive
number δ such that P (X ∈ A) < ε for all Borel sets A of Lebesgue measure less than δ. One
can easily show that absolute continuity implies global smoothness. Nevertheless, the vice versa
is false. The counterexample can be found in the following.
Counterexample. Let S1 = {x ∈ Rd : kx k ≤ 1}, S2 = {x ∈ Rd : kx k = 2}, and
Y = ηZ1 + (1 − η)Z2 , where η ∼ Bernoulli(0.5), and η, Z1 , Z2 are mutually independent. If Z1 ,
Z2 ∈ Rd are uniformly distributed over S1 and S2 , respectively, then it is easy to show that the
distribution of Y is not absolutely continuous, but smooth at ∀x ∈ Rd .
Furthermore, observe that a distribution F is said to have contiguous support if there is no
intersection of any two halfspaces with parallel boundaries that has nonempty interior but zero
probability and divides the support of F into two parts (see Kong and Zuo (2010)). We can
derive that if F has contiguous support it should be globally smooth, but once again the vice
versa is false. Counterexamples can easily be constructed by following a similar fashion to the
above one.
Global smoothness is a quite desirable sufficient condition on F if one desires the global
continuity of D(x , F ) as shown in the following lemma.
3

Lemma 1. If F is globally smooth, then D(x , F ) is globally continuous in x over Rd .
When F is globally smooth, we now show that if there ∃x 0 ∈ Rd such that

Proof.

lim D(x , F ) 6= D(x 0 , F ), then it will lead to a contradiction.

x →x 0

By noting lim D(x , F ) 6= D(x 0 , F ), we claim that there must exist a sequence {x k }∞
k=1
x →x 0

such that lim x k = x 0 but lim D(x k , F ) = d∗ 6= D(x 0 , F ). (If lim D(x k , F ) is divergent,
k→∞

k→∞

k→∞

by observing {D(x k , F )}∞
k=1 ⊂ [0, 1], we utilize one of its convergent subsequence instead.) For
simplicity, hereafter denote dk = D(x k , F ) for k = 0, 1, · · · , and assume d∗ < d0 if no confusion
arises.
Observe that S d−1 is compact. Hence, for each x k , there ∃u k ∈ S d−1 satisfying P (u ⊤
kX ≤
∞
d−1 is bounded, it should contain a convergent subsequence
u⊤
k x k ) = dk . Since {u k }k=1 ⊂ S


d0 −d∗
with
lim
u
=
u
.
For
this
u
and
∀ε
∈
0,
{u kl }∞
, there ∃δ0 > 0 such that
0
0
0
k
l
l=1
2
l→∞

P (X ∈ B(u 0 , δ0 )) < ε0

(1)

following from the global smoothness. Here B(u, c) = {z ∈ Rd : u ⊤ x 0 − c < u ⊤ z ≤ u ⊤ x 0 } for
∀u ∈ S d−1 and ∀c ∈ R1 .
⊤
⊤
⊤
On the other hand, lim P (u ⊤
kl X ≤ u kl x kl ) = d∗ < d0 ≤ P (u kl X ≤ u kl x 0 ). Using this and
l→∞

∞
the convergence of both {x kl }∞
l=1 and {u kl }l=1 , an element derivation leads to that: For δ0 given

above, there ∃M > 0 such that
⊤
⊤
P (X ∈ B(u kl , δ0 )) ≥ P (u ⊤
kl X ∈ (u kl x kl , u kl x 0 ]) >

d0 − d∗
> 0,
2

for ∀kl > M.

This clearly will contradict with (1), because B(u 0 , δ0 ) ∩ B(u kl , δ0 ) → B(u 0 , δ0 ) as u kl → u 0
when kl → ∞.



Lemma 1 indicates that, when F is globally smooth, D(x , F ) should be globally continuous
over Rd , but the vice versa is not clear. Fortunately, an equivalent relationship between the
smoothness of F and the continuity of D(x , F ) can be achieved at a special point as stated in
the following lemma.
Lemma 2. When F is halfspace symmetrical about θ0 , then the following statements are
equivalent:
(i) F is smooth at θ0 ;
(ii) D(x , F ) is continuous at θ0 with respect to x .

4

Proof. Similar to Lemma 1, one can show: (i) is true ⇒ (ii) is true. In the following, we
will show: (i) is false ⇒ (ii) is also false.
If (i) is false, we claim that there exists a halfspace H such that m0 := P (X ∈ ∂H) > 0.
Denote m+ = P (X ∈ H \ ∂H) and m− = P (X ∈ Hc ). Without confusion, assume that
m− ≤ m+ and the normal vector u 0 of ∂H points into the interior of H. Observe that D(x , F ) ≤
⊤
P (u ⊤
0 X ≤ u0 x ) ≤

1−m0
2

< 1/2 for ∀x ∈ Hc , i.e., the complementary of H. Hence, for any

c
sequence {x k }∞
k=1 ⊂ H such that lim x k = θ0 , we have lim sup D(x k , F ) ≤
k→∞

k→∞

1−m0
2 .

This in

turn implies that D(x , F ) is discontinuous at θ0 because D(θ0 , F ) ≥ 1/2 when F is halfspace
symmetrical about θ0 .



Summarily, relying on the discussions above, we obtain the following relationship schema
when F is halfspace symmetrical about θ0 .

=⇒

F is globally smooth

F is smooth at θ0

⇐

=⇒

⇒

Continuous support

⇔

Absolute continuity

D(x , F ) is globally continuous

⇒

D(x , F ) is continuous at θ0

Since the assumption that F is smooth at θ0 is quite general, we call it weak smooth condition
throughout this paper.

3

Representation of Tukey’s depth regions
To prove the main result, we need to know the representation of M(X n ). When X n is in

general position, this issue has been considered by Paindaveine and Šiman (2011). Nevertheless,
their result can not be directly applied to prove our main theorem, because when the underlying
distribution F only satisfies the weak smooth condition, the sample X n may not be in general
position. Hence, we have to solve this problem before proceeding further.
For convenience, we introduce the following notations. For ∀u ∈ S d−1 (d ≥ 2) and ∀τ ∈ (0, 1),
denote the (τ, u )-halfspace as
n
o
Hτ (u) = x ∈ Rd : u ⊤ x ≥ qτ (u )
with complementary Hτc (u) = {x ∈ Rd : u ⊤ x < qτ (u)} and boundary ∂Hτ (u) = {x ∈ Rd :
u ⊤ x = qτ (u )}, where qτ (u) = inf{t ∈ R1 : Fu n (t) ≥ τ }, and Fu n denotes the empirical
distribution of {u ⊤ X1 , u ⊤ X2 , · · · , u ⊤ Xn }. Obviously, u points into the interior of Hτ (u), and
5

(see e.g. Kong and Mizera (2012))
Dτ (X n ) =

\

Hτ (u ).

(2)

u∈S d−1

In the following, a halfspace Hτ (u ) is said to be τ -irrotatable if:
(a) nPn (X ∈ Hτc (u)) ≤ ⌈nτ ⌉ − 1, i.e., Hτ (u) cuts away at most ⌈nτ ⌉ − 1 sample points.
(b) ∂Hτ (u ) contains at least d sample points, and among them there exist d − 1 points, which
can determine a (d − 2)-dimensional hyperplane Vd−2 such that: it is possible to make
Hτ (u ) cutting away more than ⌈nτ ⌉ − 1 sample points only through deviating it around
Vd−2 by an arbitrary small scale.
Here ⌈·⌉ denotes the ceiling function, and Vd−2 is a singleton if d = 2. To gain more insight, we
provide a 2-dimensional example in Figure 1. In this example, X1 , X2 , X3 and X4 are clearly
not in general position, and H(u) is 1/2-irrotatable.

X

2

X

3

x

2

u

H(u)
X

X

1

4

x

1

Figure 1: Shown is an example of the τ -irrotatable halfspace. Observe that: (a) H(u) cuts
away no more than 1 sample point, i.e., X1 , and (b) ∂H(u) passes through at least 2 (= d)
sample points, i.e., X2 , X3 , X4 , and it is possible to make H(u) cutting away more than
⌈4 × 1/2⌉ − 1 = 1 sample points, i.e., X1 and X2 , through deviating it by an arbitrary small
scale around X3 . Hence, H(u) is 1/2-irrotatable.
Remarkably, if a τ1 -irrotatable halfspace cuts away strictly less than ⌈nτ1 ⌉ − 1 sample points,
it also should must be τ2 -irrotatable for some τ2 < τ1 .
This τ -irrotatable property is quite important for the following lemma, which further plays
a key role in the proof of Lemma 4.

6

Lemma 3. Suppose X n = {X1 , X2 , · · · , Xn } ⊂ Rd (d ≥ 2) is of affine dimension d. Then
for ∀τ ∈ (0, λ∗ ], we have
Dτ (X n ) =

m
\τ

Hτ (µi ),

i=1

where mτ denotes the number of all τ -irrotatable halfspaces Hτ (µi ).
Proof. By (2), Dτ (X n ) ⊂
T τ
Dτ (X n ) ⊃ m
i=1 Hτ (µi ).

Tmτ

i=1 Hτ (µi )

holds trivially. Hence, in the sequel we only prove:

Tmτ

such that x 0 ∈
/ Dτ (X n ), i.e., D(x 0 , Fn ) < τ , we now show that
T τ
this will lead to a contradiction. For simplicity, hereafter denote Vn (τ ) = m
i=1 Hτ (µi ).
If there ∃x 0 ∈

i=1 Hτ (µi )

Since Pn (·) takes values only on {0, 1/n, 2/n, · · · , n/n}, there ∃u 0 ∈ S d−1 such that
⊤
Pn (u ⊤
0 X ≤ u 0 x 0 ) = D(x 0 , Fn ).

(3)

Trivially, when X n is of affine dimension d, we have: Vn (τ ) ⊂ cov(X n ) for ∀τ ∈ (0, λ∗ ], where
cov(X n ) denotes the convex hull of X n . Hence, for x 0 ∈ Vn (τ ) and u 0 given in (3), there must
exist an integer k0 ∈ {1, 2, · · · , nλ∗ } and a permutation π0 := (i1 , i2 , · · · , in ) of (1, 2, · · · , n) such
that
⊤
⊤
⊤
⊤
⊤
u⊤
0 Xi1 ≤ u 0 Xi2 ≤ · · · ≤ u 0 Xik0 ≤ u 0 x 0 < u 0 Xik0 +1 ≤ · · · ≤ u 0 Xin .

(4)

Obviously, k0 /n < τ due to D(x 0 , Fn ) < τ , and hence k0 ≤ ⌈nτ ⌉ − 1.
Note that replacing u ∈ S d−1 with u ∈ Rd \ {0} does no harm to the definition of both
D(x , Fn ) and Dτ (X n ) (Liu and Zuo, 2014). Hence, in the sequel we pretend that the constraint
on u is u ∈ Rd \ {0} instead.
Denote C(π0 ) = {v ∈ Rd \ {0} : v ⊤ Xit ≤ v ⊤ Xik0 +1 for any 1 ≤ t ≤ k0 , and v ⊤ Xik0 +1 ≤
v ⊤ Xis for any k0 + 2 ≤ s ≤ n}. Obviously, u 0 ∈ C(π0 ), and C(π0 ) is a convex cone.
d
v
Let U := {νj }m
j=1 = {z ∈ R \ {0} : kz k = 1, z lies in a vertex of C(π0 )} with mv being U ’s

cardinal number. Clearly, mv < ∞ and ν1 , ν2 , · · · , νmτ are non-coplanar when X n is of affine
dimension d. By the construction of C(π0 ), each ν ∈ U determines a halfspace H(ν) such that:
(p1) ν is normal to ∂H(ν) and points into the interior of H(ν), (p2) H(ν) cuts away at most
⌈nτ ⌉ − 1 sample points, because Xik0 +1 , Xik0 +2 , · · · , Xin ∈ Hν , (p3) ∂H(ν) contains at least d
sample points, which are of affine dimension d − 1 due to ν is a vertex of C(π0 ).

7

⊤
⊤
⊤
For U , we claim that: there ∃v 0 ∈ U satisfying v ⊤
0 x 0 < v 0 Xik0 +1 . If not, νj x 0 ≥ νj Xik0 +1

for all j = 1, 2, · · · , mv . Hence,

⊤

⊤
mv
mv
X
X

ω j νj  x 0 ≥ 
ωj νj  Xik0 +1 ,
j=1

where

Pmv

j=1 ωj

j=1

= 1 with ωj ≥ 0 for all j = 1, 2, · · · , mv . This contradicts with (4) by noting

that C(π0 ) is convex and u 0 ∈ C(π0 ).
⊤
/ H(v 0 ). We have:
However, v ⊤
0 x 0 < v 0 Xik0 +1 implies x 0 ∈

S1. H(v 0 ) satisfies (b) given in Page 6: By (p1)-(p3), H(v 0 ) is τ -irrotatable, contradicting
with the definition of Vn (τ ).
S2. H(v 0 ) does not satisfy (b): Among all sample points contained by ∂H(v 0 ), there must
exist d − 1 points that determine a (d − 2)-dimensional hyperplane, around which we can
obtain a τ -irrotatable halfspace through rotating H(v 0 ).
(If not, there will be a contradiction: By (p2), there ∃Xj1 , Xj2 , · · · , Xjd ∈ ∂H(v 0 ),
d 
which are of affine dimension d − 1. Denote W1 , W2 , · · · , Wd respectively as d−1
hy-

perplanes that passing through all (d − 2)-dimensional facets of the simplex formed by

Xj1 , Xj2 , · · · , Xjd . Then similar to Part (II) of the proof of Theorem 1 in Liu et al. (2015a),
it is easy to check that:
for ∀y ∈ Rd , y can not simultaneously lie in all W1 , W2 , · · · , Wd .
Without confusion, assume y ∈
/ W1 and Xj1 ∈ W1 . Observe that no τ -irrotatable halfspace is available through rotating H(v 0 ) around W1 . Hence, for ∀δ > 0,
c
c
)} < ⌈nτ ⌉ − 1,
max{nPn (X ∈ Hδ+
), nPn (X ∈ Hδ−

(5)

⊤
d
⊤
⊤
where Hδ+ = {z ∈ Rd : u ⊤
+ z ≥ u + Xj1 }, and Hδ− = {z ∈ R : u − z ≥ u − Xj1 } with

u + = v 0 + δu ∗ and u − = v 0 − δu ∗ , where u ∗ ∈ S d−1 is orthogonal to both v 0 and W1 .
c or y ∈ Hc for ∀δ > 0, we obtain D(y, F ) < (⌈nτ ⌉ − 1)/n ≤ τ .
Since either y ∈ Hδ+
n
δ−

This is impossible because Dn (τ ) is nonempty for ∀τ ∈ (0, λ∗ ].)
Furthermore, it is easy to show that: if there is a τ -irrotatable halfspace, say H1 , obtained
through rotating H(v 0 ) around one (d − 2)-dimensional hyperplane clockwise (without
confision), then there would be an another τ -irrotatable halfspace, say H2 , by rotating
H(v 0 ) anti-clockwise. By noting Hc (v 0 ) ⊂ H1c ∪ H2c , we can obtain either x 0 ∈ H1c or
x 0 ∈ H2c , which contradicts with the definition of Vn (τ ).
8

Hence, there is no such x 0 that x 0 ∈ Vn (τ ), but x 0 ∈
/ Dτ (X n ).
This completes the proof of this lemma.



Remark 1. It may have long been known in the statistical community that Tukey’s sample
depth regions may be polyhedral and have a finite number of facets. The detailed character of each facet of these regions is unknown, nevertheless. When X n is in general position,
Paindaveine and Šiman (2011) have shown that each hyperplane passing through a facet of
Dτ (X n ), for ∀τ ∈ (0, λ∗ ], contains exactly d and cuts away exactly ⌈nτ ⌉ − 1 sample points; see
Lemma 4.1 in Page 201 of Paindaveine and Šiman (2011) for details. Lemma 3 generalizes their
result by removing the ‘in general position’ assumption, and indicates that such hyperplanes
contain at least d and cuts away no more than ⌈nτ ⌉ − 1 sample points.
To facilitate the understanding, we provide an illustrative example in Figure 2. In this example, there are n = 4 observations, i.e., X1 , X2 , X3 , X4 , where X3 and X4 take the same value.
Clearly, they are not in general position and of affine dimension 2. Figures 2(a)-2(b) indicate
that {X1 , X3 , X4 } determines two 1/2-irrotatable halfspaces, i.e., H1/2 (u 1 ) and H1/2 (u 2 ), satisfying H1/2 (u 1 ) ∩ H1/2 (u 2 ) = L1 . Similarly, the intersection of the halfspaces determined by
{X2 , X3 , X4 } is L2 . Hence, the median region is {x : x = X3 }. From Figure 2(b) we can see
that ∂H1/2 (u2 ) contains 3 (6= 2) and H1/2 (u2 ) cuts away 0 (6= 1) sample points, which obviously
is not in agreement with the results of Paindaveine and Šiman (2011).

4

The limiting breakdown point of HM
In this section, we will derive the limit of the finite sample breakdown point of HM when

the underlying distribution satisfies only the weak smooth condition (such a limit is also called
asymptotic breakdown point in the literature, the latter notion is based on the maximum bias
notion though, see Hampel(1968)). Since HM reduces to the ordinary univariate median for
d = 1, whose breakdown point robustness has been well studied, we focus only on the scenario
of d ≥ 2 in the sequel.

9

y

X2

c

Hτ (u1), the complementary of Hτ(u1)

X

3

X1

X

4

H *(u )
τ

H (u )
τ

1

1

x

(a) Halfspace H1/2 (u1 ), which is 1/2-irrotatable because 4Pn (X ∈ Hcτ (u1 )) ≤
⌈4τ ⌉ − 1 but 4Pn (X ∈
/ H∗τ (u1 )) = 2 > ⌈4τ ⌉ − 1 for τ = 1/2.

X

2

x2

H *(u )
τ

2

Hτ(u2)

X3

X1
X4

c

Hτ (u2), the complementary of Hτ(u2), with τ=1/2

x1

(b) Halfspace H1/2 (u2 ), which is similarly 1/2-irrotatable because 4Pn (X ∈
Hcτ (u2 )) ≤ ⌈4τ ⌉ − 1 but 4Pn (X ∈
/ H∗τ (u2 )) = 2 > ⌈4τ ⌉ − 1 for τ = 1/2

X2

x

2

L2

X3

X

1

X

4

L1

x1

(c) The intersection of lines L1 and L2 .

Figure 2: Shown are examples of the τ -irrotatable halfspaces and related HM.

10

The key idea is to obtain simultaneously a lower and an upper bound of ε(T ∗ , X n ) for fixed
n, and then prove that they tend to the same value as n → ∞. When X n is of affine dimension
d, it is easy to obtain a lower bound, i.e.,

λ∗
1+λ∗ ,

for ε(T ∗ , X n ) by using a similar strategy to

Donoho and Gasko (1992) though. Finding a proper upper bound is not trivial, nevertheless.
To this end, we establish the following lemma, which provides a sharp upper bound with its
λ∗
1+λ∗

asymptotically. For simplicity, denoting by Au an arbitrary d×
.
(d−1) matrix of unit vectors such that (u .. A ) constitutes an orthonormal basis of Rd , we define

limit coinciding with that of

u

d−1 . Correspondingly,
⊤
⊤
the Au -projections of X n as Xnu = {A⊤
u X1 , Au X2 , · · · , Au Xn } for ∀u ∈ S

let θ̂nu = T ∗ (Xnu ), λ∗u = D(θ̂nu , Fu n ), and Fu n to be the empirical distribution related to Xnu .
Lemma 4. For a given data set X n of affine dimension d, the finite sample breakdown point
of Tukey’s halfspace median satisfies
ε(T ∗ , X n ) ≤

l

inf u∈S d−1 λ∗u
.
1 + inf u∈S d−1 λ∗u

y

K

u
x

V
v
x

x0

H

Figure 3: Shown is a 3-dimensional illustration. Once y ’s are putted on ℓ, all of their projections
onto V are x0 . Hence, for any x ∈
/ ℓ, its depth with respect to X n ∪ Y m would be no more
than that of x with respect to the projections of X n ∪ Y m , because all projections of the sample
points contained by K would lie in H. Here H denotes the optimal (d − 1)-dimensional optimal
halfspace of x, and K the d-dimensional halfspace whose projection is H.
Since the whole proof of this lemma is very long, we present it in two parts. For ∀u ∈ S d−1 ,
in Part (I), we first project X n onto a (d − 1)-dimensional space Vud−1 that is orthogonal to
u, and then show that there ∃x0 ∈ Vud−1 , which can lie in the inner of the complementary of
a (d − 1)-dimensional optimal halfspace of ∀x ∈ Vud−1 \ {x0 }. Here by optimal halfspace of x
11

we mean the halfspace realizing the depth at x with respect to Xnu . Denote the line passing
through x0 and parallel to u as ℓu . In Part (II), we will show that by putting nλ∗u repetitions
of y 0 at any position on ℓu but outside the convex hull of X n , i.e., ℓu \ cov(X n ), it is possible to
obtain that supx ∈cov(X ) D(x , X n ∪ Y m ) ≤ nλ∗u . Hence, inf u∈S d−1 nλ∗u repetitions of y 0 suffice
for breaking down T ∗ (X n ∪ Y m ). See Figure 3 for a 3-dimensional illustration.
Proof of Lemma 4. Trivially, it is easy to check that, for ∀u ∈ S d−1 , Xnu is of affine
dimension d − 1 if X n is of affine dimension d.
(I). In this part, we only prove that: When the affine dimension of M(Xnu ) is nonzero
for d > 2, there ∃x0 ∈ M(Xnu ) such that Ux ∩ Hx,x0 6= ∅ for ∀x ∈ M(Xnu ) \ {x0 }, where
⊤
d−2 : v⊤ x < v⊤ x }.
Ux = {v ∈ S d−2 : Pn (v⊤ (A⊤
0
u X) ≤ v x) = D(x, Fu n )}, and Hx,x0 = {v ∈ S

That is, x0 lies in the inner of the complementary of a (d − 1)-dimensional optimal halfspace
of ∀x ∈ M(Xnu ) \ {x0 }. The rest proof follows a similar fashion to Lemmas 2-3 of Liu et al.
(2015b).
By Lemma 3, M(Xnu ) is polyhedral. Similar to Theorem 2 of Liu et al. (2015a), we can
n
⊤
obtain that, if there is a sample point Xi such that A⊤
u Xi ∈ M(Xu ), then Au Xi should be

a vertex of M(Xnu ) based on the representation of M(Xnu ) obtained in Lemma 3. Let Vu be
the set of vertexes of M(Xnu ) such that, for ∀y ∈ Vu , there is an optimal halfspace Hy of y
n
⊤
satisfying Hy ∩ M(Xnu ) = {y}. Trivially, A⊤
u Xi ∈ Vu if Au Xi ∈ M(Xu ).

If there is point in Vu that can sever as x0 , then this statement holds already. Otherwise,
find a candidate point z0 by using the following iterative procedure and then show that z0 can be
used as x0 . For simplicity, hereafter denote Az = {x ∈ Rd−1 : Ux ∩ Hx,z 6= ∅} and Bz = {x ∈
Rd−1 : Ux ∩ Hx,z = ∅} for ∀z ∈ M(Xnu ). Obviously, Az ∪ Bz = Rd−1 , Az ∩ Bz = ∅, z ∈ Bz , and
Bz ⊂ M(Xnu ).
Let z1 = T ∗ (Xnu ). Clearly, Vu ∩ Bz1 = ∅. (In fact, Vu ∩ Bz = ∅ for any z ∈ M(Xnu ) \ Vu .)
If Bz1 = {z1 }, let x0 = z0 and this statement is already true. Otherwise, similar to Lemma
2 of Liu et al. (2015b), for ∀x ∈ Bz1 \ {z1 }, we obtain: (o1) u⊤ x ≥ u⊤ z1 for ∀u ∈ Uz1 , (o2)
Ux ⊂ Uz1 , and (o3) Bx ⊂ Bz1 \ {z1 }.
Denote
g(z1 ) =

sup
v∈Uz1 ,x∈Bz1 \{z1 }

v⊤ (x − z1 ).

Clearly, g(z1 ) > 0 by (o1)-(o3). Along the same line of Liu et al. (2015b), we can find a
∞
n
series {zi }∞
i=1 ⊂ M(Xu ), if there is no m > 1 such that Bzm = {zm }, satisfying that: {zi }i=1

12

contains a convergent subsequence {zik }∞
k=1 with lim zik = z0 and lim g(zik −1 ) = 0. Trivially,
k→∞

k→∞

z0 ∈ M(Xnu ) \ Vu . (If not, it is easy to obtain a contradiction.)
Now we proceed to prove Bz0 = {z0 }. First, we show
(F1):

z0 ∈ Bzj−1 \ {zj−1 } for ∀j ∈ {ik }∞
k=1 .

If not, there must ∃ũ ∈ Uz0 satisfying ũ⊤ z0 < ũ⊤ zj−1 . For this ũ ∈ Uz0 , let (i′1 , i′2 , · · · , i′n )
⊤
∗
be the permutation of (1, 2, · · · , n) such that: (a) ũ⊤ (A⊤
u Xi′s ) ≤ ũ z0 for 1 ≤ s ≤ k , and (b)
⊤
∗
∗
∗
ũ⊤ (A⊤
u Xi′t ) > ũ z0 for k + 1 ≤ t ≤ n, where k = nλu . Denote


1
⊤
⊤
⊤
ε0 = min ∗ min ũ ((Au Xi′t ) − z0 ), ũ (zj−1 − z0 ) .
k +1≤t≤n
2
∗
∗
∞
Since {zik }∞
k=1 is convergent, there must ∃j ∈ {ik }k=1 with j > j such that kzj ∗ − z0 k < ε0 .
∗
This, together with |ũ⊤ (zj ∗ − z0 )| ≤ kzj ∗ − z0 k, leads to ũ⊤ zj ∗ < ũ⊤ (A⊤
u Xi′t ) for k + 1 ≤ t ≤ n,
u
∗
⊤
∗
which further implies Pn (ũ⊤ (A⊤
u X) ≤ ũ zj ∗ ) ≤ λu . Next, by noting λu = D(zj ∗ , Fn ) ≤
⊤
Pn (ũ⊤ (A⊤
u X) ≤ ũ zj ∗ ), we obtain ũ ∈ Uzj ∗ ⊂ Uzj−1 . On the other hand, for ε0 , a similar

derivation leads to ũ⊤ zj ∗ < ũ⊤ zj−1 . This contradicts with zj ∗ ∈ Bzj−1 when j ∗ > j by (o1)(o2). Then, based on lim g(zik −1 ) = 0 and (F1), we can obtain Bz0 \ {z0 } = ∅ similar to
k→∞

Lemma 3 of Liu et al. (2015b). Hence, we may let x0 = z0 .
(II). By denoting ℓu = {z ∈ Rd : z = Au x0 + γu, ∀γ ∈ R1 } and using a similar method
to the first proof part of Theorem 1 in Liu et al. (2015b), we can obtain that, for an any given
y 0 ∈ cov(X n ) \ ℓu , it holds supx ∈cov(X n ) D(x , Fn+m ) ≤

nλ∗u
n+m ,

where Fn+m denotes the empirical

distribution related to X n ∪ Y m , and Y m contains m repetitions of y 0 .
Note that u is any given, and D(y 0 , Fn+m ) =
ε(T ∗ , X n ) ≤

m
n+m

≥

nλ∗u
n+m

when m ≤ nλ∗u . Hence

inf u ∈S d−1 λ∗u
inf u∈S d−1 nλ∗u
=
.
n + inf u∈S d−1 nλ∗u
1 + inf u ∈S d−1 λ∗u

This completes the proof.



Observe that the upper bound given in Lemma 4 involves the Au -projections. A nature
problem arises: whether the Au -projection of X is still halfspace symmetrically distributed?
The following lemma provides a positive answer to this question.
Lemma 5. Suppose X is halfspace symmetrical about θ0 ∈ Rd (d ≥ 2). Then for ∀u ∈ S d−1 ,
⊤
d−1 .
A⊤
u X is halfspace symmetrical about Au θ0 ∈ R
d−1 . Note
Proof. For ∀v ∈ S d−2 , the fact (Au v)⊤ (Au v) = v⊤ (A⊤
u Au )v = 1 implies Au v ∈ S

that
 1



⊤
⊤
⊤
⊤
θ
)
=
P
(A
v)
X
≥
(A
v)
θ
X)
≥
v
(A
P v⊤ (A⊤
u
u
0 ≥ .
u 0
u
2
13

This completes the proof of this lemma.
u
Lemma 5 in fact obtains the population version, i.e., D(A⊤
u θ0 , Fu ), of D(θ̂n , Fu n ) for ∀u ∈

S d−1 , where Fu denotes the distribution of A⊤
u X.
we now are in the position to prove the following theorem.
i.i.d.

Theorem 1. Suppose that (C1) {X1 , X2 , · · · , Xn } ∼ F is of affine dimension d, (C2)
F is halfspace symmetric about point θ0 , and (C3) F is smooth at point θ0 . Then we have
a.s.

ε(T ∗ , X n ) −→ 13 ,

a.s.

as n → +∞, where −→ denotes the “almost sure convergence”.

Proof. Observe that
|D(θ̂n , Fn ) − D(θ0 , F )| ≤ sup |D(x , Fn ) − D(x , F )| + |D(θ̂n , F ) − D(θ0 , F )| .
|
{z
}
x ∈Rd
{z
}
|
E2
E1

Under Condition (C1), a direct use of Remark 2.5 in Page 1465 of Zuo (2003) leads to that
a.s.

sup |D(x , Fn ) − D(x , F )| −→ 0,

as n → +∞,

(6)

x ∈Rd
a.s.

holds with no restriction on F . Hence, E1 −→ 0.
For E2, from Lemma 2, we have that D(x , F ) is continuous at θ0 under Condition (C3). On
the other hand, since D(θ0 , F ) ≥ 1/2 > 0 under Condition (C2), an application of Lemma A.3
a.s.

a.s.

of Zuo (2003) leads to θ̂n −→ θ0 . These two facts together imply E2 −→ 0.
a.s.

a.s.

Based on E1 −→ 0 and E2 −→ 0, we in fact obtain
a.s.

D(θ̂n , Fn ) −→ D(θ0 , F ),
Relying on this and the lower bound
ε(T ∗ , X n ) ≥

λ∗
1+λ∗ ,

∀u ∈ S d−1 .

(7)

it is easy to show that

D(θ0 , F )
,
1 + D(θ0 , F )

almost surely.

d−1 . Hence,
By Lemma 5, Fu is also halfspace symmetrical and smooth at A⊤
u θ0 for ∀u ∈ S

a similar proof to (7) leads to
a.s.

D(θ̂nu , Fu n ) −→ D(A⊤
u θ0 , Fu ),

as n → ∞.

This, together with Lemma 4, and the theory of empirical processes (Pollard, 1984), leads to
ε(T ∗ , X n ) ≤

inf u∈S d−1 D(A⊤
u θ0 , Fu )
,
1 + inf u ∈S d−1 D(A⊤
u θ0 , Fu )

14

almost surely.

Next, by
D(A⊤
u θ0 , Fu )

=
=

inf

v∈S d−2



P v

inf

ū∈S d−1 , ū ⊥u

⊤

(A⊤
u X)

≤v

⊤



(A⊤
u θ0 )

P (ū ⊤ X ≤ ū ⊤ θ0 ),

where ū = Au v, we obtain
inf D(A⊤
u θ0 , Fu )
u∈S d−1

=
=

inf



inf

P (u ⊤ X ≤ u ⊤ θ0 )

u∈S d−1
u∈S d−1

inf

ū∈S d−1 ,ū ⊥u


P (ū X ≤ ū θ0 )
⊤

⊤

= D(θ0 , F ).
a.s.

This proves ε(T ∗ , X n ) −→

D(θ0 ,F )
1+D(θ0 ,F )

= 1/3, because D(θ0 , F ) =

This completes the proof of this theorem.
Remark 2

1
2

under Conditions (C2)-(C3).


It is worth noting that, both halfspace symmetry and weak smooth condition

assumptions in this paper can not be further relaxed if one wants to obtain exactly the limiting
breakdown point of HM. The former is the weakest assumotion to guarantee to have a unique
center. The latter is equivalent to the continuity of D(x , F ) at θ0 , which is necessary for deriving
the limit for both the lower and upper bound, while the upper bound given in Lemma 4 could
not be further improved for fixed n.

5

Concluding remarks
In this paper, we consider the limit of the finite sample breakdown point of HM under weaker

assumption on underlying distribution and data set. Under such assumptions, the random
observations may not be ‘in general position’. This causes additional inconvenience to the
derivation of the limiting result compared to the scenario of X n being in general position. During
our investigation, relationships between various smooth conditions have been established and the
representation of the Tukey depth and median regions has also been obtained without imposing
the ‘in general position’ assumption.
Tukey halfspace depth idea has been extended beyond the location setting to many other
settings (e.g., regression, functional data, etc.). We anticipate that our results here could also
be extended to those settings.

Acknowledgements

15

The research of the first two authors is supported by National Natural Science Foundation of
China (Grant No.11461029, 61263014, 61563018), NSF of Jiangxi Province (No.20142BAB211014,
20143ACB21012, 20132BAB201011, 20151BAB211016), and the Key Science Fund Project of
Jiangxi provincial education department (No.GJJ150439, KJLD13033, KJLD14034).

References
Adrover, J., Yohai, V., 2002. Projection estimates of multivariate location. Annals of statistics, 1760-1781.
Chen, Z., 1995. Robustness of the half-space median. Journal of statistical planning and inference, 46(2), 175-181.
Chen, Z., Tyler, D.E., 2002. The influence function and maximum bias of Tukey’s median. Ann. Statist. 30,
1737-1759.
Donoho, D.L., 1982. Breakdown properties of multivariate location estimators. Ph.D. Qualifying Paper. Dept.
Statistics, Harvard University.
Donoho, D.L., Gasko, M., 1992. Breakdown properties of location estimates based on halfspace depth and projected outlyingness. Ann. Statist. 20, 1808-1827.
Donoho, D.L., Huber, P.J., 1983. The notion of breakdown point. In: Bickel, P.J., Doksum, K.A., Hodges Jr.,
J.L. (Eds.), A Festschrift foe Erich L. Lehmann. Wadsworth, Belmont, CA, pp. 157-184.
Hampel, F.R. (1968). Contributions to the theory of robust estimation, Ph.D. Thesis, University of California,
Berkeley.
Kong, L., Zuo, Y. 2010. Smooth depth contours characterize the underlying distribution. J. Multivariate Anal.,
101, 2222-2226.
Kong, L., Mizera, I., 2012. Quantile tomography: Using quantiles with multivariate data. Statist. Sinica, 22,
1589-1610.
Liu, R. Y., 1988. On a notion of simplicial depth. Proc. Natl. Acad. Sci. USA. 85, 1732-1734.
Liu, R. Y., 1990. On a notion of data depth based on random simplices. Ann. Statist. 18, 191-219.
Liu, X.H., Zuo, Y.J., Wang, Z.Z., 2013. Exactly computing bivariate projection depth median and contours.
Comput. Statist. Data Anal. 60, 1-11.
Liu, X.H., Luo, S.H., Zuo, Y.J., 2015a. Some results on the computing of Tukey’s halfspace median.
arXiv:1604.05927, Mimeo.
Liu, X., Zuo, Y., 2014. Computing halfspace depth and regression depth. Communications in Statistics-Simulation
and Computation, 43, 969-985.
Liu, X., Zuo, Y., Wang, Q., 2015b. Finite sample breakdown point of Tukey’s halfsapce median. Preprint on
arXiv. Mimeo.
Mosler, K., Lange, T., Bazovkin, P., 2009. Computing zonoid trimmed regions of dimension d > 2. Comput.
Statist. Data Anal. 53, 2500-2510.
Paindaveine, D., Šiman, M., 2011. On directional multiple-output quantile regression. J. Multivariate Anal. 102,
193-392.
Pollard, D., 1984. Convergence of stochastic processes. Springer, New York.
Tukey, J.W., 1975. Mathematics and the picturing of data. In Proceedings of the International Congress of
Mathematicians, 523-531. Cana. Math. Congress, Montreal.
Zuo, Y., 2001. Some quantitative relationships between two types of finite sample breakdown point. Stat. Probab.
Lett. 51, 369-375.
Zuo, Y.J., 2003. Projection based depth functions and associated medians. Ann. Statist. 31, 1460-1490.
Zuo, Y.J., Serfling, R., 2000. On the performance of some robust nonparametric location measures relative to a
general notion of multivariate symmetry. Journal of Statistical Planning and Inference, 84(1), 55-79.

16

