Skip to main content

Full text of "The LIL for canonical $U$-statistics"

See other formats




o 

-(— > 



X 



The Annals of Probability 

2008, Vol. 36, No. 3, 1023-1058 

DOI: 10.1214/07-AOP351 

(c) Institute of Mathematical Statisties, 2008 



^". THE LIL FOR CANONICAL [/-STATISTICS 

o, 

O , By Radoslaw Adamczak^ and Rafal Latala^ 

r^ I Polish Academy of Sciences and Warsaw University 



We give necessary and sufficient conditions for the (bounded) law 
of the iterated logarithm for canonical [/-statistics of arbitrary order 
d, extending the previously known results for d = 2. The nasc's are 
expressed as growth conditions on a parameterized family of norms 
associated with the [/-statistics kernel. 



^^ , 1. Introduction, [/-statistics [i.e. statistics being averages of a measur- 

T^ ' able kernel h{xi,. . . ,Xd) over an i.i.d. sample Xi,X2, ■ ■ ■ ,Xn] were intro- 

C^ ■ duced by Hoeffding [11] and Halnios [9] in the 1940s and since then have 

become an important tool in asymptotic statistics, appearing for instance as 
unbiased estimators or higher-order terms in expansions of smooth statistics. 
^sg . Their relevance stems mainly from the fact that they share many basic prop- 

^ I erties with sums of i.i.d. random variables. Already in the 1960s Hoeffding 

^N . proved that E\h\ < oo is a sufficient condition for a [/-statistic to satisfy the 

-vi ! SLLN [12], the CLT under the finiteness of the second moment of the kernel 

t;^ ' (and complete degeneracy — a technical assumption which will be explained 

^D . in the sequel) was obtained by Rubin and Vitale in 1980 [18], finally the LIL 

(under the same hypothesis) was proved by Arcones and Gine in 1995 [2]. All 
the abovementioned results are occurrences of a general phenomenon, man- 
ifesting itself in the fact that the necessary and sufficient conditions for the 
classical triple of limit theorems for sums of i.i.d. random variables (SLLN, 
CLT or LIL) are sufficient for analogous limit theorems for [/-statistics. It 
may be, therefore, somewhat surprising (and as a matter of fact remained for 
some time unnoticed) that with the exception of the CLT, these conditions 
fail to be necessary. 
C^ I Recently we have witnessed a rapid development in the asymptotic theory 

of [/-statistics, following the discovery of the so-called decoupling technique 



Received April 2006; revised May 2007. 

^Supported in part by MEiN Grant 2 P03A 019 30. 

^Supported in part by MEiN Grant 1 P03A 012 29. 

AMS 2000 subject classification. 60E15. 

Key words and phrases, [/-statistics, law of the iterated logarithm. 



This is an electronic reprint of the original article published by the 
Institute of Mathematical Statistics in The Annals of Probability, 
2008, Vol. 36, No. 3, 1023-1058. This reprint differs from the original in 
pagination and typographic detail. 

i 



2 R. ADAMCZAK AND R. LATALA 

(see [3] and the references therein), which allows one to treat [/-statistics 
as sums of conditionally independent random variables. In particular, the 
sufficient conditions for the CLT given by Rubin and Vitale were proven 
to be also necessary (Gine and Zinn [7]). Also the necessary and sufficient 
conditions for the SLLN were found ([19] for d = 2, [15] for general d). In 
1999 Gine et al. [8] obtained necessary and sufficient conditions for the law 
of the iterated logarithm for [/-statistics of order 2. The conditions they 
gave turned out to be less restrictive and more subtle than just the square 
integrability of the kernel (as indicated already by Gine and Zhang [5]). 
Completing the picture requires finding the nasc's for the LIL in the general 
case and identifying the limit set in the LIL (which in general is unknown 
even for d = 2). 

In this paper, we address the first of these questions, namely we give the 
nasc's on a kernel /i(xi, . . . ,Xd) to satisfy the (bounded) law of the iterated 
logarithm. In particular we prove that a conjecture stated in [8] is false. 

2. Notation. For an integer d, let (Xj)jgN, [X^ )jgN,i<fc<d be i.i.d. ran- 
dom variables with values in a Polish space S, equipped with the Borel 
(T-field J-. Consider moreover a measurable function /i : S — > R. 

To shorten the notation, we will use the following convention. For i = 
(ii, . . . , i(i) G {1, . . . , n}'^ we will write Xi (resp. Xf^'^) for {Xi^ , . . . , Xi^) (resp. 

{Xl^' , . . . ,XlJ)) and ei (resp. ef"'^) for the product e^^ • . . . • £i^ (resp. e^-^^ • 

■ ■ ■■£\ ), the notation being thus slightly inconsistent, which however should 
not lead to a misunderstanding. The [/-statistics will, therefore, be denoted 

y^ /i(Xi) (an undecoupled [/-statistic) 



22i ^(-^i '^^) (^ decoupled [/-statistic) 



i|<n 

2_\ ei/i(Xi) (an undecoupled randomized [/-statistic) 

y^ ej'"^/i(Xj'"^) (a decoupled randomized [/-statistic), 

lil<n 



where 



max Ik , 
fc=i d ' 



-^n = {i : |i| < ^' ij / ^k for j^k]. 
Since in this notation {1, . . . , d} = /^ we will write 

/rf = {l,2,...,4. 



THE LIL FOR CANONICAL [/-STATISTICS 3 

We will also occasionally write X for (Xi, . . . ,Xd) and for / C I^, X/ = 
(Xj)jg/. Sometimes we will write simply h instead of h{X). 

Throughout the article we will write K, Ld, L to denote constants depend- 
ing only on the function h, only on d and universal constants, respectively. 
In all those cases the values of a constant may differ at each occurrence. 

To avoid technical problems with small values of h let us also define 
LLx = loglog(a; V e^). 

Let us also introduce some notation for conditional expectation. For j £ 
Id, by Kj we will denote expectation with respect to {X^ )i, {{el ,X^ ))i or 
Xj (depending on the context). Similarly, for I '^ Id, we will denote by E/, 
integration with respect to {X^)j(zj^i, {{e\ ,X^))j,zj^i or (Xj)jg/. Although 
at first this notation may seem slightly ambiguous, it turns out to be quite 
natural at specific instances and should not lead to misunderstanding. 

In the article we will consider mainly canonical (or completely degenerate) 
kernels, that is kernels h, such that for all j G Id, 

Ejh{Xi,...,Xd) = a.s. 

3. The main result. Let us now introduce the quantities, that the nec- 
essary and sufficient conditions for the LIL will be expressed in. 

Definition 1. For a finite set /, let Vj denote the family of all partitions 
of / into disjoint, nonempty sets and for a partition J GVj let degj^ be 
the number of elements of J^. For a kernel /i : S'^ — > M, a partition J' = 
{ Ji, . . . , Jk} G "P/j and a nonnegative number u, define 



j,u=\\h{X)\\j^^ 
= supi E 



k 

h{x)f[n{Xjj 



:||/.(^JJI|2<1, 
\\n{XjJ\\^<u,i = l,...,k] 



Example. For d = 3, the above definition gives 

||/l(Xi,X2,X3)||{i,2,3},«=SUp{E/l(Xi,X2,X3)/(Xi,X2,X3): 

E/(Xi,X2,X3)2<l,||/|U<n}, 

||/l(Xi,X2,X3)||{i,2H3},«=SUp{E/i(Xi,X2,X3)/(Xi,X2)5(X3): 

Ef{Xi,X2f,Eg{Xsf<l, 

.JS'lloo <u}, 



4 R. ADAMCZAK AND R. LATALA 



\\h{X,,X2,X3)\\{i}{2}{3},u=sM^HXi,X2,Xs)f{Xi)g{X2)k{Xs): 

Ef{Xif,Eg{X2f,Ek{X3f<l, 

blloo,||A;||oo <u}. 



OO; 



Although at first approach the || • \\j^u norms may seem quite unusual, 
they resemble both the quantities appearing in tail estimates for canonical 
C^-statistics and in tail estimates for Rademacher chaoses (see Sections 4.2 
and 4.3 below) and they indeed play an important role in necessary and 
sufficient conditions for the LIL, as can be seen in our main result, which is 

Theorem 1. For any symmetric /i: S"^ — > M, the law of the iterated log- 
arithm 



^^n^sup-— — -^ 

n-»oo (nloglognj"'^ 



' ^ -^ 77, 



< cxD a.s. 



holds if and only if h is completely degenerate for the law of Xi and for all 
limsup- — ^(d-dc^7)/2 \\^\\j,^ < °o- 

n-^oo (log log u)'.'^ acg^j/^ 

(Recall that according to Definition 1, deg^T denotes the number of elements 
of J.) 

Remark. Obviously, although formally in the above theorem one con- 
siders all the partitions J^ , due to symmetry of the kernel and equidistribu- 
tion of the variables Xi, . . . ,Xii, many of them give the same value of ||/i||j',u- 
For instance for d = 3 we have ||/i||{i}{2,3},« = II^II{2}{1,3},« = II^II{3}{1,2},« 
(note that we suppressed the outer brackets in the lower index and wrote 
e.g. ||^||{2}{i,3},« instead of ||/i||{{2}{i,3}},«- We will do so whenever there is 
no risk of confusion also with similar norms, which will be introduced in 
Sections 4.2 and 4.3). 

4. Preliminaries. Basic definitions and tools. 

4.1. Hoeffding^ s decomposition. We will now describe a decomposition 
of a [/-statistic with mean zero kernel into a sum of completely degenerate 
[/-statistics, introduced in [11], which is one of the basic tools in the analysis 
of [/-statistics. Recall that we are working with a fixed sequence (Xj)jgN of 
i.i.d. S-valued random variables. Then the classical definition of Hoeffding's 
projections is as follows. 



THE LIL FOR CANONICAL [/-STATISTICS 5 

'^ ^M and A; = 0,1,..., d, 



Definition 2. For an integrable kernel /i:S 
define 7r^./i : S'"' — > M with the formula 

Trkh{xi,...,Xk) = {Sxi -P) X (^2 -P) X ••• X (5. 



Xk 



P) X P^-^/i, 



where P is the law of Xi . 

In particular ttqU = E/i, 7ri/i(xi) ='E^2,...,d}f^{^ij^2, ■ ■ ■ ,Xd) — E/i. 

We will however need to extend this definition (for k = d) to [/-statistics 
based not necessarily on an i.i.d. sequence. Let us thus introduce the follow- 
ing definition 



Definition 3. Let /i : Si x • • • x S^ ^ M be a measurable function. Con- 
sider independent sequences {X- )j,...,{X- )_,• of i.i.d. random variables 

with values in Si , . . . , . 

Define Tr^/i : Si x • • • x S^ ^ M with the formula 



,Srf respectively, such that E|/i(XJ ,...,X} )| < co. 



■Kdh{xi,...,Xd) = (4i -Py(l)) X ••• X (4^ 

^1 



■Py(d))/i, 
^1 



where P„(i) is the law of X-, 

^1 



(i) 



^(i)^ 



Obviously for Si = • • • = S^ and {X^ )i&^ — independent copies of {Xi)i^^, 
the above definitions of iidh are equivalent. 

It is easy to check that for A; > 1, 7r^./i is canonical for the law of Xi (note 
also that ttq/i = E/i). 

In the sequel we will need the following comparison of moments for U- 
statistics: 



Lemma 1. Consider an arbitrary family of integrable kernels /li : Si x 
• • • X Srf — > M, |i| < n. For any p>l we have 



|i|<n. 



<2' 



|i|<n. 



Proof. For d = 1, the statement of the lemma is the classical sym- 
metrization inequality for sums of independent random variables. Now, we 
use induction with respect to d. To simplify the notation let Ttd-ihi denote 
the proper Hoeffding's projection of /ii treated as a function of X2,---,Xci, 
with the first coordinate fixed, that is 

7rd-ihi{x) = 4i X ((5^.2 - P^(2)) X • • • X {6^^ - P^(d))/ii. 

Assume now that the lemma is true for all kernels of degree smaller than 
d. Consider (X^ )ieN,k<d, an independent copy of {X^ )i£N,k<d and denote 



R. ADAMCZAK AND R. LATALA 



by El integration with respect to X^^' . Then, the complete degeneracy of 
vTrf/ii and Jensen's inequahty yield 



El 



|i|<n 



:El 



|i|<n 



<EiEi 



:ElEl 



:ElEl 



Y^inMx^\...,xl^^)-.MxS\x^:\...,xl^^)) 

|i|<n 



Y^e^(.MxS\...,X^^)-nMxS\xS\...,X^^)) 

|i|<n 



j:<'(j^^-Mxi:\...,x^:^) 

|i|<n 



-7rrf_i/ii(A.^ ,^i2 '■•■'^id )) 
so, using the triangle inequality, we obtain 



|i|<n 



<2 



E 4r*^-i/^i(x? 



dcc^ 



i|<n 



Now, the Fubini theorem, together with the induction assumption applied 
to the family of kernels /i(J2^ .^i^)(x2, . . . ,Xrf) =J2h<n4i}T'iiXil,X2,...,Xd) 
for fixed values of X^^>,e^^' , proves the lemma. D 



We will also use the classical theorem due to Hoeffding, giving a decom- 
position of a [/-statistic into sum of uncorrelated, canonical [/-statistics of 
different orders, mentioned at the beginning of this paragraph. 

Lemma 2 (Hoeffding's decomposition; see, e.g. [3], page 137). For h-.T,"^ — 
M, symmetric in its entries denote 

{n-dy. 



Un{h) 



n\ 



EMXi). 



16/^ 



Then 



Un{h) = Y.(t)Un{^kh). 



THE LIL FOR CANONICAL [/-STATISTICS 7 

4.2. Moment and tail estimates for canonical U -statistics. We will now 
present a version of sharp moment estimates for canonical ^/-statistics, 
proved in [1] (actually as we will not need these results in the whole general- 
ity, we will state only a simplified corollary, adapted to our purposes, which 
follows immediately from Theorem 6 there). 

First let us introduce some quantities, which will appear in the moment 
estimates. 



Definition 4. For any canonical kernel /i:S'^ 
{ Ji , . . . , Jfc} G Vi^ define the norm 



and each J 



l>7:=ll^ll>7,oo = sup<^E 



h{X)\{h{Xj^) 



j=i 



■Mfi{Xj^f<l,i = l,. 



Thus \\h\\j is the norm of h viewed as a fe-linear functional acting on 
the space L^ {Xj^ ) x • • • x L^ {^Jk ) ' where L^ (Xj^ ) is the space of all square 
integrable random variables, measurable with respect to a{Xj^), the a-field 
generated by XJ^. In particular \\h\\i^ = (Kh^Y'"^ and ||/i||{i}...{d} is the norm 
of h seen as a kernel of a d-linear functional. 

We have the following (cf. [1], Theorem 6) 



Theorem 2. There exist constants L^, such that for all canonical ker- 
nels /i : S*^ ^ M andp>2, 
p 



E 



|i|<n 



<Ll 



n 



dp/2 



^ pPdeg{J)/2||^||P 



J 



J^-Pl, 



+ E nP#'/V^''+*''^/'E,cmax(E,/i(Xf-)2)W2 



Remark. Note that (E//i(Xf'^'=)2)P/2 depends only on Xj^^, so the ex- 
pression maxi^c(E7/i(Xf'''^)^)P/^ in the above inequality is well defined. 

Theorem 2 implies the following theorem. 



Theorem 3. There exist constants L^, such that for all hounded, canon- 
ical kernels h:Tr ^W and t > 0, 



|i|<n 



< Lrf exp 



>t 



^ ( ■ ( 
mm 

Ld XJ'^'Pi, \ 



n 



d/2\ 



\J 



2/dcg(J) 



R. ADAMCZAK AND R. LATALA 

t 
A mm 



lci^\n#^/mEih'^y/^\ 



2/{d+#n 



Remark. We would like to stress that Theorem 3 has been obtained 
from Theorem 2 by means of the Chebyshev inequality only. Therefore, the 
same tail estimates hold for random variables whose moments are dominated 
by moments of corresponding [/-statistics, which together with Lemma 1 
yields the following. 

Theorem 4. There exist constants L^, such that for all bounded kernels 



/i:S° 



and all t>0, 

\i\<n 



>t 



< Ld exp 



K 



mm 



t 



Amin 



2/dcg(>7) 



^ -.2/{d+#n 



4.3. Moment and tail estimates for Rademacher chaoses. 



Lemma 3. Let {ai)^^jd be a d-indexed array of real numbers. Let us 
consider a random variable 

d 



S:-- 



|i|<n 

Moreover, for any partition J" = { Ji, . . . , J^} G Vi^ let us define 



E^iR^r 

i|<n fc=l 



Jij||j,p:=sup^ 



E «i n "i", 

lil<n fc=l 






V. 



"^max J^ £-/n 



EK 

loJ,. 



(fc)N2 



<l,/c=l, 



,m 



where oj^ = Jfc\{max J^} (here X^i^ Oi = ca)- Then, for all p > 1, 

"[0.i)\\j,p- 



\s\\,>- E 



In particular for some constant Cd, 



{s>cd E 



^iWJJ>Cd/\e"P. 



THE LIL FOR CANONICAL [/-STATISTICS 



Proof. We will use induction with respect to d. For d = l the inequal- 
ities of the lemma have been proved in [10], for d = 2 in [14] (as a part of 
much sharper two-sided inequalities). Let us thus assume that the moment 
estimate holds for chaoses of order smaller than d>3. 

First, consider the partition J' = {Id}- We have 



E4 






d-l 



E^^n 



>Erf 



«d 



k=i 



d-l 



E«in 



'Ik 



Sk) 






fc=i 



1/2 



E<ME«? 



>;^^sup|^a,J ^ afj :5Ial<P,|ai|<lL 



where the first inequality follows from Jensen's inequality, the second one 
from hypercontr activity of Rademacher chaos (see [3], Theorem 3.2.5, page 
115) and the contraction principle for Rademacher averages (see, for in- 
stance, [16], Theorem 4.4, page 95), whereas the third one follows from the 
induction assumption. 
It remains to show that 

1/2 
I V- / V- 9\ 

sup< 



E«^.(E «i) ^E4 <vM^\<l^ > ||(ai)|||/a,P- 

> id Vir_, , / id J 



Let thus (7i) be a d-indexed matrix, such that J2i li ^ P^ J2ir it — ^ ^^^ 

d — 1 

all id- Then 



E^i^i 



<ENN<EfE7?) (e< 

<supi^aiJ^aN :^ 

l' id Vi/j , / id 



1/2 



oti, <vMi\ < 1 



Let now J' = {Ji,. . . , Jm}, m>2. We have 



\S\\p>j 



E 



d-#Ji 



Ji 






(fc) 



'^d\Jl 



p\ 1/p 



:/\{^i},p^ 



10 R. ADAMCZAK AND R. LATALA 

>7 ^^ll(«i)ll!r,p> 

by the induction assumption and Jensen's inequality. D 

4.4. Basic consequences of the integrability condition. Now we would like 
to present some basic facts, following from the integrability condition E(/i^ A 
u) = C'((loglogti)'^~^), which is necessary for the LIL for [/-statistics of order 
d, as proved by Gine and Zhang [5]; cf. Lemma 7 below. 

Lemma 4. IfE{h^ Au) = 0{{loglogu)'^-'^) then for I C I^, I y^ 0, Id and 
a>0, 

oo oo 

^ ^ 2'+#^'"P/c(E/(/i2 A 2'^") > 22'+#^'"log'^n) < cx). 

1=0 n=3 

As a consequence, for k>0, 

^2#^'"(logn)-¥/c(E7(/i2 A 22"'^) > 2#^'"(log?i)'^-'=) < oo. 



Proof. For fixed / and k we have 

Y, 2'+#^'"P/c(E/(/i2 A 2"") > 22'+#^'"log'^n) 

2'=<logn<2fc+i 

< J2 2'+*^'"P/c (E/ {h^ A 2"^"'^' ) > 22'+#^""+'^'=) 

2*=<logn<2*=+l 



<2'E7cy2#^'"l^ , , 2fe+i 



< 2'E/c 



(fc2A2<"='^ )>22i+#/'=n+dfe} 



2 A oae^'^^Sl /'1^„„„2'=+i\d-l 



■ E/(/l^A2'*^ ) 

22i+dfc 



<2-'K^^°^ )" 



2dfc 



/,>/log'' '« , o-fc 



<2''^I^^I^ + 2 



with K depending only on h (recall the convention explained in Section 2), 
which proves the first part of the lemma. To obtain the other inequality, it is 
enough to make an approximate change of variable 2^ (logm)~ ~ 2* 
and use the convergence of the inner sum for / = in the first inequality, for 
a>2d. D 

Lemma 5. //E(/i2 An) = ©((loglogn)^) then 



THE LIL FOR CANONICAL [/-STATISTICS 



11 



Proof. Indeed, since P(|/i| >u)< /^ ('°s'°|") ^ we have for sufficiently 



large s, 



fc=0 fc=0 



2i^E 



(loglog2*^s)^ ^^/(loglogs)/3 



fe=0 



2''i 



O 



D 



Lemma 6. //E(/i2 An) = C'((loglogn)^) then 



E 



|/.p 



(LL|/.|r 



< oo 



for each e > 0. 

Proof. For large n, 

\h\' . 



E 



„2"+l- 



<K 



E(|/i|^A2 



,n + l 



(loglog|/l|)/3+s {22^"<|h|<22^ ^ }- 2"(/3+^) 

= K2^2-"^ 



<if 



2(n+l)/3 

2"(/3+£) 



D 



5. The equivalence of several LIL statements. We will now state general 
results on the correspondence of the LIL for various kinds of [/-statistics (as 
defined in Section 2) based on the same kernel, that we will use extensively 
in the sequel. Let us start with the following lemma, proved in [5]. 

Lemma 7. Let /i : S'^ — > M be a symmetric function. There exist constants 
Ld, such that if 



(1) 



lim sup ■ 



1 



n^oo (nloglogn)'^/^ 
then 

oo 

(2) E 

n=l 

for D = LdC. Moreover (2) implies 
(3) 



E MXi; 



< C a.s.. 



E ^'''Mxf 

|i|<2" 



>I)2"'^/2log'^/2n <oo 



hm sup ,, , _ ,^^1 < LdD 



(log log u 



\d~l 



12 



R. ADAMCZAK AND R. LATALA 



Lemma 8. For a symmetric function h:Tr 
lent to the decoupled LIL 



(4) 



lim sup 



1 



(n log log n)'^/^ 






dcc^ 



the LIL (1) is equiva- 



< D a.s., 



meaning that (1) implies (4) with D = L^C, and conversely (4) implies (1) 
with C = LfiD . 



Proof. We can equivalently write (1) as 

1 



lim P sup^ , 

fc^oo \„>fc (nloglogn)'*/^ 






>C + e] =0, 



for all e > 0, which can be rewritten as 



(5) 



lim I 

fc— >CXD 



E hiM'^O 

|i|<CXD 



>C + e]=0, 



where for i, A; G N, /ij^^ is an /°° -valued kernel defined as 

h h h 



h 



i,k 



(/tloglogfc)'^/2 ' {{k + l)loglog(fc + l))^/2 ' ■ ■ ■ ' (nloglogn)'^/2 ' ' ' ' 
for i<k and 

h 



hi,k= f 0, ...,0, 



(iloglogi)'^/^ ' 



h 



h 



((i + 1) log log(i + l))'^/2 ' ' (n log log n)"'/2 ' 

otherwise. Now the decoupling inequalities by de la Peha and Montgomery- 
Smith (see [4]) show that (5) is up to constant equivalent to its decoupled 
version, which is equivalent to (4). D 



Lemma 9. There exists a universal constant L < oo, such that for any 
kernel /i : Si x • • • x S^ ^ M and variables {X^ )ij like in Definition 3, we 
have 



max 

, Li Kn 



E MX? 



dcc^ 



i-ik<jk,k=l,. 



>t\<L" 



E ^(xf^^) 



i|<n 



>t/L° 



THE LIL FOR CANONICAL [/-STATISTICS 



13 



Proof. We will prove by induction with respect to d a stronger state- 
ment, namely the inequality in question for Banach space valued [/-statistics, 
with the absolute value replaced by the norm. For d = 1, it is a result by 
Montgomery-Smith [17]. Assume therefore that the statement holds for ker- 
nels of degree smaller than d and consider a kernel h:Ti^ ^ B, for some Ba- 
nach space B. Then, conditioning on X^'^' , applying the induction assump- 
tion to 1^{B) and g(xi, . . . ,Xd-i) = iJ2ia<iKxi, ■ ■ ■ ,Xd~i,Xyf) -l < n) and 
finally using the Pubini theorem, we obtain 



P max 
VlJl<" 



E MX? 

i: Jfc<ifc,A:=l,.--,rf 



dec^ 



>t 



B 



<L 



d-lj 



max 



d-i 



E Hxfn > t/L 

\i\<n:ia<j B / 

Now it is enough to apply the result by Montgomery-Smith, conditionally 

on (X«,...,X(^-i)). □ 



Corollary 1. Consider a kernel /i: Si x • • • x S^ 
variables [X^ )ij like in Definition 3 and a> 0. If 



an array of 



then 



E' 

n=l 



limsup 



E Mxf^^) 



|i|<2" 



1 



>C2"°log"n <cx). 



(n log log n) 



EMx? 



dec^ 



i <n 



< LdnC 



a.s. 



Proof. We have for < L* < oo 
1 



Vn>Ar (nloglogn)" 



< 



sup 



EMx? 

|i|<n 

max 



dccN 



>D 



Lr, 



fc>LlogAf/log2j2'=-l<n<2'= (2*^logA:)^ 



< E 

A: > [log AT/ log 2 J 



max 



^2fe-i<n<2fe (2'=log/c)^ 

SO the result follows from Lemma 9. D 



E hi^f"') 

\i\<n 

E H^fn 

i|<n 



>D 



>D 



To prove further statements concerning the equivalence of various types 
of the LIL, we will have to show that the contribution to a decoupled U- 
statistics from the "diagonal," that is from the sum over multiindices i ^ /„ 
is negligible. One of our tools will be the following. 



14 R. ADAMCZAK AND R. LATALA 

Lemma 10. ///i:S^^R is canonical and satisfies 
W.{h^ ^u) = 0{{\og\oguf), 
for Sonne j3, then 



(6) 



lim sup 



(n log log n)'^/^ 



|i|<n 



decN 







a.s. 



Proof. We will decompose the diagonal into several sums, depending 
on the "level sets" of the multiindex i. For J G Vj^ let Aj[n) be the set of 
all |i| < n such that the index i is constant on all J ^ J . Let us notice that 
the contribution to the sum in (6) from i G Aj{n) that is 



dec\ 



Uj{n):= J2 MX[ 
ieAj(n) 

can be treated as a canonical decoupled [/-statistic of order deg J if we only 
treat the variables X^*"^ as one variable for any J (z J . 

Let us now denote for j < k, j, k G Id, Ajk = {i : |i| < n, ij = i^} and A = 
{(i)^) ^ -^J :j < ^}- From the inclusion-exclusion formula we get for every 
|i| < n, 



'-{3j^feij=ife} 



Hence we have 



U{j,fc)gA'^j'= 



if) 

E E ( 

1=1 (ji,fci),...,(i,,fc,)eA 



-ly-'iA 



Jlk 



n---nA 



hh ' 



E MXf-)= E ^jUj{n) 
\i\<n J'^'Pid 



-^j^k^j — ^k 



dcgj<d 



for some numbers aj, whose absolute values are bounded by a constant, 
depending only on d. Since the number of summands on the right-hand side 
does not depend on n either, it is enough to prove that 



lim sup 



\Ujin)\ 



oo (nloglogn)'^/^ 







for all J such that degj^ < d. 

Therefore, by Corollary 1, it is enough to prove that for deg^ < d, 



(7) 



El 

n=l 



E ^dcgjH'Xi'''') 

ieAj{2") 



>C2"'^/2iQgd/2^ <oo 



THE LIL FOR CANONICAL [/-STATISTICS 



15 



for any C > 0. (Here TTdcgj denotes the Hoeffding projection of the kernel 
h considered a [/-statistics of order degj', as mentioned above. We have 
thus actually TTdegjh = h.) It is relatively easy to prove (7), as the number 
of summands is of much smaller order than 2""^. Obviously ^Aj[2"') = 
2ndegj < 2"('^-i). Let / be any subset of Id, such that for any j£j, #(/n 
J) = 1. For hn = /il{|/i|>2"di we have by Lemma 5 



E 



E 



dccr /-"vdcCN 



— I "I — 2na 2" 



and the convergence of (7) with h replaced by /i„ follows easily from Lemma 
1 and the Chebyshev inequality. On the other hand, for hn = hln^^2"<i} we 
have 



ElEi 



^dec 






docM2 



C22ndlogd^ 



^ #Aj{2^)Ehl ^ 2«('^-i)E/i2 



C22"^log° 



n 



(^22ndlog« 



n 



<KC7-22-"log' 



.l3-d 



n, 



which (again via Lemma 1 and the Chebyshev inequality) allows us to finish 
the proof. D 



Corollary 2. The randomized decoupled LIL 



(8) 



1 



limsup— , 

n.-»oo (n log log n)"/^ 



^ ef^"/i(Xf^") 

|i|<n 



<c 



is equivalent to (2), meaning that if (8) holds then so does (2) with D = L^C 
and (2) implies (8) with C = LdD. 

Proof. Implication (2) =^ (8) follows from Corollary 1. To get (2) from 
(8), it is enough to show that E(/i^ A u) = ©((loglogn)*^), since then by 
Lemma 10 we can skip the diagonal and by Lemma 8 undecouple to obtain 



limsup- 



1 






+00 (nloglogn)^/^ 
which gives (2) by Lemma 7 [note that if {£i)i, (e 



< oo, 



1, . . . ,d, are inde- 



pendent Rademacher sequences, then so are {siel )i]. This is, however, easy 
by a simple modification of arguments from [7], which we will present here 
for the sake of completeness. Notice that by the Paley-Zygmund inequality 
and hypercontractivity of Rademacher chaos, we have 

1/2n 

(9) Pj 5]ef-/i(Xf-) 

V |i|<n 



,.,.(g^„x,.,) ),i_. 



16 R. ADAMCZAK AND R. LATALA 

Moreover if E(/i^ A n) > 1, then 



\|i|<n 



An) 



Y^Y. E nn^fn' a n] [/.(xf-)^ a n] 

IQId\i\<n lj|<n 

{k.ik=jk}=I 



n) 



< n2'^[E(/i2 A n)]2 + (2^ - l)n^'^E{h^ A n) 



< 2'^n2^[E(/i2 A n)]2 = 2°^ E ^ {h{X.f''^f A n) 

V |i|<n / 

Thus again by Paley-Zygniund, we have 

V|i|<n 2 / ^"^ 

which together with (9) yields 



.dec ^/'"V" dec 
i|<n 
2 A ^^ — /'0/'/'l^„1^„^Mi 



> Z^^n'^/y E(/i2 An)) > J-, 



which gives E(/i A n) = ©((loglogn) ), since by assumption the sequence 

1 



(nloglogn)'^/^ 
is stochastically bounded. D 



E ^f''^(^i 



i|<n 



Corollary 3. For a symmetric, canonical kernel h:Yl 
(1) is equivalent to the decoupled LIL ^^with diagonal" 



the LIL 



(10) 



limsup 



(n log log n)*^/-^ 



E ^(x'^') 



i <n 



<L» 



a.s. 



again meaning that there are constants L^ such that if (1) holds for some 
D then so does (10) for D = L^C, and conversely, (10) implies (1) for 
C = LdD. 

Proof. To show that (1) implies (10) it is enough to use Lemma 8 and 
then Lemma 10 to add the diagonal (the integrability condition on h follows 
from Lemma 7). 



THE LIL FOR CANONICAL [/-STATISTICS 



17 



To obtain the converse implication, it is enough to prove E(/i(X)^ Au) = 
0{{\oglogu)'^) since then we are allowed to delete the diagonal by means of 
Lemma 10 and use Lemma 8 to undecouple the LIL. 

From the assumption it follows that for every e > and sufficiently large 
n, 



E H^f''") 



\i\<n 



>(Z) + l)n'^/2loglog'^/2^J <e. 



Now, by Lemma 9, for arbitrary subsets Ai 



,AhCI„ 






dec> 



>L'^{D + l)n'^/^ log log'^/2 ^ j < ^d^_ 



-(i) 



Moreover, for fixed values of (e^ ) , the expression J2\i\<n Ci ^(X; ) is a sum 

of 2'^ expressions of the form ^J2ieAix---xAa ^(Xf*"^), where Ak = {i: 4 = 
±1}. Thus, using the above estimate conditionally, together with the Fubini 
theorem, we get for sufficiently large n, 

E ef'^'/iCXf'^^) > 2'^L'^{D + l)n'^/^ loglog'^/^ ^ j < 2'^L'^e. 

\i\<n J 

Now we can finish just like in Corollary 2 by applying the Paley-Zygmund 
inequality and hypercontractive estimates for chaoses. D 

6. The canonical decoupled case. Before we state the necessary and suf- 
ficient conditions for the LIL, let us notice that the integrability condition 
E(/i^ Au) = ©((loglogn)''"^) can be equivalently expressed in the language 
of the II • Wj^u norms (see Section 3 for the definition). More precisely, we 
have the following. 



Lemma 11 

lim sup 



For any function h we have 
E(/i2An))V2 



(loglogn)('^-l)/2 



: lim sup 



\{Id},u 



(loglogn)('^-l)/2 



Proof. Let us denote the limsup on the right-hand side by a, and the 
other one by b. Let us also assume without loss of generality that h>0. We 
will first prove that a<b. Indeed, either E(/i^ A u) < 1 or we can use 

hAy/u 

■~ (E(/i2A'u))^/^ 

as a test function in the definition of ||/i||{/^},u5 thus obtaining for ti > 1 



18 R. ADAMCZAK AND R. LATALA 

SO we have (E(/i^ A u))^''^ < 1 + ||/i||{/^},u) which immediately yields a < b. 
To prove the other inequality, let us notice that if a < co, then for u large 
enough and any / with ||/||2 < 1, ||/||oo < u Lemma 5 gives 



Ehf < JEhn,h<^2. + uE\h\lsh>u- 



^ (Tfffh^ ^ 4^a/2^ -^(loglogn^)'^^^ 
< [E[n f\u )) ' +u 5 , 



which gives h<a since 



log log n^ 
lim - — = 1. 

u^oo log log U 



D 



Theorem 5. Let h he a canonical symmetric kernel in d variables. Then 
the decoupled LIL 



(11) limsup 



n'^/2(loglogn)'^/2 



|i|<n 



dccN 



< C a.s. 



holds if and only if for all J G Vj^ , 



(12) limsup- — x(rf_deg7-)/2 ll^ll^."^^' 

M^oo (log log U)^^ <leg^J/^ 

that is, if (11) holds for some C then (12) is satisfied for D = L^C and 
conversely, (12) implies (11) with C = LdD. 

Proof. 

Necessity. Let us first prove the following. 

Lemma 12. Let g:!!^ ^W be a square integrable function. Then 
Var [ E 9(Xf'==) J < (2'^ - l)n^'^^^Eg{Xf . 

\|i|<n / 

Proof. We have 



Var('$:ff(Xf-)) 

\|i|<n / 



:E('E(5(Xf-)-E5(Xf-))) 

\|i|<n / 



THE LIL FOR CANONICAL [/-STATISTICS 19 

= E E E IE[(5(Xf-) - Eg(Xf-))(5(Xf ^) - Eff(Xf =))] 

IQId\i\<n \]\<n: 

{k:ik=jk}=I 

= E E E IE[(ff(Xf-)-E5(Xf-))(5(Xf^)-Eg(Xf^))] 

-fC/d,/^0|i|<n |j|<n: 

{k:ik=jk}=I 

ICIa,I^0 □ 

Moving to the proof of (12), let us first note that from Corollary 3 and 
Lemma 7, the series (2) is convergent and (3) holds. Since lim„^ooZ]fc=n i = 
log 2, there exists Nq, such that for all N > Nq, there exists N <n < 2N, 
satisfying 



(13) 



I lOn 



J2 ef'^/i(Xf°^) 

|i|<2" 

Let us thus fix A^ > A'^o and consider n as above. Let J = { Ji, . . . , Jfc} G 
Vl^. Let us also fix functions fj : S*"^J — > M, j = 1, . . . , A;, such that 

ll/i(^J,)l|2<l, 
||/,(Xj^OI|oo<2"/(2'=+l). 

The Chebyshev inequality gives 

(14) f( J2 /,(Xfj^^)2logn<10-2'^2#-^^"logn]>l--i^. 

jj I- 

Moreover, for sufficiently large N, 

V- 1 ^,^dec^2 1 2"#o^^22"/(2'=+l)log?l 

|ioJjl<2" 

22n/(2fc+l)iQg^ 

- 2" ~ ■ 

Without loss of generality we may assume that the sequences {X^)ij and 
{^i )i,j are defined as coordinates of a product probability space. If for each 
j = l,...,k we denote the set from (14) by A^, we have P(nj=i ^fc) > 0.9. 
Recall now Lemma 3. On ni=i^fc we can estimate the || • Hj-w^ norms of 
the matrix (/i(Xf°'^))|i|<2n by using the test sequences 

/,(Xf-)Vb^ 



a; 



lQl/22d/22n#J,/2- 



20 R. ADAMCZAK AND R. LATALA 

Therefore, with probabihty at least 0.9, we have 



(15) 



\\{h{Xr)h<24j,lo,n 



> 



(logn)'^/^ 



|i|<2" i=l 



2dk/2iQk/22dn/2 



y: HxfnuMK 

|i|<2" i=l 



dec^ 



Our aim is now to further bound from below the right-hand side of the 
above inequality, to have, via Lemma 3, control from below on the condi- 
tional tail probability of I]|i|<2" £f°^h{X.f°^), given the sample {X^ ). 

From now on let us assume that 

k 

(16) EhiX)l[f,iXj^) >1. 

i=i 

By Corollary 3 and Lemma 7 we have K{h'^ Au) = ©((loglogu) ). Thus, 
the Markov inequality and Lemma 5 give 

'^ 2"'^|E/inLi/il\ 



(17) 



2^ ^(^i°'')l{|h{Xf<='=)|>2"} 11 fjO^i 
|i|<2" ' i=l 

^^2-''iuU\\fj\\o-)-nh\i{\h\>2-} 



<4 



dccN 



> 





2"^iE/inf=i/ii 


2' 


^'=/(2^^+l)E|/.|l{|,|>2«} 




\^hUUfj\ 


K 


{lognf-' 



<4:K 

Let now hn = hlnu<^2"}- By the Chebyshev inequality. Lemma 12 and (3), 

k k ^nd 

|i|<2" i=l ^ j=l 

Var(E|i|<2" /in(Xf-) nj=i /,(Xf-)) 



Qnd 

- 5 


k 


E/i„, n fj 



<25- 



22-'i|E/i„nLi/iP 



(2'^- l)2"(2'i-i) 

(18 <25^^- ^-r -E 

- 22"'i|E/i„n'=i/^f 



hn n /i 



< 25(2'' - 1 



THE LIL FOR CANONICAL [/-STATISTICS 

22nk/{2k+l)-^f^2 



21 



2"iE/i,,n-=i/, 



< 25K(2'^ - 1] 



log'^-i n 



2-/(2*^+1) iE/i„nJ=i/.f 



Let us also notice that for large n, by (3), Lemma 5 and (16), 



^hn n fj 



j=l 



(19) 



> 



> 



5 
> - 



Eh n fj 

i=i 

k 

EhUfj 
i=i 

k 

EhY[f, 



E/il 



{i/ii>2"} n /?■ 



,n,fc/(2fc+l) y Pog^) 



d-1 



5 
> -. 



Inequalities (17), (18) and (19) imply, that for large n with probability at 
least 0.9 we have 



y: HxfnuM^i 



dec^ 



|i|<2" 



> 



i=i 



y: /i„(xf-)n/,(xf 



dec^ 



i <2" 



j=l 



7^ ^(^i'''')l{|h(Xf°<=)|>2"} 11 /i(^i 
|i|<2" ' i=l 



dec> 



> 2"'' I - 



Ehn n /i 



>2 



nd 



4 5 

5 " 8 



E/^n/. 



EhYlf, 



E/^n/. 



> 



2' 



nd 



E/^n/. 



Together with (15) this yields that for large n with probability at least 
0.8, 



2nd/2 iQgfc/2 ^ 
i^|i|<2"llj,logn ^ 4.2^^/2 20^/2 



> 



EhY[f, 



i=i 



22 R. ADAMCZAK AND R. LATALA 

Thus, by Lemma 3, for large n 



|i|<2" 



>Cd 



2nd/2 iQgfc/2 



n 



4^ . 2dk/2lQk/2 



Ehllf, 



i=i 



> 



lOn 



which together with (13) gives 



Ehllf, 



i=i 



Cd 



In particular for sufficiently large N, for arbitrary functions fj : S* J 
j = 1, . . . ,k, such that 



we have 



EhUfj 



i=i 



4.2dfe/2io'=/2 



<idC 



Cd 



■log('^-'=)/2n<LrfClog('^-'=)/2iV. 



Thus, for large u {u>uq) 



sup< 



EhiX)Y[f,iXj^ 
<L,(loglogt.)('^-^)/2, 



:||/,(XjJ||2<l,||/,(Xj^. 



< ui/{2fc+i) 



and so 



sup<^ 






:||/j(XjJ||2<l,||/,(Xj^. 



<n 



<Ld(loglogn)('^-'^)/2, 



for all u> u, 



l/(2fc+l) 
' 



which proves the necessity part of the theorem. 



Sufficiency. The proof consists of several truncation arguments. In the 
first part, until the || • \\j^u norms come into play, we follow the lines of the 
proof of the special case d = 2, presented in [8], with some modifications. At 
each step we will show that 



(20) 



El 

n=l 



E ^dhni^fn 

|i|<2" 



>C2"'^/2log^/2n <oo, 



with /i„ = hlA„ for some sequence of sets An. 



THE LIL FOR CANONICAL [/-STATISTICS 23 

Step 1. Inequality (20) holds for any C > if 

An^{x:h\x)>2'"^log'^n}. 

We have, by the Chebyshev inequality and the inequality E|7r£;/i„| < 2'^E|/i„| 
(which follows directly from the definition of ira or may be considered a triv- 
ial case of Lemma 1), 



El 



< 



|i|<2" 



E 



decN 



> C'2"'^/2 iQgd/2 ^ 

]E|E|i|<2"^rffen(Xf"^)| 
C2^d/2 logrf/2 ^ 

2" E|/i|l{|/j|>2nd/2logd/2 



<2''E ^■™""'" 



C2nd/2 logrf/2 ^ 
2nd/2 

log'^/^ ^ 



2'^C7 lE|/l|^^— ^7— -l^|^|>2nd/2l„gd/2„} 



|/l|2 

where the last inequality follows from Lemma 6, Lemma 11 and condition 
(12) for J = {/rf}. 

Step 2. Inequality (20) holds for any C > if 

^n ^ {x G S"^ : h'^ix) < 22"'^, 3i^0jJEi{h'^ A 2^"'^) > 2#^'" log'^n}. 
By Lemma 1 and the Chebyshev inequality, it is enough to prove that 

E|E|i|<2>^ef^^/^n(Xf"^)| _^ 

^ 2"'^/2 log'^/2 n ^°°' 

The set An can be written as 

U MI), 

where the sets An{I) are pairwise disjoint and 

An{I) C {x:h^{x) < 22"'^,E/(/i2 A22"'^) > 2#^'"log'^n}. 
Therefore, it suffices to prove that 

^E|E|i|<2"ef°^/i(xf°^)U.(/)(xf^')l 

(21) 2^ = 777^ <00. 



2nd/2 logd/2 



n 



24 



R. ADAMCZAK AND R. LATALA 



Let for I G N, 

An,i{I):={x:h\x)<2'^^, 

22'+2+#^'"log'^n > E/(/i2 A 22"^) > 22'+#^'" log^ n} n An{I). 

Then KlAnii) = Ei^o^n,«, where hn,i := /inlyi„,K/)- 
We have 



E 



E ef^n,KX? 



dec^ 



|i|<2" 



|ijc|<2" 



|i/l<2" 



|i/c|<2" V 



2\ 1/2 



\il\<2" / 

<2(#^^+#^/2)"Ejc(E,|/i„,;|2)i/2 
Therefore, to get (21), it is enough to show that 

oo 
£^2'+#^-"Pjc(E,(^' A22"'^) > 22'+#^^"log'^n) < oo. 

1=0 n 

But this is just the statement of Lemma 4 for o = 2d. 
Step 3. Inequahty (20) holds for any C > if 

AnC{x: 2"'^n-2'^ < /i^ (x) < 2""' log"^ n 

and y 1^0,1, Ej{h^ A 2^''^) < 2#^'"log'^n}. 
By Lemma 1 and the Chebyshev inequahty, it is enough to show that 



E- 



n E\i\<2'^erK{ xf 

J2d, 



•-AecwA 



< OO. 



„ 22""! log- n 

The Khintchine inequality for Rademacher chaoses gives 

4 / \ 2 

E ef^^/in(Xf«=) 

|i|<2" 

= E E E E/.„(xf-)2/,„(x 

/C7^|i|<2" |j|<2": 

{k-ik=jk}=I 



Lf^ 



<e('e Ko^n'] 

V|i|<2" / 



decN2 



THE LIL FOR CANONICAL [/-STATISTICS 25 

< Y, 2"^2"(^-#^)e[/i„(X)2./i„(X(/))2], 
iQld 

where X = (Xi, . . . ,Xrf) and X(/) = ((X^ie/, (Xp^)ie/c). 

To prove the statement of this step it thus suffices to show that for / C /^ 
we have 

2-n#i 
n log n 

(a) I = Id- Then 

by Lemma 6. 

(b) I ^ IdT^- Let us denote by K[,Kic,Kj<: respectively the expectation 
with respect to (Xj)jg7, {Xi)i^jc and (X^- )j6/c. Let also h, hn stand respec- 
tively for /i(X(/)), /i„(X(/)). Then 






;^2"#^log2"'n 

^,2 . ^,2-, 



Eihl-hll 



2'^#-flog2^n 

1 



<2E/.2/,2i X^ 



< L,E/.^/.-l^|,|<|^|^ 



{|/i|<|/i|}Z^ 2"#'flog2'^n^'^^"^'''''^^''"')-^*''"^°^ "'''''-^''"'*1 
1 
2"#Jbg^''n 
1 



<2Eh h I{|fe|<|/,|}ZJ^„#/, 2d^{E,c(h2Aft2)<2#^"log''n,h2<22nd} 



(E7c(/i2A/l2))(LL|/l|)'^ 



LrfE/E/c/i^E/c/i^i 



{|/^l<|/^|}(]E^^(/j2A/j2))(LL|/i|)d 



/l2 

< LrfE = — < oo 

- {LL\h\y 



by Lemma 6. 



26 R. ADAMCZAK AND R. LATALA 



(c) 1 = 0. We have, 



Z^ l„„2d „ - -^ Z^ l„„d+l , 



(22) ~ ^ 

For M > let us now estimate #{n : 2"'^n-2'^ < M < 2"^(logn)'^}. Let 
nma.xyiT'^i^ denote the greatest and the smallest element of this set. Then 

logM 



rimin log 2 + log log nmin > 
nmax log 2 - 2 log Tlmax < 



d ' 

logM 



d ' 
hence 

(f^max - "■mill) log 2 < 2 log n^ax + log log Umm < 3 log rimax 

< L log logM. 
The right-hand side of (22) is thus bounded by 

by Lemma 6. 

Step 4. Inequality (20) holds for any C > if 

A C |x : /i2 < 2"'^n-2'^, V7^0,/,E/(/i2 A 22""') < 2#^'" log'^n, 

log^ n J 

The only difference between this step and the previous one is the proof 
of convergence in the case (c), as in the two other cases we were using only 
bounds from above on h"^ and Kj{h'^ A 2'^"''^), which are still valid. 

Let us notice, that 

IE/l„ < 22 ^(^ /\2 " )l|(i^3g„)_#/c^2-#.f<="E/(/i2A22"d)<(logn)d} 

ICIa,Ij^0,Ia 

< 2^ 2^ E/cE/(/l A2 " )l|(log„^d-fc<2-#I':n]E^(;,2A22ud)<(logn)d+l-fc} 

d+m" 

< Y. Y. 2#^'"(logn)'^+i-¥7c(E7(/i2A22"'>')>2#^'"(logn)'^-'=). 



THE LIL FOR CANONICAL [/-STATISTICS 



27 



Thus 



E 



•)2nd 



i^hi: 



22nd(lQgnyd 



< 



^E- 



E/i? 






(logn)'^+i 

< oo 
by Lemma 4. 

5te|3 5. Inequality (20) holds for some C < L^D if 



2#/'=n 



^„ = |x:/j2 < 2"'^n-2'^,V7^0,,, E,(/i' A 2^"'^) < ^-^ 



n 



This is the only part of the proof in which we use the assumptions on the 
II • IIj-^m norms of h for deg^T > 1. Our aim is to estimate ||/iri||j7 and then 
use Theorem 4. 

Let us note that we can assume that 

(23) D = 1 

[if Z) 7^ then we simply scale the function, otherwise (12) for J' = {{1},. . . , {d}} 
gives h = 0]. 

Let us thus consider J7 = { Ji, . . . , J^} G Vi^ and denote as usual X = 
{Xi, . . .,Xd), Xi = {Xi)i^i. Recah that 



|/i„||j7 = sup<E 



K{x)X{u{Xj^) 



i=l 



:E/2(XjJ<l 



In what follows, to simplify the already quite complicated notation, let 
us suppress the arguments of all the functions and write just h instead of 
h{X) and fi instead of fi{Xj-). 

Let us notice that if Kff < 1, i = 1,. . . ,k, then for each j = 1,. . . ,k and 
J C Jj by the Schwarz inequality applied conditionally to Xj.\j, 



E 



hnllfi^ 



i=l 



{Ej/2>a2} 



<E 



JjV 



E 



ijj\jy 



i=l 



1/2 



^Ej/2>a2}(JE(J,\J)c/l, 



2^1/2 
n) 



<E,,^,y[(Ej/|)l/2l^^^^,^^,^(E(^^.\^)./l2)V2] 



28 



R. ADAMCZAK AND R. LATALA 
< 2n#{J,\J)/2^-l_ 



This way we obtain 



\hn\\j < sup<E 



/inH/* 



i=l 



:||/i||2<l, 



(Ej/2)V2||^<2«#(M^)/2 for JC J,| 



(24) +^(2#^'-l) 



i=l 



< Ld + sup{E 



hnYlfi 



i=l 



:||/.||2<1, 



(Ej/f)V2||oo<2^#(^Ai)/2forJCjA 



Let us thus consider arbitrary /j, i = 1, . . . ,k, such that ||/i||2 < 1, 
||(Ej/2)V2||^ < 2"#{^>\^)/2 for J CJi (note that the latter condition means 
in particular that ||/i||oo < 2"#"''/2). 

We have, by assumptions (12) and (23) for large n, 



(25) 



E 



hllf^ 



i=l 



< 



J',2"'*/2 



<L<,log('^-^^S'^)/2^. 



For sufficiently large n, 



E 



hi 



||ft|>2nd/2„d} 



Un 



i=l 



< iE|^|imi>2-/^„^} n ll/dloo < i^2"'/^^S < 1 



i=l 



2nd/2^d 



where the second inequality follows from Lemma 5. 

Moreover, if we denote hn = |/i| A2'^°''P(ri°g"l), we get for K^h,!^ 0,ld, 



E 



hn[[fd{Eihl>2'^*l''n] 



1=1 



<Kr 



i^ihl)'/\E,hl>2-*'^n}]li^J.nif!)' 



/2 



i=l 



<J|2"#(^^n.=)/^E,4(E,/.^)^/^l^,^,.>,„,.„j 



i=l 






THE LIL FOR CANONICAL [/-STATISTICS 



29 



for large n. 

By the last three inequalities we obtain 



E 



/inH/' 



i=l 



< 



mllfi 



4 = 1 



+ 



E/iiA. n /* 



i=l 



<Ldlog('^-<^'^g'^)/2^ + E 



hUfi'^ 



{|h|>2"''/2n-'*} 



i=l 



+ E K 

ICId,I^0,Id 



^l{|/i(<2"d/2n-'«} 11 /«1{E7 



(/i2A22"'«)>2n#-r=(logn)-#-f'=} 



«=1 



< Lrflog('^-'^^g'^)/2 ^ ^ 1 ^ (E|/l|2l^2"<*/2n-^<|hl<2"^/2nn) 



1/2 



+ E E 



^n 11 /il{E^h2>2n#/=(iog„)-#/=} 
i=l 

<Lrflog('^-'^^S^)/2^ + 2''+ ^ dnil), 



I^Irl 



where 



dn{I) — ^E^nl{2"#-f'=n-i<Ejh2<2"#^''n} ^OT I ^ 0,ld, 

dn{0) =E/l l|2nd/2„-d<|/j|<2nd/2„d}. 

Using (24) we eventually obtain 

(26) \\K\\j<LAog^''~'''^'^y'n + Dn, 

where L>„ = E/c/^ dn{I)- 

This estimate will allow us to finish the proof by means of the following 

Lemma 13. For sufficiently large C = L^A and all J G Vi^, 



^exp 



Clog's/2 



n 



2/AcgJ 



< OO. 



Proof. Let us notice that for A; = 1, 2, . . . 

/ . ^ l{2"'*/2n-''<|h|<2"''/2n''} — -^d(^ + 1) l{|/i|<2ne'=+V2ed('=+i)} 

fc<logn<fc+l 



30 R. ADAMCZAK AND R. LATALA 

and 

2^ E//l„l|2n#/'=„-l<]E^^2<2n#/'=n} 

k<logn<k+l 

= 2^ ^^^efc+il{2"#-f'=n-l<Ej/i\_^^<2"#-f'^n} 

fc<log?i<fe+l 

< LaEihl,+,ik + 1) = Laik + l)Ej{h^ A 22'^^'+'), 

since for any numbers 1 < a,b < d and x > 0, the number of intervals of 
the form [2""n~ , 2""n ] with k < logn < A; + 1, containing x is smaher than 
Ld{k + 1). 

Integrating the above inequahties and using Lemma 11, assumption (12) 
for J' = {Id}, assumption (23) and the Cauchy-Schwarz inequahty we get 

y: Di<{2'^-i) Y. j:Mif<uk+ir. 

k<logn<k+l k<logn<k+lICId 

Thus 

#{n ■.k<logn<k + l, D,, > 1} < Ld{k + 1)*^ 
and therefore for C large enough (since D^ < L^ log*- ~ '' n) 

Clog'^'^n \2/dcg^N 



^exp 



<^exp(-(C/2A)2/d^g^logn) 

n 

^ // Clog'^/'^n \2/dcgj 

^i^i"'vl-A(l + L,)log(^-)/2nJ 

<^exp(-(C/2A)2/'i^g^logn) 

n 

+ LdYi^ + l)^exp(-(CM(l + Lrf))2/^^S'7fcVdeg^) < oo 



k 

for C = LrfA. D 



Going back to the proof of Step 5, let us notice that by Theorem 4 and 
(26), we have 



Y vrd/i„(Xf-) 

|i|<2" 



> C2"'^/2 log'^/2 



n 



THE LIL FOR CANONICAL [/-STATISTICS 



31 






^/C2"'^/2log'^/2 



n 



2/dcgJ 






<Ld ^ exp(L/ 



J&T^i. 



Clog's/2 



n 



2/id+#n 



2/dcgJ 



L,\og^^~^'^^^)/'n + Dn 



+ Ld^ex:p[L 



IQIh. 



--1 



C2"'^/2log'^/2 



n 



X 2/(d+#/'= 



Clog's/2 n \2/dcgJ 



+ L,5:exp(L,-ic2/('^+#^^)logn), 

so convergence of the series in (20) for C large enough {C = Ld = L^D) 
follows from Lemma 13. This completes the proof of Step 5. 

To prove sufficiency of (12), by Corollary 1 it is enough to show conver- 
gence of the series 



(27) 



El 



E M^i 



dec^ 



i <2" 



> Cl'^dn ^Qgd/2 



n 



for C = L^D. To this end for each n we simply decompose S into five disjoint 
sets A\, i = 1, . . . , 5, with A^ being a set of the form defined at the ith step 
above (which clearly can be done as the union of the sets from Steps 1-5 is 
the whole S). For C = L^D, from the triangle inequality and Steps 1-5, we 
get the convergence of the series 



E^ 



E ^dK^^f'^: 

|i|<2" 



> C2"°'/2 iQgd/2 



n 



which is exactly (27), since by the complete degeneracy tt^/i = h. D 

7. The undecoupled case. We are now ready to prove our main result. 

Proof of Theorem 1. Sufficiency follows from Corollary 3 and The- 
orem 5. To prove the necessity assume that (1) holds and observe that from 
Lemma 7 and Corollary 2, h satisfies the randomized decoupled LIL (8) 
and thus, by Theorem 5, the growth conditions on functions ||/i||j',« are 



32 



R. ADAMCZAK AND R. LATALA 



also satisfied [note that the || • \\j^u norms of the kernel h{Xi, . . . ,Xfi) and 
El- ■ ■edh{Xi,. . . ,X(i) are equal]. Thus, the only thing that remains to be 
proved is the complete degeneracy of h. The integrability condition (3) im- 
plies that E|7rrf/i|P < oo for all p < 2 and thus from the Marcinkiewicz type 
laws of large numbers for completely degenerate [/-statistics by Gine and 
Zinn [6] it follows that 

y^ ■Kdh{'K.\) -^ a.s. 



n' 



d/p 






as n ^ oo. Moreover, from the LIL, we have also 



n 



Lem^o-o 



d/p 



a.s. 



ieii 



Let us notice that by Hoeffding's decomposition (Lemma 2), 
5](/i(Xi)-7rd/i(Xi)) 



(28) 



'y^(d\ {n-ky. 

k=0 ^ 



ni 



n'. 



{n-d)\ 



E vrfc/i(Xj, , . . . , Xi J 



{n-d+1) Y. 9{Xi, 

ij^il for jj^l 



ijy^il for jjtl 



) ■ • ■ 7-^Jd-l)' 



where 



g{xi,...,Xd-i) 



1 



pryE5(2^a(i),---,a;^(d-i); 



where the sum is over all permutations of Id-i and 

a 



g{xi,...,Xd-i) = Y^ , 7rfc/i(xi,...,Xfc 



fc=o 



We thus obtain 

n-d + 1 



re' 



d/p 



Therefore 



22 9{Xi^,---,Xi^-i. 

Ji,...,id_i<n 
ijy^il for JT^l 



E 5(Xi) 

h,---,id-i<n 
ijy^il for j^l 



a.s. 



re 



d/p-i 



THE LIL FOR CANONICAL [/-STATISTICS 



33 



is stochastically bounded. Putting p = 2d/{d+ 1) we obtain the CLT normal- 
ization for [/-statistics of order d—1 (see for instance [3], Theorem 4.2.4) 
and from the results by Gine and Zinn ([7], Theorem 1, or [3], Theorem 
4.2.6) we get that g is canonical and "Kg^ < oo. Now the CLT for canonical 
[/-statistics yields that 



= 



a.s. 



and (28) for n = d gives 
h. D 



g{Xi,...,Xd-l) —yi a.a. 

h = TTdh, which proves the complete degeneracy of 



8. Final remarks. 



Remark. In Theorem 5 the necessary and sufficient conditions for the 
decoupled LIL were found, under an additional assumption that the kernel 
is canonical. We would like to remark that the canonicity actually follows 
from the decoupled LIL, similarly as in the proof of Theorem 5. The proof 
would however require developing "a decoupled counterpart" of all the limit 
theorems for [/-statistics (like CLT and Marcinkiewicz LLN), which would 
make it quite lengthy and would not involve genuinely new ideas. 



The cluster set. 
surely equal to 



When E/i^ < cxd, the limit set in the LIL (1) is almost 



{Eh{Xi, . . .,Xd)fiXi) ■ ■ ■ f{Xd):EfiXi) < 1} 

as is proven in [2]. In general this is not the case. For d = 2 it is known that 
the cluster set is an interval [8], whose end-points are known in some special 
cases [13]. In these special cases, the limsup turns out to be a relatively 
complicated function of the "deterministic" lim sup's appearing in the nasc's 
conditions. It is natural to conjecture that in general the limsup is also a 
function of these quantities. 

Now we would like to state the following. 

Theorem 6. The cluster set in the LIL (1) is an interval. 

Proof. It is enough to show that 



lim sup 



n^/2 log log'^/^ n (n - 1 ) '^/2 log log"'/^ (n - 1 ) 
which will follow if we prove that 

1 







a.s. 



lim sup - 

n— »oo n' 



d/2loglogd/2 



n 



E MXi) 







a.s. 



34 R. ADAMCZAK AND R. LATALA 

We can reduce the last statement to 



(29) 



E E 1 



E MXi; 



ieli,id=k 



><52"'^/2log'^/2n <oo 



for all 5 > 0. Let vf^-i stand for the Hoeffding projection with respect to 
the first d — 1 variables only. Then, the complete degeneracy of h, gives 
Ttd-ih = h, thus to get (29) it suffices to prove that 



E E ] 






> 



^2"d/2l d/2^ <00. 



We will now proceed similarly as in the first steps of the proof of Theorem 
5, that is we will prove the above convergence with h replaced by /i„ = hlA„ 
for suitable sets An. 

Step 1. 

^„ C {x G S"^ : /i2 (x) > 2"^ log'^ n} . 

Since for 2"-^ <k<2'\ #{i el^:id = k}< 2"('='-i) we can use the Cheby- 
shev inequality, exactly as in the first step of the proof of Theorem 5. 

Step 2. 

An C {x:h\x) < 2"'^log'^n,3,c/,_i,/^0 E,(/i' A 2^""') > 2#^^"log'^n}. 

Note that by the decoupling inequalities for the moments of [/-statistics 
(see, e.g., [3], Theorem 3.1.1) and Lemma 1 applied conditionally on X^, we 
have 



E 



Y^ TTd-lhCXi] 



i£lf.,ia=k 



<LdE 



E ^d~lh(^i 



dec^ 



iel^,id=k 



< 2'^~^LdE 



J2 ef'^hiXf""] 



Therefore if we define the sets An{I) and An^i{I) (for / C I^-i,! ^ 0) like 
in Step 2 of the proof of Theorem 5, it is enough to prove 



1 



" 2"-i<A,<2" ^& i=0 



EiE 



^ 6f^^/l„,KXi) 



i£l^,id=k 



< OO, 



where for fixed / the function /i„ ; are defined as in the proof of Theo- 
rem 5. But for each 2"~^ < k < 2",/ we have by a similar computation as 



THE LIL FOR CANONICAL [/-STATISTICS 



35 



there 



E 



Y, ef''K,i{X,) 



i£l^,id=k 



Thus 



2'^-l<fc<2" 



<[2(#^=+'^/2-l)n+'+llog<^/2^] 

X Fjc (E/ {h^ A 22"'^) > 22^+#^'" log'^ n) . 



^ p{#/<:+d/2)n+/+l jQgd/2 



n 



X P/c(E/(/i2 A22"^) > 22^+#^'"log'^n) 
and we can finish this step just as Step 2 in the proof of Theorem 5. 

Step 3. 

AnQ{x: h\x) < 2"'^log^i, V,c/,_„/^0 mh' A 2^-'^) < 2#^^"log'^n}. 

Using the same arguments as above and the Khintchine inequahty for Rade- 
macher chaoses we obtain 



E 



Y^ -Kd^ih(Xi] 



i&li,id=k 



<LdE 



J2 T^d^lK^l 



dcc^ 



ielf.,id=k 



< 2^('^-^)LdE 



Y ef'^/j(Xf^^) 



iel^,id=k 



\\i\<kA.=k J 



^|i|<fc,id= 

where in the last inequahty we have added the diagonal summands just to 
make the proof more similar to the analogous step (Step 3) in the proof of 
Theorem 5. Therefore, it suffices to prove 



E 



2"E(X]|i|<2",jrf=2" ^n(Xi '^'^)) 



dec\N2 



22nd log. 



2d 



< OO. 



n 



But again this can be done just as in Step 3 in the proof of Theorem 5, 
by considering just the cases (a), (b) there. The case (c) (which made all 
the consequent work in the proof of Theorem 5 necessary) cannot appear 
here because the index i^ is fixed. The proof of the theorem may be thus 
complete just as for Theorem 5, by splitting S'^ into 3 parts (for each n), 
corresponding to Steps 1-3 above. D 



36 R. ADAMCZAK AND R. LATALA 

REFERENCES 

[1] Adamczak, R. (2006). Moment inequalities for [/-statistics. Ann. Probab. 34 2288- 

2314. MR2294982 
[2] Arcones, M. and Gine, E. (1995). On the law of the iterated logarithm for canonical 

[/-statistics and processes. Stochastic Process. Appl. 58 217-245. MR1348376 
[3] DE LA Pena, V. H. and Gine, E. (1999). Decoupling. From Dependence to Indepen- 
dence. Springer, New York. MR1666908 
[4] DE LA Pena, V. H. and Montgomery-Smith, S. (1994). Bounds for the tail proba- 
bilities of [/-statistics and quadratic forms. Bull. Amer. Math. Soc. 31 223-227. 
MR1261237 
[5] Gine, E. and Zhang, C.-H. (1996). On integrability in the LIL for degenerate [/- 

statistics. J. Theoret. Probab. 9 385-412. MR1385404 
[6] Gine, E. and Zinn, J. (1992). Marcinkiewicz type laws of large numbers and conver- 
gence of moments for [/-statistics. In Probability in Banach Spaces 8 (R. M. Dud- 
ley, M. G. Hahn and J. Kuelbs, eds.) 273-291. Birkhauser, Boston. MR1227625 
[7] Gine, E. and Zinn, J. (1994). A remark on convergence in distribution of [/-statistics. 

Ann. Probab. 22 117-125. MR1258868 
[8] Gine, E., Kwapien, S., Latala, R. and Zinn, J. (2001). The LIL for canonical 

[/-statistics of order 2. Ann. Probab. 29 520-557. MR1825163 
[9] Halmos, p. R. (1946). The theory of unbiased estimation. Ann. Math. Statist. 17 
34-43. MR0015746 
[10] HiTCZENKO, P. (1993). Domination inequality for martingale transforms of a 

Rademacher sequence. Israel J. Math. 84 161-178. MR1244666 
[11] HOEFFDING, W. (1948). A class of statistics with asymptotically normal distribution. 

Ann. Math. Statist. 19 293-325. MR0026294 
[12] HOEFFDiNG, W. (1961). The strong law of large numbers for [/-statistics. Inst. Statist. 

Mimeo Ser. 302. Univ. North Carolina, Chapel HiU. 
[13] Kwapien, S., Latala, R., Oleszkiewicz, K. and Zinn, J. (2003). On the limit 
set in the law of the iterated logarithm for [/-statistics of order two. In High 
Dimensional Probability III (J. Hoffmann- j0rgensen, M. B. Marcus and J. A. 
Wellner, eds.) 111-126. Birkhauser, Basel. MR2033884 
[14] Latala, R. (1999). Tail and moment estimates for some types of chaos. Studia Math. 

135 39-53. MR1686370 
[15] Latala, R. and Zinn, J. (2000). Necessary and sufficient conditions for the strong 
law of large numbers for [/-statistics. Ann. Probab. 28 1908-1924. MR1813848 
[16] Ledoux, M. and Talagrand, M. (1991). Probability in Banach Spaces. Isoperimetry 

and Processes. Springer, Berlin. MR1102015 
[17] Montgomery-Smith, S. (1993). Comparison of sums of independent identically dis- 
tributed random variables. Probab. Math. Statist. 14 281-285. MR1321767 
[18] Rubin, H. and Vitale, R. A. (1980). Asymptotic distribution of symmetric statis- 
tics. Ann. Statist. 8 165-170. MR0557561 
[19] Zhang, C.-H. (1999). Sub-Bernoulli functions, moment inequalities and strong 
laws for nonnegative and symmetrized [/-statistics. Ann. Probab. 27 432-453. 
MR1681165 



THE LIL FOR CANONICAL [/-STATISTICS 



37 



Institute of Mathematics 

Polish Academy of Sciences 

Sniadeckich 8 

P.O.Box 21 

00-956 Warszawa 10 

Poland 

E-MAIL: R.Adamczak@impan.gov.pl 



Institute of Mathematics 

Warsaw University 

Banacha 2 

02-097 Warszawa 

Poland 

E-MAIL: rlatala@mimuw.cdu.pl