Quasi-Monte Carlo method

Summary

A quasi-Monte Carlo method approximates an integral over the unit cube $[0, 1]^s$ by an average of the integrand at deterministic points. The points are spread evenly: they come from a low-discrepancy sequence. It keeps the simple form of Monte Carlo integration, an equal-weight average, but replaces random points by structured ones. For integrands of bounded variation, the Koksma–Hlawka inequality bounds the error by the variation of the integrand times the discrepancy of the points. This gives an error of order $(\log N)^s / N$ instead of $N^{-1/2}$. Quasi-Monte Carlo methods are widely used in computational finance and in high-dimensional integration.