Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Ex 1: Monte Carlo integration in one dimension
Function to integrate and domain
In[1]:= g@x_D := HE-x Sin@xDL3
DistributeDefinitions@gD;xMin = 0; xMax = 10;
In[4]:= Plot@g@xD, 8x, xMin, xMax<, PlotRange ® FullD
Out[4]=
2 4 6 8 10
0.005
0.010
0.015
0.020
0.025
0.030
Exact value of the integral. Good to know in order to compare the accuracy of the MC algorithms.
In[5]:= Integrate@g@xD, 8x, 0, 10<D �� FullSimplifyN@%D
Out[5]=1
1204 +
-9 Cos@10D + 5 Cos@30D - 27 Sin@10D + 5 Sin@30D
ã30
Out[6]= 0.0333333
Mode of g(x). Happens to be nearly the integral
In[7]:= Solve@D@g@xD, xD � 0, 8x<Dg@xD �. %@@3DDH* only maximum *Lmode = % �� N
Solve::ifun :Inverse functions are being used by Solve, so some solutions may not be found;
use Reduce for complete solution information. �
Out[7]= 98x ® 0<, 9x ® -3 Π
4=, 9x ®
Π
4=, 8x ® Π<=
Out[8]=ã-3 Π�4
2 2
Out[9]= 0.0335099
Hit or Miss
flat cover. Defined only for the domain
In[10]:= Clear@coverHitD;coverHit@x_D := mode �; Hx ³ xMin && x £ xMax LcoverHit@-1DcoverHit@+2D
Out[12]= coverHit@-1D
Out[13]= 0.0335099
In[14]:= Plot@8g@xD, coverHit@xD<, 8x, xMin, xMax<D
Out[14]=
2 4 6 8 10
0.005
0.010
0.015
0.020
0.025
0.030
Find the zeros of g(x) to divide integral into parts over domains of fixed sign. It occurs at multiples of x=Π. For x>Π, the contribu-tion to the integral is negligible though. Neglecting x>Π will dramatically increase the acceptance ratio, thus efficiency, of ouralgorithm.
In[15]:= Map@g, 80 Π, 1 Π, 2 Π, 3 Π<DPlot@g@xD - Abs@g@xDD, 8x, 0, 10<, PlotRange ® FullDxMax = Π;Integrate@g@xD, 8x, 0, Π<D �� FullSimplifyIcorrect = N@%D
Out[15]= 80, 0, 0, 0<
Out[16]=
2 4 6 8 10
-5. ´ 10-6
-4. ´ 10-6
-3. ´ 10-6
-2. ´ 10-6
-1. ´ 10-6
Out[18]=1
30I1 + ã-3 ΠM
Out[19]= 0.033336
SeedRandom@234D;
integral over constant cover is easy
2 Session08.nb
In[30]:= coverIntegral = HxMax - xMinL * coverHit@xMinD
Out[30]= 0.105274
In[33]:= acceptedSamples = 8<;
hitOrMiss@D := ModuleB
8error, r, ratio, x, nAccepted, nTrials, EstimatesError, EstimatesIntegral, nTrialsMin<,H* start with maximum error *Lerror = 1;H* ration of I�coverArea *L
r = 10-6;H* keep track of run duration *LnTrials = 0;nAccepted = 0;EstimatesError = 8<;EstimatesIntegral = 8<;H* minimum number of trials *LnTrialsMin = 100;H* loop for at least 100 trials, but quit if relative error less than 1% *L
WhileBerror � r ³ 1 � 100 ÈÈ nTrials < nTrialsMin,
H* position in @0,ΠD *Lx = RandomReal@ΠD;
ratio =g@xD
coverHit@xD;
nTrials++;H* accept or reject point *LIf@RandomReal@D < ratio,nAccepted++;
D;H* update integral estimate *L
r =nAccepted + 1
nTrials + 1;
AppendTo@EstimatesIntegral, rD;H* update error estimate *L
error = SqrtBr H1 - rL1
nTrials + 3F;
AppendTo@ EstimatesError, errorD
F;
Return@8EstimatesIntegral, EstimatesError<D;
F
results = hitOrMiss@D �� N;Last@results@@1DDDLast@results@@2DDD
Out[36]= 0.314861
Out[37]= 0.00314832
the cover area
In[38]:= coverArea = coverHit@1D * Π
Out[38]= 0.105274
In[39]:= H* the correct ratio *L
Session08.nb 3
In[40]:= correctRatio =
1
30I1 + ã-3 ΠM
coverArea
correctRatioH1 - correctRatioL
Icorrect * 1 � 100- 3
Out[40]= 0.316659
Out[41]= 646.105
Translatio ratio into estimate for the integral
EstimatesIntegral = results@@1DD * coverArea;EstimatesError = results@@2DD * coverArea;Last@EstimatesIntegralDLast@EstimatesErrorD
Out[42]= 21761
Out[45]= 0.0331468
Out[46]= 0.000331438
Total number of iterations (= evaluations of g) needed to converge
In[104]:= Length@results@@1DD D
Out[104]= 624
Look at the rate convergence
In[47]:= Show@ListLogLinearPlot@EstimatesIntegral,PlotRange ® 80, 0.1<, AxesLabel ® 8"Iteration", "I"<D,
Plot@Icorrect, 8x, 1, Length@results@@1DDD<, PlotStyle ® RedDD
Out[47]=
1 10 100 1000 104Iteration
0.02
0.04
0.06
0.08
0.10I
The error estimate shows the usual 1
N scaling. The actual error is the random walk zig zag around the true value.
4 Session08.nb
In[48]:= Show@ListLogLinearPlot@EstimatesError,PlotRange ® 8-.05, .05<, AxesLabel ® 8"Iteration", "DI"<D,
ListLogLinearPlot@EstimatesIntegral - Icorrect, PlotStyle ® RedD,Plot@0, 8x, 1, Length@results@@1DDD<, PlotStyle ® GreenD
D
Out[48]=
1 10 100 1000 104Iteration
-0.04
-0.02
0.00
0.02
0.04
DI
In[49]:= PlotB1
x, 8x, 1, Length@results@@1DDD<, PlotStyle ® Red, AxesOrigin ® 80, 0<F
Out[49]=
5000 10 000 15 000 20 000
0.005
0.010
0.015
0.020
0.025
Sample mean. Generate according to flat distribution f HxL =1
10-0
Now we integrate over the full domain from 0 to 10 again.
Session08.nb 5
In[95]:= xMax = 10;
sampleMean@D := ModuleB8error, I, ratios, nTrials, EstimatesError, EstimatesIntegral,
nTrialsMin, nTrialsMax, runningSum, nBatchIterations, batchMeans, fun<,H* start with maximum error *Lerror = 1;H* integral estimate *LI = 0;runningSum = 0;H* keep track of run duration *LnTrials = 0;EstimatesIntegral = 8<;H* store batch means and overall mean *LEstimatesError = 8<;batchMeans = 8<;nBatchIterations = 100; DistributeDefinitions@nBatchIterationsD;H* minimum number of trials *L
nTrialsMin = 1 ´ 103;nTrialsMax = 1 ´ 105;
H* function to evaluate in each iteration *Lfun@x_D := g@xD * xMax;DistributeDefinitions@funD;H* loop for at least 1000 trials, but quit if relative error less than 1% *LH* nBatchIterations at a time, then update integral and uncertainty estimates *L
WhileB nTrials < nTrialsMax && HnTrials < nTrialsMin ÈÈ error � I ³ 1 � 100L,
H* batch update *LH* look at positions in @0,10D *Lratios = ParallelMap@fun,
Table@RandomReal@xMaxD, 8nBatchIterations<D, Method ® "CoarsestGrained"D;nTrials += nBatchIterations;
H* update integral estimate *LrunningSum += Total@ratiosD;
I =runningSum
nTrials;
AppendTo@EstimatesIntegral, ID;H* update error estimate *L
H* mean of last 100 iterations *LAppendTo@batchMeans, Mean@ratiosD D;H* estimate the error from variance of the batch mean values *Lerror = If@Length@batchMeansD == 1,
1,Sqrt@ Variance@batchMeansD � Length@batchMeansDD
D;AppendTo@ EstimatesError, errorD
F;
Return@8EstimatesIntegral, EstimatesError<D;
F
results = sampleMean@D;Length@results@@1DD DEstimatesIntegral = results@@1DD ;EstimatesError = results@@2DD ;Last@EstimatesIntegralDLast@EstimatesErrorD
Out[98]= 624
6 Session08.nb
Out[101]= 0.0329983
Out[102]= 0.00032959
Total number of iterations (= evaluations of f and g) needed to converge
In[103]:= Length@EstimatesIntegral D * 100
Out[103]= 62400
convergence
In[61]:= Show@ListLogLinearPlot@EstimatesIntegral,PlotRange ® 80, 0.1<, AxesLabel ® 8"Batch Iteration", "I"<D,
Plot@Icorrect, 8x, 1, Length@results@@1DDD<, PlotStyle ® RedDD
Out[61]=
1 5 10 50 100 500Batch Iteration
0.02
0.04
0.06
0.08
0.10I
The error estimate (blue) shows the usual 1
N scaling. The actual error is the random walk zig zag (red) around the true value.
In[62]:= Show@ListLogLinearPlot@EstimatesError,PlotRange ® 8-.01, .01<, AxesLabel ® 8"Batch Iteration", "DI"<D,
ListLogLinearPlot@EstimatesIntegral - Icorrect, PlotStyle ® RedD,Plot@0, 8x, 1, Length@results@@1DDD<, PlotStyle ® GreenD
D
Out[62]=
1 5 10 50 100 500Batch Iteration
-0.005
0.000
0.005
0.010DI
Session08.nb 7
Importance sampling: now RN from a distribution f(x) that is close to g(x), the function to integrate
In[63]:= normConstant = IntegrateAE-3 x, 8x, 0, 10<E
Clear@fD
f@x_D := 1 � normConstant * E-3 x
Out[63]=1
3-
1
3 ã30
In[66]:= PlotBE3 z - E-3
E3 - E-3, 8z, 0, 10<F
Out[66]=
2 4 6 8 10
1 ´ 109
2 ´ 109
3 ´ 109
4 ´ 109
5 ´ 109
6 ´ 109
In[67]:=
the CDF
In[68]:= Integrate@f@xD, 8x, 0, z<D �� SimplifySolve@% � u, zD
Out[68]=
ã30-3 z I-1 + ã3 zM
-1 + ã30
Solve::ifun :Inverse functions are being used by Solve, so some solutions may not be found;
use Reduce for complete solution information. �
Out[69]= ::z ®1
330 - LogBI-1 + ã30M -
ã30
1 - ã30- u F >>
Use inverse transform method to generate RV according to f(x)
In[70]:= fGenerator@D := ModuleB8u<,
u = RandomReal@D;
ReturnB1
330 - LogBI-1 + ã30M -
ã30
1 - ã30- u F F;
F;
DistributeDefinitions@fGeneratorD;fGenerator@D
Out[72]= 1.05227
Random numbers look OK
8 Session08.nb
Random numbers look OK
In[73]:= Show@Histogram@Table@fGenerator@D, 810 000<D , 80.02<D,Plot@10000 * f@xD * 0.02, 8x, 0, 2<, PlotStyle ® RedD
D
Out[73]=
0.5 1.0 1.5 2.0 2.5 3.0 3.5
100
200
300
400
500
600
Just copied from sample mean with two changes marked by (* UPDATE *)
Session08.nb 9
In[116]:= xMax = 10;
importanceSampling@D := ModuleB8error, I, ratios, nTrials, EstimatesError, EstimatesIntegral,
nTrialsMin, nTrialsMax, runningSum, nBatchIterations, batchMeans, fun<,H* start with maximum error *Lerror = 1;H* integral estimate *LI = 0;runningSum = 0;H* keep track of run duration *LnTrials = 0;EstimatesIntegral = 8<;H* store batch means and overall mean *LEstimatesError = 8<;batchMeans = 8<;nBatchIterations = 100; DistributeDefinitions@nBatchIterationsD;H* minimum number of trials *L
nTrialsMin = 1 ´ 103;nTrialsMax = 1 ´ 105;
H* function to evaluate in each iteration *L
fun@x_D :=g@xD
f@xD; H* UPDATE *L
DistributeDefinitions@funD;H* loop for at least 100 trials, but quit if relative error less than 1% *L
WhileB nTrials < nTrialsMax && HnTrials < nTrialsMin ÈÈ error � I ³ 1 � 100L,
H* batch update *LH* look at positions in @0,10D *Lratios = ParallelMap@fun, Table@fGenerator@D, H* UPDATE *L
8nBatchIterations<D, Method ® "CoarsestGrained"D;nTrials += nBatchIterations;
H* update integral estimate *LrunningSum += Total@ratiosD;
I =runningSum
nTrials;
AppendTo@EstimatesIntegral, ID;H* update error estimate *L
H* mean of last 100 iterations *LAppendTo@batchMeans, Mean@ratiosD D;H* estimate the error from variance of the batch mean values *Lerror = If@Length@batchMeansD == 1,
1,Sqrt@ Variance@batchMeansD � Length@batchMeansDD
D;AppendTo@ EstimatesError, errorD
F;
Return@8EstimatesIntegral, EstimatesError<D;
F
results = importanceSampling@D;
EstimatesIntegral = results@@1DD ;EstimatesError = results@@2DD ;Last@EstimatesIntegralDLast@EstimatesErrorD
Out[121]= 0.0332259
10 Session08.nb
Out[122]= 0.000331765
Total number of iterations needed to converge
In[112]:= Length@EstimatesIntegral D * 100
Out[112]= 34800
In[113]:= Show@ListLogLinearPlot@EstimatesIntegral,PlotRange ® 80, 0.05<, AxesLabel ® 8"Batch Iteration", "I"<D,
Plot@Icorrect, 8x, 1, Length@results@@1DDD<, PlotStyle ® RedDD
Out[113]=
1 5 10 50 100Batch Iteration
0.01
0.02
0.03
0.04
0.05I
In[114]:= Show@ListLogLinearPlot@EstimatesError,PlotRange ® 8-.01, .01<, AxesLabel ® 8"Batch Iteration", "DI"<D,
ListLogLinearPlot@EstimatesIntegral - Icorrect, PlotStyle ® RedD,Plot@0, 8x, 1, Length@results@@1DDD<, PlotStyle ® GreenD
D
Out[114]=
1 5 10 50 100Batch Iteration
-0.005
0.000
0.005
0.010DI
The uncertainty band contains the true value, but not at the beginning.
Session08.nb 11
In[115]:= Show@ListLogLinearPlot@EstimatesIntegral + EstimatesError,PlotRange ® 80.02, 0.05<, AxesLabel ® 8"Batch Iteration", "I"<D,
ListLogLinearPlot@EstimatesIntegral - EstimatesErrorD,Plot@Icorrect, 8x, 1, Length@results@@1DDD<, PlotStyle ® RedD
D
Out[115]=
1 5 10 50 100Batch Iteration
0.025
0.030
0.035
0.040
0.045
0.050I
Comparison between the three methodsè Uncertainty estimate using Bayes theorem well behaved
è variance estimate from batches crude. Tends to declare converge much later ( safe alternative)
è importance sampling can save about 1/3 of iterations compared to simple sample-mean. But remember: generating RV ~ f(x) takes time as well
Ex 2. Unit hypersphere in 6 dimensions
volume of hypersphere [wikipedia.org]
In[85]:= vol@n_D :=Πn�2
GammaAn
2+ 1E
vol@6D
Out[86]=Π3
6
12 Session08.nb