Necessary and Sufficient Conditions for the Strong

NecessaryandSucientConditionsfortheStrongLawofLargeNumbersforU-statisticsRafalLatalaandJoelZinnWarsawUniversityandTexasA&MUniversityAbstractUndersomemildregularityonthenormalizingsequence,weob-tainnecessaryandsucientconditionsfortheStrongLawofLargeNumbersfor(symmetrized)U-statistics.Wealsoobtainnasc’sforthea.s.convergenceofseriesofananalogousform.1Introduction.Thegeneralquestionaddressedinthispaperisthatofnecessaryandsucientconditionsfor1nXi2Inih(Xi)!0;a.s.;whereIn=fi=(ii;i2;:::;id):1i1i2:::idng,fXjg1j=1isasequenceofiidr.v.’s,Xi=(Xi1;;Xid).Withnolossofgeneralitywemayassumethathissymmetricinitsarguments.Further,asin[CGZ]andin[Zh1],itisalsoimportanttoconsiderthequestionofthealmostsureconvergencetozeroof1nmaxi2Injh(Xi)j:SupportedinpartbyNSFGrantDMS-9626778AMS1991SubjectClassication:Primary60F15,Secondary60E15Keywordsandphrases:U-statistics,StrongLawofLargeNumbers,randomseries12R.LATALAANDJ.ZINNInfact,itisthroughthestudyofthisproblemthatoneisabletocompletethecharacterizationfortheoriginalquestion.WithoutthesymmetrizationbyRademachers,Hoeding([H])in1961provedthatforgeneraldandn=nd,meanzeroissucientforthenor-malizedsumabovetogotozeroalmostsurely.And,underapthmomentonehasthea.s.convergencetozerowithn=ndp([S]when0p1,intheproductcasewithmeanzero[T]for1p2andinthecaseofgeneraldegenerateh[GZ]for1p2).Itissomewhatsurprisingthatittookuntilthe90’stoseethatHoeding’ssucientconditionwasnotnecessary([GZ]).Intheparticularcaseinwhichd=2,h(x;y)=xyandthevariablesaresymmetric,necessaryandsucientconditonsweregivenin([CGZ])in1995.Thiswaslaterextendedtod3byZhang([Zh1]).VeryrecentlyZhang[Zh2]obtained\computablenecessaryandsucientconditionsinthecased=2and,ingeneral,foundequivalentconditionsintermsofalawoflargenumbersformodiedmaxima.Otherrelatedworkisthatof[M]inwhichthedierentindicesgotoinnityattheirownpaceand[G]inwhichthevariablesindierentcoordinatescanbebasedondierentdistributions.Inthispaperweobtainnasc’sforstronglawsfor‘maxima’forgenerald.ThislikelywouldhaveenabledonetocompleteZhang’sprogram.However,wealsofoundamoreclassicalwayofhandlingthereductionofthecaseofsumstothecaseofmax’s.Theorganizationofthepaperisasfollows.InSection2weintroducethenecessarynotationandgivethebasicLemmas.NowtheformofourmainTheoremisinductive.Thereasonwepresenttheresultinthisformisthattheconditionsinthecased2arequiteinvolved.BecauseoftheformatofourTheoremwerstpresentinSection3,thecasethatthefunction,h,istheproductofthecoordinates.Asmentionedearlier,thiscasereceivedquiteabitattention,culminatinginZhang’spaper([Zh1]).IntherstpartofSection3weshowhowthemethodsdevelopedinthispaperallowonetogivearelativelysimple,andperhapstransparent,proofofZhang’sresult.We,then,provethemainresult,namely,thenasc’sfortheStrongLawforsymmetricU-statistics.Again,becauseofourinductiveformat,inordertoclearlybringoutthemainidea’sofourproof,wealsogiveasimpleproofofZhang’sresultforthecased=2.FinallyinSection4weconsiderthequestionofconvergenceofmul-tidimensionalrandomseriesPi2Zd+hi(~Xi).Weobtainnecessaryandsuf-SLLNFORU-STATISTICS3cientconditionsfora.s.convergenceinthecaseofnonnegativeorsym-metrizedkernels.Thisgeneralizestheresultsof[KW1](cased=2andhi;j(x;y)=ai;jxy).2PreliminariesandBasicLemmas.Letusrstintroducemultiindexnotationwewilluseinthepaper:i=(ii;i2;:::;id)-multiindexofsizedXi=(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=i1i2id,where(i)isaRademachersequence(i.e.asequenceofi.i.d.symmetricrandomvariablestakingonvalues1)independentofotherrandomvariables~i=(1)i1(2)i2(d)id,where((j)i)isadoublyindexedRademacherse-quenceindependentofotherrandomvariablesk=ki=1-productmeasureonEkforIf1;2;:::;dg,byEIandE0Iwewilldenoteexpectationwithrespectto(Xki)k2Iand(Xki)k=IrespectivelyiI=(ik)k2IandI0=f1;2;:::;dgnIforIf1;2;:::;dgIn=fi=(ii;i2;:::;id):1i1i2:::idng,Cn=fi=(ii;i2;:::;id):1i1;i2;:::;idngAI;x=AxI=fz2EI:9a2A;aI=xI;aI0=zgforAEd;If1;:::;dg.Theresultsinthissectionweremotivatedbythedicultyincomputingquantitiessuchas:P(maxi;jnh(Xi;Yj)t);4R.LATALAANDJ.ZINNwherefXigareindependentrandomvariablesandfYigisanindependentcopy,andhis,say,symmetricinitsarguments.Intheone-dimensionalcase,namely,P(maxinit),wherefigareindependentr.v.’s,wehavethesimpleinequality12min(XiP(jijt);1)P(maxijijt)min(XiP(jijt);1):(1)Ifthistypeofinequalityheldforanydimension,theproofsandresultswouldlookmuchthesameasindimension1.Herewegiveanexampletoseethedierencebetweenthecasesd=1andd1.Considerthesetintheunitsquaregivenby:A=f(x;y)2[0;1]2:xa;yborxb;yagandassumethattheXi;Yjareiiduniformlydistributedon[0;1].By(1)iteasilyfollowsthatP(max1i;jnIA(Xi;Yj)0)min(na;1)min(nb;1);whichisequivalenttoPni;j=1P(IA(Xi;Yj)0)n2abifandonlyifbothaandbareoforderO(1n):2Lemma1Supposethatthenonnegativefunctionsfi(xi)satisfythefollowingconditionsfi(~Xi)1a.s.foralli(2)EIXiIfi(~Xi)1a.s.foranyIf1;2;:::;dg,0Card(I)d(3)Let~m1=EPifi(~Xi),t