Quasi-Monte Carlo integration (Q1908724)

Monte Carlo methods for multidimensional integration using random (pseudo-random) and quasi-random nodes are compared both through error analysis and extensive numerical computations. Known error expressions in terms of variance, discrepancy and variation are reviewed, and the expected advantages of some quasi-random nodes (Halton, Sobol', Faure) of low discrepancy are investigated numerically. Convergence like \(N^{-\alpha}({1\over 2}\leq \alpha\leq 1)\) for \(N\) points is found empirically for problems with widely differing characteristics and dimension \(s\). The authors find that the integrand's variation is not a useful indicator of error in these practical problems, but that its variance, the determining factor for random Monte Carlo analysis, can often provide a rough bound. The general conclusion is that quasi-Monte Carlo methods are superior to random Monte Carlo, but the advantages can sometimes be slight, especially for higher dimensions or non-smooth integrands. For discontinuous integrands an error bound is found suggesting that behaviour better than \(\alpha=s/(2s-1)\) cannot be counted on even when using nodes of low discrepancy.