Probability & Statistics · Monte Carlo method

Monte Carlo method

A Monte Carlo method estimates a number by random sampling: drop N points independently and uniformly in a unit square, and the share that land in a region estimates its area, with a standard error proportional to 1/√N. Drop points and watch an estimate of π settle, its uncertainty shown all the way.

Monte Carlo method in this visualization

A Monte Carlo method estimates a fixed number by random sampling. Here the number is an area: NN points are dropped uniformly at random in the unit square, HH of them land in a region, and H/NH/N estimates the region’s area aa. The quarter circle has area π/4\pi/4, so 4H/N4H/N estimates π\pi; the region under y=e−x2y = e^{-x^2} turns an integral with no elementary antiderivative into the same kind of count. The lower plot follows the estimate as NN grows to a million, with the range it should fall in 95% of the time.

Why the share estimates the area

A point spread evenly over a square of area 1 lands in a region with probability equal to the region’s area. Each point is an independent trial with that chance, so the share of hits settles towards aa by the law of large numbers. Nothing about the shape matters except the ability to tell whether a point is inside.

How accurate it is

The number of hits is binomial, so the share H/NH/N has standard deviation a(1−a)/N\sqrt{a(1-a)/N}. The typical error shrinks like 1/N1/\sqrt{N}: ten times as many points narrow it by about 10≈3.16\sqrt{10} \approx 3.16, so making it ten times smaller takes about a hundred times as many points; a million points still leave π uncertain by about ±0.003. The true area is not needed to judge this: putting the observed share p^=H/N\hat p = H/N in place of aa gives the range ±1.96p^(1−p^)/N\pm 1.96\sqrt{\hat p(1-\hat p)/N}, an approximate 95% confidence interval, used here once there are at least ten hits and ten misses. If the whole experiment were repeated many times with the same NN, about one range in twenty would miss the true value; the lower plot’s blue funnel is that range around the truth for each NN separately, not a band the whole path must stay in, and a single run’s error does not fall steadily: more points can land a little further from the truth. What shrinks reliably is the range.

When it pays

For a smooth function of one variable, a deterministic rule such as Simpson’s (see numerical integration) is far more accurate for the same number of evaluations. The strength of the Monte Carlo method is that the exponent in its rate, 1/N1/\sqrt{N}, does not change with the number of dimensions, while a grid with mm points per side needs mdm^d points in dd dimensions; in high-dimensional problems it can therefore be the better choice. Its weakness shows with small targets: the standard error relative to the area is (1−a)/(aN)\sqrt{(1-a)/(aN)}, so a region a hundredth of the square needs far more points for the same relative accuracy.

Things to notice

  • Random points are not spread evenly: with a few hundred of them, clusters and empty patches are normal.
  • The points come from a pseudo-random generator with a numbered seed, so a shared link brings back the same points; at a million, Drop points starts again with the next seed.

Related