第九章

MonteCarlo積分第九章MonteCarlo積分MonteCarlo法的重要應(yīng)用領(lǐng)域之一：計算積分和多重積分適用于求解：被積函數(shù)、積分邊界復(fù)雜，難以用解析方法或一般的數(shù)值方法求解；被積函數(shù)的具體形式未知，只知道由模擬返回的函數(shù)值。本章內(nèi)容：用MonteCarlo法求定積分的幾種方法：均勻投點法、期望值估計法、重要抽樣法、半解析法、…第九章MonteCarlo積分Goal:Evaluateanintegral:Whyuserandommethods?Computationby“deterministicquadrature”canbecomeexpensiveandinaccurate.gridpointsaddupquicklyinhighdimensionsbadchoicesofgridmaymisrepresentg(x)第九章MonteCarlo積分MonteCarlomethodcanbeusedtocomputeintegralofanydimensiond(d-foldintegrals)Errorcomparisonofd-foldintegralsSimpson’srule,…purelystatistical,notrelyonthedimension!MonteCarlomethodWINS,whend>>3MonteCarlomethodapproximatingtheintegralofafunctionfusingquadraticpolynomials第九章MonteCarlo積分Hit-or-MissMethodSampleMeanMethodVarianceReductionTechniqueVarianceReductionusingRejectionTechniqueImportanceSamplingMethodHit-or-MissMethodEvaluationofadefiniteintegralabhXXXXXXOOOOOOOProbabilitythatarandompointresideinsidetheareaN:TotalnumberofpointsM:pointsthatresideinsidetheregionHit-or-MissMethodSampleuniformlyfromtherectangularregion[a,b]x[0,h]TheprobabilitythatwearebelowthecurveisSo,ifwecanestimatep,wecanestimateI:whereisourestimateofpHit-or-MissMethodWecaneasilyestimatep:throwN“uniformdarts”attherectangleletletMbethenumberoftimesyouendupunder thecurvey=g(x)Hit-or-MissMethodabhXXXXXXOOOOOOOStartSetN:largeinteger

M=0Chooseapointxin[a,b]Chooseapointyin[0,h]if[x,y]resideinsidethenM=M+1I=(b-a)h(M/N)EndLoopNtimesHit-or-MissMethodErrorAnalysisoftheHit-or-MissMethodItisimportanttoknowhowaccuratetheresultofsimulationsare

notethatMisbinomial(M,p)第九章MonteCarlo積分Hit-or-MissMethodSampleMeanMethodVarianceReductionTechniqueVarianceReductionusingRejectionTechniqueImportanceSamplingMethodSampleMeanMethodStartSetN:largeinteger

s1=0,s2=0xn=(b-a)un+ayn=r(xn)s1=s1+yn,s2=s2+yn2Estimatemeanm’=s1/NEstimatevarianceV’=s2/N–m’2EndLoopNtimesSampleMeanMethodWritethisas:whereX~unif(a,b)SampleMeanMethodwhereX~unif(a,b)So,wewillestimateIbyestimatingE[g(X)]withwhereX1,X2,…,Xnisarandomsamplefromtheuniform(a,b)distribution.SampleMeanMethodExample:(weknowthattheanswerise3-119.08554)writethisaswhereX~unif(0,3)SampleMeanMethodwritethisaswhereX~unif(0,3)estimatethiswithwhereX1,X2,…,Xnarenindependentunif(0,3)’s.SampleMeanMethodSimulationResults:true=19.08554,n=100,000

1 19.107242 19.082603 18.972274 19.068145 19.13261 SimulationSampleMeanMethodDon’tevergiveanestimatewithoutaconfidenceinterval!Thisestimatoris“unbiased”:SampleMeanMethodSampleMeanMethodanapproximationSampleMeanMethodX1,X2,…,Xniid->g(X1),g(X2),…,g(Xn)iidLetYi=g(Xi)fori=1,2,…,nThenandwecanonceagaininvoketheCLT.SampleMeanMethodForn“l(fā)argeenough”(n>30),So,aconfidenceintervalforIisroughlygivenbybutsincewedon’tknow,we’llhavetobecontentwiththefurtherapproximation:SampleMeanMethodBytheway…NooneeversaidthatyouhavetousetheuniformdistributionExample:whereX~exp(rate=2).SampleMeanMethodComparisonofHit-and-MissandSampleMeanMonteCarloLetbethehit-and-missestimatorofIThenLetbethesamplemeanestimatorofISampleMeanMethodComparisonofHit-and-MissandSampleMeanMonteCarloSamplemeanMonteCarloisgenerallypreferredoverHit-and-MissMonteCarlobecause:theestimatorfromSMMChaslowervarianceSMMCdoesnotrequireanon-negativeintegrand (oradjustments)H&MMCrequiresthatyoubeabletoputg(x)ina “box”,soyouneedtofigureoutthemax valueofg(x)over[a,b]andyouneedtobe integratingoverafiniteintegral.2.1VarianceReductionTechnique-Introduction第九章MonteCarlo積分Hit-or-MissMethodSampleMeanMethodVarianceReductionTechniqueVarianceReductionusingRejectionTechniqueImportanceSamplingMethodVarianceReductionTechniqueIntroductionMonteCarloMethodandSamplingDistributionMonteCarloMethod:TakevaluesfromrandomsampleFromcentrallimittheorem,3sruleMostprobableerrorImportantcharacteristicsVarianceReductionTechniqueIntroductionReducingerror*100samplesreducestheerrororderof10ReducingvarianceVarianceReductionTechniqueThevalueofvarianceiscloselyrelatedtohowsamplesaretakenUnbiasedsamplingBiasedsamplingMorepointsaretakeninimportantpartsofthepopulationVarianceReductionTechniqueMotivationIfweareusingsample-meanMonteCarloMethodVariancedependsverymuchonthebehaviorofr(x)r(x)varieslittlevarianceissmallr(x)=constvariance=0EvaluationofaintegralNearminimumpointscontributelesstothesummationNearmaximumpointscontributemoretothesummationMorepointsaresamplednearthepeak”importancesamplingstrategy”第九章MonteCarlo積分1.2Hit-or-MissMethod1.3SampleMeanMethod2.1VarianceReductionTechnique2.3VarianceReductionusingRejectionTechnique2.4ImportanceSamplingMethodVarianceReductionTechniqueVarianceReductionforHit-or-MissmethodInthedomain[a,b]chooseacomparisonfunctionabw(x)XXXXXOOOOOOOr(x)Pointsaregeneratedontheareaunderw(x)functionRandomvariablethatfollowsdistributionw(x)VarianceReductionTechniquePointslyingabover(x)isrejectedq10P(q)r1-rabw(x)XXXXXOOOOOOOr(x)VarianceReductionTechniqueErrorAnalysisHitorMissmethodErrorreductionVarianceReductionTechniqueStartSetN:largeinteger

N’=0Generateu1,x=W-1(Au1)Generateu