Monte-Carlo与积分计算

第九章MonteCarlo积分第九章MonteCarlo积分MonteCarlo法的重要应用领域之一：计算积分和多重积分适用于求解：1.被积函数、积分边界复杂，难以用解析方法或一般的数值方法求解；2.被积函数的具体形式未知，只知道由模拟返回的函数值。本章内容：用MonteCarlo法求定积分的几种方法：均匀投点法、期望值估计法、重要抽样法、半解析法、…第九章MonteCarlo积分Goal:Evaluateanintegral:baIdxg(x)Whyuserandommethods?Computationby“deterministicquadrature”canbecomeexpensiveandinaccurate.gridpointsaddupquicklyinhighdimensionsbadchoicesofgridmaymisrepresentg(x)第九章MonteCarlo积分MonteCarlomethodcanbeusedtocomputeintegralofanydimensiond(d-foldintegrals)Errorcomparisonofd-foldintegralsSimpson’srule,…dNE/121NEpurelystatistical,notrelyonthedimension!MonteCarlomethodWINS,whend3MonteCarlomethodapproximatingtheintegralofafunctionfusingquadraticpolynomials)]()(4)([31)()(210000xfxfxfhdxxfdxxfhxxxxhxxxx1201第九章MonteCarlo积分Hit-or-MissMethodSampleMeanMethodVarianceReductionTechniqueVarianceReductionusingRejectionTechniqueImportanceSamplingMethodHit-or-MissMethod•EvaluationofadefiniteintegraldxxIba)(xxhanyfor)(abhXXXXXXOOOOOOO•ProbabilitythatarandompointresideinsidetheareaNMhabIp)(NMhabI)(N:TotalnumberofpointsM:pointsthatresideinsidetheregionHit-or-MissMethodSampleuniformlyfromtherectangularregion[a,b]x[0,h]a)-h(bI:pTheprobabilitythatwearebelowthecurveisSo,ifwecanestimatep,wecanestimateI:a)-h(bpIˆˆwhereisourestimateofppˆHit-or-MissMethodWecaneasilyestimatep:throwN“uniformdarts”attherectangleNMpˆletletMbethenumberoftimesyouendupunderthecurvey=g(x)Hit-or-MissMethodabhXXXXXXOOOOOOOStartSetN:largeintegerM=0Chooseapointxin[a,b]Chooseapointyin[0,h]if[x,y]resideinsidethenM=M+1I=(b-a)h(M/N)EndLoopNtimesauabx1)(2huyHit-or-MissMethodErrorAnalysisoftheHit-or-MissMethodItisimportanttoknowhowaccuratetheresultofsimulationsarenotethatMisbinomial(M,p))1()()(2PNpMNpMEIpabhMENabhabhNMEabhpEIE)()()()()(ˆ)ˆ(NppabhMNabhabhNMabhpI)1()()()()()(ˆ)ˆ(222222222NMppˆ)1()()ˆ(NMMNabhI21)1()()ˆ(NNppabhI第九章MonteCarlo积分Hit-or-MissMethodSampleMeanMethodVarianceReductionTechniqueVarianceReductionusingRejectionTechniqueImportanceSamplingMethodSampleMeanMethodStartSetN:largeintegers1=0,s2=0xn=(b-a)un+ayn=(xn)s1=s1+yn,s2=s2+yn2Estimatemeanm’=s1/NEstimatevarianceV’=s2/N–m’2EndLoopNtimesNVabISMerror'6745.0)(SampleMeanMethoddxg(x)IbaWritethisas:dxa-b1g(x)a)-(bdxg(x)Ibabag(X)Ea)-(bwhereX~unif(a,b)SampleMeanMethodg(X)Ea)-(bIwhereX~unif(a,b)So,wewillestimateIbyestimatingE[g(X)]withn1i)ˆig(Xn1[g(X)]EwhereX1,X2,…,Xnisarandomsamplefromtheuniform(a,b)distribution.SampleMeanMethoddxeI30xExample:(weknowthattheanswerise3-119.08554)writethisas]3E[edx31e3IX30xwhereX~unif(0,3)SampleMeanMethodwritethisas]3E[edx31e3IX30xwhereX~unif(0,3)estimatethiswithn1ixXien13][eE3IˆˆwhereX1,X2,…,Xnarenindependentunif(0,3)’s.SampleMeanMethodSimulationResults:true=19.08554,n=100,000119.10724Iˆ219.08260318.97227419.06814519.13261SimulationSampleMeanMethodDon’tevergiveanestimatewithoutaconfidenceinterval!Thisestimatoris“unbiased”:n1ii)g(Xn1a)-(bE]IE[ˆn1ii)]E[g(Xn1a)-(bbadxa-b1g(x)n1a)-(bbadxg(x)ISampleMeanMethod]IVar[:σ2Iˆˆn1ii)g(Xn1a)-(bVarn1ii22)g(XVarna)-(b(indep))]Var[g(Xna)-(bn1ii22(indent))]Var[g(Xna)-(b12ba22dxa-b1E[g(X)]g(x)na)-(bba22dxa-b1a-bIg(x)na)-(bSampleMeanMethodanapproximation1nabI)g(xna)-(bsn1ii22IˆˆSampleMeanMethodn1ii)g(Xn1a)-(bIˆX1,X2,…,Xniid-g(X1),g(X2),…,g(Xn)iidLetYi=g(Xi)fori=1,2,…,nThenYa)-(bIˆandwecanonceagaininvoketheCLT.SampleMeanMethod)N(I,I2IˆˆForn“largeenough”(n30),So,aconfidenceintervalforIisroughlygivenbyI/2zIˆˆbutsincewedon’tknow,we’llhavetobecontentwiththefurtherapproximation:IˆI/2szIˆˆSampleMeanMethodba2x1/2dxex:IBytheway…NooneeversaidthatyouhavetousetheuniformdistributionExample:0b][a,2x1/2dx(x)I2ex21(X)IXE21b][a,1/2whereX~exp(rate=2).SampleMeanMethodComparisonofHit-and-MissandSampleMeanMonteCarloLetbethehit-and-missestimatorofIHMIˆ)IVar()IVar(SMHMˆˆThenLetbethesamplemeanestimatorofISMIˆSampleMeanMethodComparisonofHit-and-MissandSampleMeanMonteCarloSamplemeanMonteCarloisgenerallypreferredoverHit-and-MissMonteCarlobecause:theestimatorfromSMMChaslowervarianceSMMCdoesnotrequireanon-negativeintegrand(oradjustments)H&MMCrequiresthatyoubeabletoputg(x)ina“box”,soyouneedtofigureoutthemaxvalueofg(x)over[a,b]andyouneedtobeintegratingoverafiniteintegral.2.1VarianceReductionTechnique-Introduction第九章MonteCarlo积分Hit-or-MissMethodSampleMeanMethodVarianceReductionTechniqueVarianceReductionusingRejectionTechniqueImportanceSamplingMethodVarianceReductionTechniqueIntroductionMonteCarloMethodandSamplingDistributionMonteCarloMethod:TakevaluesfromrandomsampleFromcentrallimittheorem,3ruleMostprobableerrorImportantcharacteristicsN/22mm9973.0)33(mmXPNError6745.0NError/1ErrorVarianceReductionTechniqueIntroductionReducingerror*100samplesreducestheerrororderof10ReducingvarianceVarianceReductionTechniqueThevalueofvarianceiscloselyrelatedtohowsamplesaretakenUnbiasedsamplingBiasedsamplingMorepointsaretakeni