On inference validity of weighted U-statistics under data
heterogeneity

arXiv:1804.00034v1 [math.ST] 30 Mar 2018

Fang Han∗ and Tianchen Qian†

Abstract
Motivated by challenges on studying a new correlation measurement being popularized in
evaluating online ranking algorithms’ performance, this manuscript explores the validity of uncertainty assessment for weighted U-statistics. Without any commonly adopted assumption,
we verify Efron’s bootstrap and a new resampling procedure’s inference validity. Specifically,
in its full generality, our theory allows both kernels and weights asymmetric and data points
not identically distributed, which are all new issues that historically have not been addressed.
For achieving strict generalization, for example, we have to carefully control the order of the
“degenerate” term in U-statistics which are no longer degenerate under the empirical measure
for non-i.i.d. data. Our result applies to the motivating task, giving the region at which solid
statistical inference can be made.

Keywords: weighted U-statistics, nondegeneracy, bootstrap inference, data heterogeneity, rank
correlation, average-precision correlation.

1

Introduction

This manuscript studies the following general weighted U-statistic of degree m:
X
(n − m)!
an (i1 ,...,im )hn (Xi1 ,...,Xim ).
Un =
n!

(1.1)

1≤i1 ,i2 ,...,im ≤n:
ij 6=ik if j6=k

Here we assume X1 ,...,Xn are independent but not necessarily identically distributed random
variables, taking values in a measurable space (X ,BX ) (Korolyuk and Borovskich, 2013). The
weight function an (·) and kernel function hn (·) are both possibly asymmetric, and they are both
allowed to be sample size dependent.
Our study on weighted U-statistics is motivated from the following new correlation measurement
popularized in the information retrieval area (Yilmaz et al., 2008). It is formulated as a weighted
∗
†

Department of Statistics, University of Washington, Seattle, WA 98195; e-mail: fanghan@uw.edu
Department of Statistics, Harvard University, Cambridge, MA 02138; e-mail: qiantianchen@fas.harvard.edu

1

U-statistic of asymmetric kernels and weights:
n

τ

AP

2 X
:=
n−1

Pi−1

j=1 1(Xj

i−1

i=2

> Xi )

− 1.

(1.2)

Here 1(·) represents the indicator function and X1 ,...,Xn are specified to be real-valued. For
this specific example, X1 ,...,Xn correspond to the scores the ranking machine gives for each online
page, aligned by the rankings of human labels. The data points X1 ,...,Xn are usually modeled by a
location-scale model, and are usually non-i.i.d.. The statistic in (1.2), named average-precision (AP)
correlation, aims to evaluate the performance of any given online ranking algorithm by calculating
a reweighted rank correlation measurement between the algorithm’s rankings, while “giving more
weights to the errors at high rankings”. For the AP correlation, it is desirable to derive confidence
intervals for solid inference.
Obviously, τ AP is an extension to the Kendall’s tau statistic:
o
Xn
2
1(Xi > Xj )1(i < j) + 1(Xi < Xj )1(i > j) − 1.
(1.3)
τ Ken :=
n(n − 1)
i6=j

τ Ken ,

Compared to
the analysis of τ AP is much more involved, but naturally falls into the application
regime of our theory.
The analysis of unweighted U-statistics (i.e., an (·) ≡ 1) has a long history. There has been
a vast literature on evaluating their asymptotic behaviors since the seminal paper of Hoeffding
(1948). Specifically, regarding the simple independent and identically distributed (i.i.d.) setting,
inference results have been summarized in Lee (1990), Serfling (1980), and Korolyuk and Borovskich
(2013). For extensions, Lee (1990) proved the asymptotic normality under a Lyapunov-type noni.i.d. condition. Yoshihara (1976) and Dehling and Wendler (2010) derived central limit theorem
and (block) bootstrap inference validity for stationary weakly dependent time series. Csörgő and
Nasari (2013) proved the m-out-of-n bootstrap inference validity.
Weighted U-statistic is comparably less touched in the literature. Here, under the i.i.d. setting, Shapiro and Hubert (1979) and O’Neil and Redner (1993) conducted asymptotic analysis for
weighted U-statistics of degree two. Major (1994) and Rifi and Utzet (2000) made extensions to
weighted U-statistics of degree m ≥ 2, with focus on the degenerate cases. Hsing and Wu (2004)
relaxed the independence assumption, proving the asymptotic normality for a wide range of stationary stochastic processes. Recently, Zhou (2014) generalized the results in Hsing and Wu (2004),
proving central and noncentral limit theorems for a class of nonstationary time series.
Despite the above substantial advances, i.i.d. or stationary assumption is commonly posed,
especially for proving Efron’s bootstrap inference validity. A notable exception is Zhou (2014),
who established central limit theorem for nonstationary time series. However, bootstrap inference
is not discussed, and the regularity conditions therein are too strong to include statistics like τ AP .
In addition, the kernels and weights are required to be symmetric.
Motivated from our study on the AP correlation, this manuscript aims to fill the above gaps.

2

In particular, we build unified theory for analyzing nondegenerate weighted U-statistics, namely,
establishing sufficient conditions for their asymptotic normality and bootstrap inference validity.
Both Efron’s bootstrap and a new resampling procedure stemmed from Politis and Romano (1994)
and Bickel et al. (1997) are considered. For this, we waive the i.i.d. assumptions, allowing researchers to analyze statistics like τ AP in practical settings. In addition, our analysis allows both
the kernels and weights to be asymmetric.

1.1

Other related work

Our results are very related to bootstrap inference under data heterogeneity. In Liu (1988), Regina
Liu pioneered the study on Efron’s bootstrap inference validity for non-i.i.d. models. Her results
showed that bootstrap is robust to these specific non-i.i.d. settings with common locations (means).
However, bootstrap is very sensitive to mean differences. The inference validity is captured by a
function of {µi := EXi }ni=1 , which she called “heterogeneity factors” (Liu, 1988; Liu and Singh,
1995). For example, for the sample mean, at the worse case, the distance between the largest
and smallest means needs to shrink to zero as n → ∞ for bootstrap consistency. Mammen (2012)
summarized the existing results, providing necessary and sufficient conditions of bootstrap validity
for the sample-mean-type statistics under non-i.i.d. settings.
Politis and Romano’s subsampling (Politis et al., 1999) and many other resampling schemes
(Bickel et al., 1997) are appealing alternatives to Efron’s bootstrap. They are designed to correct
the bootstrap inference inconsistency problem in many different settings, where the data could
be, for example, dependent or heavy-tailed. In this manuscript, we examine a new resampling
procedure’s inference validity for weighted U-statistics.

1.2

Notation

Let R be the set of real numbers, and Z be the set of integers. For a positive integer n, we
d
write [n] = {a ∈ Z : 1 ≤ a ≤ n}. For any set A, let card(A) represent the cardinality of A. Let →
P
denote “convergence in distribution”, and → denote “convergence in probability”. Let “a.s.” be the
abbreviation of “almost surely”. Let Φ(t) be the cumulative distribution function of the standard
Gaussian. For two positive integers m < n, define
 
n
n!
,
=
(n − m)!m!
m
where n! represents the factorial of n. Let C be a generic absolute positive constant, whose actual
value may vary at different locations. For any two real sequences {an } and {bn }, we write an . bn , or
equivalently bn & an , if there exists an absolute constant C such that |an | ≤ C|bn | for all sufficiently
large n. We write an  bn if both an . bn and an & bn hold. We write an  bn , or equivalently
bn  an , if an & bn holds, but an . bn does not. We write an = O(bn ) if an . bn , and an = o(bn ) if
an = O(bn ) and bn 6= O(an ). We write an = OP (bn ) if an /bn is stochastically bounded, that is, for

3

any  > 0, there exists a finite M > 0 and a finite N > 0 such that P (|an /bn | > M ) <  for all n > N .
We write an = oP (bn ) if for any  > 0, limn→∞ P (|an /bn | ≥ ) = 0.

1.3

Structure of the manuscript

The rest of the manuscript is organized as follows. In Section 2 we provide the unified theory for
asymmetric weighted U-statistic, deriving central limit theorem, bootstrap, and a new resampling
procedure’s inference validity under data non-i.i.d. settings. In Section 3, we apply the developed
theory to explore the inference validity of Kendall’s tau in (1.3) and AP correlation in (1.2). All
proofs are relegated to Appendix.

2

Main results

Throughout the manuscript, we focus on the following triangular array setting: Assume we have n
independent random variables {Xn,i },n ≥ 1,1 ≤ i ≤ n. Each Xn,i follows the distribution Pn,i . The
elements in {Pn,i ,i ∈ [n]} are not necessarily equal to each other. When n increases, Pn,i could
possibly change. For notational simplicity, in the sequel we drop n in the subscripts of Xn,i and
Pn,i when no confusion could be made.
We are focused on the following weighted U-statistic of degree m, with weight function a(·) :
m
Z → R and kernel h(·) : X m → R:
(n − m)! X
an (i1 ,...,im )hn (Xi1 ,...,Xim ).
(2.1)
Un = Un (X1 ,...,Xn ) =
n!
m
In

Here the summation is over all possible m elements in [n] without overlap:
n
o
Inm := 1 ≤ i1 ,i2 ,...,im ≤ n : ij 6= ik if j 6= k .
Such Un is usually referred to as a weighted U-statistic in the literature (Serfling, 1980). We do
not assume symmetry of an (·) or hn (·) in their arguments. For notation simplicity, in the sequel
we omit the subscript n in an (·) and hn (·).
Let’s define
Z
θ(i1 ,...,im ) := E{h(Xi1 ,...,Xim )} = h(y1 ,...,ym )dPi1 (y1 )...dPim (ym )
(2.2)
to be the population mean of h(Xi1 ,...,Xim ). For any l ∈ [m], define πl (·;·) to be a function that
takes two arguments (a scalar and a vector of length m − 1), and returns a vector of length m by
inserting the first argument into the l-th position of the second argument. Formally, we define
πl (y;y1 ,y2 ,...,ym−1 ) := (y1 ,...,yl−1 ,y,yl ,...,ym−1 ).

4

We further define
a(l) (i;i1 ,i2 ,...,im−1 ) := a{πl (i;i1 ,i2 ,...,im−1 )},
h(l) (x;x1 ,...,xm−1 ) := h{πl (x;x1 ,...,xm−1 )},
θ(l) (i;i1 ,i2 ,...,im−1 ) := θ{πl (i;i1 ,i2 ,...,im−1 )}.
Define the first order expansion of h(·) for each Xi , regarding the specific sequence Xi1 ,...,Xim−1 ,
to be:
m
X
 (l)
h1,i;i1 ,...,im−1 (x) :=
a(l) (i;i1 ,...,im−1 ) fi1 ,...,im−1 (x) − θ(l) (i;i1 ,...,im−1 ) ,
l=1

where
(l)

fi1 ,...,im−1 (x) := Ei1 ,...,im−1 {h(l) (x;Y1 ,...,Ym−1 )}
Z
= h(l) (x;y1 ,...,ym−1 )dPi1 (y1 )...dPim−1 (ym−1 ).
Define the first order expansion of h(·) for Xi to be
(n − m)! X
h1,i (x) :=
(n − 1)! m−1

h1,i;i1 ,...,im−1 (x),

(2.3)

(2.4)

In−1 (−i)

where the summation is over
n
o
m−1
(−i) := 1 ≤ i1 ,...,im−1 ≤ n : ij 6= ik if j 6= k, and ij 6= i for all j ∈ [m − 1] .
In−1
For l ∈ [m], we write (i1 ,...,im )\il := (i1 ,...,il−1 ,il+1 ,...,im ), and define
h2;i1 ,...,im (x1 ,...,xm ) := h(x1 ,...,xm ) −

m
X

(l)

f(i1 ,...,im )\il (xl ) + (m − 1)θ(i1 ,...,im ),

(2.5)

l=1

where by (2.3) we have
Z
(l)
f(i1 ,...,im )\il (x) = h(y1 ,...,yl−1 ,x,yl+1 ,...,ym )dPi1 (y1 )...dPil−1 (yl−1 )dPil+1 (yl+1 )...dPim (ym ).
Before presenting the main theorem, we have to introduce more notation on the weight function
a(·). For K,q ∈ Z with K ≥ 2 and 0 ≤ q ≤ m, let (Inm )⊗K
≥q be the collection of all K-dimensional index
m
vectors from In that share at least q common indices:
(Inm )⊗K
≥q

K
n
\

o
(1)
(K)
(k)
(1)
m
(K)
m
:= (i1 ,...,im ) ∈ In ,...,(i1 ,...,im ) ∈ In : card
{i1 ,...,i(k)
m } ≥q ,
k=1

(Inm )⊗K
=q

and
be the collection of all K-dimensional index vectors from Inm that share exactly q
indices in common:
K
n
\

o
(1)
(K)
(k)
m ⊗K
(1)
m
(K)
m
(In )=q = (i1 ,...,im ) ∈ In ,...,(i1 ,...,im ) ∈ In : card
{i1 ,...,i(k)
m } =q .
k=1

5

m ⊗K
With fixed K,q,m, it is easy to observe card{(Inm )⊗K
≥q }  card{(In )=q } as n → ∞, and
 
 

n
n−q
n − (K − 1)m − q
m ⊗K
card{(In )=q } 
···
 nq+K(m−q) .
q
m−q
m−q
2m−2 , card{(I m )⊗2 }  n2m−1 , and card{(I m )⊗3 }  n3m−2 .
In particular, we have card{(Inm )⊗2
n ≥1
n ≥1
≥2 }  n
Define the average weight, AK,q (n), as
X
1
(1)
(K)
(K)
a(i1 ,...,i(1)
(2.6)
AK,q (n) :=
m )···a(i1 ,...,im ) .
⊗K
m
card{(In )≥q } m ⊗K
(In )≥q

The following theorem gives sufficient conditions on the weights and distributions of {Xi } for
guaranteeing Un to be asymptotically normal.
Theorem 2.1 (Sufficient condition for asymptotic normality of Un ). For each n, assume there
exists a positive constant M (n) > 0 only depending on n such that
max

(i1 ,...,im )∈Inm

Define V (n) = Var{n−1
hold:

Pn

i=1 h1,i (Xi )}

n

E{h(Xi1 ,...,Xim )4 } ≤ M (n).

(2.7)

with h1,i (·) defined in (2.4). Assume the following conditions

n−2 V (n)−1 A2,2 (n)M (n)1/2 → 0,

(2.8)

−2

(2.9)

−3/2

V (n)

A3,1 (n)M (n)

3/4

→ 0.

Then we have
Var(Un )/V (n) → 1,

(2.10)

and
d

Var(Un )−1/2 {Un − E(Un )} → N (0,1).

(2.11)

The first step of the proof, which establishes a von-Mises-expansion type result, is simple yet
inspiring. Of note, under i.i.d. settings, an analogous theorem has been (inexplicitly) stated in
Shapiro and Hubert (1979).
Lemma 2.2 (Hoeffding’s decomposition). With h1,i (·) and h2;i1 ,...,im (·) defined in (2.4) and (2.5),
we have
n
1X
Un − E(Un ) =
h1,i (Xi ) + Un (a,h2 ),
(2.12)
n
i=1

where
Un (a,h2 ) :=

(n − m)! X
a(i1 ,...,im )h2;i1 ,...,im (Xi1 ,...,Xim ),
n!
m
In

6

(2.13)

and for any i,k ∈ [n] and (i1 ,...,im ) ∈ Inm ,
E{h1,i (Xi )} = 0,
E{h2;i1 ,...,im (Xi1 ,...,Xim ) | Xk } = 0 a.s..

(2.14)
(2.15)

For putting Theorem 2.1 appropriately in the literature, let’s first give a brief review on the most
relevant existing results. The first proof of asymptotic normality for (unweighted) nondegenerate
U-statistics was given in Hoeffding (1948). Grams and Serfling (1973) studied general unweighted
U-statistics of degree m ≥ 2 and bounded their central moments . The techniques therein also play
a central role in our analysis. Shapiro and Hubert (1979) and O’Neil and Redner (1993) analyzed
the asymptotic behavior of weighted U-statistics of degree 2. They assumed weight function a(·)
symmetric. The above results all assume data i.i.d.-ness. For unweighted U-statistics, Lee (1990)
outlined an extension to non-i.i.d. data.
Theorem 2.1 is stronger than the results in the literature, allowing a(·) and h(·) asymmetric, and
the Xi ’s non-i.i.d.. By examining the proof, one can also easily check that, when the corresponding
symmetry, boundedness, or i.i.d. assumptions are made, our results can reduce to the ones in
Hoeffding (1948), Shapiro and Hubert (1979), O’Neil and Redner (1993), and Lee (1990).
P
Remark 2.3. Condition (2.8) is added to enforce domination of n−1 ni=1 h1,i (Xi ) over Un (a,h2 ) in
(2.12). Condition (2.9) evolves from the Lyapunov condition with δ = 1, which is readily weakened
to the condition of a smaller 0 < δ < 1 or the Lindeberg-Feller condition. Condition (2.7) is made
and could be weakened based on the same argument. For presentation clearness, we choose the
current conditions.
Inferring the distribution of Un or approximating Var(Un ) is usually challenging in practice.
Resampling procedures are hence recommended. The rest of this section gives asymptotic results
for Efron’s bootstrap (Efron, 1979) and a new resampling procedure for approximating Var(Un ).
Due to the heterogeneity in Pi , it is well known that bootstrap could possibly no longer be
consistent (Liu, 1988). However, it is still possible to recover bootstrap consistency by restricting
the heterogeneity degree. But before that, let’s first provide a theoretically interesting theorem.
It states that, under very mild conditions, bootstrapped mean from the set {h1,i (Xi ) : 1 ≤ i ≤ n}
P
approximates the distribution of n−1 ni=1 h1,i (Xi ) consistently. This is consistent to the discovery
in Liu (1988) by noting that E{h1,i (Xi )} = 0 no matter how different {Pi }ni=1 are.
Theorem 2.4 (Sufficient condition for bootstrapping main term to work). Denote
σn2 := Var(Un ).

(2.16)

P
Consider the term n−1 ni=1 h1,i (Xi ) with h1,i (Xi ) defined in (2.4) and its bootstrapped version
P
n−1 ni=1 {h1,i (Xi )}∗ , where conditional on X1 ,...,Xn the {h1,i (Xi )}∗ ’s are i.i.d. draws from the
empirical distribution of {h1,j (Xj ) : 1 ≤ j ≤ n}. Assume (2.7) and (2.9) hold. In addition, assume

7

for every  > 0, we have
n h (X )
o
1,i
i
≥  → 0,
nσn
1≤i≤n
n
oi2
X h n h1,i (Xi )  h1,i (Xi )
→ 0.
1
≤
E
nσn
nσn
sup P

(2.17)
(2.18)

i=1

Then
n
n
n
nX
o
nX
o
{h1,i (Xi )}∗ X h1,i (Xi )
h1,i (Xi )
P
sup P
−
≤ t −P
≤ t → 0,
nσ
nσ
nσ
n
n
n
t∈R
∗

i=1

where P ∗ denotes the conditional probability given X1 ,...,Xn . If further (2.8) holds, then
n
n
nX
o
n
o
{h1,i (Xi )}∗ X h1,i (Xi )
P
sup P ∗
−
≤ t − P Var(Un )−1/2 {Un − E(Un )} ≤ t → 0.
nσ
nσ
n
n
t∈R
i=1

(2.19)

i=1

i=1

(2.20)

i=1

Remark 2.5. Equations (2.17) and (2.18) are rather mild constraints. As we will show in Corollary
3.1, usually they can be directly deduced from the asymptotic normality of Un . However, unless
we know much about Xi , the form of h1,i (·) is unknown.
We now focus on bootstrapping the original U-statistic for estimating Var(Un ). The following theorem shows that Efron’s bootstrap still gives consistent variance estimate for Un under
some additional conditions on data heterogeneity. Although the bootstrap inference validity for Ustatistics under i.i.d. assumptions has been established (check, for example, Korolyuk and Borovskich (2013)), the corresponding one for non-i.i.d. settings, even for the simplest unweighted Ustatistics, is still absent in the literature. Our manuscript fills this gap.
Theorem 2.6 (Sufficient condition for consistent bootstrap variance estimation). Given X1 ,...,Xn ,
let X1∗ ,...,Xn∗ denote the bootstrapped sample, which are i.i.d. draws from the empirical distribution
of X1 ,...,Xn . Define the bootstrapped U-statistic
(n − m)! X
a(i1 ,...,im )h(Xi∗1 ,...,Xi∗m ).
Un∗ =
n!
m
In

Assume all conditions in Theorem 2.1 are satisfied. Also assume the following conditions hold:
(i) Bounded second moment of von-Mises type kernel:
limsup

max

n→∞ 1≤i1 ,...,im ≤n

E{h(Xi1 ,...,Xim )2 } < ∞.

(ii) Control of heterogeneity in the distributions of Xi :
n n
1 X X n h1,i (Xj ) o2 P
→ 1,
n
nσn
1
n2

i=1 j=1
n nX
n
X
i=1

j=1

8

h1,i (Xj ) o2 P
→ 0,
nσn

(2.21)

(2.22)

(2.23)

and
n−1 σn−2 A2,1 (n){M1 (n)2 + M2 (n) + n−1 } → 0,

(2.24)

where
M1 (n) = max |θ(i1 ,...,im ) − θ(j1 ,...,jm )|,

(2.25)

(Inm )⊗2
≥0

M2 (n) = max

max

max

1≤p,q≤m r,s∈(I m )⊗2
k∈Inm
n =1
r∩s=rp =sq k∩s=kp =sq

E[E{h(Xr1 ,...,Xrm )h(Xs1 ...Xsm ) | Xkp }]

− E[E{h(Xk1 ,...,Xkm )h(Xs1 ,...,Xsm ) | Xkp }] .

(2.26)

Here we define r := (r1 ,...,rm ), and similarly for s,k.
Then we have
P

Var∗ (σn−1 Un∗ ) − Var(σn−1 Un ) → 0,

(2.27)

where the operator Var∗ (·) denotes the conditional variance given X1 ,...,Xn .
The detailed proof of Theorem 2.6 is very involved and highly combinatorial. Of note, in
the theorem, (2.21) comes from Bickel and Freedman (1981), ensuring that the bootstrapped
U-statistic won’t explode. Equations (2.22) and (2.23) ensure that the conditional variance of
P
n−1 ni=1 h1,i (Xi∗ ) approximates Var(Un ). Equation (2.24) ensures that Un∗ (a,h2 ) is negligible comP
pared to n−1 ni=1 h1,i (Xi∗ ).
Remark 2.7. Although Un (a,h2 ) in the decomposition (2.12) is degenerate and hence negligible
under the conditions of Theorem 2.1, its bootstrapped version Un∗ (a,h2 ) is not necessarily degenerate, because the empirical measure does not equal the true measure. This makes Un∗ (a,h2 ) not
P
necessarily negligible compared to the bootstrapped version of the main term, n−1 ni=1 h1,i (Xi∗ ).
Therefore, bootstrap may fail without careful control on both the main term and the remainder
Un∗ (a,h2 ). We developed delicate analysis to bound Un∗ (a,h2 ) and showed that it is negligible under
the constraint (2.24).
Remark 2.8. Condition (2.24) puts homogeneity conditions mainly on the means. This is consistent to Theorem 2.4 and the discoveries in Liu (1988), who showed that bootstrap is most sensitive
to mean differences. To illustrate, assume a(·) ≡ 1 and the kernel h(·) to be a bounded function.
Assume the assumptions in Theorem 2.1 hold, so that we have asymptotic normality of Un . Equation (2.9) requires σn2  n−4/3 . Therefore, for (2.24) to hold, it is necessary that M1 (n)2  n−1/3 and
M2 (n)  n−1/3 . The space to improve our requirements, if existing, is relatively small. This is by
noting that, even for the simplest sample-mean-type statistics, for most cases, Liu (1988) required
the mean differences shrink to zero as n → ∞ for bootstrap consistency.
An immediate implication of Theorem 2.6 proves the validity of bootstrapping weighted Ustatistics for i.i.d. data.
9

Corollary 2.1. Assume that X1 ,...,Xn are i.i.d., and that (2.7), (2.8), (2.9), and (2.21) hold. In
addition, assume n−2 σn−2 A2,1 (n) → 0. Then (2.22), (2.23), and (2.24) hold, and we have
P

Var∗ (σn−1 Un∗ ) − Var(σn−1 Un ) → 0.
Remark 2.9. The assumption n−2 σn−2 A2,1 (n) → 0 is mild. Actually it follows immediately from
(2.8) if we have A2,1 (n) . A2,2 (n). It is reasonable to expect A2,1 (n) and A2,2 (n) to be of similar
order because of their definitions in (2.6). Indeed, for the two applications in Section 3, we have
A2,1 (n)  A2,2 (n) for UnKen and A2,1 (n) . A2,2 (n) . A2,1 (n)logn for UnAP .
In many cases, although the data are in general non-i.i.d., they possess some locally stationary property (Dahlhaus, 1997). For example, consider the following nonparametric regression
model. Assume Xi ∼ N (µi ,1) with µi = gn (i/n) for i = 1,...,n. If the function gn (·) is smooth
enough (e.g., (n)-Lipschitz), then, although |gn (1) − gn (0)| could increase to infinity, the subsample {Xi ,Xi+1 ,...,Xi+b−1 }, for each i ∈ 1,...,n − b + 1, can be approximately i.i.d..
Adopting this thinking, we consider the following revised resampling procedure whose idea
comes from Politis and Romano (1994) and Bickel et al. (1997), but is tailored for non-i.i.d. data.
This is also related to the local block bootstrap developed in Paparoditis and Politis (2002) and
Kreiss and Paparoditis (2015). In detail, for m < b → ∞, we consider the following statistic:
Vn∗ =

n−b+1
X
(b − m)! X
1
∗
∗
:=
a(i1 ,...,im )h(Xi∗1 ,b,i ,...,Xi∗m ,b,i ),
Var∗ (Ub,i
), where Ub,i
hn (n − b + 1)
b!
m
i=1

Ib

and for each i ∈ [n − b + 1], Xi∗1 ,b,i ,...,Xi∗m ,b,i are independently drawn from the empirical distribution
of {Xi ,...,Xi+b−1 } with replacement. The tuning parameter hn regulates the scale.
The following theorem verifies the new resampling procedure’s inference consistency for Vn∗ ,
showing that the procedure tends to give conservative variance estimate under non-i.i.d. settings.
It also shows that the inference is more tractable compared to Efron’s bootstrap when we have
more prior information on the heterogeneity degree, reflected in the consistency rate of Un and the
choice of hn . We also refer the readers to Remark 3.4 and discussions therein for the order of σn
in a specific example.
Theorem 2.10. Assume that all conditions in Theorem 2.6 hold for each “moving block” {Xi ,...,Xi+b−1 }
of i ∈ [n − b + 1] as n,b → ∞. Assume Var(Ub,i (Xi ,...,Xi+b−1 )) = σb2 (1 + o(1)) for any i ∈ [n − b + 1],
and σb2 /σn2 = ζn,b · (1 + o(1)) for some ζn,b > 0. We then have
σn−2 Vn∗ − Var(σn−1 Un ) =

10

ζn,b
· (1 + oP (1)) − 1.
hn

3

Application

This section explores two specific statistics, the Kendall’s tau (denoted as τ Ken ) (Kendall, 1938)
and average-precision (AP) correlation (denoted as τ AP ) (Yilmaz et al., 2008):
X
2
τ Ken =
{1(Xi > Xj )1(i < j) + 1(Xj > Xi )1(j < i)} − 1,
n(n − 1)
i6=j
n Pi−1
X
2
j=1 1(Xj > Xi )
τ AP =
− 1.
n−1
i−1
i=2

Without loss of generality, we focus on the transformed versions of these two statistics:
X
1
τ Ken + 1
=
1(j < i)1(Xj > Xi ),
UnKen =
4
n(n − 1)
i6=j

UnAP :=

τ AP + 1
2

=

1
n(n − 1)

X n1(j < i)
i6=j

i−1

1(Xj > Xi ).

We assume {Pi ,i ∈ [n]} to be absolutely continuous with regard to the Lebesgue measure. Obviously,
both UnKen and UnAP enjoy the distribution-free property (Kendall and Stuart, 1973) when the data
are i.i.d.. Of note, these two statistics could also be treated as (weighted) U-statistics of symmetric
kernels and weights with non-i.i.d. data (X1 ,1),...,(Xn ,n). However, we found the following analysis
based on X1 ,...,Xn much neater, and as will be seen in the proof, non-i.i.d.-ness is the major obstacle
in analysis.

3.1

Asymptotic theory

Note that the statistics UnKen and UnAP have the same kernel h(x,y) = 1(y > x). Using the definition
in (2.2), we have θ(i,j) = E{h(Xi ,Xj )} = P (Xj > Xi ). The forms of h1,i (·) and h2;i,j (·) for UnKen
and UnAP are then summarized in the following two lemmas.
Lemma 3.1 (Hoeffding’s decomposition of UnKen ). We have
n

UnKen − E(UnKen ) =

X
1
1 X Ken
h1,i (Xi ) +
1(j < i)hKen
2;i,j (Xi ,Xj ),
n
n(n − 1)
i=1

i6=j

where
n

hKen
1,i (x) =

1 X
{1(j < i) − 1(j > i)}{P (Xj > x) − θ(i,j)}
n−1
j=1

and
hKen
2;i,j (x,y) = 1(y > x) − P (Xj > x) − P (y > Xi ) + θ(i,j).

11

(3.1)

Lemma 3.2 (Hoeffding’s Decomposition of UnAP ). We have
n

UnAP − E(UnAP ) =

X n1(j < i)
1
1 X AP
h1,i (Xi ) +
hAP
2;i,j (Xi ,Xj ),
n
n(n − 1)
i−1
i=1

i6=j

where
n

hAP
1,i (x) =

1 X n n1(j < i) n1(j > i) o
−
{P (Xj > x) − θ(i,j)},
n−1
i−1
j −1

(3.2)

j=1

and
hAP
2;i,j (x,y) = 1(y > x) − P (Xj > x) − P (y > Xi ) + θ(i,j).
In (3.2), by convention, we have 0/0 := 0.
The next theorem characterizes sufficient distributional conditions for UnKen and UnAP to be
asymptotically normal, allowing for data non-i.i.d.-ness.
Theorem 3.3 (Sufficient conditions for asymptotic normality of UnKen and UnAP ). Assume a se∞
quence {δn ∈ (0,1)}∞
n=1 and a sequence {pn ∈ (0,1)}n=1 such that for any sufficiently large n and for
each i ∈ [n], one of the following two conditions holds:
(i) P {P (Xj > Xi | Xi ) − P (Xj > Xi ) ∈ [δn ,1],∀j ∈ [n]\{i}} ≥ pn ;
(ii) P {P (Xj > Xi | Xi ) − P (Xj > Xi ) ∈ [−1,−δn ],∀j ∈ [n]\{i}} ≥ pn .
In addition, if
δn3 pn n−1/3 ,

(3.3)

then UnKen is asymptotically normal,
d

Var(UnKen )−1/2 {UnKen − E(UnKen )} → N (0,1).
If we have
δn3 pn  n−1/3 (logn)2 ,

(3.4)

then UnAP is asymptotically normal,
d

Var(UnAP )−1/2 {UnAP − E(UnAP )} → N (0,1).
The proof of Theorem 3.3 exploits Theorem 2.1. A key step in the proof is to bound V (n) :=
P
i Var{h1,i (Xi )} from below. The magnitude of Var{h1,i (Xi )} varies greatly with different
i, making it a challenging task to bound the entire summation. To tackle this, we break V (n)
into summations over multiple subsets of [n]. Within each of these summations, the magnitude of
Var{h1,i (Xi )} is stable. Then we develop bounds on the summations for i with large Var{h1,i (Xi )}.
The sequences {δn } and {pn } in Conditions (i) and (ii) of Theorem 3.3 characterize the heterogeneity degree among the Pi ’s. If all Pi ’s are identical, it is easy to check that there exist absolute
constants δn and pn not depending on n such that Condition (i) or (ii) holds. Equations (3.3) and
n−2

12

(3.4) allow δn and pn to decay to zero as n → ∞. The legitimate decaying rate of δn3 pn depends
on the average weight of each of the two statistics. The conditions for asymptotic normality of
UnAP (3.4) are slightly stronger than that for UnKen (3.3), because for UnAP the weight is much more
skewed.
Remark 3.4. In the literature about Kendall’s tau, the classical result gives root-n convergence
rate (Sen, 1968). Theorem 3.3 gives a more general result regarding the convergence rate due to the
non-i.i.d.-ness of {X1 ,...,Xn }. In the proof of Theorem 3.3, we show that the Var(UnKen )  n−1 δn3 pn .
As we vary the distribution of Xi from i.i.d. to the more heterogeneous ones, δn3 pn changes from
O(1) to O(n−1/3+ ) for some small  > 0. Therefore, the upper bound on the order of Var(UnKen )−1/2
can vary from n1/2 to n2/3−/2 .
Motivated by the studies in Yilmaz et al. (2008), in the sequel we consider the following specific
location-scale model. In particular, given two sets of real values µi with µ1 ≥ µ2 ≥ ... ≥ µn and
σ12 ,...,σn2 > 0, let’s consider absolute continuous (with respect to Lebesgue measure) probability
distribution Pi with mean µi and variance σi2 for i ∈ [n]. Assume X1 ,...,Xn are independent draws
from P1 ,...,Pn . The following theorem characterizes the explicit sufficient conditions on {(µi ,σi ),i ∈
[n]} for Kendall’s tau and AP correlation to be asymptotically normal.
Theorem 3.5 (Sufficient condition for asymptotic normality of UnKen and UnAP under two tail
conditions). For each i ∈ [n], assume Xi follows distribution Pi with mean µi and variance σi2 .
Define
rij := (µi − µj )/σi , Rn := max |rij |, ρij := σi /σj , and ρn := max ρij .
1≤i6=j≤n

1≤i6=j≤n

For n,i,j such that 1 ≤ i 6= j ≤ n, define

n X − X − (µ − µ )
o
X −µ
j
i
j
i
j
j
> t and Fjic (t) = P
>
t
.
Fjc (t) = P
σj
(σi2 + σj2 )1/2

(3.5)

Then the following results hold.
(i) Assume there exist absolute constants c1 ,c2 > 0, b1 > b2 > 0, and t0 > 0, such that for any n,i,j
with 1 ≤ i 6= j ≤ n and for any t ≥ t0 ,
c1 t−b1 ≤ Fjc (t) ≤ c2 t−b2 ,
−b1

c1 t

≤ Fjic (t) ≤ c2 t−b2 .

(3.6)
(3.7)

Then the sufficient condition for asymptotic normality of UnKen is
(3b1 b2 +b21 )/b2 b1
ρn

Rn

 n1/3 ,

(3.8)

and the sufficient condition for asymptotic normality of UnAP is
(3b1 b2 +b21 )/b2 b1
ρn

Rn

 n1/3 (logn)−2 .

(3.9)

(ii) Assume there exist absolute constants c1 ,c2 > 0, b1 > b2 > 0, and t0 > 0, such that for any n,i,j
13

with 1 ≤ i 6= j ≤ n and for any t ≥ t0 ,
c1 exp(−b1 tλ ) ≤ Fjc (t) ≤ c2 exp(−b2 tλ ),
λ

c1 exp(−b1 t

) ≤ Fjic (t) ≤ c2 exp(−b2 tλ ).

Then the sufficient condition for asymptotic normality of UnKen is
1
3b1 Rnλ + b1 (Rn + K3 ρn + K4 ρn Rn )λ  logn,
3
and the sufficient condition for asymptotic normality of UnAP is
1
3b1 Rnλ + b1 (Rn + K3 ρn + K4 ρn Rn )λ  logn − 2loglogn,
3
where
 1
 1
c1
b1 1/λ
c1 1/λ
K3 := t0 + − log
+ tλ0
+ ξ(λ−1 ) − log
,
b2
2c2 b2
b2
2c2
 b 1/λ
1
K4 := ξ(λ−1 )
,
b2

(3.10)
(3.11)

(3.12)

(3.13)

(3.14)

and ξ(p) := 1(p ≤ 1) + 2p−1 1(p > 1).
Remark 3.6. It is worth noting that distributions satisfying (3.6) in Theorem 3.5(i) are commonly
referred to as “heavy-tailed” distributions, whereas distributions satisfying (3.10) in Theorem 3.5(ii)
are considered to be “light-tailed” (Mikosch, 1999; Resnick, 2007).
We compare Condition (3.8) in (i) and Condition (3.12) in (ii) for UnKen . Assume σi = 1 for
all i ∈ [n]. In this case, we have ρn = 1, and Rn = max1≤i6=j≤n |µi − µj | becomes the spread of the
means. Equation (3.8) becomes
b2

2

Rn  n 3(3b1 b2 +b1 ) .

(3.15)

Equation (3.12) becomes
1
3b1 Rnλ + b1 (Rn + K3 + K4 Rn )λ  logn.
(3.16)
3
Lemma C.9 in Appendix yields (Rn + K3 + K4 Rn )λ ≤ ξ(λ)(1 + K4 )λ Rnλ + ξ(λ)K3λ . So for (3.16) to
hold, it suffices to have ξ(λ)(1 + K4 )λ Rnλ + 3b1 Rnλ  (logn)/3. Rearranging terms, we obtain a sufficient condition for (3.16) to hold:
h
i1/λ
logn
.
(3.17)
Rn 
3b1 {3 + ξ(λ)(1 + K4 )λ }
For heavy-tailed distributions in (i), (3.15) implies that the spread of means should not grow faster
than a polynomial of n. For light-tailed distributions in (ii), (3.17) implies that the spread of means
should not grow faster than the logarithm of n (up to some constant scaling factor). Of note, under
both tail conditions, Rn is allowed to increase to infinity at proper rates.
Example 3.1. A special distribution satisfying the conditions in Theorem 3.5(ii) is the Gaussian.
Again, consider UnKen and assume σi = 1 for all i ∈ [n]. Note in this case Fjc (·) is the survival function
14

for Gaussian with variance 1, whereas Fjic (·) is for Gaussian with variance 2. Let λ = 2, b1 = 1/2 + ,
b2 = 1/4 −  for arbitrarily small  > 0, and c1 ,c2 ,t0 be properly chosen constants (whose value does
not affect the rate in (3.17)). Equations (3.6) and (3.7) are satisfied due to Lemma C.11. It then
follows from (3.17) that
 2logn 1/2
√
Rn 
27 + 12 2
is sufficient for UnKen to be asymptotically normal.
Remark 3.7. We comment on a modified version of Theorem 3.5(i), with a condition alternative to
(3.6) (A similar modification applies to Theorem 3.5(ii)). In detail, define Fj (t) = P {(Xj − µj )/σj ≤
t} to be the standardized cumulative distribution function that is complement to the survival
function Fjc (t). The conclusion in Theorem 3.5(i) still holds if we replace the condition (3.6) by
c1 t−b1 ≤ Fj (−t) ≤ c2 t−b2 .

(3.18)

For comparison, (3.6) regulates the upper-tail behavior of Xj , whereas (3.18) regulates the lowertail of Xj . Technically speaking, the proof of Theorem 3.5(i) examines Condition (ii) in Theorem
3.5, whereas the alternative version examines Condition (i) in Theorem 3.5. Note that (3.7) is
required in both versions, and regulates both the upper- and lower-tail behaviors of Xj − Xi .
The following three corollaries give asymptotic results for bootstrapping UnKen and UnAP . The
first of them states that bootstrapping the main term is very insensitive to data non-i.i.d.-ness.
This is as expected by the results in Liu (1988).
Corollary 3.1 (Bootstrap of main term works for UnKen and UnAP ). If (3.3) holds, we have that
AP
(2.17) and (2.18) hold for hKen
1,i . If (3.4) holds, we have that (2.17) and (2.18) hold for h1,i .
As has been shown in Section 2, bootstrapping the whole U-statistic requires much stronger
assumptions for guaranteeing its consistency. The following two corollaries provide sufficient conditions for bootstrap inference validity of the two considered U-statistics.
Corollary 3.2 (Sufficient condition for consistent bootstrap variance estimation of UnKen ). Assume
(3.3) holds. Assume there exist θ > 0 and an absolute constant C > 0 such that for all (i,j) ∈ In2 ,
|P (Xi > Xj ) − θ| ≤ Cn−1/6 .

(3.19)

In addition, assume there exist η 2 > 0 and an absolute constant C > 0 such that for all i ∈ [n] and
all 1 ≤ j,k ≤ n such that j 6= i and k 6= i,
|E{P (Xj > Xi | Xi )P (Xk > Xi | Xi )} − η 2 | ≤ Cn−1/3 .
Assume η 2 6= θ2 . Then we have
P

|Var∗ (σn−1 UnKen∗ ) − Var(σn−1 UnKen )| → 0.

15

(3.20)

Corollary 3.3 (Sufficient condition for consistent bootstrap variance estimation of UnAP ). Assume
(3.4) holds. Assume there exist θ > 0 and an absolute constant C > 0 such that for all (i,j) ∈ In2 ,
|P (Xi > Xj ) − θ| ≤ Cn−1/6 logn.

(3.21)

In addition, assume there exist η 2 > 0 and an absolute constant C > 0 such that for all 1 ≤ i ≤ n
and all 1 ≤ j,k ≤ n such that j 6= i and k 6= i,
|E{P (Xj > Xi | Xi )P (Xk > Xi | Xi )} − η 2 | ≤ Cn−1/3 (logn)2 .

(3.22)

Assume η 2 6= θ2 . Then we have
P

|Var∗ (σn−1 UnAP∗ ) − Var(σn−1 UnAP )| → 0.
In the proof of Corollaries 3.2 and 3.3, for verifying (2.22), we exploit the weak law of large
numbers for independent but not identically distributed variables. For verifying (2.23), we break
the left-hand side into the sum of an unweighted U-statistic and a negligible term, and apply the
law of large numbers for unweighted U-statistics.
Remark 3.8. The condition η 2 6= θ2 in Corollaries 3.2 and 3.3 is mild. Under the i.i.d. case, it
essentially requires that the Xi ’s are not degenerate random variables. To see this, let θ := P (X1 >
X2 ) and η 2 := E{P (X1 > X2 | X1 )2 }. Since the Xi ’s are i.i.d., it follows that
|P (Xi > Xj ) − θ| = 0 and |E{P (Xj > Xi | Xi )P (Xk > Xi | Xi )} − η 2 | = 0.
Jensen’s inequality implies that η 2 ≥ θ2 , with equality only if Xi is a degenerate random variable.

3.2

Numerical experiments

In this section, we evaluate the developed theory and examine the finite sample behavior of Kendall’s
tau and AP correlation via synthetic data analysis. Both central limit theorem and bootstrap inference validity are examined under different data heterogeneity degree. The numerical results show
that central limit theorem holds under relatively weaker data homogeneity requirement, whereas
bootstrap variance estimation is much more sensitive to data heterogeneity. These observations
agree with the theory developed in this manuscript.
In the first simulation study, we examine the validity of central limit theorem for Kendall’s tau
and AP correlation. We consider generating the data from Gaussian distribution and t-distribution.
For Gaussian distribution, each time, we generate the data sequence X1 ,...,Xn with Xi ∼ N (θi ,1) for
i ∈ [n]. The means {θi ,i ∈ [n]} are assigned equally spaced between Rn and 0, with Rn = max|θi − θj |
representing the heterogeneity degree, taking values 0, 10, 30, and 50. For t-distribution, we
generate X1 ,...,Xn with Xi follows noncentral t-distribution with noncentrality parameter θi and 5
degrees of freedom. The noncentrality parameters {θi ,i ∈ [n]} are assigned equally spaced between
Rn and 0, and Rn takes values 0, 8, 25, and 42. We choose these Rn , so that the difference between
the means of X1 and Xn are similar under Gaussian distribution and under t-distribution. We
consider the sample size n being 50, 100, 200, and 500.
16

Under each setting, we repeat the simulation for 50,000 times. We use two goodness-of-fit tests
to examine the normality of the considered statistics: Cramer-von Mises test (CvM) and Lilliefors
test (L). Both tests are implemented in the R package “Rnortest”, and we refer the readers to
Thode (2002) for detailed descriptions on these tests. We also calculate the coverage probability
for confidence intervals of nominal level 80% and 95% based on Gaussian approximation.
Table 1 presents the p-values of two tests for normality and the coverage probabilities, when the
data are generated from Gaussian distribution. For both statistics, with large sample size (n = 500)
normality is plausible for Rn up to 50, as both tests fail to reject at significance level 0.05. Test
rejection occurs as sample size decreases. In terms of confidence interval, for sample size as small
as n = 50, the coverage probabilities are all close to the nominal level even for large Rn . Note that
with Rn = 50 the 95% confidence interval for UnAP becomes slightly conservative, especially with
smaller sample size.
Table 2 presents the p-values and the coverage probabilities when the data follow noncentral
t-distribution. The trend is similar to that of Table 1, while by comparison, we observed that
the statistics are more robust to location shifts for the heavy-tailed t-distribution as compared to
Gaussian distribution, supporting our theoretical discoveries.
In the second simulation study, we examine the bootstrap variance estimation consistency and
present the results in Tables 3 - 6. We consider the following three approaches: (i) bootstrapping
the original U-statistic as in Theorem 2.6, termed as “Efron” in the tables; (ii) bootstrapping the
main term of the U-statistic as in Theorem 2.4, termed as “Efron-main term” in the tables; (iii)
the new resampling strategy as in Theorem 2.10, termed as “moving-block” in the tables. Among
them, the “Efron-main term” bootstrap is not of practical use because it requires knowledge of
h1i (Xi ), which depends on the probability distribution of Xi . We include it for theoretical purpose
in order to validate Theorem 2.4. Similar to the first simulation study, we generate the data from
Gaussian distribution and t-distribution. For Gaussian distribution, we simulate Xi ∼ N (θi ,1). For
t-distribution, we simulate Xi following noncentral t-distribution with noncentrality parameter θi
and 5 degrees of freedom. For both distributions, parameters {θi ,i ∈ [n]} are assigned equally spaced
between Rn and 0, and the degree of heterogeneity Rn is set to be 0, 1, 2, and 3. We consider
the sample size n being 50, 100, 200, and 500. We set the number of bootstrap replicates within
each simulation to be 2,000 in bootstrap approaches (i) and (ii), 200 for each block in bootstrap
approach (iii), and the block-size in (iii) to be n/5.
Under each setting, we repeat the simulation for 50,000 times. In the “bias” column of each
table, we present the relative bias of the bootstrap variance estimators, where the relative bias
d n )}/Var(Un ). Relative bias being positive/negative means that the
is defined as {Var(Un ) − Var(U
bootstrap method tends to underestimate/overestimate the variance. We also compute the coverage
probability for confidence intervals of nominal level 80% and 95% based on Gaussian approximation
and the estimated variance.

17

Table 3 shows the performance of three bootstrap variance estimators for UnKen when Xi follows
Gaussian distribution. When there is no heterogeneity in the data (Rn = 0), all three bootstrap
methods consistently estimates the variance, with close to zero bias and close to nominal level
confidence interval coverage. As the distribution of Xi becomes more heterogeneous (larger Rn ),
bootstrapping the main-term still estimates the variance consistently, whereas Efron’s bootstrap
and the moving-block bootstrap tend to overestimates the variance, resulting in negative relative
bias and larger than nominal confidence interval coverage. This is as expected due to Corollary
3.1 and Corollary 3.2. Table 4 gives the bootstrap performance for UnAP when Xi follows Gaussian
distribution, and the trend is similar to UnKen . A comparison between Table 3 and Table 4 shows
that the finite sample performance of all three bootstrap methods is better for UnAP than for UnKen .
This is consistent with our theoretical findings in Corollary 3.2 and Corollary 3.3. Tables 5 and 6
present the results for both statistics when Xi follows t-distribution. The trends there are similar
to the Gaussian case, and by comparison, the statistics are more robust to location shifts for
t-distribution, supporting our theorems.
Comparing the first and the second simulation studies, we see that the central limit theorem
for our considered statistics holds under much weaker homogeneity conditions than the resampling
procedures. This is as expected due to the theory developed in Section 3.1. We also see that central
limit theorem holds approximately with sample size as small as n = 50, whereas bootstrap variance
estimation requires much larger sample size to have decent performance.
Table 1: Asymptotic normality of UnKen and UnAP when Xi follows Gaussian distribution.
Rn = 0
p-value

Rn = 10

cov.prob.(%)

p-value

Rn = 30

cov.prob.(%)

p-value

Rn = 50

cov.prob.(%)

p-value

cov.prob.(%)

statistic

n

CvM

L

80%

95%

CvM

L

80%

95%

CvM

L

80%

95%

CvM

L

80%

95%

UnKen

50
100
200
500

0.11
0.10
0.78
0.92

0.05
0.09
0.67
0.68

79.5
79.9
80.1
80.2

95.1
95.0
95.1
94.9

0.00
0.00
0.61
0.09

0.00
0.00
0.43
0.10

79.7
80.1
80.1
80.3

95.1
95.0
95.1
95.0

0.00
0.00
0.02
0.32

0.00
0.00
0.01
0.21

82.1
80.0
79.9
80.1

94.1
94.9
94.9
95.0

0.00
0.00
0.02
0.33

0.00
0.00
0.00
0.26

79.4
81.3
80.1
79.9

95.0
95.0
95.0
95.0

UnAP

50
100
200
500

0.37
0.23
0.02
0.88

0.63
0.12
0.07
0.87

80.0
79.9
79.9
79.9

95.0
95.0
95.0
94.9

0.00
0.02
0.71
0.69

0.01
0.04
0.54
0.67

79.8
79.9
80.0
79.8

95.2
95.1
95.0
95.1

0.00
0.00
0.01
0.19

0.00
0.00
0.08
0.23

79.6
79.9
79.8
80.1

95.8
95.2
95.1
95.1

0.00
0.00
0.01
0.06

0.00
0.00
0.09
0.09

81.1
79.7
79.7
79.9

96.0
95.5
95.3
95.0

4

Discussion

One of the main focus of this manuscript is the consistency of bootstrap variance estimator for
U-statistics under data heterogeneity. The proof is based on brutal combinatorial calculation. This
cannot be readily extended to analyzing bootstrap distributional consistency. We believe using

18

Table 2: Asymptotic normality of UnKen and UnAP when Xi follows t-distribution.
Rn = 0
p-value

Rn = 8

cov.prob.(%)

p-value

Rn = 25

cov.prob.(%)

p-value

Rn = 42

cov.prob.(%)

p-value

cov.prob.(%)

statistic

n

CvM

L

80%

95%

CvM

L

80%

95%

CvM

L

80%

95%

CvM

L

80%

95%

UnKen

50
100
200
500

0.29
0.06
0.64
0.62

0.06
0.09
0.36
0.59

79.6
80.0
80.0
80.0

95.1
95.0
94.9
95.0

0.00
0.00
0.01
0.20

0.00
0.00
0.06
0.33

79.9
80.0
80.0
80.0

95.2
95.1
95.1
95.0

0.00
0.00
0.00
0.75

0.00
0.00
0.00
0.88

80.6
80.1
80.1
80.0

95.2
95.1
95.1
95.0

0.00
0.00
0.00
0.51

0.00
0.00
0.00
0.44

80.7
79.9
80.2
80.0

95.1
95.1
95.0
95.0

UnAP

50
100
200
500

0.72
0.08
0.74
0.53

0.39
0.11
0.62
0.75

79.9
80.0
79.8
80.1

95.0
95.1
95.1
94.8

0.33
0.02
0.01
0.54

0.32
0.04
0.11
0.62

80.1
80.0
80.0
79.9

95.0
95.0
94.9
95.1

0.00
0.03
0.00
0.29

0.00
0.08
0.03
0.35

80.1
80.1
80.2
80.1

95.1
95.0
95.0
95.1

0.00
0.03
0.00
0.16

0.00
0.02
0.01
0.36

80.1
80.1
80.2
79.9

95.1
95.0
95.0
95.1

Table 3: Bootstrap variance estimation validity for UnKen when Xi follows Gaussian distribution.
Rn = 0

Rn = 1

Rn = 2

Rn = 3

cov.prob.(%)

cov.prob.(%)

cov.prob.(%)

cov.prob.(%)

bootstrap method

n

bias

80%

95%

bias

80%

95%

bias

80%

95%

bias

80%

95%

Efron

50
100
200
500

0.02
-0.02
-0.02
-0.01

79.5
80.8
80.6
79.9

95.0
95.2
95.1
95.4

-0.10
-0.13
-0.14
-0.13

82.1
83.0
83.2
82.7

95.9
96.1
96.4
96.3

-0.49
-0.51
-0.55
-0.52

88.4
88.8
89.0
88.9

98.1
98.3
98.8
98.5

-1.25
-1.23
-1.31
-1.28

94.6
94.7
95.0
94.5

99.7
99.5
99.6
99.7

Efron-main term

50
100
200
500

0.06
0.00
0.00
-0.01

78.1
80.1
79.9
79.7

93.6
94.6
94.8
95.4

0.07
0.02
-0.01
-0.01

77.9
79.0
80.3
80.0

93.4
94.1
94.8
95.0

0.07
0.03
-0.01
0.00

77.5
78.8
80.3
79.9

93.1
93.7
94.8
94.9

0.07
0.05
-0.01
0.00

77.0
78.6
80.0
79.8

92.3
93.4
94.8
94.6

moving-block

50
100
200
500

-0.28
-0.17
-0.09
-0.04

85.4
83.5
82.1
80.4

97.3
96.6
95.8
95.6

-0.42
-0.29
-0.22
-0.16

87.9
85.7
84.5
83.3

98.1
97.3
97.0
96.6

-0.93
-0.73
-0.66
-0.57

92.8
90.7
90.1
89.2

99.2
99.0
99.0
98.6

-1.92
-1.55
-1.48
-1.34

97.1
96.2
95.8
94.9

99.9
99.7
99.7
99.7

19

Table 4: Bootstrap variance estimation validity for UnAP when Xi follows Gaussian distribution.
Rn = 0

Rn = 1

Rn = 2

Rn = 3

cov.prob.(%)

cov.prob.(%)

cov.prob.(%)

cov.prob.(%)

bootstrap method

n

bias

80%

95%

bias

80%

95%

bias

80%

95%

bias

80%

95%

Efron

50
100
200
500

0.01
-0.03
-0.02
-0.02

79.6
80.6
81.1
80.5

94.9
95.5
95.0
96.0

-0.05
-0.09
-0.09
-0.09

80.5
81.9
82.6
81.9

95.5
95.9
95.5
96.0

-0.25
-0.29
-0.30
-0.30

84.9
85.6
85.9
85.6

97.3
97.3
97.2
97.3

-0.53
-0.59
-0.62
-0.61

89.0
89.7
89.7
89.9

98.5
98.5
98.8
98.6

Efron-main term

50
100
200
500

0.10
0.04
0.02
0.00

76.2
79.0
79.7
79.8

93.3
94.2
94.9
95.4

0.12
0.04
0.01
0.00

75.8
78.3
80.1
79.7

92.9
94.5
94.7
95.1

0.13
0.05
0.02
0.01

75.4
77.7
79.7
79.8

92.7
93.9
94.7
95.0

0.14
0.07
0.02
0.01

74.7
76.6
78.8
79.4

92.2
93.6
94.8
94.7

moving-block

50
100
200
500

-0.49
-0.33
-0.19
-0.11

88.5
86.0
84.1
82.3

98.4
97.5
96.8
96.6

-0.58
-0.42
-0.28
-0.18

89.5
87.2
85.9
83.6

98.8
97.9
97.2
97.0

-0.87
-0.68
-0.53
-0.41

91.8
90.6
88.6
87.2

99.3
98.8
98.3
97.8

-1.30
-1.06
-0.90
-0.75

94.6
93.5
92.3
91.6

99.7
99.4
99.4
99.0

Table 5: Bootstrap variance estimation validity for UnKen when Xi follows t-distribution.
Rn = 0

Rn = 1

Rn = 2

Rn = 3

cov.prob.(%)

cov.prob.(%)

cov.prob.(%)

cov.prob.(%)

bootstrap method

n

bias

80%

95%

bias

80%

95%

bias

80%

95%

bias

80%

95%

Efron

50
100
200
500

0.03
-0.02
0.03
0.01

79.5
80.1
79.2
79.8

94.5
95.1
94.6
94.7

-0.08
-0.13
-0.09
-0.09

81.3
82.9
82.2
81.2

96.2
96.3
96.0
95.9

-0.40
-0.46
-0.42
-0.40

87.0
88.1
87.1
86.9

98.0
98.3
98.2
97.8

-0.88
-0.97
-0.91
-0.89

91.9
93.0
92.3
92.0

99.2
99.4
99.3
99.3

Efron-main term

50
100
200
500

0.08
0.01
0.04
0.02

77.5
79.1
78.8
79.2

93.1
94.6
94.3
94.7

0.08
0.01
0.03
0.03

76.4
79.5
79.4
78.7

93.5
94.7
94.3
94.4

0.09
0.01
0.03
0.03

76.8
78.5
79.3
79.0

92.4
94.6
94.2
94.1

0.09
0.01
0.02
0.02

77.2
79.2
79.3
79.5

91.7
94.2
94.2
94.6

moving-block

50
100
200
500

-0.26
-0.17
-0.04
-0.02

85.1
83.5
80.8
80.2

97.1
96.6
95.4
95.0

-0.40
-0.30
-0.17
-0.12

87.0
85.7
83.7
81.9

98.2
97.4
96.8
96.1

-0.81
-0.67
-0.52
-0.44

91.5
90.5
88.5
87.4

99.0
98.9
98.6
98.1

-1.44
-1.25
-1.05
-0.94

95.7
94.8
93.3
92.6

99.6
99.6
99.4
99.3

20

Table 6: Bootstrap variance estimation validity for UnAP when Xi follows t-distribution.
Rn = 0

Rn = 1

Rn = 2

Rn = 3

cov.prob.(%)

cov.prob.(%)

cov.prob.(%)

cov.prob.(%)

bootstrap method

n

bias

80%

95%

bias

80%

95%

bias

80%

95%

bias

80%

95%

Efron

50
100
200
500

0.02
0.01
0.02
-0.01

79.2
79.8
79.7
80.0

95.1
94.7
94.7
94.6

-0.05
-0.04
-0.05
-0.07

80.6
81.1
81.0
81.0

95.8
95.2
95.4
95.7

-0.21
-0.20
-0.22
-0.24

84.0
84.2
84.1
84.3

96.8
96.7
97.0
97.0

-0.43
-0.41
-0.44
-0.47

87.3
86.6
87.7
87.7

98.2
98.1
98.1
98.2

Efron-main term

50
100
200
500

0.11
0.07
0.05
0.01

75.7
77.9
78.6
79.4

93.1
94.2
94.0
94.6

0.11
0.07
0.05
0.01

75.5
77.7
78.8
79.3

93.4
94.3
94.1
94.7

0.13
0.08
0.05
0.02

75.0
77.0
78.2
79.1

92.9
93.9
94.2
94.6

0.13
0.08
0.05
0.00

75.4
77.0
78.3
79.3

92.8
94.1
94.5
94.7

moving-block

50
100
200
500

-0.48
-0.28
-0.15
-0.09

88.3
85.4
83.1
81.5

98.3
97.5
96.3
95.8

-0.58
-0.35
-0.23
-0.16

89.4
86.8
84.3
83.3

98.7
97.8
97.0
96.3

-0.81
-0.56
-0.43
-0.34

91.6
89.1
87.0
85.7

99.3
98.6
98.2
97.6

-1.14
-0.83
-0.69
-0.59

93.8
91.7
90.6
89.3

99.7
99.3
98.8
98.6

techniques developed by Mammen (2012) and Hall (1992), it is promising to devise the corresponding bootstrap distributional consistency theory. However, there are still some challenges and
open problems to be resolved before rigorous distributional consistency theory can be established.
Details will be worked out in a future work.
We have considered U-statistics with data that are independent but not identically distributed.
In the literature, there have been many developments of bootstrap methods for stationary time
series since the seminal work of block bootstrap methods by Kunsch (1989). See, for example,
Politis and Romano (1992), Lahiri (1993), and Politis and Romano (1994). Among the few developments for nonstationary time series, Fitzenberger (1998) showed that block bootstrap is robust
for linear regression estimation, and Gonçalves and White (2002) established the consistency for
block bootstrap variance estimator of sample means. To the best of knowledge, there is no work
on bootstrapping U-statistics in the nonstationary time-series setting. It would be interesting to
extend our current techniques in this manuscript to allow for dependent data. We believe our
technique and the techniques used in the bootstrapping time-series literature (e.g., Carlstein et al.
(1998), Paparoditis and Politis (2001), and Shao (2010)) can be potentially combined for analyzing
bootstrapping U-statistics for nonstationary time series data. However, the analysis will become
even more challenging technically, and will be left for future research.

21

Acknowledgement
We thank the editor, the associate editor, and two anonymous referees for their careful reviews
and constructive comments. Dr. Fang Han’s research is supported by NSF grant DMS-1712536
and a UW faculty start-up grant. Dr. Tianchen Qian’s research is supported by Patient-Centered
Outcomes Research Institute (ME-1306-03198).

A

Proofs of main results

In this section, we prove theoretical results presented in the manuscript. The results are proved
in the order they appear in the manuscript. For succinctness, the supporting lemmas that appear
in the proof are proven in Section B. In those proof, sometimes we also have to refer to certain
auxiliary results. Those are numbered by C.

A.1

Proof of Theorem 2.1

Proof. By Lemma 2.2, we have
P


Var(Un ) 1/2 Un − E(Un ) n−1 ni=1 h1,i (Xi ) Un (a,h2 )
=
+
.
(A.1)
V (n)
Var(Un )1/2
V (n)1/2
V (n)1/2
For proving Theorem 2.1, by Slutsky’s theorem it suffices to establish the following results:
n
X
d
−1/2 −1
V (n)
n
h1,i (Xi ) → N (0,1),
(A.2)
i=1
−1/2

V (n)

P

Un (a,h2 ) → 0,

(A.3)

and
Var(Un )/V (n) → 1.

(A.4)

First we show (A.2) using Lyapunov’s Central Limit Theorem (Lemma C.4). The following
P
lemma gives bound on ni=1 E|h1,i (Xi )|3 .
Lemma A.1. For A3,1 (n) defined in (2.6) and M (n) defined in (2.7), we have
n
X

E|h1,i (Xi )|3 ≤ CnA3,1 (n)M (n)3/4 ,

i=1

where C is some absolute constant.
By Lemma A.1 and the fact that E{h1,i (Xi )} = 0, we deduce
n
X

E|h1,i (Xi ) − E{h1,i (Xi )}|3 ≤ CnA3,1 (n)M (n)3/4 .

i=1

22

(A.5)

Since V (n) := n−2

Pn

i=1 Var{h1,i (Xi )},

it follows from (A.5) and (2.9) that

Pn

3
i=1 E|h1,i (Xi ) − E{h1,i (Xi )}|
i3/2
n
2
i=1 E|h1,i (Xi ) − E{h1,i (Xi )}|

hP

≤

CnA3,1 (n)M (n)3/4
→ 0.
n3 V (n)3/2

(A.6)

Equation (A.6) and Lemma C.4 with δ = 1 yield (A.2).
Next we show (A.3). To simplify notation, let i denote the index vector (i1 ,...,im ) and Xi
denote (Xi1 ,...,Xim ). Consider two index vectors i,j from Inm . If i ∩ j = ∅, by independence of the
Xi ’s we have Cov{h2;i (Xi ),h2;j (Xj )} = 0. If i ∩ j = ip = jq for some p,q ∈ [n] (i.e., the two vectors
only share one common index), Lemma C.2 and (2.15) imply that
Cov{h2;i (Xi ),h2;j (Xj )} = Cov[E{h2;i (Xi ) | Xip },E{h2;j (Xj ) | Xjq }] = 0.
Therefore, we have
Var{Un (a,h2 )} =

n (n − m)! o2
n!

X

a(i)a(j)Cov{h2;i (Xi ),h2;j (Xj )}.

(A.7)

i,j∈(Inm )⊗2
≥2

By Lemma C.1(i) and Cauchy-Schwarz inequality, the right-hand side of (A.7) is bounded by
Cn−2 A2,2 (n)M (n)1/2 for some absolute constant C, where A2,2 (n) is defined in (2.6). This combined
with (2.8) yields that
V (n)−1 Var{Un (a,h2 )} ≤ CV (n)−1 n−2 A2,2 (n)M (n) → 0.
Equation (A.3) follows from (A.8) and Lemma C.3.
Lastly, we establish (A.4). Taking variance on both sides of (A.1) gives
n Pn h (X ) U (a,h ) o
Var(Un )
Var{Un (a,h2 )}
i
n
2
i=1 1,i
= 1+
+ Cov
,
V (n)
V (n)
nV (n)1/2
V (n)1/2
Var{Un (a,h2 )}
= 1+
V (n)

(A.8)

(A.9)

Equations (A.8) and (A.9) imply that
Var(Un )/V (n) → 1.
This completes the proof.

A.2

Proof of Lemma 2.2

Proof. We have
Un − E(Un ) =

n
X

n
h
i
X
{E(Un | Xi ) − E(Un )} + Un − E(Un ) −
{E(Un | Xi ) − E(Un )} .

i=1

i=1

For proving Lemma 2.2, it suffices to show
n
n
X
1X
{E(Un | Xi ) − E(Un )} =
h1,i (Xi )
n
i=1

i=1

23

(A.10)

and
Un − E(Un ) −

n
X
(n − m)! X
{E(Un | Xi ) − E(Un )} =
a(i1 ,...,im )h2;i1 ,...,im (Xi1 ,...,Xim ),
n!
m
i=1

(A.11)

In

where h1,i (·) and h2;i1 ,...,im (·) are defined in (2.14) and (2.15), respectively.
First we establish (A.10). We have
i
h
(n − m)! X
E(Un | Xi ) − E(Un ) =
a(i1 ,...,im ) E{h(Xi1 ,...,Xim ) | Xi } − θ(i1 ,...,im ) .
n!
m

(A.12)

In

Consider a fixed i ∈ [n] and fixed (i1 ,...,im ) ∈ Inm . If i ∈
/ {i1 ,...,im },
E{h(Xi1 ,...,Xim ) | Xi } − θ(i1 ,...,im ) = 0 a.s..
It follows that
i
h
X
a(i1 ,...,im ) E{h(Xi1 ,...,Xim ) | Xi } − θ(i1 ,...,im )
Inm

X

=

h
i
a(i,i1 ,...,im−1 ) E{h(Xi ,Xi1 , ...,Xim−1 ) | Xi } − θ(i,i1 ,...,im−1 )

m−1
In−1
(−i)

h
i
a(i1 ,i,i2 ,...,im−1 ) E{h(Xi1 ,Xi ,Xi2 ,...,Xim−1 ) | Xi } − θ(i1 ,i,i2 ,...,im−1 ) + ···

X

+

m−1
In−1
(−i)

h
i
a(i1 ,...,im−1 ,i) E{h(Xi1 , ...,Xim−1 ,Xi ) | Xi } − θ(i1 ,...,im−1 ,i)

X

+

m−1
In−1
(−i)

X

=

m
X

h
i
a(l) (i;i1 ,...,im−1 ) E{h(l) (Xi ;Xi1 ,...,Xim−1 ) | Xi } − θ(l) (i;i1 ,...,im−1 ) .

(A.13)

m−1
In−1
(−i) l=1

By the definition of h1,i (·), (A.13) equals {(n − 1)!/(n − m)!}h1,i (Xi ). Combining this with (A.12)
yields (A.10).
Pn
Next we establish (A.11). The following lemma shows that
i=1 {E(Un | Xi ) − E(Un )} is a
U-statistic.
Lemma A.2. We have
m X
n
h
i
X
X
a(l) (i;i1 ,...,im−1 ) E{h(l) (Xi ;Xi1 ,...,Xim−1 ) | Xi } − θ(l) (i;i1 ,...,im−1 )
l=1 i=1 I m−1 (−i)
n−1

=

X
Inm

m
hX
i
a(i1 ,...,im )
E{h(Xi1 ,...,Xim ) | Xij } − mθ(i1 ,...,im ) .

(A.14)

j=1

Using Lemma A.2, it follows from (A.13) that
n
m
hX
i
X
X
{E(Un | Xi ) − E(Un )} =
a(i1 ,...,im )
E{h(Xi1 ,...,Xim ) | Xij } − mθ(i1 ,...,im ) .
i=1

Inm

j=1

By the definition of h2;i1 ,...,im (·), we deduce that (A.11) holds.
24

Equations (2.14) and (2.15) follow immediately from the definitions in (2.4) and (2.5). This
completes the proof.

A.3

Proof of Theorem 2.4

Proof. In Lemma C.6, let Yn,i = σn−1 h1,i (Xi ), gn be the identity function, tn = 0 and σn2 = 1. By the
P
definition of Tbn we have Tbn = n−1 ni=1 σn−1 h1,i (Xi ). Equation (2.17) implies (C.2). (2.18) implies
(C.3). Equations (A.2), (2.10) and Slutsky’s theorem imply that for any t ∈ R,
n
o
P Tbn − tn ≤ t − Φ(t) → 0.
By Lemma C.5 the above convergence is uniform in t ∈ R. This yields (C.4). Therefore, all conditions in Lemma C.6 hold, which implies
X

X

n
n
n
{h1,i (Xi )}∗ X h1,i (Xi )
h1,i (Xi )
P
∗
sup P
−
≤ t −P
≤ t → 0.
nσ
nσ
nσ
n
n
n
t∈R
i=1

i=1

i=1

This proves (2.19). Equation (2.20) follows immediately from Theorem 2.1.

A.4

Proof of Theorem 2.6

Proof. By the definition of σn2 , we have Var(σn−1 Un ) = 1. For proving Theorem 2.6 it suffices to
show that
P

Var∗ (σn−1 Un∗ ) → 1.

(A.15)

In Lemma 2.2, replacing Xi by Xi∗ yields
n

Un∗ − E(Un ) =

1X
h1,i (Xi∗ ) + Un∗ (a,h2 ),
n

(A.16)

i=1

where
Un∗ (a,h2 ) :=

(n − m)! X
a(i1 ,...,im )h2;i1 ,...,im (Xi∗1 ,...,Xi∗m ).
n!
m

(A.17)

In

Multiplying σn−1 and then taking Var∗ on both sides of (A.16) yields
n
n
n ∗
o
nX
nX
h1,i (Xi∗ ) Un∗ (a,h2 ) o
h1,i (Xi∗ ) o
∗ Un (a,h2 )
∗
∗ −1 ∗
∗
Var (σn Un ) = Var
+ Var
+ Cov
,
, (A.18)
nσn
σn
nσn
σn
i=1

i=1

∗

where Cov (·) denotes the covariance operator on the empirical measure. By (A.18) and Slutsky’s
theorem, for proving (A.15) it suffices to show the following:
n
nX
h1,i (Xi∗ ) o P
∗
Var
→ 1,
(A.19)
nσn
i=1
n U ∗ (a,h ) o
P
2
n
Var∗
→ 0,
(A.20)
σn

25

and
Cov∗

n
nX
h1,i (Xi∗ ) Un∗ (a,h2 ) o P
→ 0,
,
nσn
σn

(A.21)

i=1

First we prove (A.19). Since conditional on X1 ,...,Xn the Xi∗ ’s are i.i.d. draws from the
empirical distribution of X1 ,...,Xn , we have
n
n
n
n n
hn X
h1,i (Xi∗ ) o2 i 1 X X n h1,i (Xj ) o2 1 X X X h1,i1 (Xj1 ) h1,i2 (Xj2 )
E∗
=
+ 2
,
(A.22)
nσn
n
nσn
n
nσn
nσn
i=1

i1 6=i2 j1 =1 j2 =1

i=1 j=1

and
n
n
n
n
n
h nX
h1,i (Xi∗ ) oi2
1 n X X h1,i1 (Xj1 ) on X X h1,i2 (Xj2 ) o
= 2
E∗
nσn
n
nσn
nσn
i1 =1 j1 =1

i=1

i2 =1 j2 =1

n
n
n
n
n
1 X n X h1,i (Xj1 ) on X h1,i (Xj2 ) o 1 X X X h1,i1 (Xj1 ) h1,i2 (Xj2 )
= 2
.
+ 2
n
nσn
nσn
n
nσn
nσn
i=1

j1 =1

(A.23)

i1 6=i2 j1 =1 j2 =1

j2 =1

Equations (A.22) and (A.23) yield
n
n
n
nX
hn X
h1,i (Xi∗ ) o
h1,i (Xi∗ ) o2 i h ∗ n X h1,i (Xi∗ ) oi2
Var∗
= E∗
− E
nσn
nσn
nσn
i=1

=

1
n

i=1
n
n n
XX
i=1 j=1

i=1

n
n
h1,i (Xj ) o2 1 X n X h1,i (Xj ) o2
− 2
.
nσn
n
nσn
i=1

(A.24)

j=1

Equation (A.19) follows from (A.24), (2.22), (2.23), and Slutsky’s theorem.
The following lemma establishes (A.20).
P

Lemma A.3. Under conditions of Theorem 2.6, we have Var∗ {Un∗ (a,h2 )/σn } → 0, where Un∗ (a,h2 )
is defined in (A.17).
Equation (A.21) follows from (A.19), (A.20), and Cauchy-Schwarz inequality. This completes
the proof.

A.5

Proof of Corollary 2.1

Proof. For proving Corollary 2.1, by Theorem 2.6, it suffices to show (2.22), (2.23), and (2.24) when
the Xi ’s are i.i.d..
First we show (2.22). Equations (2.7), (2.8), and (2.9) imply (2.10) according to Theorem
2.1. By the i.i.d.-ness of the Xi ’s we have E{h1,i (Xj )} = E{h1,i (Xi )} = 0 and E{h1,i (Xj )2 } =
E{h1,i (Xi )2 }. It follows from (2.10) that for any j ∈ [n],
Pn
n
n n
hX
Var{h1,i (Xi )}
h1,i (Xj ) o2 i X E{h1,i (Xj )2 }
=
= i=1 2 2
→ 1.
(A.25)
E
2
2
nσn
n σn
n σn
i=1

i=1

26

By the weak law of large numbers for i.i.d. random variables, we have
n n
n n
hX
h1,i (Xj ) o2 i P
1 X X n h1,i (Xj ) o2
−E
→ 0.
n
nσn
nσn
Equations (A.25), (A.26), and Slutsky’s theorem yield (2.22).
Next we prove (2.23). By algebra we have
n
n
n
n n
1 X X n h1,i (Xj ) o2 1 X X h1,i (Xj1 )h1,i (Xj2 )
1 X n X h1,i (Xj ) o2
=
+
.
n2
nσn
n2
nσn
n2
n2 σn2
i=1

j=1

(A.26)

i=1

j=1 i=1

(A.27)

j1 6=j2 i=1

j=1 i=1

Equation (2.22) implies that the first term on the right-hand side of (A.27) converges to 0 in
probability. The second term on the right-hand side of (A.27) equals (n − 1)/n times a U-statistic
P
with symmetric kernel g(x,y) = n−2 σn−2 ni=1 h1,i (x)h1,i (y). By the triangle inequality, Jensen’s
inequality, and the i.i.d.-ness of the Xi ’s, we deduce
n
n
n h (X ) 2 o
X
X
h1,i (X1 )
h1,i (X2 )
1,i
i
E |g(X1 ,X2 )| ≤
E
≤ 1.
(A.28)
E
≤
E
nσn
nσn
nσn
i=1

i=1

The i.i.d.-ness of the Xi ’s and the fact that E{h1,i (Xi )} = 0 yield
E{g(X1 ,X2 )} = n−2 σn−2

n
X

E{h1,i (X1 )}E{h1,i (X2 )} = 0.

(A.29)

i=1

By (A.28) and (A.29), it follows from the weak law of large numbers for U-statistics of i.i.d. variables
(Serfling, 1980, Theorem 5.4 A) that the second term on the right-hand side of (A.27) converges
to 0 in probability. Therefore, by Slutsky’s theorem, the left-hand side of (A.27) converges to 0 in
probability, which establishes (2.23).
Lastly, we establish (2.24). By the definition of θ(·) in (2.2), we have θ(i1 ,...,im ) − θ(j1 ,...,jm ) =
0 for any (i1 ,...,im ) and (j1 ,...,jm ) in Inm . This implies that M1 (n) = 0. For any p,q ∈ [m] and
r,s,k ∈ Inm such that r ∩ s = k ∩ s = rp = sq = kp , by the i.i.d.-ness of the Xi ’s, we have
h n
oi
E E h(Xr1 ,...,Xrm )h(Xs1 ...Xsm ) | Xkp
h n
oi
= E E h(X1 ,...,Xm )h(Xm+1 ,...,Xm+q−1 ,Xp ,Xm+q ,...,X2m−1 ) | Xp ,
(A.30)
and
h n
oi
E E h(Xk1 ,...,Xkm )h(Xs1 ,...,Xsm ) | Xkp
h n
oi
= E E h(X1 ,...,Xm )h(Xm+1 ,...,Xm+q−1 ,Xp ,Xm+q ,...,X2m−1 ) | Xp .

(A.31)

Equations (A.30) and (A.31) imply that M2 (n) = 0. Therefore, (2.24) follows from the fact that
M1 (n) = M2 (n) = 0 and the assumption that n−2 σn−2 A2,1 (n) → 0.

27

A.6

Proof of Theorem 2.10

Proof. By the definition of Vn∗ , we have
Vn∗ =
=

n−b+1
X
1
∗
Var∗ (Ub,i
)
hn (n − b + 1)

1
hn (n − b + 1)

i=1
n−b+1
X

σb2 (1 + oP (1))

i=1

1
= σb2 (1 + oP (1)),
hn
where the second equality follows from the assumption Var(Ub,i (Xi ,...,Xi+b−1 )) = σb2 (1 + o(1)) and
Theorem 2.6. This combines with the assumption σb2 /σn2 = ζn,b · (1 + o(1)) gives the desired result.

A.7

Proof of Lemma 3.1

Proof. For UnKen we have a(i,j) = 1(j < i) and h(Xi ,Xj ) = 1(Xj > Xi ). Using definitions in (2.2)
(1)
(2)
and (2.3), we have fi (x) = E{h(x,Xi )} = P (Xi > x), fi (x) = E{h(Xi ,x)} = 1 − P (Xi > x), and
θ(i,j) = 1 − θ(j,i). By Lemma 2.2 we obtain
n

hKen
1,i (x) =

=

1 X
(1)
(2)
a(i,j){fj (x) − θ(i,j)} + a(j,i){fj (x) − θ(j,i)}
n−1
1
n−1

j=1
j6=i
n
X

{1(j < i) − 1(j > i)}{P (Xj > x) − θ(i,j)},

j=1

and
(1)

(2)

hKen
2;i,j (x,y) = h(x,y) − fj (x) − fi (y) + θ(i,j) = 1(y > x) − P (Xj > x) − P (y > Xi ) + θ(i,j).
This completes the proof.

A.8

Proof of Lemma 3.2

Proof. For UnAP , we have a(i,j) = n(i − 1)−1 1(j < i) and h(Xi ,Xj ) = 1(Xj > Xi ). The form of
(1)
(2)
fi (x) and fi (x) is the same as in the proof of Lemma 3.1. By Lemma 2.2 we obtain
n

hAP
1,i (x) =

=

1 X
(1)
(2)
a(i,j){fj (x) − θ(i,j)} + a(j,i){fj (x) − θ(j,i)}
n−1
1
n−1

j=1
j6=i
n n
X
j=1

n1(j < i) n1(j > i) o
−
{P (Xj > x) − θ(i,j)},
i−1
j −1

and
(1)

(2)

hAP
2;i,j (x,y) = h(x,y) − fj (x) − fi (y) + θ(i,j) = 1(y > x) − P (Xj > x) − P (y > Xi ) + θ(i,j).
28

This completes the proof.

A.9

Proof of Theorem 3.3

Proof. We divide the proof into two parts. In Part I, we prove the theorem for UnAP . In Part II,
we prove the theorem for UnKen .
Part I (for UnAP ). By Theorem 2.1, for proving asymptotic normality of UnAP , it suffices
to show that (2.7), (2.8), and (2.9) hold under the assumption of Theorem 3.1. Equation (2.7)
holds trivially with M (n) = 1 due to boundedness of the kernel function h(·). In the following, we
establish (2.8) and (2.9) by calculating the orders of A2,2 (n), A3,1 (n), and V (n).
First we derive upper bound on A2,2 (n) and A3,1 (n). We will repeatedly use Lemma C.8 to
bound the partial sum of harmonic series. By the definition of A2,2 (n) in (2.6), we have
1 X
1 X
|a(i1 ,j1 )a(i2 ,j2 )| = 2
a(i,j)2 + a(i,j)a(j,i) .
(A.32)
A2,2 (n) := 2
n
n
2
⊗2
(i,j)∈In

(In2 )≥2

Since a(i,j) = n(i − 1)−1 1(j < i), we have a(i,j)a(j,i) = 0 and a(i,i) = 0. It then follows from (A.32)
that
n i−1
n
1 XX n 2 X 1
) =
≤ 1 + log(n − 1).
(A.33)
A2,2 (n) = 2
(
n
i−1
i−1
i=2 j=1

i=2

By the definition of A3,1 (n) in (2.6), we have
n
n
1 X X n
A3,1 (n) = 4
|a(i,j1 )a(i,j2 )a(i,j3 )| + 3|a(i,j1 )a(i,j2 )a(j3 ,i)|
n
i=1 j1 ,j2 ,j3 =1
o
+ 3|a(i,j1 )a(j2 ,i)a(j3 ,i)| + |a(j1 ,i)a(j2 ,i)a(j3 ,i)| .

(A.34)

The term |a(i,j1 )a(i,j2 )a(i,j3 )| is nonzero only if j1 ,j2 ,j3 < i, so the corresponding summation in
(A.34) equals
n

i−1
X

1 X
n4

i=2 j1 ,j2 ,j3 =1

n−1

n
n
n
1X
1 3 n−1
·
·
≤
(i − 1)3 (
) =
.
i−1 i−1 i−1 n
i−1
n

(A.35)

i=1

The term |a(i,j1 )a(i,j2 )a(j3 ,i)| is nonzero only if j1 ,j2 < i < j3 , so the corresponding summation in
(A.34) equals
n−1 i−1
3 X X
n4

n
X

(

i=2 j1 ,j2 =1 j3 =i+1

n−1
n
n−1
1
n 2 n
3X X
3X
n−1
) (
)=
≤
log
≤ 3logn.
i − 1 j3 − 1
n
j3 − 1 n
i−1
i=2 j3 =i+1

(A.36)

i=2

The term |a(i,j1 )a(j2 ,i)a(j3 ,i)| is nonzero only if j1 < i < j2 ,j3 , so the corresponding summation in
(A.34) equals

n
n−1 i−1
n−1 
n
3 XX X
n
n
3X
n−1 2
(
)(
)(
)≤
log
≤ 3(logn)2 .
(A.37)
n4
i − 1 j2 − 1 j3 − 1
n
i−1
i=2 j1 =1 j2 ,j3 =i+1

i=2

29

The term |a(j1 ,i)a(j2 ,i)a(j3 ,i)| is nonzero only if j1 ,j2 ,j3 > i, so the corresponding summation in
(A.34) equals

n−1 
n−1
n
X
n−1 3
1 X
n
n
1X
n
log
·
·
≤
≤ (logn)3 .
(A.38)
n4
j1 − 1 j2 − 1 j3 − 1 n
i−1
i=1

i=1 j1 ,j2 ,j3 =i+1

By (A.35)-(A.38), it follows from (A.34) that
A3,1 (n) ≤ C(logn)3 .
(A.39)
P
Next we establish lower bound on V (n) := n−2 ni=1 Var{hAP
1,i (Xi )}. The following lemma gives
AP
lower bound on |h1,i (Xi )|.
Lemma A.4. Consider a fixed i with 2 ≤ i ≤ n. If δn /2 ≥ log{(n − 1)/(i − 1)}, either Condition (i)
or Condition (ii) in Theorem 3.3 implies
P {|hAP
1,i (Xi )| ≥ δn /2} ≥ pn .

(A.40)

If δn log(n/i) ≥ 2, either Condition (i) or Condition (ii) in Theorem 3.3 implies
P {|hAP
1,i (Xi )| ≥ 1} ≥ pn .

(A.41)

If i ≥ 1 + (n − 1)exp(−δn /2), we have δn /2 ≥ log{(n − 1)/(i − 1)}. Lemma A.4 implies that (A.40)
holds. By Chebyshev’s inequality we deduce
1 2
(A.42)
Var{hAP
1,i (Xi )} ≥ δn pn .
4
If 2 ≤ i ≤ nexp(−2/δn ), we have δn log(n/i) ≥ 2. Lemma A.4 implies that (A.41) holds. By Chebyshev’s inequality we deduce
Var{hAP
1,i (Xi )} ≥ pn .

(A.43)

By (A.42) and (A.43), we have
n
X
i=1

bnexp(− δ2 )c
n

Var{hAP
1,i (Xi )} ≥

X
i=2

pn +

n
X
i=b1+(n−1)exp(− δ2n )c+1

1 2
δ pn
4 n

n
 2
o
 δ  o
1n
n
≥ nexp −
− 2 pn + n − (n − 1)exp −
− 1 δn2 pn
δn
4
2
 2
 δ o δ 2 p n
 δ 
o
nδ 2 pn n
n
n
n
= nexp −
pn + n
1 − exp −
+ n
exp −
− 1 − 2pn .
δn
4
2
4
2
By (3.4) we have
n
 δ o
n
nδn2 pn 1 − exp −
 nδn3 pn  n2/3 (logn)2 .
2
Note that
 2
 δ  o
δ 2 pn n
n
nexp −
pn ≥ 0 and n
exp −
− 1 − 2pn = O(1).
δn
4
2

30

(A.44)

(A.45)

(A.46)

Combining (A.44) with (A.45) and (A.46) gives
n
X

2/3
Var{hAP
(logn)2 .
1,i (Xi )}  n

i=1

This implies
n

V (n) :=

1 X
−4/3
Var{hAP
(logn)2 .
1,i (Xi )}  n
n2

(A.47)

i=1

Equations (A.33), (A.39), and (A.47) yield (2.8) and (2.9). The asymptotic normality of UnAP
then follows from Theorem 2.1. This completes the proof for Part I.
Part II (for UnKen ). Proof for UnKen follows the same logic as the proof for UnAP . In the
following we calculate the orders of A2,2 (n), A3,1 (n), and V (n) for UnKen .
Since a(i,j) = 1(j < i) for UnKen , we have a(i,j)a(j,i) = 0 and a(i,i) = 0. It then follows from
(A.32) that
n i−1

A2,2 (n) =

1 XX
1 = O(1).
n2

(A.48)

i=2 j=1

By (A.34), following the same argument as in (A.35)-(A.38) we deduce
A3,1 (n) = O(1).
(A.49)
P
Next we establish lower bound on V (n) := n−2 ni=1 Var{hKen
1,i (Xi )}. The following lemma gives
lower bound on |hKen
1,i (Xi )|.
Lemma A.5. Consider a fixed i ∈ [n]. If n − i ≤ (i − 1)δn /2, either Condition (i) or Condition (ii)
in Theorem 3.3 implies
n
i − 1 δn o
≥ pn .
(A.50)
P |hKen
(X
)|
≥
i
1,i
n−1 2
If i − 1 ≤ (n − i)δn /2, either Condition (i) or Condition (ii) in Theorem 3.3 implies
n
n − i δn o
≥ pn .
(A.51)
P |hKen
(X
)|
≥
i
1,i
n−1 2
If i ≥ (2n − δn )/(2 + δn ), we have n − i ≤ (i − 1)δn /2 and (i − 1)/(n − 1) ≥ 2/(δn + 2). Lemma A.5
implies that (A.50) holds. By Chebyshev’s inequality we deduce
i − 1 δn 2
4
} pn ≥
(A.52)
Var{hKen
δ 2 pn .
1,i (Xi )} ≥ {
n−1 2
(2 + δn )2 n
If i ≤ (nδn + 2)/(2 + δn ), we have i − 1 ≤ (n − i)δn /2 and (n − i)/(n − 1) ≥ 2/(2 + δn ). Lemma A.5
implies that (A.51) holds. By Chebyshev’s inequality we deduce
n − i δn 2
1
Var{hKen
} pn ≥
δ 2 pn .
(A.53)
1,i (Xi )} ≥ {
n−1 2
(2 + δn )2 n

31

By (A.52) and (A.53), we have
n
X

b(nδn +2)/(2+δn )c

X

Var{hKen
1,i (Xi )} ≥

i=1

i=1

1
δ 2 pn +
(2 + δn )2 n

n
X
i=b(2n−δn )/(2+δn )c+1

4
δ 2 pn .
(2 + δn )2 n

(A.54)

Note that
b(nδn +2)/(2+δn )c

X
i=1

(nδn + 2)/(2 + δn ) − 1 2
1
δ 2 pn =
δn pn  nδn3 pn .
(2 + δn )2 n
(2 + δn )2

(A.55)

Combining (A.54) and (A.55) yields
n
X

3
Var{hKen
1,i (Xi )} & nδn pn .

(A.56)

i=1

It follows from (3.3) and (A.56) that
n

V (n) :=

1 X
−4/3
Var{hKen
.
1,i (Xi )}  n
n2

(A.57)

i=1

Equations (A.48), (A.49), and (A.57) yield (2.8) and (2.9). The asymptotic normality of UnKen
then follows from Theorem 2.1. This completes the proof for Part II.

A.10

Proof of Theorem 3.5

Proof. Define
fij (x) := P (Xj > x) − P (Xj > Xi ),

(A.58)

zi = zi (x) := (x − µi )/σi .

(A.59)

and

Using the definitions of Fjc and Fjic in (3.5), we have
nX −µ
n X − X − (µ − µ ) µ − µ
o
(x − µi ) + (µi − µj ) σi o
σi
j
j
j
i
j
i
i
j
fij (x) = P
>
·
−P
·
>
σj
σi
σj
σi
(σi2 + σj2 )1/2
(σi2 + σj2 )1/2
−1/2
= Fjc {ρij (zi + rij )} − Fjic {rij (1 + ρ−2
}.
ij )

(A.60)

For proving Theorem 3.5, it suffices to show the existence of δn and pn satisfying the conditions in
Theorem 3.3. Because the proofs for UnKen and UnAP are almost identical, we give detailed proof
for UnKen and comment on the proof for UnAP at the end. We divide the proof for UnKen into two
parts. In Part I we construct such δn and pn under conditions (3.6), (3.7), and (3.8). In Part II we
construct such δn and pn under conditions (3.10), (3.11), and (3.12).
Part I: Assume (3.6), (3.7), and (3.8) hold. The following lemma gives bound on fij (x).
Lemma A.6. Define

 c −1/b2
c1 −1/b2
1
1
and
K
=
.
K1 = t0 + t−b
2
0
2c2
2c2

32

Consider a fixed i ∈ [n]. If x satisfies
zi (x) ≥ Rn + K1 ρn + K2 ρn Rnb1 /b2 ,

(A.61)

then for all j ∈ [n]\{i} we have
fij (x) ≤ −min

nc

1

2

Rn−b1 ,

c1 −b1 1 o
t , .
2 0 2

(A.62)

1 1
Define δn := min{ c21 Rn−b1 , c21 t−b
0 , 2 }., Zi := (Xi − µi )/σi , and

pn := P {Zi ≥ Rn + K1 ρn + K2 ρn Rnb1 /b2 }.

(A.63)

Lemma A.6 yields that
P {fij (x) ≤ −δn ,∀j ∈ [n]\{i}} ≥ pn .
Since ρn ≥ 1, by the definition of K1 we have
Rn + K1 ρn + K2 ρn Rnb1 /b2 ≥ K1 ρn ≥ t0 .

(A.64)

Combining (A.63), (A.64) and (3.6) yields
pn ≥ c1 (Rn + K1 ρn + K2 ρn Rnb1 /b2 )−b1 .
Thus by dropping constants we obtain
δn3 pn & (Rn + ρn + ρn Rnb1 /b2 )−b1 min(Rn−3b1 ,1).

(A.65)

In the following we show that (A.65) and (3.8) imply
δn3 pn  n−1/3 .

(A.66)

If limsupn→∞ Rn = ∞, the fact that ρn ≥ 1 and b1 > b2 > 0 yields
−b21 /b2

1
(Rn + ρn + ρn Rnb1 /b2 )−b1  ρ−b
n Rn

(A.67)

and
min(Rn−3b1 ,1)  Rn−3b1 .

(A.68)

Equation (A.65) together with (A.67) and (A.68) gives
−b21 /b2

1
δn3 pn & ρ−b
n Rn

Rn−3b1 .

(A.69)

By (A.69) and (3.8), we deduce (A.66). If limsupn→∞ Rn < ∞, by (A.65) we have
1
δn3 pn & ρ−b
n .

(A.70)

−1/3
1
ρ−b
.
n n

(A.71)

Equation (3.8) implies

Combining (A.70) and (A.71) yields (A.66). Therefore, the asymptotic normality of UnKen follows
from Theorem 3.3.
This completes the proof of Part I for UnKen . For UnAP the proof is almost the same, except that
33

(3.8) is replaced by (3.9), and the right-hand side of (A.66) and (A.71) is replaced by n−1/3 (logn)2 .
Part II: Assume (3.9), (3.10), and (3.11) hold. The following lemma gives bound on fij (x).
Lemma A.7. Recall that zi = zi (x) := (x − µi )/σi . For a fixed i ∈ [n], assume that
zi ≥ Rn + K3 ρn + K4 ρn Rn ,
where K3 ,K4 are defind in (3.14). Then for all j ∈ [n]\{i} we have
nc
c1
1o
1
fij (x) ≤ −min
exp(−b1 Rnλ ), exp(−b1 tλ0 ), .
2
2
2
Define δn = min

n

c1
λ c1
λ 1
2 exp(−b1 Rn ), 2 exp(−b1 t0 ), 2

(A.72)

(A.73)

o
, Zi = (Xi − µi )/σi , and

pn = P {Zi ≥ Rn + K3 ρn + K4 ρn Rn }.

(A.74)

Lemma A.7 yields that
P {fij (x) ≤ −δn ,∀j ∈ [n]\{i}} ≥ pn .
Since ρn ≥ 1, by the definition of K3 , we have
Rn + K3 ρn + K4 ρn Rn ≥ K3 ρn ≥ t0 .

(A.75)

Combining (A.74), (A.75), and (3.10) yields
pn ≥ c1 exp{−b1 (Rn + K3 ρn + K4 ρn Rn )λ }.
Thus by dropping constants we obtain
δn3 pn & exp{−b1 (Rn + K3 ρn + K4 ρn Rn )λ }min{exp(−3b1 Rnλ ),1}.
h
i
 min exp{−3b1 Rnλ − b1 (Rn + K3 ρn + K4 ρn Rn )λ },exp{−b1 (Rn + K3 ρn + K4 ρn Rn )λ } (A.76)
With an argument similar to (A.67)-(A.71), it follows from (A.76) and (3.12) that
δn3 pn  n−1/3 .

(A.77)

This completes the proof of Part II for UnKen . For UnAP the proof is almost the same, except
that (3.12) is replaced by (3.13), and the right-hand side of (A.77) is replaced by n−1/3 (logn)2 .

A.11

Proof of Corollary 3.1

Proof. We divide the proof into two parts. In Part I, we show that (2.17) and (2.18) hold for hKen
1,i .
In Part II, we show that (2.17) and (2.18) hold for hAP
1,i .
Part I. By (3.3) and Theorem 3.3, we have that (2.10) holds. This combined with (A.57) gives
nσn  n1/3 ,

(A.78)

where σn2 := Var(UnKen ). By (3.1), we have |hKen
1,i (x)| ≤ 1 for any x. It then follows from Markov’s

34

inequality that for any  > 0,
o E|hKen (Xi )|
n hKen (Xi )
1
1,i
1,i
≤
.
≥ ≤
nσn
nσn
nσn
Taking sup1≤i≤n on both sides of (A.79), we deduce (2.17) from (A.78).
By (2.14) we have
n hKen (Xi )  hKen (Xi )
o
n hKen (Xi )  hKen (Xi )
o
1,i
1,i
1,i
1,i
E
1
1
≤  = −E
> .
nσn
nσn
nσn
nσn
Cauchy-Schwarz inequality gives
n hKen (Xi )  hKen (Xi )
o h n hKen (Xi ) o2 i1/2  hKen (Xi )
1/2
1,i
1,i
1,i
1,i
≤ E
E
1
>
P
>
.
nσn
nσn
nσn
nσn
Combining (A.80) and (A.81) yields
h n hKen (Xi )  hKen (Xi )
n hKen (Xi ) o2  hKen (Xi )
oi2

1,i
1,i
1,i
1,i
E
1
≤E
P
≤
> .
nσn
nσn
nσn
nσn
Taking summation over 1 ≤ i ≤ n on both sides of (A.82), it follows from (A.79) that
n
n h n Ken
oi2
o
X
h1,i (Xi )  hKen
1 X n hKen
1,i (Xi )
1,i (Xi ) 2
1
≤
≤
E
.
E
nσn
nσn
nσn
nσn
P

(A.79)

(A.80)

(A.81)

(A.82)

(A.83)

i=1

i=1

By (2.14) and (2.10) we obtain
n
n
n hKen (Xi ) o2
X
X
1,i
−2 −2
= σn n
E
Var{hKen
1,i (Xi )} → 1.
nσn
i=1

(A.84)

i=1

Equation (2.18) then follows from (A.78), (A.83), and (A.84).
Part II. By (3.4) and Theorem 3.3, we have that (2.10) hold. This combined with (A.47) gives
nσn  n1/3 logn,

(A.85)

where σn2 := Var(UnAP ). By (3.2) and the fact that |{1(j < i) − 1(j > i)}{P (Xj > x) − θ(i,j)}| ≤ 1,
we obtain
n
i−1
X
1 
n X 1
+
.
(A.86)
|hAP
(x)|
≤
1,i
n−1
i−1
j −1
j=1

j=i+1

It follows from (A.86) and Lemma C.8 that
n
|hAP
{1 + 1 + log(n − 1)} ≤ 4 + 2logn.
(A.87)
1,i (x)| ≤
n−1
By Markov’s inequality and (A.87) we have for any  > 0,
n hAP (Xi )
o E|hAP (Xi )| 4 + 2logn
1,i
1,i
P
≥ ≤
≤
.
(A.88)
nσn
nσn
nσn
Taking sup1≤i≤n on both sides of (A.88), we deduce (2.17) from (A.85).
Equations (A.80), (A.81) and (A.82) hold for hAP
1,i as well. Taking summation over 1 ≤ i ≤ n on

35

both sides of (A.82), it follows from (A.88) that
n
n h n AP
oi2 4 + 2logn X
n hAP (Xi ) o2
X
h1,i (Xi )  hAP
1,i (Xi )
1,i
1
.
≤
≤
E
E
nσn
nσn
nσn
nσn

(A.89)

i=1

i=1

By (2.14) and (2.10) we obtain
n
n
n hAP (Xi ) o2
X
X
1,i
−2 −2
E
= σn n
Var{hAP
1,i (Xi )} → 1.
nσn
i=1

(A.90)

i=1

Equation (2.18) then follows from (A.85), (A.89), and (A.90).
This completes the proof.

A.12

Proof of Corollary 3.2

Proof. By Theorem 2.6, for proving Corollary 3.2, it suffices to show that (2.21), (2.22), (2.23), and
(2.24) hold. For UnKen we have |h(x,y)| ≤ 1 for any x,y. This implies (2.21).
Now we establish (2.24). For UnKen , we have |a(i,j)| = |1(j < i)| ≤ 1. By the definition in (2.6),
we have
X
A2,1 (n) = n−3
|a(i1 ,j1 )a(i2 ,j2 )| = O(1).
(A.91)
(In2 )⊗2
≥1

By (2.25) and (3.19) we have
M1 (n) . n−1/6 .

(A.92)

M2 (n) . n−1/3 .

(A.93)

By (2.26) and (3.20) we have

Equation (3.3) implies (A.57) by Theorem 3.3. Combining (A.57) and (2.10) yields
σn2  n−4/3 .

(A.94)

Equation (2.24) follows from (A.91), (A.92), (A.93), and (A.94).
Next we establish (2.22).
Pn
Ken
2
i=1 E{h1,i (Xi ) }.

The following lemma gives bounds on

Lemma A.8. Under the assumptions of Corollary 3.2, we have
n
X
n(n + 1) 2
2
E{hKen
(η − θ2 ) + O(n5/6 ),
1,i (Xj ) } =
3(n − 1)

Pn

Ken
2
i=1 E{h1,i (Xj ) }

and

(A.95)

i=1

and
n
X
i=1

2
E{hKen
1,i (Xi ) } =

n(n + 1) 2
(η − θ2 ) + O(n5/6 ).
3(n − 1)

36

(A.96)

By (2.10) we have
σn2 = n−2

n
X

2
E{hKen
1,i (Xi ) }{1 + o(1)}.

(A.97)

i=1

Using (A.96) and (A.97) we obtain
o
n n(n + 1)
(η 2 − θ2 ) + O(n5/6 ) .
n2 σn2 = {1 + o(1)}
3(n − 1)

(A.98)

Note that
n n
o i n−1
1 X X hn hKen
1,i (Xj ) 2
E
=
n
nσn

Pn Pn

i=1 j=1

i=1

Ken
2
j=1 E{h1,i (Xj ) }
.
n2 σn2

(A.99)

Combining (A.99) with (A.95), (A.98), and the fact that η 2 6= θ2 yields
n n
o i
3−1 (n − 1)−1 n(n + 1)(η 2 − θ2 ) + O(n5/6 )
1 X X hn hKen
1,i (Xj ) 2
n
o → 1. (A.100)
=
E
n
nσn
{1 + o(1)} 3−1 (n − 1)−1 n(n + 1)(η 2 − θ2 ) + O(n5/6 )
i=1 j=1

By (3.1) we have |h1,i (x)| ≤ 1. Therefore, for any x
Pn
n n
2
X
h1,i (x) o2
1
i=1 h1,i (x)
≤ 2.
=
nσn
n2 σn2
nσn

(A.101)

i=1

Equations (A.98) and (A.101) imply that
n
n
n n
hX
X
h1,i (Xj ) o2 i X 1
≤
= O(n) = o(n2 ).
Var
nσn
n2 σn4
j=1

j=1

i=1

It then follows from Lemma C.7 that
n
n
1 X h X n h1,i (Xj ) o2
n

j=1 i=1

nσn

n 
nX
h1,i (Xj ) 2 oi P
→ 0.
−E
nσn

(A.102)

i=1

Equation (2.22) follows from (A.100) and (A.102).
Lastly, we prove (2.23). By algebra we have
n
n
n n
n
Ken
o
o
1 X n X hKen
1 X X n hKen
1 X X hKen
1,i (Xj ) 2
1,i (Xj ) 2
1,i (Xj1 )h1,i (Xj2 )
.
= 2
+ 2
n2
nσn
n
nσn
n
n2 σn2
i=1

j=1

(A.103)

j1 6=j2 i=1

j=1 i=1

By (2.22) we have
n n
o
1 X X n hKen
1,i (Xj ) 2 P
→ 0.
n2
nσn

(A.104)

j=1 i=1

The second term on the right-hand side of (A.103) is (n − 1)/n times a U-statistic with symmetric
P
Ken
kernel g(x,y) = n−2 σn−2 ni=1 hKen
1,i (x)h1,i (y). By (3.1) and (3.19) we have
n

E{hKen
1,i (Xj )} =

1 X
sgn(i − k){P (Xk > Xj ) − P (Xk > Xi )} = O(n−1/6 ).
n−1
k=1

37

(A.105)

It follows from (A.105) and (A.98) that
E{g(Xj1 ,Xj2 )} = n−2 σn−2

n
X

Ken
E{hKen
1,i (Xj1 )}E{h1,i (Xj2 )} → 0.

(A.106)

i=1

By (A.106) and the weak law of large numbers for U-statistics with independent but not identically
distributed variables (Lee, 1990, Theorem 1, Section 3.7.2), we deduce
n
Ken
1 X X hKen
1,i (Xj1 )h1,i (Xj2 ) P
→ 0.
n2
n2 σn2

(A.107)

j1 6=j2 i=1

Equation (2.23) follows from (A.103), (A.104), and (A.107).
This completes the proof.

A.13

Proof of Corollary 3.3

Proof. By Theorem 2.6, for proving Corollary 3.3, it suffices to show that (2.21), (2.22), (2.23), and
(2.24) hold. For UnAP we have |h(x,y)| ≤ 1 for any x,y. This implies (2.21).
Now we establish (2.24). For UnAP , we have a(i,j) = 1(j < i)n/(i − 1). It follows that a(i,j)a(j,i) =
0 and a(i,i) = 0. By the definition in (2.6), we have
A2,1 (n) = n−3

X

n
X

{|a(i,j)a(i,k)| + |a(i,j)a(k,i)|}.

(i,j)∈In2 k=1,k6=i

= n−3

n X
n−1
i−1 X
i−1 X
i−1
n
nX
XX
n
n o
n
n
·
+
·
.
i−1 i−1
i−1 k−1
i=2 j=1 k=1

(A.108)

i=2 j=1 k=i+1

By algebra, we have
n X
i−1 X
i−1
X
n
n
·
= n2 (n − 1),
i−1 i−1

(A.109)

i=2 j=1 k=1

and
n−1
i−1
XX

n
X

i=2 j=1 k=i+1

n k−1

n

XX 1
X k−2
n
n
·
= n2
= n2
= O(n3 ).
i−1 k−1
k−1
k−1
k=3 i=2

(A.110)

k=3

Combining (A.108) with (A.109) and (A.110) yields
A2,1 (n) = O(1).

(A.111)

M1 (n) . n−1/6 logn.

(A.112)

M2 (n) . n−1/3 (logn)2 .

(A.113)

By (2.25) and (3.21) we have

By (2.26) and (3.22) we have

38

Equation (3.4) implies (A.47) by Theorem 3.3. Combining (A.47) and (2.10) yields
σn2  n−4/3 (logn)2 .

(A.114)

Equation (2.24) follows from (A.111), (A.112), (A.113), and (A.114).
Next we establish (2.22). The following lemma gives useful bounds.
Lemma A.9. Under the assumptions of Corollary 3.3, we have
n
X
n2
2
E{hAP
(η 2 − θ2 ) + O(n5/6 logn),
1,i (Xj ) } =
n−1

(A.115)

i=1

and
n
X

2
E{hAP
1,i (Xi ) } =

i=1

n2
(η 2 − θ2 ) + O(n5/6 logn).
n−1

(A.116)

By (2.10) we have
σn2 = n−2

n
X

2
E{hAP
1,i (Xi ) }{1 + o(1)}.

(A.117)

i=1

Using (A.117) and (A.116) we obtain
n n2
o
(η 2 − θ2 ) + O(n5/6 logn) .
n2 σn2 = {1 + o(1)}
n−1

(A.118)

Note that
n n
o i n−1
1 X X hn hAP
1,i (Xj ) 2
E
=
n
nσn
i=1 j=1

Pn Pn
i=1

AP
2
j=1 E{h1,i (Xj ) }
.
n2 σn2

Combining (A.119) with (A.115), (A.118), and the fact that η 2 6= θ2 yields
n n
o i
1 X X hn hAP
n2 (n − 1)−1 (η 2 − θ2 ) + O(n5/6 logn)
1,i (Xj ) 2
n
o → 1.
=
E
n
nσn
{1 + o(1)} n2 (n − 1)−1 (η 2 − θ2 ) + O(n5/6 logn)

(A.119)

(A.120)

i=1 j=1

By (3.2) we have |hAP
1,i (x)| ≤ 1 + ϕ(n − 1) − ϕ(i − 1) for all x. This combined with Lemma C.8 yields
n
|hAP
(A.121)
1,i (x)| ≤ 1 + log ≤ 1 + logn.
i
It then follows from (A.121) that
Pn AP 2
n n AP
X
h1,i (x) o2
(1 + logn)2
i=1 h1,i (x)
=
≤
.
(A.122)
nσn
n2 σn2
nσn2
i=1

Equations (A.118) and (A.122) imply that
n
n n AP
n
hX
X
h1,i (Xj ) o2 i X
(1 + logn)4
Var
≤
= O{n(logn)4 } = o(n2 ).
nσn
n2 σn4
j=1

i=1

j=1

39

It then follows from Lemma C.7 that
n
n
o
1 X h X n hAP
1,i (Xj ) 2
n

j=1 i=1

nσn

−E

n  AP
nX
h (Xj ) 2 oi
1,i

i=1

nσn

P

→ 0.

(A.123)

Equation (2.22) follows from (A.120) and (A.123).
Lastly, we prove (2.23). By algebra we have
n
n
n
n n
AP
o
o
1 X n X hAP
1 X X n hAP
1 X X hAP
1,i (Xj1 )h1,i (Xj2 )
1,i (Xj ) 2
1,i (Xj ) 2
=
+
.
n2
nσn
n2
nσn
n2
n2 σn2
i=1

j=1

(A.124)

j1 6=j2 i=1

j=1 i=1

By (2.22) we have
n n
o
1 X X n hAP
1,i (Xj ) 2 P
→ 0.
n2
nσn

(A.125)

j=1 i=1

The second term on the right-hand side of (A.124) is (n − 1)/n times a U-statistic with symmetric
P
AP
kernel g(x,y) = n−2 σn−2 ni=1 hAP
1,i (x)h1,i (y). By (A.121) and (3.21) we have
n

E{hAP
1,i (Xj )} =

1 X n n1(j < i) n1(j > i) o
−
O(n−1/6 logn).
n−1
i−1
j −1
k=1

This combined with Lemma C.8 yields
−1/6
E{hAP
(logn)2 }.
1,i (Xj )} = O{n

(A.126)

It follows from (A.126) and (A.118) that
E{g(Xj1 ,Xj2 )} = n−2 σn−2

n
X

AP
E{hAP
1,i (Xj1 )}E{h1,i (Xj2 )} → 0.

(A.127)

i=1

By (A.127) and Theorem 1 in Lee (1990, Section 3.7.2), we deduce
n
AP
1 X X hAP
1,i (Xj1 )h1,i (Xj2 ) P
→ 0.
n2
n2 σn2
j1 6=j2 i=1

Equation (2.23) follows from (A.124), (A.125), and (A.128).
This completes the proof.

B

Proofs of the supporting lemmas

In this section, we prove the supporting lemmas that appear in Section A.

40

(A.128)

B.1

Proof of Lemma A.1

Proof. To simplify notation, define i = (i1 ,...,im ), Xi = (Xi1 ,...,Xim ), and i−m = (i1 ,...,im−1 ). By
definition of h1,i (Xi ) in (2.4) we have
m
n
n n
n
o3
X
X X
X
(n − m)! o3
(l)
(B.1)
a(l) (i;i−m ) fi−m (Xi ) − θ(l) (i;i−m ) .
E|h1,i (Xi )|3 =
E
(n − 1)!
m−1
i=1

i=1

In−1 (−i) l=1

Define
(l )

(l )

1
1
Ti−m
(Xi ) = fi−m
(Xi ) − θ(l1 ) (i;i−m ),

(l )

(l )

2
3
and define Tj−m
(Xi ) and Tk−m
(Xi ) similarly. The right-hand side of (B.1) equals
n (n − m)! o3 X
(l1 )
(l2 )
(l3 )
a(l1 )(i;i−m )a(l2 )(i;j−m )a(l3 )(i;k−m ) E Ti−m
(Xi )Tj−m
(Xi )Tk−m
(Xi ) ,
(n − 1)!

(B.2)

m−1
(−i). By Cauchywhere the summation is over i ∈ [n], l1 ,l2 ,l3 ∈ [m], and i−m ,j−m ,k−m ∈ In−1
Schwarz inequality and Lemma C.1(ii), we have
h
i1/2 h
i1/2
(l1 )
(l2 )
(l3 )
(l1 )
(l2 )
(l3 )
E Ti−m
(Xi )Tj−m
(Xi )Tk−m
(Xi ) ≤ E{Ti−m
(Xi )2 Tj−m
(Xi )2 }
E{Tk−m
(Xi )2 }
h
i1/4 h
i1/4 h
i1/4
(l1 )
(l2 )
(l3 )
≤ E{Ti−m
(Xi )4 }
E{Tj−m
(Xi )4 }
E{Tk−m
(Xi )4 }
≤ CM (n)3/4 .
(B.3)

By the definition of A3,1 (n) in (2.6) and algebra, we have
X
X
|a(l1 ) (i;i−m )a(l2 ) (i;j−m )a(l3 ) (i;k−m )| ≤ C
|a(i)a(j)a(k)| = Cn3m−2 A3,1 (n),

(B.4)

(Inm )⊗3
≥1

where the summation in the leftmost part of (B.4) is over i ∈ [n], l1 ,l2 ,l3 ∈ [m], and i−m ,j−m ,k−m ∈
m−1
(−i). By (B.1), (B.2), (B.3), and (B.4), we deduce
In−1
n
X

E |h1,i (Xi )|3 ≤ CnA3,1 (n)M (n)3/4 .

(B.5)

i=1

This completes the proof.

B.2

Proof of Lemma A.2

Proof. We prove Lemma A.2 by showing that for each (i∗1 ,...,i∗m ) ∈ Inm , the coefficients of a(i∗1 ,...,i∗m )
on both sides of (A.14) are equal. In the following we fix (i∗1 ,...,i∗m ) ∈ Inm .
For the left-hand side of (A.14), we enumerate the combinations in
m−1
{l,i,(i1 ,...,im−1 ) : l ∈ [m],i ∈ [n],(i1 ,...,im−1 ) ∈ In−1
(−i)}

41

such that a(l) (i;i1 ,...,im−1 ) = a(i∗1 ,...,i∗m ), as follows:
l = 1,i = i∗1 ,(i1 ,...,im−1 ) = (i∗1 ,...,i∗m )\i∗1 ;
..
.
l = j,i = i∗j ,(i1 ,...,im−1 ) = (i∗1 ,...,i∗m )\i∗j ;
..
.

(B.6)

l = m,i = i∗m ,(i1 ,...,im−1 ) = (i∗1 ,...,i∗m )\i∗m .
When l = j,i = i∗j ,(i1 ,...,im−1 ) = (i∗1 ,...,i∗m )\i∗j ,
E{h(l) (Xi ;Xi1 ,...,Xim−1 ) | Xi } − θ(l) (i;i1 ,...,im−1 ) = E{h(Xi∗1 ,...,Xi∗m ) | Xi∗j } − θ(i∗1 ,...,i∗m ).
So the coefficient of a(i∗1 ,...,i∗m ) on the left-hand side of (A.14) is
m h
i
X
E{h(Xi∗1 ,...,Xi∗m | Xi∗j } − θ(i∗1 ,...,i∗m ) .
j=1

This equals the coefficient of a(i∗1 ,...,i∗m ) on the right-hand side of (A.14). This completes the
proof.

B.3

Proof of Lemma A.3

Lemmas B.1 and B.2 that appear in this proof are proven immediately after this proof.
Proof. Define i := (i1 ,...,im ) and Xi := (Xi1 ,...,Xim ). By (A.17) we have
n (n − m)! o2 X
E ∗ {σn−2 Un∗ (h2 )2 } = σn−2
a(i)a(j)E ∗ {h2;i (Xi∗ )h2;j (Xj∗ )}
n!
⊗2

(B.7)

(Inm )≥0

and

[E ∗ {σn Un∗ (h2 )}]2 = σn−2

n (n − m)! o2 X
n!

a(i)a(j)E ∗ {h2;i (Xi∗ )}E ∗ {h2;j (Xj∗ )}.

(B.8)

(Inm )⊗2
≥0

Define
h
i
g(i,j) := a(i)a(j) E ∗ {h2;i (Xi∗ )h2;j (Xj∗ )} − E ∗ {h2;i (Xi∗ )}E ∗ {h2;j (Xj∗ )} .

(B.9)

It follows from (B.7) and (B.8) that
Var∗ {σn−1 Un∗ (h2 )} = σn−2

n (n − m)! o2
n!

X

g(i,j).

The following proof consists of two steps. In the first step, we establish
n (n − m)! o2
X
Var∗ {σn−1 Un∗ (h2 )} = σn−2
g(i,j) + oP (1).
n!
⊗2
(i,j)∈(Inm )=1

42

(B.10)

(i,j)∈(Inm )⊗2
≥0

(B.11)

In the second step, we show that
σn−2

n (n − m)! o2
n!

X

P

g(i,j) → 0.

(B.12)

(i,j)∈(Inm )⊗2
=1

Lemma A.3 then follows from (B.11), (B.12), and Slutsky’s theorem.
∗
∗
∗
∗
∗
∗
∗
Step I. If (i,j) ∈ (Inm )⊗2
=0 , we have E {h2;i (Xi )h2;j (Xj )} = E {h2;i (Xi )}E {h2;j (Xj )} a.s..
This implies
X
g(i,j) = 0 a.s..
(B.13)
(i,j)∈(Inm )⊗2
=0

For any (i,j) ∈ (Inm )⊗2
≥2 , by the law of iterated expectation, Cauchy-Schwarz inequality, and triangular inequality we have
n
o h
i1
2
E E ∗ {h2;i (Xi∗ )h2;j (Xj∗ )} ≤ E |h2;i (Xi∗ )||h2;j (Xj∗ )| ≤ E{h2;i (Xi∗ )2 }E{h2;j (Xj∗ )2 } . (B.14)
Similarly, by Jensen’s inequality and triangular inequality we have
n
o
E E ∗ {h2;i (Xi∗ )}E ∗ {h2;j (Xj∗ )} ≤ E E ∗ |h2;i (Xi∗ )|E ∗ |h2;j (Xj∗ )|
i1 h
i1
h
2
2
≤ E{E ∗ |h2;i (Xi∗ )|}2 E{E ∗ |h2;j (Xj∗ )|}2 ≤ E{h2;i (Xi∗ )2 }E{h2;j (Xj∗ )2 } .

(B.15)

Using the law of iterated expectation, we deduce
X

E{h2;i (Xi∗ )2 } = E[E ∗ {h2;i (Xi∗ )2 }] = n−m

E{h2;i (Xj1 ,...,Xjm )2 }.

(B.16)

1≤j1 ,...,jm ≤n

By Lemma C.1(iii) and (2.21), there exists an absolute constant C > 0 such that for any n, for any
i ∈ Inm , and for any 1 ≤ j1 ,...,jm ≤ n,
E{h2;i (Xj1 ,...,Xjm )2 } ≤ C.

(B.17)

Combining (B.16) and (B.17) yields that E{h2;i (Xi∗ )2 } ≤ C. It then follows from (B.14) and (B.15)
that

and

E E ∗ {h2;i (Xi∗ )h2;j (Xj∗ )} ≤ C,

(B.18)

E E ∗ {h2;i (Xi∗ )}E ∗ {h2;j (Xj∗ )} ≤ C.

(B.19)

Equations (B.9), (B.18), and (B.19) imply that
X
X
E
g(i,j) ≤ 2C
|a(i)a(j)| = 2Cn2m−2 A2,2 (n).
(Inm )⊗2
≥2

(Inm )⊗2
≥2

By (2.8), (2.10), and (B.20), we deduce
n (n − m)! o2
X
σn−2
E
g(i,j) → 0.
n!
⊗2
(Inm )≥2

43

(B.20)

It then follows from Markov’s inequality that
n (n − m)! o2 X
P
σn−2
g(i,j) → 0.
n!
⊗2

(B.21)

(Inm )≥2

Combining (B.10), (B.13), and (B.21) yields (B.11). This concludes Step I.
Step II. Consider a fixed (i,j) ∈ (Inm )⊗2
=1 . Without loss of generality assume i ∩ j = {ip } = {jq }
for some 1 ≤ p,q ≤ m. By the i.i.d.-ness of Xi∗ ’s given X1 ,...,Xn , we have
X
E[E ∗ {h2;i (Xi∗ )h2;j (Xj∗ )}] = n−(2m−1)
E{h2;i (Xr )h2;j (Xs )}
(B.22)
r,s∈[n]2m
rp =sq

and
X

E[E ∗ {h2;i (Xi∗ )}E ∗ {h2;j (Xj∗ )}] = n−2m

E{h2;i (Xr )h2;j (Xs )}.

(B.23)

r,s∈[n]2m

The number of pairs (r,s) in {(r,s) ∈ [n]2m : rp = sq } satisfying any of the following three statements
is of order O(n2m−2 ): (1) r or s has duplicate indices (i.e., r ∈
/ Inm or s ∈
/ Inm ); (2) i ∩ r 6= ∅; or (3)
j ∩ s 6= ∅. It then follows from (B.18) that
X
X
E{h2;i (Xr )h2;j (Xs )} =
E{h2;i (Xr )h2;j (Xs )} + O(n2m−2 ).
(B.24)
(r,s)∈(Inm )⊗2
=1
rp =sq ,i∩r=∅=j∩s

r,s∈[n]2m
rp =sq

The following lemma gives bound on the right-hand side of (B.24).
Lemma B.1. For any (i,j) ∈ (Inm )⊗2
=1 , under the assumptions of Theorem 2.6, there exists a constant
C such that
X
E{h2;i (Xr )h2;j (Xs )} ≤ Cn2m−1 {M1 (n)2 + M2 (n)}.
(B.25)
(r,s)∈(Inm )⊗2
=1
rp =sq ,i∩r=∅=j∩s

It follows from (B.22), (B.24) and Lemma B.1 that
|E[E ∗ {h2;i (Xi∗ )h2;j (Xj∗ )}]| ≤ C{M1 (n)2 + M2 (n) + n−1 }.
Using an argument similar to (B.24), we have
X
X
E{h2;i (Xr )h2;j (Xs )} =

E {h2;i (Xr )h2;j (Xs )} + O(n2m−1 ).

(B.26)

(B.27)

(r,s)∈(Inm )⊗2
=0

r,s∈{1,...,n}2m

i∩r=∅=j∩s

The following lemma gives bound on the right-hand side of (B.27).
Lemma B.2. For any (i,j) ∈ (Inm )⊗2
=1 , under the assumptions of Theorem 2.6, there exists a constant
C such that
X
E{h2;i (Xr )h2;j (Xs )} ≤ Cn2m M1 (n)2 .
(B.28)
(r,s)∈(Inm )⊗2
=0
i∩r=∅=j∩s

44

It follows from (B.23), (B.27) and Lemma B.2 that
|E[E ∗ {h2;i (Xi∗ )}E ∗ {h2;j (Xj∗ )}]| ≤ CM1 (n)2 .

(B.29)

Combining (B.9) with (B.26) and (B.29) yields that, for any (i,j) ∈ (Inm )⊗2
=1 ,
|g(i,j)| ≤ C|a(i)a(j)|{M1 (n)2 + M2 (n) + n−1 }.
Therefore, by the definition of A2,1 (n) in (2.6), we have
X
g(i,j) ≤ Cn2m−1 A2,1 (n){M1 (n)2 + M2 (n) + n−1 }.

(B.30)

(Inm )⊗2
=1

Equation (B.12) follows from (B.30) and (2.24). This concludes Step II.
The proof is thus finished.
m ⊗2
Proof of Lemma B.1. For a fixed (i,j) ∈ (Inm )⊗2
=1 , consider any (r,s) ∈ (In )=1 with rp = sq and i ∩
r = ∅ = j ∩ s. By the law of iterated expectation and the independence of Xi ’s we have

E{h2;i (Xr )h2;j (Xs )} = E[E{h2;i (Xr ) | Xrp }E{h2;j (Xs ) | Xsq }].

(B.31)

For i = (i1 ,...,im ) and l ∈ [m], define
i\il := (i1 ,...,il−1 ,il+1 ,...,im ).
Using the definition of h2;i (·) in (2.5) we have
E{h2;i (Xr ) | Xrp } = E{h(Xr ) | Xrp }
−

m
X

E[Ei\il {h(l) (Xrl ;Y1 ,...,Ym−1 ) | Xrl } | Xrp ] + (m − 1)θ(i).

(B.32)

l=1

By the independence of the Xi ’s we have
m
X
E[Ei\il {h(l) (Xrl ;Y1 ,...,Ym−1 ) | Xrl } | Xrp ].
l=1

=

m
X

θ(l) (rl ;i\il ) + Ei\ip {h(l) (Xrp ;Y1 ,...,Ym−1 ) | Xrp }

(B.33)

l=1
l6=p

Using (B.32) and (B.33) we obtain
E{h2;i (Xr ) | Xrp } = E{h(Xr ) | Xrp } −

m
X

θ(l) (rl ;i\il )

l=1
l6=p

−Ei\ip {h(l) (Xrp ;Y1 ,...,Ym−1 ) | Xrp } + (m − 1)θ(i).

45

(B.34)

We introduce some notation:
i\il ⊕ k := (i1 ,...,il−1 ,k,il+1 ,...,im ),
Xi\il ⊕k := (Xi1 ,...,Xil−1 ,Xk ,Xil+1 ,...,Xim ),
θ(i | il ) := E{h(Xi ) | Xil }.
Using the new notation, (B.34) becomes
E{h2;i (Xr ) | Xrp } = θ(r | rp ) −

m
X

θ(i\il ⊕ rl ) − θ(i\ip ⊕ rp | rp ) + (m − 1)θ(i).

(B.35)

θ(j\jl ⊕ sl ) − θ(j\jq ⊕ sq | sq ) + (m − 1)θ(j).

(B.36)

l=1
l6=p

Similarly, we have
E{h2;j (Xs ) | Xsq } = θ(s | sq ) −

m
X
l=1
l6=q

By algebra and the law of iterated expectation, we derive from (B.35) and (B.36) that
E[E{h2;i (Xr ) | Xrp }E{h2;j (Xs ) | Xsq }] = T1 + T2 + T3 + T4 + T5 ,

(B.37)

where
T1 = E{θ(r | rp )θ(s | sq )} − E{θ(r | rp )θ(j\jq ⊕ sq | sq )}
− E{θ(i\ip ⊕ rp | rp )θ(s | sq )} + E{θ(i\ip ⊕ rp | rp )θ(j\jq ⊕ sq | sq )},
X
X
T2 = (m − 1)θ(r)θ(j) − θ(r)
θ(j\jl ⊕ sl ) + (m − 1)θ(i)θ(s) − θ(s)
θ(i\il ⊕ rl ),
l6=q

T3 =

m
nX
l=1

T4 = θ(i)

l6=p

m
on X
o
θ(i\il ⊕ rl ) − mθ(i)
θ(j\jl ⊕ sl ) − mθ(j) ,

m
X
l=1

l=1

θ(j\jl ⊕ sl ) + θ(j)

m
X

θ(i\il ⊕ rl ) − 2mθ(i)θ(j),

l=1

T5 = θ(i)θ(j) − θ(i\ip ⊕ rp )θ(j\jq ⊕ sq ).
By the definitions of M1 (n) and M2 (n) in (2.25) and (2.26), we have |T1 | ≤ 2M2 (n), |T2 | ≤ CM1 (n),
|T3 | ≤ CM1 (n)2 , |T4 | ≤ CM1 (n), and |T5 | ≤ CM1 (n). Therefore, it follows from (B.37) that
|E[E{h2;i (Xr ) | Xrp }E{h2;j (Xs ) | Xsq }]| ≤ C{M1 (n)2 + M2 (n)}.
This yields (B.25). The proof is thus finished.
m ⊗2
Proof of Lemma B.2. For a fixed (i,j) ∈ (Inm )⊗2
=1 , consider any (r,s) ∈ (In )=0 such that i ∩ r = ∅ =
j ∩ s. By independence of the Xi ’s we have

E{h2;i (Xr )h2;j (Xs )} = E{h2;i (Xr )}E{h2;j (Xs )}.

46

(B.38)

By the definition of h2;i (·) in (2.5), we have
E{h2;i (Xr )} = E{h(Xr )} −

m
X

E[Ei\il {h(l) (Xrl ;Y1 ,...,Ym−1 ) | Xrl }] + (m − 1)θ(i)

l=1

= θ(r) −

m
X

θ(l) (rl ;i\il ) + (m − 1)θ(i).

l=1

It then follows from the definition of M1 (n) in (2.25) that
|E{h2;i (Xr )}| ≤ mM1 (n).

(B.39)

Combining (B.38) and (B.39) yields that
|E{h2;i (Xr )h2;j (Xs )}| ≤ m2 M1 (n).
This implies (B.28). The proof is thus finished.

B.4

Proof of Lemma A.4

Proof. Define
(1)

fij (x) := P (Xj > x) − θ(i,j), Si (x) :=

n
i−1
X
X
n
n
(2)
fij (x), and Si (x) :=
fij (x). (B.40)
i−1
j −1
j=i+1

j=1

(1)
(2)
By (3.2) we have hAP
1,i (Xi ) = {Si (Xi ) − Si (Xi )}/(n − 1)
P
Lemma C.8 repeatedly to bound ϕ(n) := nk=1 k −1 .

for any i ∈ [n]. In the following we use

First, we show that (A.40) and (A.41) hold under Condition (i) of Theorem 3.3. Using fij (·)
notation, Condition (i) becomes
P {δn ≤ fij (Xi ) ≤ 1,∀j ∈ [n]\{i}} ≥ pn .

(B.41)

If δn ≤ fij (x) ≤ 1,∀j ∈ [n]\{i}, we have
nδn =

i−1
i−1
X
X
n
n
(1)
δn ≤ Si (x) ≤
= n,
i−1
i−1

(B.42)

j=1

j=1

and
(2)

n
X

(2)

j=i+1
n
X

Si (x) ≥
Si (x) ≤

j=i+1

n
n
δn = nδn {ϕ(n − 1) − ϕ(i − 1)} ≥ nδn log ,
j −1
i

(B.43)

n−1
n
= n{ϕ(n − 1) − ϕ(i − 1)} ≤ nlog
.
j −1
i−1

(B.44)

Using (B.42), (B.43), and (B.44), it follows from (B.41) that
n
n
n−1o
(2)
(1)
P nδn ≤ Si (Xi ) ≤ n,nδn log ≤ Si (Xi ) ≤ nlog
≥ pn .
i
i−1

47

(B.45)

If log{(n − 1)/(i − 1)} ≤ δn /2, the monotonicity property of probability measure gives
(2)
n S (1) (X )
S (Xi )
n
n
n−1o
i
i
P {h1,i (Xi ) ≥ δn /2} ≥ P
≥
δn , i
≤
log
n−1
n−1
n−1
n−1
i−1
n
n
n−1o
n
n−1o
(1)
(2)
(1)
(2)
=P Si ≥ nδn ,Si ≤ nlog
≥ P nδn ≤ Si ≤ n,nδn log ≤ Si ≤ nlog
.
i−1
i
i−1
Note that
P {|h1,i (Xi )| ≥ δn /2} ≥ P {h1,i (Xi ) ≥ δn /2}.

(B.46)

(B.47)

Equation (A.40) follows from (B.45), (B.46), and (B.47). If δn log(n/i) ≥ 2, the monotonicity property of probability measure gives
(2)
n S (1) (X )
n Si (Xi )
n
no
i
i
≤
,
≥
δn log
P {h1,i (Xi ) ≤ −1} ≥ P
n−1
n−1 n−1
n−1
i
n
n
no
n
n−1o
(1)
(2)
(1)
(2)
=P Si ≤ n,Si ≥ nδn log
≥ P nδn ≤ Si ≤ n,nδn log ≤ Si ≤ nlog
.
(B.48)
i
i
i−1
Note that
P {|h1,i (Xi )| ≥ 1} ≥ P {h1,i (Xi ) ≤ −1}.

(B.49)

Equation (A.41) follows from (B.45), (B.48), and (B.49).
Secondly, we show that (A.40) and (A.41) hold under Condition (ii) of Theorem 3.3. Using
fij (·) notation, Condition (ii) becomes
P {−1 ≤ fij (Xi ) ≤ −δn ,∀j ∈ [n]\{i}} ≥ pn .
By an argument similar to (B.42)-(B.44), if −1 ≤ fij (x) ≤ −δn ,∀j ∈ [n]\{i} we have
n
n−1
(2)
(1)
≤ Si (x) ≤ −nδn log .
− n ≤ Si (x) ≤ −nδn , and − nlog
i−1
i
By (B.51), Condition (ii) in Theorem 3.3 implies that
n
n−1
no
(1)
(2)
P − n ≤ Si (Xi ) ≤ −nδn ,−nlog
≤ Si (Xi ) ≤ −nδn log
≥ pn .
i−1
i
If log{(n − 1)/(i − 1)} ≤ δn /2, the monotonicity property of probability measure gives
(2)
n S (1) (X )
Si (Xi )
n
n
n−1o
i
i
P {h1,i (Xi ) ≤ −δn /2} ≥ P
≤−
δn ,
≥−
log
n−1
n−1
n−1
n−1
i−1
n
o
n
−
1
(1)
(2)
=P Si ≤ −nδn ,Si ≥ −nlog
i−1
n
n
−1
no
(1)
(2)
≥P − n ≤ Si ≤ −nδn ,−nlog
≤ Si ≤ −nδn log
.
i−1
i
Note that
P {|h1,i (Xi )| ≥ δn /2} ≥ P {h1,i (Xi ) ≤ −δn /2}.

(B.50)

(B.51)

(B.52)

(B.53)

(B.54)

Equation (A.40) follows from (B.52), (B.53), and (B.54). If δn log(n/i) ≥ 2, the monotonicity prop-

48

erty of probability measure gives
(2)
n S (1) (X )
n Si (Xi )
n
no
i
i
P {h1,i (Xi ) ≥ 1} ≥ P
≥−
,
≤−
δn log
n−1 o n−1 n−1
n−1
i
n
n
(1)
(2)
=P Si ≥ −n,Si ≤ −nδn log
i
n
n−1
no
(1)
(2)
≥P − n ≤ Si ≤ −nδn ,−nlog
≤ Si ≤ −nδn log
.
i−1
i

(B.55)

Note that
P {|h1,i (Xi )| ≥ 1} ≥ P {h1,i (Xi ) ≥ 1}.

(B.56)

Equation (A.41) follows from (B.52), (B.55), and (B.56).
This completes the proof.

B.5

Proof of Lemma A.5

Proof. Define
fij (x) := P (Xj > x) − θ(i,j),

(1)
Si (x) :=

i−1
X

fij (x), and

(2)
Si (x) :=

j=1
(1)

n
X

fij (x).

(B.57)

j=i+1

(2)

By (3.1) we have hAP
1,i (Xi ) = {Si (Xi ) − Si (Xi )}/(n − 1) for 2 ≤ i ≤ n.
First, we show that (A.50) and (A.51) hold under Condition (i) of Theorem 3.3. Using fij (·)
notation, Condition (i) becomes
P {δn ≤ fij (Xi ) ≤ 1,∀j ∈ [n]\{i}} ≥ pn .

(B.58)

If δn ≤ fij (x) ≤ 1,∀j ∈ [n]\{i}, we have
(i − 1)δn =

i−1
X

(1)

δn ≤ Si (x) ≤

j=1

i−1
X

1 = i − 1,

(B.59)

j=1

and
(n − i)δn =

n
X

(2)

δn ≤ Si (x) ≤

j=i+1

n
X

1 = n − i.

(B.60)

j=i+1

Using (B.59) and (B.60), it follows from (B.58) that
n
o
(1)
(2)
P (i − 1)δn ≤ Si (Xi ) ≤ i − 1,(n − i)δn ≤ Si (Xi ) ≤ n − i ≥ pn .

(B.61)

If n − i ≤ (i − 1)δn /2, the monotonicity property of probability measure gives
(2)
n S (1) (X ) i − 1
n
S (Xi ) n − i o
i − 1 δn o
i
i
≥P
≥
δn , i
≤
P h1,i (Xi ) ≥
n
−
1
2
n
−
1
n
−
1
n
−
1
n−1
n
o
(1)
(2)
=P Si ≥ (i − 1)δn ,Si ≤ n − i
n
o
(1)
(2)
≥P (i − 1)δn ≤ Si ≤ i − 1,(n − i)δn ≤ Si ≤ n − i .

(B.62)

49

Note that
n
n
i − 1 δn o
i − 1 δn o
P |h1,i (Xi )| ≥
≥ P h1,i (Xi ) ≥
.
(B.63)
n−1 2
n−1 2
Equation (A.50) follows from (B.61), (B.62), and (B.63). If i − 1 ≤ (n − i)δn /2, the monotonicity
property of probability measure gives
n S (1) (X ) i − 1 S (2) (X ) n − i o
n − i δn
i
i
i
P {h1,i (Xi ) ≤ −
}≥P
≤
, i
≥
δn
n
−
1
2
n
−
1
n
−
1
n
−
1
n−1
n
o
(1)
(2)
=P Si ≤ i − 1,Si ≥ (n − i)δn
n
o
(1)
(2)
≥P (i − 1)δn ≤ Si ≤ i − 1,(n − i)δn ≤ Si ≤ n − i .
(B.64)
Note that
n
n
n − i δn o
n − i δn o
P |h1,i (Xi )| ≥
≥ P h1,i (Xi ) ≤ −
.
n−1 2
n−1 2
Equation (A.51) follows from (B.61), (B.64), and (B.65).

(B.65)

Secondly, we show that (A.50) and (A.51) hold under Condition (ii) of Theorem 3.3. Using
fij (·) notation, Condition (ii) becomes
P {−1 ≤ fij (Xi ) ≤ −δn ,∀j ∈ [n]\{i}} ≥ pn .

(B.66)

If −1 ≤ fij (x) ≤ −δn ,∀j ∈ [n]\{i}, we have
− (i − 1) = −

i−1
X

(1)

1 ≤ Si (x) ≤ −

j=1

i−1
X

δn = −(i − 1)δn ,

(B.67)

j=1

and
− (n − i) = −

n
X

(2)

1 ≤ Si (x) ≤ −

j=i+1

n
X

δn = −(n − i)δn .

(B.68)

j=i+1

Using (B.67) and (B.68), it follows from (B.58) that
n
o
(1)
(2)
P − (i − 1) ≤ Si (Xi ) ≤ −(i − 1)δn ,−(n − i) ≤ Si (Xi ) ≤ −(n − i)δn ≥ pn .

(B.69)

If n − i ≤ (i − 1)δn /2, the monotonicity property of probability measure gives
(2)
n S (1) (X )
n
S (Xi )
i−1
n−i o
i − 1 δn o
i
i
P h1,i (Xi ) ≤ −
≥P
≤−
δn , i
≥−
n−1 2
n−
n−1
n−1
n−1
n
o1
(1)
(2)
=P Si ≤ −(i − 1)δn ,Si ≥ −(n − i)
n
o
(1)
(2)
≥P − (i − 1) ≤ Si ≤ −(i − 1)δn ,−(n − i) ≤ Si ≤ −(n − i)δn .

(B.70)

Note that
n
n
i − 1 δn o
i − 1 δn o
P |h1,i (Xi )| ≥
≥ P h1,i (Xi ) ≤ −
.
(B.71)
n−1 2
n−1 2
Equation (A.50) follows from (B.69), (B.70), and (B.71). If i − 1 ≤ (n − i)δn /2, the monotonicity

50

property of probability measure gives
(2)
n S (1) (X )
n − i δn
i − 1 Si (Xi )
n−i o
i
i
P {h1,i (Xi ) ≥
}≥P
≥−
,
≤−
δn
n−1 2
n − 1o
n−1 n−1
n−1
n
(1)
(2)
=P Si ≥ −(i − 1),Si ≤ −(n − i)δn
n
o
(1)
(2)
≥P − (i − 1) ≤ Si ≤ −(i − 1)δn ,−(n − i) ≤ Si ≤ −(n − i)δn .

(B.72)

Note that
n
n
n − i δn o
n − i δn o
P |h1,i (Xi )| ≥
≥ P h1,i (Xi ) ≥
.
n−1 2
n−1 2
Equation (A.51) follows from (B.69), (B.72), and (B.73).
This completes the proof.

B.6

(B.73)

Proof of Lemma A.6

Proof. As in the statement of Lemma A.6, we consider a fixed i ∈ [n]. For any j ∈ [n]\{i}, we have
−1
ρ−1
ij ≤ ρn and −rij ≤ Rn . This combined with (A.61) implies that zi ≥ ρij t0 − rij , or equivalently
ρij (zi + rij ) ≥ t0 .

(B.74)

Fjc {ρij (zi + rij )} ≤ c2 {ρij (zi + rij )}−b2 .

(B.75)

Equations (B.74) and (3.6) imply that

Define
δn := min

nc

1

2

Rn−b1 ,

c1 −b1 1 o
t , .
2 0 2

This implies that δn ∈ (0,1) and
δn c1 −b1
c1 −b1
+ t0 ≥
t ,
c2 c2
2c2 0
c1 −b1
δn c1
R .
and − + Rn−b1 ≥
c2 c2
2c2 n
−

(B.76)
(B.77)

−1/2 ≤ t or r (1 + ρ−2 )−1/2 > t holds. In the folFor an arbitrary j ∈ [n]\{i}, either rij (1 + ρ−2
0
ij
0
ij )
ij
lowing we show fij (x) ≤ −δn for all j ∈ [n]\{i} under these two mutually exclusive and collectively
exhaustive cases.

Case 1: Assume that for a fixed j we have
−1/2
rij (1 + ρ−2
≤ t0 .
ij )

(B.78)

−1/2
Fjic {rij (1 + ρ−2
} ≥ Fjic (t0 ).
ij )

(B.79)

1
Fjic (t0 ) ≥ c1 t−b
0 .

(B.80)

By the monotonicity of Fjic (·) we have

By (3.7) we have

51

Combining (B.79) and (B.80) yields
−1/2
1
Fjic {rij (1 + ρ−2
} ≥ c1 t−b
0 .
ij )

(B.81)

Combining (A.60), (B.75), and (B.81) gives
1
fij (x) ≤ c2 {ρij (zi + rij )}−b2 − c1 t−b
0 .

(B.82)

Equation (B.76) implies
δn c1 −b1 −1/b2  −b1 c1 −1/b2
+ t
≤ t0
.
c2 c2 0
2c2
Noting that t0 > 0 and Rn ≥ −rij , (A.61) implies

c1 −1/b2
1
ρn ,
zi ≥ −rij + t−b
0
2c2
Combining (B.83) and (B.84) gives
 δ
c1 1 −1/b2
n
ρij (zi + rij ) ≥ − + t−b
.
c2 c2 0
Therefore, by (B.82) and (B.85) we deduce


−

(B.83)

(B.84)

(B.85)

−b1
1
fij (x) ≤ −δn + c1 t−b
= −δn .
0 − c1 t0

Case 2: Assume that for a fixed j we have
−1/2
rij (1 + ρ−2
> t0 .
ij )

(B.86)

−1/2
−1/2 −b1
Fjic {rij (1 + ρ−2
} ≥ c1 {rij (1 + ρ−2
} .
ij )
ij )

(B.87)

By (3.7) we have

Combining (A.60), (B.75), and (B.87) gives
−1/2 −b1
fij (x) ≤ c2 {ρij (zi + rij )}−b2 − c1 {rij (1 + ρ−2
} .
ij )

(B.88)

Equation (B.77) implies
δn c1 −b1 −1/b2  c1 −b1 −1/b2
+ R
R
≤
.
c2 c2 n
2c2 n
Noting that t0 > 0 and Rn ≥ −rij , (A.61) implies
 c −1/b2
1
Rnb1 /b2 .
zi ≥ −rij + ρ−1
ij
2c2
Combining (B.89) and (B.90) gives
 δ
−1/b2
c1
n
ρij (zi + rij ) ≥ − + Rn−b1
.
c2 c2
Equation (B.91) implies


−

c2 {ρij (zi + rij )}−b2 ≤ −δn + c1 Rn−b1 .

52

(B.89)

(B.90)

(B.91)

(B.92)

−1/2 ≤ 1, we have
Since rij ≤ Rn and (1 + ρ−2
ij )
−1/2 −b1
c1 {rij (1 + ρ−2
}
≥ c1 Rn−b1 .
ij )

(B.93)

Therefore, by (B.88), (B.92), and (B.93) we deduce
fij (x) ≤ −δn + c1 Rn−b1 − c1 Rn−b1 = −δn .
This completes the proof.

B.7

Proof of Lemma A.7

Proof. For any j ∈ [n]\{i}, we have ρ−1
ij ≤ ρn and −rij ≤ Rn . This combined with (A.72) implies
−1
that zi ≥ ρij t0 − rij , or equivalently
ρij (zi + rij ) ≥ t0 .

(B.94)

Fjc {ρij (zi + rij )} ≤ c2 exp[−b2 {ρij (zi + rij )}λ ].

(B.95)

Equations (B.94) and (3.10) imply that

Define
δn := min

nc

1

exp(−b1 Rnλ ),

c1
1o
exp(−b1 tλ0 ), .
2
2

2
This implies that δn ∈ (0,1) and that
δn c1
c1
− + exp(−b1 tλ0 ) ≥
exp(−b1 tλ0 )
(B.96)
c2 c2
2c2
δn c1
c1
and − + exp(−b1 Rnλ ) ≥
exp(−b1 Rnλ ).
(B.97)
c2 c2
2c2
In the following we show fij (x) ≤ −δn for all j ∈ [n]\{i} under these two mutually exclusive and
collectively exhaustive cases.
Case 1: Assume that for a fixed j we have
−1/2
rij (1 + ρ−2
≤ t0 .
ij )

(B.98)

−1/2
Fjic {rij (1 + ρ−2
} ≥ Fjic (t0 ).
ij )

(B.99)

By the monotonicity of Fjic (·) we have

By (3.11) we have
Fjic (t0 ) ≥ c1 exp(−b1 tλ0 ).

(B.100)

−1/2
Fjic {rij (1 + ρ−2
} ≥ c1 exp(−b1 tλ0 ).
ij )

(B.101)

Combining (B.99) and (B.100) yields

Combining (A.60), (B.95), and (B.101) gives
fij (x) ≤ c2 exp[−b2 {ρij (zi + rij )}λ ] − c1 exp(−b1 tλ0 ).

53

(B.102)

Equation (B.96) implies
δn c1
1
c1
b1
1
log{− + exp(−b1 tλ0 )} ≤ − log
+ tλ0 .
b2
c2 c2
b2
2c2 b2
Noting that t0 > 0 and Rn ≥ −rij , (A.72) implies
 1
c1
b1 λ 1/λ
−1
log
+
t
.
zi ≥ −rij + ρ−1
K
≥
−r
+
ρ
−
3
ij
ij
ij
b2
2c2 b2 0
Combining (B.103) and (B.104) gives
h 1
n δ
oi1/λ
c1
n
ρij (zi + rij ) ≥ − log − + exp(−b1 tλ0 )
.
b2
c2 c2
Therefore, by (B.102) and (B.105) we deduce
−

(B.103)

(B.104)

(B.105)

fij (x) ≤ −δn + c1 exp(−b1 tλ0 ) − c1 exp(−b1 tλ0 ) = −δn .
Case 2: Assume that for a fixed j we have
−1/2
rij (1 + ρ−2
> t0 .
ij )

(B.106)

By (3.11) we have
−1/2
Fjic {rij (1 + ρ−2
} ≥ c1 exp
ij )

h

n 
−1/2 oλ i
−2
− b1 rij 1 + ρij
.

(B.107)

Combining (A.60), (B.95), and (B.107) gives
−1/2 λ
fij (x) ≤ c2 exp[−b2 {ρij (zi + rij )}λ ] − c1 exp[−b1 {rij (1 + ρ−2
} ].
ij )

(B.108)

Equation (B.97) implies
−

1
δn c1
1
c1
b1
log{− + exp(−b1 Rnλ )} ≤ − log
+ Rλ .
b2
c2 c2
b2
2c2 b2 n

(B.109)

1
c1 1/λ  b1 λ 1/λ o
log
R
.
+
b2
2c2
b2 n

(B.110)

Equation (A.72) implies
zi ≥ Rn + ρn ξ(λ−1 )

n

−

It follows from (B.110) and Lemma C.9 that
 1
c1
b1 1/λ
+ Rnλ
zi ≥ Rn + ρn − log
.
b2
2c2 b2
Noting that t0 > 0 and Rn ≥ −rij , (B.111) implies
 1
c1
b1 λ 1/λ
zi ≥ −rij + ρ−1
−
log
+
R
.
ij
b2
2c2 b2 n
Combining (B.109) and (B.112) gives
h 1
i1/λ
δn c1
.
ρij (zi + rij ) ≥ − log{− + exp(−b1 Rnλ )}
b2
c2 c2
Equation (B.113) implies
c2 exp[−b2 {ρij (zi + rij )}λ ] ≤ −δn + c1 exp(−b1 Rnλ ).

54

(B.111)

(B.112)

(B.113)

(B.114)

−1/2 ≤ 1, we have
Since rij ≤ Rn and (1 + ρ−2
ij )
h
i
−1/2 λ
c1 exp − b1 {rij (1 + ρ−2
)
}
≥ c1 exp(−b1 Rnλ ).
ij

(B.115)

Therefore, by (B.108), (B.114), and (B.115) we deduce
fij (x) ≤ −δn + c1 exp(−b1 Rnλ ) − c1 exp(−b1 Rnλ ) = −δn .
This completes the proof.

B.8

Proof of Lemma A.8

Proof. Consider an arbitrary vector (l1 ,...,ln ), with each li ∈ [n]. Define the sign function sgn(x) :=
1(x > 0) − 1(x < 0). It follows from (3.1) that
n
n
n
hX
i2
X
X
1
Ken
2
E{h1,i (Xli ) } =
E
sgn(i
−
k){P
(X
>
X
|
X
)
−
P
(X
>
X
)}
i
k
l
l
k
i
i
(n − 1)2
i=1

i=1

k=1

= T1 − 2T2 + T3 ,

(B.116)

where
T1 =

n
n
X
X
1
sgn(i − k1 )sgn(i − k2 )E [P (Xk1 > Xli | Xli )P (Xk2 > Xli | Xli )],
(n − 1)2

(B.117)

i=1 k1 ,k2 =1

T2 =

T3 =

1
(n − 1)2
1
(n − 1)2

n
n
X
X
i=1 k1 ,k2 =1
n
n
X
X

sgn(i − k1 )sgn(i − k2 )P (Xk1 > Xj )P (Xk2 > Xi ),

(B.118)

sgn(i − k1 )sgn(i − k2 )P (Xk1 > Xi )P (Xk2 > Xi ).

(B.119)

i=1 k1 ,k2 =1

We have
n
n
X
X

sgn(i − k1 )sgn(i − k2 ) =

i=1 k1 ,k2 =1

n
X
i=1

1
(2i − n − 1)2 = n(n − 1)(n + 1).
3

(B.120)

It follows from (3.20), (B.117), and (B.120) that
T1 =

n(n − 1)(n + 1) 2
n(n + 1) 2
{η + O(n−1/3 )} =
η + O(n2/3 ).
3(n − 1)2
3(n − 1)

(B.121)

It follows from (3.19), (B.118), (B.119), and (B.120) that
n(n − 1)(n + 1)
n(n + 1) 2
{θ + O(n−1/6 )}2 =
θ + O(n5/6 ),
2
3(n − 1)
3(n − 1)
n(n − 1)(n + 1)
n(n + 1) 2
T3 =
{θ + O(n−1/6 )}2 =
θ + O(n5/6 ).
2
3(n − 1)
3(n − 1)

T2 =

(B.122)
(B.123)

Combining (B.116) with (B.121), (B.122), and (B.123) yields
n
X

n(n + 1) 2
2
E hKen
= T1 − 2T2 + T3 =
(η − θ2 ) + O(n5/6 ).
1,i (Xli )
3(n − 1)
i=1

55

(B.124)

In (B.124), letting (l1 ,...,ln ) = (j,j,...,j) yields (A.95), and letting (l1 ,...,ln ) = (j,j,...,j) yields
(A.96).
This completes the proof.

B.9

Proof of Lemma A.9

Proof. Consider an arbitrary vector (l1 ,...,ln ), with each li ∈ [n]. It follows from (3.2) that
n
n
n n
i2
hX
X
X
1
n1(k < i) n1(k > i) o
2
E{hAP
(X
)
}
=
−
{P
(X
>
X
|
X
)
−
P
(X
>
X
)}
E
i
l
k
l
l
k
1,i
i
i
i
(n − 1)2
i−1
k−1
i=1

i=1

k=1

= T1 − 2T2 + T3 ,

(B.125)

where
n
n
n2 X X
T1 =
γ(i,k1 ,k2 )E [P (Xk1 > Xli | Xli )P (Xk2 > Xli | Xli )],
(n − 1)2

T2 =

T3 =

n2
(n − 1)2

i=1 k1 ,k2 =1
n
n
X
X

(n − 1)2

γ(i,k1 ,k2 )P (Xk1 > Xj )P (Xk2 > Xi ),

(B.127)

γ(i,k1 ,k2 )P (Xk1 > Xi )P (Xk2 > Xi ),

(B.128)

i=1 k1 ,k2 =1
n
n
X
X

n2

(B.126)

i=1 k1 ,k2 =1

and
n 1(k < i) 1(k > i) on 1(k < i) 1(k > i) o
1
2
2
1
−
−
.
i−1
k1 − 1
i−1
k2 − 1
By Lemma C.10 and Lemma C.8 we have
n
n
X
X
γ(i,k1 ,k2 ) = (n − 1) + ϕ(n − 1) = (n − 1) + O(logn).
γ(i,k1 ,k2 ) :=

(B.129)

i=1 k1 ,k2 =1

It follows from (3.22), (B.126), and (B.129) that
T1 =

n2 2
n2 {(n − 1) + O(logn)} 2
−1/3
2
{η
+
O(n
(logn)
)}
=
η + O{n2/3 (logn)2 }.
(n − 1)2
n−1

(B.130)

It follows from (3.21), (B.127), (B.128), and (B.129) that
n2 {(n − 1) + O(logn)}
n2 2
−1/6
2
{θ
+
O(n
logn)}
=
θ + O(n5/6 logn),
(n − 1)2
n−1
n2 {(n − 1) + O(logn)}
n2 2
−1/6
2
T3 =
{θ
+
O(n
logn)}
=
θ + O(n5/6 logn).
(n − 1)2
n−1

T2 =

(B.131)
(B.132)

Combining (B.125) with (B.130), (B.131), and (B.132) yields
n
X

n2
2
E hAP
= T1 − 2T2 + T3 =
(η 2 − θ2 ) + O(n5/6 logn).
1,i (Xli )
n−1

(B.133)

i=1

In (B.133), letting (l1 ,...,ln ) = (j,j,...,j) yields (A.95), and letting (l1 ,...,ln ) = (j,j,...,j) yields
(A.96). This completes the proof.

56

C

Auxiliary lemmas and proofs

In this Section, we state and prove (or give reference to) the auxiliary lemmas that are used in the
proofs in earlier sections.
Lemma C.1. There exists a constant cm which only depends on m, such that the following results
hold.
(i) For any n and any (i1 ,...,im ) ∈ Inm ,
E{h2;i1 ,...,im (Xi1 ,...,Xim )2 } ≤ cm E{h(Xi1 ,...,Xim )2 }.
m−1
(ii) For any n, any i ∈ [n], any (i1 ,...,im−1 ) ∈ In−1
(−i), and any l ∈ [m],
(l)

E[{fi1 ,...,im−1 (Xi ) − θ(l) (i;i1 ,...,im−1 )}4 ] ≤ cm E{h(l) (Xi ;Xi1 ,...,Xim−1 )4 }.
(iii) For any n, any (i1 ,...,im ) ∈ Inm , and any j1 ,...,jm ∈ [n],
E{h2;i1 ,...,im (Xj1 ,...,Xjm )2 } ≤ cm

sup
1≤k1 ,...,km ≤n

E{h(Xk1 ,...,Xkm )2 }.

Lemma C.2 (Lee, 1990, Section 1.3, Theorem 2). Consider three random variables X,Y,Z. Assume
Y is independent of Z conditional on X. Then for two measurable functions f,g : R2 → R, we have
h
i
Cov{f (X,Y ),g(X,Z)} = Cov E{f (X,Y ) | X},E{g(X,Z) | X} .
Lemma C.3. Consider a sequence of random variables X1 ,X2 ,..., with E(Xn ) = 0 for all Xn . If
P
Var(Xn ) → 0, then Xn → 0.
Lemma C.4 (Lyapunov’s central limit theorem). Let X1 ,X2 ,... be a sequence of independent
P
random variables and let Sn = n−1 ni=1 Xi . If there exists δ > 0 such that
Pn
E|Xi − E(Xi )|2+δ
lim n i=1
(C.1)
o 2+δ = 0,
n→∞ P
2
n
2
i=1 E |Xi − E(Xi )|
then
d

Var(Sn )−1/2 {Sn − E(Sn )} → N (0,1).
Lemma C.5 (Lehmann, 1999, Theorem 2.6.1). If a sequence of cumulative distribution functions
Hn tends to a continuous cdf H, then Hn (x) converges to H(x) uniformly in x.
Lemma C.6 (Mammen, 2012, Theorem 2.2). Consider a sequence Yn,1 ,...,Yn,n of independent
P
random variables with distribution Pn,i . For a function gn define Tbn = n−1 ni=1 gn (Yn,i ). Consider
∗ ,...,Y ∗ and define T
b∗ = n−1 Pn gn (Y ∗ ). Then for every sequence tn the
a bootstrap sample Yn,1
n,n
n
n,i
i=1
following assertions are equivalent:

57

(i) There exists σn such that for every  > 0
o
n g (Y ) − t
n n,i
n
≥  → 0,
nσn
1≤i≤n
n
oi2
X  h gn (Yn,i ) − tn n gn (Yn,i ) − tn
→ 0,
1
≤
E
nσn
nσn

(C.2)

sup P

(C.3)

i=1

sup |P (Tbn − tn ≤ t) − Φ(t)| → 0.

(C.4)

t∈R

(ii) Bootstrap works:
P
sup |P (Tbn∗ − Tbn ≤ t | Yn,1 ,...,Yn,n ) − P (Tbn − tn ≤ t)| → 0.
t∈R

Lemma C.7 (Serfling, 1980, Theorem 1.8 C). Let X1 ,X2 ,... be uncorrelated with means µ1 ,µ2 ,...
P
and variances σ12 ,σ22 ,.... If ni=1 σi2 = o(n−2 ), n → ∞, then
n

n

i=1

i=1

1X
1X P
Xi −
µi → 0.
n
n
Lemma C.8 (Bound on the partial sum of harmonic series). Denote ϕ(n) =
any two integers m,n such that 1 ≤ m ≤ n,
n
n+1
≤ ϕ(n) − ϕ(m) ≤ log ,
log
m+1
m
log(n + 1) ≤ ϕ(n) ≤ 1 + logn.

Pn

k=1 k

−1 .

Then for

(C.5)
(C.6)

Lemma C.9. For any two positive real numbers a,b and real number p > 0, we have
(a + b)p ≤ ξ(p)(ap + bp ),
where

2p−1
ξ(p) =
1
Lemma C.10. We have
n X
n X
n n
X
1(j < i)

if p ≥ 1,
if 0 < p < 1.

1(j > i) on 1(k < i) 1(k > i) o
−
= (n − 1) + ϕ(n − 1),
i−1
j −1
i−1
k−1
i=1 j=1 k=1
P
where we define 0/0 := 0 and ϕ(n) := nk=1 k −1 .
−

(C.7)

R∞
2
Lemma C.11. Define Φc (x) = √12π x exp(− t2 )dt to be the complement distribution function for
the standard Gaussian. We have the following bounds for Φc (x):


1
1
1
x2
1 1
x2
√
− 3 exp(− ) ≤ Φc (x) ≤ √
exp(− ),
if x > 0,
2
2
2π x x
2π x


1 1
x2
1
1
1
x2
c
1+ √
exp(− ) ≤ Φ (x) ≤ 1 + √
− 3 exp(− ),
if x < 0.
2
2
2π x
2π x x

58

C.1

Proof of auxiliary lemmas

Proof of Lemma C.1. Define i = (i1 ,...,im ), Xi = (Xi1 ,...,Xim ), and i−m = (i1 ,...,im−1 ).
(i) By the definition of h2;i (·) in (2.5) we have
m
h
i
X
(l)
E{h2; (Xi )2 } ≤ 2m+2 E{h(Xi )2 } +
E{fi\il (Xil )2 } + (m − 1)2 θ2 (i) .

(C.8)

l=1

Jensen’s inequality and the law of iterated expectation yield
(l)

E{fi\il (Xil )2 } = Eil [Ei\il {h(l) (Xil ;Y1 ,...Ym−1 ) | Xil }2 ] ≤ E{h(Xi )2 }

(C.9)

θ2 (i) ≤ E{h(Xi )2 }.

(C.10)

and

Equations (C.8), (C.9), and (C.10) imply
E{h2;i (Xi )2 } ≤ 2m+2 {1 + m + (m − 1)2 }E{h(Xi )2 }.
This proves (i).
(ii) We have
(l)

(l)

E[{fi−m (Xi ) − θ(l) (i;i−m )}4 ] ≤ 24 [E{fi−m (Xi )4 } + θ(l) (i;i−m )4 ]

(C.11)

(l)

By the definition of fi−m (·) in (2.3) and Jensen’s inequality we have
(l)

E{fi−m (Xi )4 } ≤ Ei [Ei−m {h(l) (Xi ;Y1 ,...Ym−1 )4 | Xi }] = E{h(l) (Xi ;Xi−m )4 }.

(C.12)

Jensen’s inequality also implies that
θ(l) (i;i−m )4 = {Eh(l) (Xi ;Xi−m )}4 ≤ E{h(l) (Xi ;Xi−m )4 }.

(C.13)

Combining (C.11) with (C.12) and (C.13) yields
(l)

E[{fi−m (Xi ) − θ(l) (i;i−m )}4 ] ≤ 24 E{h(l) (Xi ;Xi−m )4 }.
This proves (ii).
(iii) Consider j := (j1 ,...,jm ) with each jl ∈ [m]. Define Xj := (Xj1 ,...,Xjm ). By the definition of
h2;i (·) in (2.5) we have
m
h
i
X
(l)
E{h2;i (Xj )2 } ≤ 2m+2 E{h(Xj )2 } +
E{fi\il (Xjl )2 } + (m − 1)2 θ2 (i) .
(C.14)
l=1
(l)

By the definition of fi−m (·) in (2.3) and Jensen’s inequality we have
(l)

E{fi−m (Xjl )2 } ≤ Ejl [Ei−m {h(l) (Xjl ;Y1 ,...Ym−1 )2 | Xjl }] = E{h(l) (Xjl ;Xi−m )2 }.

59

(C.15)

Combining (C.14), (C.15), and (C.10) yields
m
h
i
X
E{h2;i (Xj )2 } ≤ 2m+2 E{h(Xj )2 } +
E{h(l) (Xjl ;Xi−m )2 } + (m − 1)2 E{h(Xi )2 }
l=1

≤2

m+2

m

2

sup
1≤k1 ,...,km ≤n

E{h(Xk1 ,...,Xkm )2 }.

This proves (iii).
The proof is thus finished.
P
Proof of Lemma C.8. We have ϕ(n) − ϕ(m) = nk=m+1 k −1 . By integral bound, we have
Z n+1
Z n
n
X
n+1
1
1
1
n
log
=
dx ≤
≤
dx = log ,
m+1
k
m
m+1 x
m x
k=m+1

which yields (C.5). We also have
Z

n+1

log(n + 1) ≤
1

n

X1
1
dx ≤
≤ 1+
x
k
k=1

Z

n

1

1
dx ≤ 1 + logn,
x

which yields (C.6). The proof is thus finished.
Proof of Lemma C.10. By algebra we have
n X
n X
n n
X
1(j < i) 1(j > i) on 1(k < i) 1(k > i) o
−
−
= T1 − T2 − T3 + T4 ,
i−1
j −1
i−1
k2 − 1

(C.16)

i=1 j=1 k=1

where
T1 =

n X
n X
n X
n X
n
n
X
X
1(j < i) 1(k > i)
1(j < i) 1(k < i)
·
, T2 =
·
,
i−1
i−1
i−1
k−1
i=1 j=1 k=1

i=1 j=1 k=1

n X
n X
n
n X
n X
n
X
X
1(j > i) 1(k < i)
1(j > i) 1(k > i)
T3 =
·
, T4 =
·
.
j −1
i−1
j −1
k−1
i=1 j=1 k=1

i=1 j=1 k=1

For T1 we have
T1 =

n X
i−1 X
i−1
X
i=2 j=1 k=1

1
= n − 1.
(i − 1)2

(C.17)

For T2 we have
T2 =

n−1
i−1
XX

n
X

i=2 j=1 k=i+1

n k−1

n

XX 1
X
1
1
1 
·
=
=
1−
= (n − 1) − ϕ(n − 1).
i−1 k−1
k−1
k−1
k=3 i=2

(C.18)

k=3

By symmetry T2 = T3 , so
T3 = (n − 1) − ϕ(n − 1).

(C.19)

For T4 we have
T4 =

n−1
X

n
n
X
X

i=1 j=i+1 k=i+1

j−1
j X
n X
n X
n X
k−1
X
X
1
1
1
1
1
1
·
=
·
+
·
.
j −1 k−1
j −1 k−1
j −1 k−1
j=2 k=j+1 i=1

60

j=2 k=2 i=1

(C.20)

Note that
j−1
n X
n X
n X
n
n X
k−1
X
X
X
1
1
1
1
·
=
=
= (n − 1) − ϕ(n − 1)
j −1 k−1
k−1
k−1
j=2 k=j+1 i=1

j=2 k=j+1

j X
j
n X
k−1
n X
n
X
X
X
1
1
1
and
·
=
=
1 = n − 1.
j −1 k−1
j −1
j=2 k=2 i=1

(C.21)

k=3 j=2

j=2 k=2

(C.22)

j=2

Combining (C.20) with (C.21) and (C.22) yields
T4 = 2(n − 1) − ϕ(n − 1).
Equation (C.7) follows from (C.16), (C.17), (C.18), and (C.23).
This completes the proof.

61

(C.23)

References
Bickel, P. J. and Freedman, D. A. (1981). Some asymptotic theory for the bootstrap. The Annals
of Statistics, 9(6):1196–1217.
Bickel, P. J., Götze, F., and van Zwet, W. R. (1997). Resampling fewer than n observations: gains,
losses, and remedies for losses. Statistica Sinica, 7:1–31.
Carlstein, E., Do, K.-A., Hall, P., Hesterberg, T., and Künsch, H. R. (1998). Matched-block
bootstrap for dependent data. Bernoulli, 4(3):305–328.
Csörgő, M. and Nasari, M. M. (2013). Asymptotics of randomly weighted U- and V-statistics:
application to bootstrap. Journal of Multivariate Analysis, 121:176–192.
Dahlhaus, R. (1997). Fitting time series models to nonstationary processes. The Annals of Statistics,
25(1):1–37.
Dehling, H. and Wendler, M. (2010). Central limit theorem and the bootstrap for U-statistics of
strongly mixing data. Journal of Multivariate Analysis, 101(1):126–137.
Efron, B. (1979). Bootstrap methods: Another look at the jackknife. The Annals of Statistics,
7(1):1–26.
Fitzenberger, B. (1998). The moving blocks bootstrap and robust inference for linear least squares
and quantile regressions. Journal of Econometrics, 82(2):235–287.
Gonçalves, S. and White, H. (2002). The bootstrap of the mean for dependent heterogeneous
arrays. Econometric Theory, 18(6):1367–1384.
Grams, W. F. and Serfling, R. J. (1973). Convergence rates for U-statistics and related statistics.
The Annals of Statistics, 1(1):153–160.
Hall, P. (1992). The Bootstrap and Edgeworth Expansion. Springer.
Hoeffding, W. (1948). A class of statistics with asymptotically normal distribution. The Annals of
Mathematical Statistics, 19(3):293–325.
Hsing, T. and Wu, W. B. (2004). On weighted U-statistics for stationary processes. The Annals of
Probability, 32(2):1600–1631.
Kendall, M. G. (1938). A new measure of rank correlation. Biometrika, 30(1/2):81–93.
Kendall, M. G. and Stuart, A. (1973). The Advanced Theory of Statistics, volume 2. Charles
Griffin.

62

Korolyuk, V. S. and Borovskich, Y. V. (2013). Theory of U-Statistics. Springer.
Kreiss, J.-P. and Paparoditis, E. (2015). Bootstrapping locally stationary processes. Journal of the
Royal Statistical Society: Series B (Statistical Methodology), 77(1):267–290.
Kunsch, H. R. (1989). The jackknife and the bootstrap for general stationary observations. The
Annals of Statistics, 17(3):1196–1217.
Lahiri, S. N. (1993). On the moving block bootstrap under long range dependence. Statistics and
Probability Letters, 18(5):405–413.
Lee, J. (1990). U-Statistics: Theory and Practice. CRC Press.
Lehmann, E. L. (1999). Elements of Large-Sample Theory. Springer.
Liu, R. Y. (1988). Bootstrap procedures under some non-i.i.d. models. The Annals of Statistics,
16(4):1696–1708.
Liu, R. Y. and Singh, K. (1995). Using i.i.d. bootstrap inference for general non-i.i.d. models.
Journal of Statistical Planning and Inference, 43(1):67–75.
Major, P. (1994). Asymptotic distributions for weighted U-statistics. The Annals of Probability,
21(2):1514–1535.
Mammen, E. (2012). When Does Bootstrap Work? Asymptotic Results and Simulations. Springer.
Mikosch, T. (1999). Regular variation, subexponentiality and their applications in probability
theory. Technical report, Eindhoven University of Technology.
O’Neil, K. A. and Redner, R. A. (1993). Asymptotic distributions of weighted U-statistics of degree
2. The Annals of Probability, 21(2):1159–1169.
Paparoditis, E. and Politis, D. N. (2001). Tapered block bootstrap. Biometrika, 88(4):1105–1119.
Paparoditis, E. and Politis, D. N. (2002). Local block bootstrap. Comptes Rendus Mathematique,
335(11):959–962.
Politis, D. N. and Romano, J. P. (1992). A circular block-resampling procedure for stationary data.
In Exploring the Limits of Bootstrap, pages 263–270. John Wiley, New York.
Politis, D. N. and Romano, J. P. (1994). Large sample confidence regions based on subsamples
under minimal assumptions. The Annals of Statistics, 22(4):2031–2050.
Politis, D. N., Romano, J. P., and Wolf, M. (1999). Subsampling. Springer.
Resnick, S. I. (2007). Heavy-Tail Phenomena: Probabilistic and Statistical Modeling. Springer.
63

Rifi, M. and Utzet, F. (2000). On the asymptotic behavior of weighted U-statistics. Journal of
Theoretical Probability, 13(1):141–167.
Sen, P. K. (1968). Estimates of the regression coefficient based on Kendall’s tau. Journal of the
American Statistical Association, 63(324):1379–1389.
Serfling, R. J. (1980). Approximation Theorems of Mathematical Statistics. John Wiley and Sons.
Shao, X. (2010). The dependent wild bootstrap. Journal of the American Statistical Association,
105(489):218–235.
Shapiro, C. P. and Hubert, L. (1979). Asymptotic normality of permutation statistics derived from
weighted sums of bivariate functions. The Annals of Statistics, 7(4):788–794.
Thode, H. C. (2002). Testing for Normality. CRC Press.
Yilmaz, E., Aslam, J. A., and Robertson, S. (2008). A new rank correlation coefficient for information retrieval. In Proceedings of the 31st Annual International ACM SIGIR Conference on
Research and Development in Information Retrieval, pages 587–594.
Yoshihara, K.-i. (1976). Limiting behavior of U-statistics for stationary, absolutely regular processes. Probability Theory and Related Fields, 35(3):237–252.
Zhou, Z. (2014). Inference of weighted V-statistics for nonstationary time series and its applications.
The Annals of Statistics, 42(1):87–114.

64

