Necessary and Su#cient Conditions for the Strong L

NecessaryandSufficientConditionsfortheStrongLawofLargeNumbersforU-statisticsRafalLatala∗andJoelZinn†WarsawUniversityandTexasA&MUniversityAbstractUndersomemildregularityonthenormalizingsequence,weob-tainnecessaryandsufficientconditionsfortheStrongLawofLargeNumbersfor(symmetrized)U-statistics.Wealsoobtainnasc’sforthea.s.convergenceofseriesofananalogousform.1Introduction.Thegeneralquestionaddressedinthispaperisthatofnecessaryandsufficientconditionsfor1γnXi∈Inεih(Xi)→0,a.s.,whereIn={i=(ii,i2,...,id):1≤i1i2...id≤n},{Xj}∞j=1isasequenceofiidr.v.’s,Xi=(Xi1,···,Xid).Withnolossofgeneralitywemayassumethathissymmetricinitsarguments.∗ResearchpartiallysupportedbyPolishGrantKBN2P03A04315†ResearchpartiallysupportedbyNSFGrantDMS-9626778AMS1991SubjectClassification:Primary60F15,Secondary60E15Keywordsandphrases:U-statistics,StrongLawofLargeNumbers,randomseries12R.LATALAANDJ.ZINNFurther,asin[2]andin[12],itisalsoimportanttoconsiderthequestionofthealmostsureconvergencetozeroof1γnmaxi∈In|h(Xi)|.Infact,itisthroughthestudyofthisproblemthatoneisabletocompletethecharacterizationfortheoriginalquestion.WithoutthesymmetrizationbyRademachers,Hoeffding[5]in1961provedthatforgeneraldandγn=nd
,meanzeroissufficientforthenormalizedsumabovetogotozeroalmostsurely.And,underapthmomentonehasthea.s.convergencetozerowithγn=ndp([10]when0p1,intheproductcasewithmeanzero[11]for1≤p2andinthecaseofgeneraldegenerateh[4]for1p2).Itissomewhatsurprisingthatittookuntilthe90’stoseethatHoeffding’ssufficientconditionwasnotnecessary[4].Intheparticularcaseinwhichd=2,h(x,y)=xyandthevariablesaresymmetric,necessaryandsufficientconditionsweregivenin[2]in1995.Thiswaslaterextendedtod≥3byZhang[12].VeryrecentlyZhang[13]obtained“computable”necessaryandsufficientconditionsinthecased=2and,ingeneral,foundequivalentconditionsintermsofalawoflargenumbersformodifiedmaxima.Otherrelatedworkisthatof[8]inwhichthedifferentindicesgotoinfinityattheirownpaceand[3]inwhichthevariablesindifferentcoordinatescanbebasedondifferentdistributions.Inthispaperweobtainnasc’sforstronglawsfor‘maxima’forgenerald.ThislikelywouldhaveenabledonetocompleteZhang’sprogram.However,wealsofoundamoreclassicalwayofhandlingthereductionofthecaseofsumstothecaseofmax’s.Theorganizationofthepaperisasfollows.InSection2weintroducethenecessarynotationandgivethebasicLemmas.NowtheformofourmainTheoremisinductive.Thereasonwepresenttheresultinthisformisthattheconditionsinthecased2arequiteinvolved.BecauseoftheformatofourTheoremwefirstpresentinSection3,thecasethatthefunction,h,istheproductofthecoordinates.Asmentionedearlier,thiscasereceivedquiteabitattention,culminatinginZhang’spaper[12].InthefirstpartofSection3weshowhowthemethodsdevelopedinthispaperallowonetogivearelativelysimple,andperhapstransparent,proofofZhang’sresult.We,then,provethemainresult,namely,thenasc’sfortheStrongLawforSLLNFORU-STATISTICS3symmetricU-statistics.Again,becauseofourinductiveformat,inordertoclearlybringoutthemainideasofourproof,wealsogiveasimpleproofofZhang’sresultforthecased=2.FinallyinSection4weconsiderthequestionofconvergenceofmultidi-mensionalrandomseriesPi∈Zd+hi(˜Xi).Weobtainnecessaryandsufficientconditionsfora.s.convergenceinthecaseofnonnegativeorsymmetrizedker-nels.Thisgeneralizestheresultsof[6](cased=2andhi,j(x,y)=ai,jxy).2PreliminariesandBasicLemmas.Letusfirstintroducemultiindexnotationwewilluseinthepaper:•i=(ii,i2,...,id)-multiindexofsized•Xi=(Xii,Xi2,...,Xid),whereXjisasequenceofi.i.d.randomvari-ableswithvaluesinsomespaceEandthecommonlawμ•˜Xi=(X(1)ii,X(2)i2,...,X(d)id),where(X(k)j),k=1,...,dareindependentcopiesof(Xj),•εi=εi1εi2···εid,where(εi)isaRademachersequence(i.e.asequenceofi.i.d.symmetricrandomvariablestakingonvalues±1)independentofotherrandomvariables•˜εi=ε(1)i1ε(2)i2···ε(d)id,where(ε(j)i)isadoublyindexedRademacherse-quenceindependentofotherrandomvariables•μk=⊗ki=1μ-productmeasureonEk•forI⊂{1,2,...,d},byEIandE′Iwewilldenoteexpectationwithrespectto(Xki)k∈Iand(Xki)kǫ/Irespectively•intheundecoupledcaseEIh(Xi)(resp.E′Ih(Xi))willdenoteexpecta-tionwithrespectto(Xik)k∈I(resp.(Xik)kǫ/I)•iI=(ik)k∈IandI′={1,2,...,d}\IforI⊂{1,2,...,d}•In={i=(ii,i2,...,id):1≤i1i2...id≤n},•Cn={i=(ii,i2,...,id):1≤i1,i2,...,id≤n}4R.LATALAANDJ.ZINN•forI⊂{1,2,...,d}weputPiIai=Pj∈Cn:jI′=iI′aj•AI,x=AxI={z∈EI′:∃a∈A,aI=xI,aI′=z}forA⊂Ed,I⊂{1,...,d}.Theresultsinthissectionweremotivatedbythedifficultyincomputingquantitiessuchas:P(maxi,j≤nh(Xi,Yj)t),where{Xi}areindependentrandomvariablesand{Yi}isanindependentcopy,andhis,say,symmetricinitsarguments.Intheone-dimensionalcase,namely,P(maxi≤nξit),where{ξi}areindependentr.v.’s,wehavethesimpleinequality12min(XiP(|ξi|t),1)≤P(maxi|ξi|t)≤min(XiP(|ξi|t),1).(1)Ifthistypeofinequalityheldforanydimension,theproofsandresultswouldlookmuchthesameasindimension1.Herewegiveanexampletoseethedifferencebetweenthecasesd=1andd1.Considerthesetintheunitsquaregivenby:A={(x,y)∈[0,1]2:xa,yborxb,ya}andassumethattheXi,Yjareiiduniformlydistributedon[0,1].By(1)iteasilyfollowsthatP(max1≤i,j≤nIA(Xi,Yj)0)∼min(na,1)min(nb,1),whichisequivalenttoPni,j=1P(IA(Xi,Yj)0)∼n2abifando