IMPORTANCE RESAMPLING FOR BOOTSTRAP CONFIDENCE REG

IMPORTANCERESAMPLINGFORBOOTSTRAPCONFIDENCEREGIONSBYCHENG-DERFUHANDINCHIHUAcademiaSinicaandHongKongUniversityofScienceandTechnologyABSTRACTInthisarticle,weobtainanimportanceresamplingformulatoreducetheamountofresam-plingnecessaryfortheconstructionofbootstrapcondenceregions.Intheone-dimensionalcase,theformulareducestothatofJones(1988)andDo&Hall(1991).However,themethodsemployedbypreviousauthorsarenottamedfordirectgeneralizationtomulti-dimensionalpa-rameters.Thereforenoformulaisavailableforbootstrapcondenceregionsintheliterature.Ourmethod,whichiscloselyrelatedtothelargedeviationtilting,allowsarelativelyeasytreatmentofthemulti-dimensionalcase.Themethodalsorevealsaphenomenonthathap-pensonlyinthemulti-dimensionalcase.Thatis,theoptimallytilteddistributionisamixtureofexponentiallytilteddistributions,andthemixturecomponentsdependontheshapeofthecondenceregion.Wealsoprovideageneralaccountoftheimportanceresamplinginrelationtothelargedeviationtilting.Eciencypropertiesofthesimulationschemeusingtheproposedformulaisestablishedtogetherwithnumericalevidence.Somekeywords:Bootstrap;Condenceregion;Importanceresampling;Largedeviation;Uni-formresamplingResearchpartiallysupportedbytheNationalScienceCouncilofROC.VisitingNationalTaiwanUniversityandAcademiaSinica,researchpartiallysupportedbyHongKongResearchGrantCouncil.1INTRODUCTIONImportanceresamplingisrstsuggestedbyJones(1988)andDavison(1988)asawaytoimprovetheeciencyofMonteCarlomethodsforcalculatingquantilesofbootstrapdistri-butions.Theideaofimportanceresamplingisthatinsteadofuniformresampling,wecanresamplefroma\tilteddistribution.Ifthetilteddistributionissuchthattheeventsimu-latedhashighprobabilityandthatitisroughlyproportionaltothebootstrapdistributionoverthatevent,thenimportanceresamplinghaspotentialfordramaticimprovementinper-formanceoveruniformresampling;seeforexampleHinkley&Shi(1989)inthecontextof1iteratedbootstrapcondenceintervals.Thereforethemajortaskinimportanceresamplingistoidentifytheoptimallytilteddistributionsothatthevarianceoftheestimatorisminimizedwithinaclassofcandidatedistributions.Otherresamplingmethodshavebeenproposedtoimprovetheeciencyofbootstrapsimu-lation.Amongthem,balancedresamplingandantitheticresamplingaremostnotable(seee.g.Davison&Hinkley,1997,andHall,1992).AspointedoutbyHall(1992),whensimulatingtaileventsofsmallprobabilities,whichiscommoninbootstrapcondenceintervals/regionscon-struction,importanceresamplingprovidesmuchmoresignicantimprovementthanbalancedresamplingandantitheticresampling.Jones(1988)proposedatiltingformulatocalculatetheoptimallytilteddistributionforimportanceresampling.Do&Hall(1991)complementeditwithcomprehensivederivationandanempiricalversion.TheessenceofDo&Hall’sargumentistoexpressthevarianceoftheestimatorunderatilteddistributionintermsofthelikelihoodratiobetweentheuniformresamplingandthetilteddistribution.NextmakeuseofacentrallimittheoremofHolst(1972)formultinomialsumstoreducethevarianceoftheestimatortoanexpressioninvolvingonlyamultivariatenormaldistribution.Thenminimizethisexpressiontoidentifytheoptimallytilteddistribution.Thisapproachworksquitewellforone-dimensionalproblems.However,inthemulti-dimensionalcase,theproceduretoidentifytheoptimumdistributionafterminimizingtheexpressionconcerningamultivariatenormaldistributionisneitherobviousnorintuitive.Thatiswhytherehasbeennomulti-dimensionaltiltingformulaforimportanceresampling.Onecontributionofthispaperistollinthisgapintheliteratureofimportanceresampling.Theimportanceresamplinginthebootstrapliteratureusuallyconcernsnormaltailevents,forexample,thep-thquantileofanasymptoticnormaldistributionwithptakingvalues.01,.05,or.1,etc..Ontheotherhand,thereisanothersetofliteraturedealingwitheventsoflargedeviationusingimportancesampling.Thatis,whenasequenceofrandomvectorsfYngconverginginprobabilitytoaconstantvector,foraneventEnotcontaining,theprobabilityPfYn2Egusuallydecaysexponentiallyasntendsto1.EcientMonteCarlosimulationofsucheventshasbeenproposedbyBucklew,Ney&Sadowsky(1990)andSadowsky&Bucklew(1990),basedonthetheoryoflargedeviations.Ourapproachemploysacontiguityargumenttoapproximatethelargedeviationtiltingformula.Thisapproachcanidentifytheoptimumtilteddistributioninaratherstraightforwardfashion.Italsodisclosesaphenomenonwhichoccursonlyinthemulti-dimensionalcase.Forotherrelatedliterature,Booth,Hall&Wood(1993)describedalgorithmsforbalancedimportanceresampling.Chen&Do(1994)discussedtheeciencygainsfromcombiningsad-dlepointmethodswithimportanceresampling.Hesterberg(1995)suggestedtheapplicationofratioandregressionestimatorsandofdefensivemixturedistributionsinimportancesampling,anddescribedtheirproperties.Gonet&Wallach(1996)studiedtheadaptiveimportance2resampling.ForbootstrapcondenceregionspleaseseeBeran&Millar(1986);Beran(1987);Hall(1987);Davison&Hinkley(1997).SummariesforimportancesamplingaregiveninHammersley&Handscomb(1964)andGlynn&Iglehart(1989).Therestofthearticleisorganizedasfollows.Inx2,wederiveatiltingformulaforatwo-dimensionalexample,wherewealsodemonstratethedicultyofusingth