Convergence of the empirical process in Mallows di

arXiv:math/0406603v1[math.PR]29Jun2004ConvergenceoftheempiricalprocessinMallowsdistance,withanapplicationtobootstrapperformanceRichardSamworth∗†OliverJohnson∗‡February1,2008RunningTitle:EmpiricalprocessinMallowsdistanceKeywords:Bootstrap,empiricaldistribution,empiricalprocess,hazardfunction,Mallowsdistance,probabilitymetric,samplemean,Wassersteindistance.MathematicsSubjectClassification:62E20;60F25;62F40.AbstractWestudytherateofconvergenceoftheMallowsdistancebetweentheempiricaldistributionofasampleandtheunderlyingpopulation.Thesurprisingfeatureofourresultsisthattheconvergencerateisslowerinthediscretecasethanintheabsolutelycontinuoussetting.Weshowhowthehazardfunctionplaysasignificantroleinthesecalcu-lations.Asanapplication,werecallthatthequantitystudiedprovidesanupperboundonthedistancebetweenthebootstrapdistributionofasamplemeananditstruesamplingdistribution.Moreover,thecon-venientpropertiesoftheMallowsmetricyieldastraightforwardlowerbound,andthereforearelativelyprecisedescriptionoftheasymptoticperformanceofthebootstrapinthisproblem.∗StatisticalLaboratory,DPMMS/CMS,UniversityofCambridge,WilberforceRoad,CambridgeCB30WB,UK.Fax:[phone]†Email:[e-mail]‡Email:[e-mail]11IntroductionandmainresultsDifferentproblemsinProbabilityandStatisticsnaturallyleadtodifferentchoicesofprobabilitymetric.OnesuchchoiceistheMallowsdistance,alsoknownastheWassersteinorKantorovichdistance.Thismetrichasfoundextensiveapplicationstoawidevarietyoffields;seeRachev(1984)forareview.Definition1.1Forr≥1,letFrdenotethesetofdistributionfunctionsFsatisfyingR∞−∞|x|rdF(x)∞.ForF,G∈Fr,theMallowsmetricdr(F,G)isdefinedbydr(F,G)=infTX,YE|X−Y|r 1/r,whereTX,YisthesetofalljointdistributionsofpairsofrandomvariablesXandYwhosemarginaldistributionsareFandGrespectively.Wealsowritedr(X,Y)fordr(F,G),wherethiswillcausenoconfusion.Theempiricalprocessisafundamentalquantityofinterest.Thoughoftennotexplicitlyrecognisedassuch,theMallowsdistancebetweentheempiricaldistributionandtheunderlyingpopulationhasarisenintheworkofseveralauthors,includingCs¨org˝oandHorv´ath(1990)anddelBarrioetal.(1999,2000).SupposeX1,...Xnareindependentrandomvariables,eachhavingdistribu-tionfunctionFwithmeanμandfinitevarianceσ20,andletˆFndenotetheempiricaldistributionfunctionofthesample,givenbyˆFn(x)=1nnXi=11{Xi≤x}.Themaincontributionsofthispaperarethreefold:1.InTheorem2.6,weshowthatinthecaseofadiscreteunderlyingpop-ulationoffinitesupport,n1/4d2(ˆFn,F)convergestoanexplicitnon-degeneratelimitingdistribution.Wecontrastthiswiththen1/2nor-malisationrequiredbythepreviouslycitedauthorsintheabsolutelycontinuouscase.22.InSection3,westudythetailconditionsrequiredbyCs¨org˝oandHorv´ath(1990)anddelBarrioetal.(2000)fortheconvergenceofn1/2d2(ˆFn,F)intheabsolutelycontinuouscase.Inparticular,byconsideringthehazardfunction,weshowthatoneoftheconditionsofdelBarrioetal.(2000)isredundant,andthestatementofTheorem2.1ofCs¨org˝oandHorv´ath(1990)maybesimplified.3.Section4isdevotedtoanapplicationoftheseresults.WerecallthecalculationofShaoandTu(1995),showingthatd2(ˆFn,F)providesanupperboundontheMallowsdistancebetweenthebootstrapdistribu-tionofthesamplemeananditstruesamplingdistribution.Wegiveastraightforwardlowerboundonthislatterquantity,yieldingconditionsunderwhichtheupperandlowerboundsareofthesameorder.2Convergenceratesandlimitingdistribu-tionsfordr(ˆFn,F)First,recallthefollowingtwolemmasaboutdr,whichareprovedinMajor(1978)andBickelandFreedman(1981)respectively.Lemma2.1ForF,G∈Fr,theinfimuminDefinition1.1isattainedbythefollowingconstruction:letU∼U(0,1),andsetX=F−1(U),Y=G−1(U),where,forexample,F−1(p)=inf{x∈R:F(x)≥p}.Thusdr(F,G)=Z10|F−1(p)−G−1(p)|rdp1/r.Lemma2.2If(Fn)∈FandF∈F,thendr(Fn,F)→0asn→∞ifandonlyif,foreverybounded,continuousfunctiong:R→R,wehaveboth1.limn→∞Z∞−∞g(x)dFn(x)=Z∞−∞g(x)dF(x);2.limn→∞Z∞−∞|x|rdFn(x)=Z∞−∞|x|rdF(x).Thus,convergenceintheMallowsmetricdrisequivalenttoconvergenceindistributiontogetherwithconvergenceoftherthabsolutemoments.3ItfollowsimmediatelybyLemma2.2andthestronglawoflargenumbersthatd2(ˆFn,F)→0almostsurelyasn→∞.Itisimportanttoremarkthatalthoughwecancalculatearateofconvergenceofthetwopartsabove(thatis,convergenceindistributionandoftherthabsolutemoment),thiswillnothelpusfindarateofconvergenceofd2(ˆFn,F),andwemustuseothertechniques.WhenFhasadensityf,Cs¨org˝oandHorv´ath(1990)anddelBarrioetal.(2000)giveconditionsunderwhichn1/2d2(ˆFn,F)convergestoanondegen-eratelimitingdistribution.AsimpleversionofsuchresultsisgiveninThe-orem2.4below.However,theseresultsdonotcoverthecaseofadiscreteunderlyingpopulation,whichisstudiedlater,inTheorem2.6.InordertoproveTheorem2.4,weneedtointroducesomenotation.LetD=D[0,1]denotethespaceofleft-continuous,real-valuedfunctionson[0,1]possessingrightlimitsateachpoint.WemayequipDwiththeuniformnormkx−yk∞=supp∈[0,1]|x(p)−y(p)|.Asmallcomplicationarisesfromthefactthatthenormedspace(D,k·k∞)isnon-separable,andtheσ-algebra,D,generatedbytheopenballsisstrictlysmallerthantheBorelσ-algebra,DBorel,generatedbytheopensets.Thiscreatesmeasurabilityproblems,asexplainedinChibisov(1965),whic