Seminar Details

Seminar Details


Apr 1

3:30 pm

Monte Carlo Meets Quasi-Monte Carlo

Art Owen


Stanford University - Department of Statistics

Hybrids of Quasi-Monte Carlo (equidistribution) and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the latter. This talk considers one such hybrid: randomized (t,m,s)-nets in base b. Integral estimates over randomized nets are unbiassed and have a variance that is o(1/n) for any square integrable integrand. Thus the method is asymptotically superior to Monte Carlo. For the finite n used, the variance is not more than a small multiple of the Monte Carlo variance.

Stronger assumptions on the integrand allow one to find rates of convergence. For smooth integrands over s dimensions, the variance is of order n^{-3}(log n)^{s-1}, compared to n^{-1} for ordinary Monte Carlo. Thus the integration errors are of order n^{-3/2}(log n)^{(s-1)/2} in probability. This compares favorably with the rate n^{-1}(log n)^{s-1} for unrandomized (t,m,s)-nets.