Monte Carlo methods
Estimate π by throwing random darts at a circle inscribed in a square. Watch convergence. Then estimate integrals by sampling — the brute-force method that solves the unsolvable.
π ≈ 4 · (points inside circle) / (total points) Error ∝ 1/√n
The idea
Monte Carlo methods use randomness to solve deterministic problems. The name comes from the Monte Carlo Casino in Monaco — a nod to the role of chance. The technique was formalized during the Manhattan Project by Stanislaw Ulam and John von Neumann, who needed to simulate neutron diffusion through shielding materials and found that random sampling worked where analytical methods failed.
Estimating π
Inscribe a circle of radius 1 inside a 2×2 square. The area of the circle is π, the area of the square is 4, so the ratio is π/4. Throw random darts uniformly at the square and count what fraction land inside the circle. Multiply by 4 and you have an estimate of π. The more darts, the better the estimate — but convergence is slow.
The 1/√n convergence rate
The error of a Monte Carlo estimate decreases as 1/√n, where n is the number of samples. To get one more decimal digit of accuracy, you need 100 times more samples. This is terrible for computing π (there are far better algorithms), but the convergence rate does not depend on dimensionality — which is why Monte Carlo methods dominate in high dimensions, where grid-based methods become exponentially expensive.
Monte Carlo integration
To estimate ∫f(x)dx over [a,b], sample random points in the bounding rectangle. The integral is approximately the area of the rectangle times the fraction of points that fall under the curve. This works for any function, no matter how irregular — no need for antiderivatives, Taylor series, or regularity conditions. In higher dimensions, this is often the only practical method.
Applications
Monte Carlo methods are used in physics (particle transport, statistical mechanics), finance (option pricing, risk analysis), computer graphics (path tracing, global illumination), machine learning (MCMC sampling), and any field where the integral is too complex to solve analytically. The Metropolis algorithm, a Monte Carlo method, was named one of the top 10 algorithms of the 20th century.