The mean square discrepancy of randomized nets

Reviewer: Mitchell Snyder

Multidimensional integrals over the S -dimensional unit cube can be approximated by the sample mean of the integral evaluated on a point set, P , with N points. The quadrature error depends in part on how uniformly the points in P are distributed on the unit cube. A good set P for quadrature is one that has a small discrepancy, D P , where discrepancy is defined as a measure of the spread of the points in P . Several deterministic sets have been found that have smaller discrepancies than simple random points. These sets are often called quasi-random points. Much effort has been directed towards finding quasi-random sequences that have asymptotically small L -star discrepancies as N tends to infinity. The t,m,s -nets are one example. Calculating the L -star discrepancy of a particular set is impractical because it requires O N 5 operations. By comparison, the L 2 -star discrepancy is easier to compute, requiring only O N 2 operations using a naive algorithm, or O N log 5 N operations using a more sophisticated algorithm. Recently, a randomization of t,m,s -nets was proposed that preserves their net properties. The aim is to obtain probabilistic quadrature error estimates in a similar manner as one would for simple Monte Carlo quadrature. In this paper, a formula for the mean square L 2 -discrepancy of randomized 0,m,s -nets is derived that requires only O s log N+s 2 mathematical operations as N , s , or both tend to infinity. The L 2 -discrepancy for these randomized nets is shown to decay like O N -1 log N s-1 2 for large N , the same asymptotic order as the known lower bound for the L 2 -discrepancy of an arbitrary set. — From the Introduction The paper consists primarily of mathematical derivations of the expected value of the square of the discrepancy, under various assumptions, as well as asymptotic derivations. The paper is highly mathematical and is readable only by mathematicians with a background in probability theory. It is well structured and, for those readers, should not be difficult to follow. The results should be applicable by people working in the fields of numerical quadrature and differentiation and Monte Carlo simulation, even if they cannot follow the derivations.