Quasi-Monte Carlo Beyond Hardy-Krause

We examine the problem of numerically estimating the integral of a function f . The classical approaches to this problem are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate f and have error O(σ(f )/ √ n), where σ(f ) is the standard deviation of f . QMC methods are based on evaluating f at explicit point sets with low discrepancy, and as given by the classical Koksma-Hlawka inequality, they have error O(σ HK (f )/n), where σ HK (f ) is the variation of f in the sense of Hardy and Krause. These two methods have distinctive advantages and shortcomings, and a fundamental question is to find a method that combines the advantages of both.

In this work, we give a simple randomized algorithm that produces QMC point sets with the following desirable features:

1. It achieves substantially better error than given by the classical Koksma-Hlawka inequality.

In particular, it has error O(σ SO (f )/n), where σ SO (f ) is a new measure of variation that we introduce, which is substantially smaller than the Hardy-Krause variation.

2. The algorithm only requires random samples from the underlying distribution, which makes it as flexible as MC.

3. It automatically achieves the best of both MC and QMC (and the above improvement over Hardy-Krause variation and Koksma-Hlawka inequality) in an optimal way.