Monte Carlo integration

Remarks

The density of $X_1$ is $1/V$ on $\Omega$, so $\mathbb E[V f(X_1)] = \int_\Omega f$; this gives clause 1. Clause 2 is the strong law of large numbers for the variables $V f(X_i)$, and clause 4 is the central limit theorem. Clause 3 follows from the variance of a sum of independent random variables. So the root-mean-square error is $V\sigma / \sqrt{n}$; the rate $n^{-1/2}$ does not depend on the dimension $d$ or on the smoothness of $f$. Example: for $f(x) = x^2$ on $\Omega = [0, 1]$ one has $I = 1/3$ and $\sigma^2 = 1/5 - 1/9 = 4/45$, so with $n = 10^4$ the standard error is about $0.003$. In practice $\sigma$ is unknown and is replaced by the sample standard deviation, which gives approximate confidence intervals. Without square-integrability clause 3 fails, and the convergence in clause 2 may be much slower than $n^{-1/2}$.

Going deeper

For a student

This is the basic Monte Carlo method applied to $Y = V f(X)$ with $X$ uniform. In low dimension and for smooth $f$, classical quadrature rules converge much faster than $n^{-1/2}$, so Monte Carlo is mainly useful when $d$ is large or $f$ is rough. Variance reduction techniques, such as importance sampling, control variates and stratification, keep the rate $n^{-1/2}$ but reduce the constant $\sigma$. Quasi-Monte Carlo methods replace the random points by deterministic low-discrepancy points. For functions of bounded variation in the sense of Hardy and Krause, they reach a rate close to $n^{-1}$. Uniform sampling on $\Omega$ is often replaced by sampling from another density, which is the idea of importance sampling.