The mean square discrepancy of randomized nets

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 L2-discrepancy of (0, m, s)-nets in base b is derived. This formula has a computational complexity of only O(s log(N) + s2) for large N or s, where N = bm is the number of points. Moreover, the root mean square L2-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 L2-discrepancy of an arbitrary set.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: FAURE, H. 1982. Discr~pance de suites associ~es f~ un systame de numeration (en dimension s). Acta Arith. 41, 337-351.
• 3: S. Heinrich, Efficient algorithms for computing the L2-discrepancy, Mathematics of Computation, v.65 n.216, p.1621-1633, Oct. 1996 [doi>10.1090/S0025-5718-96-00756-9]
• 4: Fred J. Hickernell, Quadrature Error Bounds with Applications to Lattice Rules, SIAM Journal on Numerical Analysis, v.33 n.5, p.1995-2016, Oct. 1996 [doi>10.1137/S0036142994261439]
• 5: Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Mathematics of Computation, v.67 n.221, p.299-322, Jan. 1998 [doi>10.1090/S0025-5718-98-00894-1]
• 6: KUIPERS, L., AND NIEDERREITER, H. 1974. Uniform Distribution of Sequences. Wiley, New York.
• 7: William J. Morokoff , Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM Journal on Scientific Computing, v.15 n.6, p.1251-1279, Nov. 1994 [doi>10.1137/0915077]
• 8: NIEDERREITER, H. 1978. Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Sac. 84, 957-1041.
• 9: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 10: OWEN, A. B. 1995. Equidistributed Latin hypercube samples. In Monte Carlo and Quasi- Monte Carlo Methods in Scientific Computing. Lecture Notes in Statistics, Vol. 106. Springer-Verlag, New York, 299-317.
• 11: Art B. Owen, Monte Carlo Variance of Scrambled Net Quadrature, SIAM Journal on Numerical Analysis, v.34 n.5, p.1884-1910, Oct. 1997 [doi>10.1137/S0036142994277468]
• 12: OWEN, A.B. 1997b. Scrambled net variance for integrals of smooth functions. Ann. Stat. 25 (to appear).
• 13: PRUDNIKOV, A. P., BRYCIIKOV, Y. A., AND MARICIIEV, O.I. 1986. Integrals and Series. Gordon and Breach, New York.
• 14: RITTER, K. 1995. Average case analysis of numerical problems. Ph.D. dissertation, Universitiit Erlangen-Nfirnberg, Erlangen, Germany.
• 15: ROTH, K.F. 1954. On irregularities of distribution. Mathematika 1, 73-79.
• 16: SACKS, J., AND YLVISACKER, D. 1970. Statistical design and integral approximation. In Proceedings of the 12th Biennial Canadian Math Congress. Canadian Math Society, Montreal, Canada, 115-136.
• 17: SLOAN, I. H., AND JOE, S. 1994. Lattice Methods for Multiple Integration. Oxford University Press, Oxford, England.
• 18: SOBOL', I. M. 1969. Multidimensional quadrature formulas and Hoar functions. Izdat "Nauka," Moscow (in Russian).
• 19: WARNOCK, T. T. 1972. Computational investigations of low discrepancy point sets. In Applications af Number Theory to Numerical Analysis. Academic Press, Orlando, Fla., pp. 319-343.
• 20: WOZNIAKOWSKI, H. 1991. Average case complexity of multivariate integration. Bull. Amer. Math. Sac. 24, 185-194.
• 21: ZAREMBA, S. K. 1968. Some applications of multidimensional integration by parts. Ann. Palan. Math. 21, 85-96.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Monte Carlo

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Error analysis
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Performance, Theory

Keywords:
multidimensional integration, number-theoretic nets and sequences, quadrature, quasi-Monte Carlo methods, quasi-random sets