第八章-Monte-Carlo积分.ppt

1、MonteCarlo模拟,第四章MonteCarlo积分,第四章MonteCarlo积分,MonteCarlo法的重要应用领域之一：计算积分和多重积分,适用于求解：,被积函数、积分边界复杂，难以用解析方法或一般的数值方法求解；被积函数的具体形式未知，只知道由模拟返回的函数值。,本章内容：,用MonteCarlo法求定积分的几种方法：均匀投点法、期望值估计法、重要抽样法、半解析法、,第四章MonteCarlo积分,目的：计算一个定积分（一维或多维）,数值方法：,将积分区间分成n个子区间，用一些近似的方法计算各个子区间的积分值，然后对n个子区间的积分值求和,梯形法(trapezoidalrule)

2、：对每个子区间用梯形近似Simpsonsrule：approximatingtheintegralofafunctiongusingquadraticpolynomials,第四章MonteCarlo积分,数值方法存在的问题:,计算速度慢、精度低：,需计算的函数值的数目随着积分维数急剧增长,不恰当的子区间划分将导致不能很好地近似表示被积函数g(x)导致计算误差,积分维数d=10,各方向分点数目n=50,需计算函数值的数目：nd=5010,第四章MonteCarlo积分,MonteCarlo方法可用于计算任何的d重积分,两种方法计算d-重积分的误差比较,Simpsonsrule,purelyst

3、atistical,notrelyonthedimension!,MonteCarlomethodWINS,whend3,MonteCarlomethod,MonteCarlo模拟,第四章MonteCarlo积分,Hit-or-MissMethodSampleMeanMethodVarianceReduction:ImportanceSamplingMethodCorrelationmethodsforvariancereduction,1.Hit-or-MissMethod,Evaluationofadefiniteintegral,a,b,h,X,X,X,X,X,X,O,O,O,O,O,O

4、,O,Probabilitythatarandompointresideinsidethearea,N:TotalnumberofpointsM:pointsthatresideinsidetheregion,1.Hit-or-MissMethod,Sampleuniformlyfromtherectangularregion,a,bx0,h,Theprobabilitythatwearebelowthecurveis,So,ifwecanestimatep,wecanestimateI:,whereisourestimateofp,1.Hit-or-MissMethod,Wecaneasil

5、yestimatep:,throwN“uniformdarts”attherectangle,let,letMbethenumberoftimesyouendupunderthecurvey=g(x),1.Hit-or-MissMethod,a,b,h,X,X,X,X,X,X,O,O,O,O,O,O,O,Start,SetN:largeinteger,M=0,Chooseapointxina,b,Chooseapointyin0,h,ifx,yresideinsidethenM=M+1,I=(b-a)h(M/N),End,LoopNtimes,1.Hit-or-MissMethod,Error

6、AnalysisoftheHit-or-MissMethod,Itisimportanttoknowhowaccuratetheresultofsimulationsare,notethatMisbinomial(M,p),1.Hit-or-MissMethod,推广到多重积分：,区间,内均匀分布的随机数,=hr:区间0,h内均匀分布的随机数,选取n组,，若其中满足g()的共有m组,1.Hit-or-MissMethod,积分结果的置信水平：,对于任意给定的正数，怎样才能保证积分计算值In与真值I之差的绝对值小于的概率大于(01),根据中心极限定理,MonteCarlo模拟,第四章MonteC

7、arlo积分,Hit-or-MissMethodSampleMeanMethodVarianceReduction:ImportanceSamplingMethodCorrelationmethodsforvariancereduction,2.SampleMeanMethod,设欲求的d-重积分为,令X为积分域Vd上均匀分布的随机向量，其概率密度函数为：,2.SampleMeanMethod,产生容量为n的X的随机样本Xi,并计算g(Xi),则根据大数定理，当n足够大时,X在积分域Vd上均匀分布,2.SampleMeanMethod,误差分析：,Thisestimatoris“unbiase

8、d”:,2.SampleMeanMethod,Varianceofthisestimator:,2.SampleMeanMethod,一维积分的情况：,2.SampleMeanMethod,Start,SetN:largeinteger,s=0,xn=(b-a)un+a,yn=g(xn),s=s+yn,EstimatemeanIn=s/N,End,LoopNtimes,2.SampleMeanMethod,Example:,(weknowthattheanswerise3-119.08554),2.SampleMeanMethod,writethisas,whereXunif(0,3),2.S

9、ampleMeanMethod,SimulationResults:true=19.08554,n=100,000,119.10724,219.08260,318.97227,419.06814,519.13261,Simulation,2.SampleMeanMethod,ComparisonofHit-and-MissandSampleMeanMonteCarlo,Letbethehit-and-missestimatorofI,Then,LetbethesamplemeanestimatorofI,2.SampleMeanMethod,ComparisonofHit-and-Missan

10、dSampleMeanMonteCarlo,SamplemeanMonteCarloisgenerallypreferredoverHit-and-MissMonteCarlobecause:,theestimatorfromSMMChaslowervariance,SMMCdoesnotrequireanon-negativeintegrand(oradjustments),H&MMCrequiresthatyoubeabletoputg(x)ina“box”,soyouneedtofigureoutthemaxvalueofg(x)overa,bandyouneedtobeintegrat

11、ingoverafiniteintegral.,MonteCarlo模拟,第四章MonteCarlo积分,Hit-or-MissMethodSampleMeanMethodVarianceReduction:ImportanceSamplingMethodCorrelationmethodsforvariancereduction,3.Variancereduction:ImportanceSamplingMethod,Samplemeanmethod:,减小积分误差的方法：,增大抽样的次数n；减小方差Vh,3.Variancereduction:ImportanceSamplingMetho

12、d,Reducingerror,*100samplesreducestheerrororderof10ReducingvarianceVarianceReductionTechnique,Thevalueofvarianceiscloselyrelatedtohowsamplesaretaken,UnbiasedsamplingBiasedsampling,Morepointsaretakeninimportantpartsofthepopulation,3.Variancereduction:ImportanceSamplingMethod,Ifweareusingsample-meanMo

13、nteCarloMethod,Variancedependsverymuchonthebehaviorofg(x),g(x)varieslittlevarianceissmallg(x)=constvariance=0,Evaluationofaintegral,NearminimumpointscontributelesstothesummationNearmaximumpointscontributemoretothesummationMorepointsaresamplednearthepeak”importancesamplingstrategy”,3.Variancereductio

14、n:ImportanceSamplingMethod,Importancesamplingmethod,Basicidea,PutmorepointsnearmaximumPutlesspointsnearminimum,X的概率密度函数为f(x),3.Variancereduction:ImportanceSamplingMethod,令f(x)为积分域Vd上随机向量X的概率密度函数,设欲求的d-重积分为,3.Variancereduction:ImportanceSamplingMethod,So,wewillestimateIbyestimatingEh(X)with,whereX1,X

15、2,Xnisarandomsamplefromthef(X)distribution.,3.Variancereduction:ImportanceSampleMethod,误差分析：,Thisestimatoris“unbiased”:,3.Variancereduction:ImportanceSampleMethod,Varianceofthisestimator:,3.Variancereduction:ImportanceSampleMethod,一维积分的情况：,3.Variancereduction:ImportanceSampleMethod,Start,SetN:largei

16、nteger,s=0,Generatexnaccordingtof(x),hn=g(xn)/f(xn),Addhntos,I=s1/N,End,LoopNtimes,MonteCarlo模拟,第四章MonteCarlo积分,Hit-or-MissMethodSampleMeanMethodVarianceReduction:ImportanceSamplingMethodCorrelationmethodsforvariancereduction,4.CorrelationmethodsforVariancereduction,Correlationmethod:,Usecorrelatedp

17、ointsinthesamplingtoreducethevarianceoftheintegrandandimprovetheefficiencyoftheestimation,ControlvariatesAntitheticvariables,4.CorrelationmethodsforVariancereduction,Controlvariates,f(x):Controlvariateforg(x),mustsatisfy:,SimpleenoughtoallowanalyticalintegrationShouldmimicg(x)toabsorbmostofitsfluctu

18、ation,f(x)g(x),4.CorrelationmethodsforVariancereduction,第九章MonteCarlo积分,Hit-or-MissMethodSampleMeanMethodVarianceReductionTechniqueVarianceReductionusingRejectionTechniqueImportanceSamplingMethod,VarianceReductionTechnique,Introduction,MonteCarloMethodandSamplingDistributionMonteCarloMethod:Takevalu

19、esfromrandomsampleFromcentrallimittheorem,3sruleMostprobableerrorImportantcharacteristics,VarianceReductionTechnique,Introduction,Reducingerror*100samplesreducestheerrororderof10ReducingvarianceVarianceReductionTechniqueThevalueofvarianceiscloselyrelatedtohowsamplesaretakenUnbiasedsamplingBiasedsamp

20、lingMorepointsaretakeninimportantpartsofthepopulation,VarianceReductionTechnique,Motivation,Ifweareusingsample-meanMonteCarloMethodVariancedependsverymuchonthebehaviorofr(x)r(x)varieslittlevarianceissmallr(x)=constvariance=0EvaluationofaintegralNearminimumpointscontributelesstothesummationNearmaximu

21、mpointscontributemoretothesummationMorepointsaresamplednearthepeak”importancesamplingstrategy”,2.SampleMeanMethod,X1,X2,Xniid-g(X1),g(X2),g(Xn)iid,LetYi=g(Xi)fori=1,2,n,Then,andwecanonceagaininvoketheCLT.,2.SampleMeanMethod,Forn“largeenough”(n30),So,aconfidenceintervalforIisroughlygivenby,butsincewedontknow,wellhavetobecontentwiththefurtherapproximation:,2.SampleMeanMethod,Bytheway,Nooneeversaidthatyouhavetousetheuniformdistribution,Example:,whereXexp(rate=2).,第九章MonteCarlo积分,1.2Hit-or-MissMetho