Monte Carlo Integration

Throw darts at a shape and count the hits. Hopeless in one dimension, unbeatable in twenty.

810
darts thrown
estimated area
exact area
error

To get one more decimal place you need a hundred times as many darts. That's the deal.

Throw more darts and watch the error fall — slowly.

What you're looking at

Here is a way to measure an area with no calculus at all. Draw a box you know the area of, scatter points at random inside it, and count what fraction land in your shape. That fraction times the box's area is your answer. It is embarrassingly simple and it works for any shape you can test membership of.

The price is on the graph below. The error falls like 1/√N — the straight line of slope −½ on log-log axes. A hundred times the work buys one extra decimal digit. Against the trapezoid rule in one dimension, which does far better than that, this looks like a terrible bargain.

Except that 1/√N has no dimension in it. A grid rule needs its sample points arranged along every axis, so in d dimensions the cost of a fixed accuracy grows like a power of d — a grid of ten points per axis is a hundred in 2D, a thousand in 3D, and utterly hopeless by the time you reach twenty. Random points don't care. They converge at the same slow, reliable rate whether the problem has two dimensions or two hundred.

That is why financial models, particle physics and machine learning are full of random sampling. Not because it's accurate, but because in high dimensions it is the only thing that still works at all.