Scrambled net variance for integrals of smooth functions (Q1372846): Difference between revisions

Hybrids of quasi-Monte Carlo and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the later. This paper studies the variance of one such hybrid, randomized \((t,m,s)\)-nets, one of the best low-discrepancy sequence, by applying a multidimensional multiresolution (wavelet) analysis to the integrand. For any square integrable integrand over \(s\) dimensions, the integral estimates are unbiased and the variance is \(o(1/n)\). For smooth integrand, the variance is even of order \(n^{-3}n^{-3}(\log n)^{s-1}\), compared to \(n^{-1}\) for classical Monte Carlo method. Thus the integration errors are of order \(n^{-3/2}(\log n)^{(s-1)/2}\) in probability which compares favorably with the rate \(n^{-1}(\log n)^{s-1}\) for the best low-discrepancy sequence. Of course, the rate for randomized \((t,m,s)\)-nets is an average case result for a fixed function, while the rate for the latter describes the worst case over functions, for a fixed set of integration points.