the curse of dimensionality in integration

The polished quadrature rules — Simpson, Gauss, Romberg — are dazzlingly efficient in one dimension. The obvious way to integrate over a square, a cube, or a 100-dimensional box is to lay down a grid and apply a one-dimensional rule along each axis (a tensor product). In two or three dimensions this works fine. In high dimensions it collapses catastrophically, and that collapse is the curse of dimensionality.

Count the points. A good one-dimensional rule might use m nodes per axis. A tensor-product rule over d dimensions then needs m^d points — the cost grows EXPONENTIALLY in the dimension. With a modest m = 20 nodes per axis, three dimensions costs 8,000 evaluations (fine), but ten dimensions costs 20^10, about 10 trillion, and twenty dimensions is hopeless on any computer that will ever exist. Worse, the achieved accuracy degrades: a rule that is O(m^-p) per axis becomes only O(N^(-p/d)) in terms of the total work N = m^d, so each extra dimension dilutes the convergence rate. High-dimensional integrals arise constantly — in statistical mechanics, Bayesian inference, financial derivatives on many assets, and machine learning — so this is a real and frequent wall.

The curse is exactly why Monte Carlo integration exists and dominates in high dimensions. Monte Carlo estimates the integral by averaging the integrand at random sample points; its error falls like 1/sqrt(N) regardless of the number of dimensions. That 1/sqrt(N) rate is slow and unimpressive in one dimension — where Gauss crushes it — but its INDEPENDENCE from dimension is the whole point: in 50 dimensions a 1/sqrt(N) method that ignores d beats any grid method whose rate is divided by d. Refinements like quasi-Monte Carlo (low-discrepancy sequences) and sparse grids push the frontier further, but the fundamental message stands: above a handful of dimensions, classical tensor-product quadrature is the wrong tool.