The mean square discrepancy of randomized nets
- 1 October 1996
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 6 (4) , 274-296
- https://doi.org/10.1145/240896.240909
Abstract
One popular family of low dicrepancy sets is the ( t, m, s )-nets. Recently a randomization of these nets that preserves their net property has been introduced. In this article a formula for the mean square L 2 -discrepancy of ( 0, m, s )-nets in base b is derived. This formula has a computational complexity of only O(s log( N ) + s 2 ) for large N or s, where N = b m is the number of points. Moreover, the root mean square L 2 -discrepancy of ( 0, m, s )-nets is show to be O( N -1 [log(N)] (s-1)/2 ) as N tends to infinity, the same asymptotic order as the known lower bound for the L 2 -discrepancy of an arbitrary set.Keywords
This publication has 13 references indexed in Scilit:
- A generalized discrepancy and quadrature error boundMathematics of Computation, 1998
- Monte Carlo Variance of Scrambled Net QuadratureSIAM Journal on Numerical Analysis, 1997
- Scrambled net variance for integrals of smooth functionsThe Annals of Statistics, 1997
- Quadrature Error Bounds with Applications to Lattice RulesSIAM Journal on Numerical Analysis, 1996
- Efficient algorithms for computing the $L_2$-discrepancyMathematics of Computation, 1996
- Quasi-Random Sequences and Their DiscrepanciesSIAM Journal on Scientific Computing, 1994
- Random Number Generation and Quasi-Monte Carlo MethodsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1992
- Discrépance de suites associées à un système de numération (en dimension s)Acta Arithmetica, 1982
- Quasi-Monte Carlo methods and pseudo-random numbersBulletin of the American Mathematical Society, 1978
- On irregularities of distributionMathematika, 1954