Interactive demo · Probability and Statistical Inference · Chapter 24

Monte Carlo integration: the error shrinks like 1/√N

To compute an integral I = Ef w(X), draw X1, …, XN from f and average the w(Xi). The law of large numbers makes the average converge to I; the central limit theorem says the error is about σ/√N and Normal, whatever the dimension. Top left: one run, with its estimated 95% interval, as N grows. Top right: the spread of many independent runs against the exact σ/√N (log scales: a line of slope −1/2). Bottom: the estimates of all runs at the chosen N against their Normal approximation, and the 95% intervals of the first runs.

Integral

Sample size N

Point x (Example 24.2)

Independent runs R

Try these

Each run is a separate seeded stream of uniforms; Normal draws use the Box-Muller transform. The standard error of a run is s/√N with s2 the sample variance of the w(Xi), and its interval is the estimate ± 1.96 standard errors. In Example 24.3 a Beta(k, n − k + 1) draw is the k-th smallest of n uniforms. When R × N is very large the number of runs is reduced so that the page stays responsive (the readout says so).

In the lecture notes