Quasi-Monte Carlo Methods for Multidimensional Numerical Integration

Abstract

The Monte Carlo approximation to an integral is obtained by averaging values of the integrand at randomly selected nodes. Concretely, if we normalize the integration domain to be \({\bar I^S}\) = [0,1]^s, s ≥ 1, then $$\int\limits_{{{\overline I }^s}} {f\left( {\underline t } \right)} d\underline t \approx \frac{1}{N}\sum\limits_{n = 1}^N {f\left( {{{\underline x }_n}} \right),}$$ (1) where x ₁,..., x _N are N independent random samples from the uniform distribution on \({\bar I^S}\) . The expected value of the integration error is O(N^-½). The basic idea of a quasi-Monte Carlo method is to replace random nodes by well-chosen deterministic nodes, with the aim of getting a deterministic error bound that is smaller than the stochastic error bound under weak regularity conditions on the integrand.