# 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