Importance Sampling for Sums of Random Variables w

ImportanceSamplingforSumsofRandomVariableswithRegularlyVaryingTailsPaulDupuis,∗KevinLederandHuiWang†LefschetzCenterforDynamicalSystemsBrownUniversityProvidence,R.I.02912USAAbstractImportancesamplingisavariancereductiontechniqueforefficientestimationofrare-eventprobabilitiesbyMonteCarlo.Forrandomvariableswithheavytailsthereislittleconsensusonhowtochoosethechangeofmeasureusedinimportancesampling.Inthispaperwestudydynamicimportancesamplingschemesforsumsofindependentandidenticallydistributedrandomvariableswithregularlyvaryingtails.Thenumberofsummandscanberandombutmustbeindepen-dentofthesummands.Forestimatingtheprobabilitythatthesumexceedsagiventhreshold,weexplicitlyidentifyaclassofdynamicim-portancesamplingalgorithmswithboundedrelativeerrors.Infact,theseschemesarenearlyasymptoticallyoptimalinthesensethatthesecondmomentofthecorrespondingimportancesamplingestimatorcanbemadeascloseasdesiredtotheminimalpossiblevalue.1IntroductionSupposeonewishestoestimatethequantitypb=P(Snb),whereSn=X1+···+XnandtheXi’sarereal-valued,independentandidenticallydistributed(iid).AsimpleandofteneffectivemeansistouseMonteCarlosimulation.OnegeneratesKiidreplicas{Skn}oftherandomvariableSn,∗ResearchofthisauthorsupportedinpartbytheNationalScienceFoundation(NSF-DMS-0306070andNSF-DMS-0404806)andtheArmyResearchOffice(DAAD19-02-1-0425andW911NF-05-1-0289).†ResearchofthisauthorsupportedinpartbytheNationalScienceFoundation(NSF-DMS-0103669andNSF-DMS-0404806).andformstheestimateZK.=(PKk=1I{Sknb})/K.TherateofconvergenceofZKisdeterminedbyitsvariance:var(ZK)=(pb−p2b)/K.Notethatpb→0asb→∞impliesvar(ZK)→0asb→∞.However,whenestimatingsmallprobabilitiesamoreimportantstatisticistherelativeerroroftheestimate:RE(ZK).=standarddeviationofZKmeanofZk=1√K·r1−pbpb.HenceforboundedrelativeerroritisnecessarythatKgrowsasfastas1/pb,andbecauseofthisstandardMonteCarlosimulationisrarelyusedtoestimaterareeventprobabilities.Analternativeapproachtotheproblemofestimatingsmallprobabil-itiesisimportancesampling,whereinsteadofsamplingfromtheoriginaldistributionsamplesaredrawnfromanewdistributionunderwhichtherareeventsarenolongerrare.Morespecifically,iidsamplesoftheran-domvariableI{˜Snb}aredrawn,where˜Sn=˜X1+···+˜Xnandthevector(˜X1,...,˜Xn)hasanalternativedistribution,sayνbn.Thecorrespondingimportancesamplingestimatorisjustthesampleaverageofiidcopiesofˆpb.=I{˜Snb}dμdνbn(˜X1,...,˜Xn),whereμdenotesthedistributionof(X1,...,Xn).Clearlythisestimatorisunbiased.Thegoalofimportancesamplingistochooseνbnsoastominimizethevariance,orequivalently,thesecondmomentofˆpb:Eˆp2b=EI{Snb}dμdνbn(X1,...,Xn).Itturnsoutthatsolvingfortheunconstrainedminimizationproblemoverallpossibledistributionsrequiresknowingpb.Instead,onetypicallysearcheswithinaparametricfamilyofchangesofmeasureandlooksforadistributionthatsatisfiesanoptimalitycriterion.Jensen’sinequalityimpliesEˆp2b≥(E[ˆpb])2=p2b,thusgivingalowerboundonthesecondmoment.Achangeofmeasureνbnissaidtobeasymptoticallyoptimal,orhaveasymptoticallyoptimalrelativeerror,iflimb→∞Eˆp2bp2b=EI{Snb}dμ/dνbn(X1,...,Xn)p2b=1.(1.1)2Onewouldliketoconstructschemeswhoseasymptoticrelativeerrorisclosetoorequaltothisminimalvalue1.In[6,7]itwasshownthatideasfromstochasticcontrolandgametheorycanbeusedeffectivelyinthedesignofimportancesamplingschemesforrandomvariableswithfinitemomentgeneratingfunctions.Thispaperisconcernedwithsumsofnon-negativerandomvariableswithheavytaileddistributions(bywhichwemeanE[exp(tXi)]=∞forallt0).Forthissetup,therewasnogeneraltheoryforchoosingsamplingdistributionsνbnthatsatisfythisasymptoticoptimalitycriterion,orevendistributionsthathaveuniformly(inb)boundedrelativeerror.Agoalofthecurrentpaperistodemonstratethatthetechniquesofcontroltheorycanagainserveasbasictoolsinthedesignandanalysisofasymptoticallyoptimalimportancesamplingschemesforheavytaileddistributions.Thepaperisorganizedasfollows.Section2introducesaparametricfamilyofalternativesamplingdistributions(i.e.,controls)νbn.InSection3,weuseweakconvergenceargumentstoshowthat,whenthenumberofsummandsisfixed,suchchangesofmeasureinduceestimatorswithboundedrelativeerrors.Moreover,onecanalwaysidentifynearlyasymptoticallyoptimalschemesinthesensethatthecorrespondingimportancesamplingestimatorscomewithinan(arbitrarily)prescribederroroftheabsolutelowerbound1in(1.1).InSection4weadaptthisconstructiontoestimateρb=P(X1+···+XNb)whenNisarandomvariablethatisindependentof{Xi,i∈N}andsatis-fiesE[zN]∞forsomez1.Forthiscasewearealsoabletoidentifyimportancesamplingschemesthatarenearlyasymptoticallyoptimal.Sec-tion5presentsacollectionofnumericalresults.Wecompareourschemewithtwoexistingsimulationmethods,oneofwhichisbasedonconditionalMonteCarloratherthanimportancesampling[1],andtheotherisbasedondelayedhazardratetwisting[9].ItisworthmentioningthattheconditionalMonteCarloalgorithmproducesestimatesthathaveboundedrelativeer-rors,althoughitisnotknownwhethertheysatisfytheasymptoticoptimalitycriterion.2ProblemsetupConsiderasequenceofiidnon-negativerandomvariables{Xi,i∈N}withtailprobability¯F(x).=P(Xix).LetSn.=X1+···+Xn.Assumethat,3forso