How accurate is Monte Carlo integration?

Its error shrinks like one over the square root of the number of samples, so quadrupling the sample size halves the error. The estimator also comes with a built-in error estimate from the sample standard deviation of the integrand values.

When should I prefer Monte Carlo over standard quadrature?

For low-dimensional smooth integrals deterministic quadrature usually converges faster. Monte Carlo wins in high dimensions, where the cost of a grid grows exponentially but the Monte Carlo error rate stays the same.

Monte Carlo Integration

Monte Carlo integration estimates a definite integral as the average of the integrand over random sample points, recasting integration as the estimation of an expectation.

Definition

Monte Carlo integration is the approximation of an integral by writing it as the expectation of a function under a sampling distribution and estimating that expectation by the sample mean over draws from the distribution.

Scope

This topic covers the representation of an integral as an expectation, the plain (crude) Monte Carlo estimator and its unbiasedness, the root-n convergence rate and its dimension-independence, error estimation through the sample standard deviation, and the comparison with deterministic quadrature. Variance-reduction refinements are treated as extensions covered elsewhere.

Core questions

How is an arbitrary integral expressed as an expectation suitable for sampling?
Why is the crude Monte Carlo estimator unbiased and consistent?
What governs the root-n error rate, and why is it independent of dimension?
When does Monte Carlo integration outperform deterministic quadrature?

Key concepts

Crude Monte Carlo estimator
Unbiasedness
Standard error
Dimension-independence
Sampling density

Key theories

Integral as expectation: Writing an integral as the expectation of the integrand divided by a sampling density turns integration into estimating a mean, which the sample average estimates without bias.
Convergence rate and error estimation: The central limit theorem gives a standard error proportional to one over the square root of the sample size, independent of the integral's dimension, and the empirical standard deviation of the summands provides a usable error estimate.

Clinical relevance

Monte Carlo integration computes normalizing constants, posterior expectations, marginal likelihoods and high-dimensional expectations that arise throughout statistics and the physical sciences; its dimension-independent error rate makes it the method of choice where grid-based quadrature becomes infeasible.

History

The idea of estimating integrals by sampling dates to the 1940s Los Alamos computations and the 1949 paper of Metropolis and Ulam; it became routine practice as computing power grew and as statisticians recognized its advantage over quadrature in high dimensions.

Key figures

Stanislaw Ulam
Nicholas Metropolis
Christian P. Robert

Seminal works

robert2004
metropolis1949

Frequently asked questions

How accurate is Monte Carlo integration?: Its error shrinks like one over the square root of the number of samples, so quadrupling the sample size halves the error. The estimator also comes with a built-in error estimate from the sample standard deviation of the integrand values.
When should I prefer Monte Carlo over standard quadrature?: For low-dimensional smooth integrals deterministic quadrature usually converges faster. Monte Carlo wins in high dimensions, where the cost of a grid grows exponentially but the Monte Carlo error rate stays the same.