Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Statistical properties of generalized discrepancies

Authors: Christine Choirat and Raffaello Seri
Journal: Math. Comp. 77 (2008), 421-446
MSC (2000): Primary 65D30, 60F05, 68U20, 65C05, 11K45
Published electronically: September 12, 2007
MathSciNet review: 2353960
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: When testing that a sample of $ n$ points in the unit hypercube $ \left[0,1\right]^{d}$ comes from a uniform distribution, the Kolmogorov-Smirnov and the Cramér-von Mises statistics are simple and well-known procedures. To encompass these measures of uniformity, Hickernell introduced the so-called generalized $ \mathcal{L}^{p}$-discrepancies. These discrepancies can be used in numerical integration through Monte Carlo and quasi-Monte Carlo methods, design of experiments, uniformity testing and goodness-of-fit tests. The aim of this paper is to derive the statistical asymptotic properties of these statistics under Monte Carlo sampling. In particular, we show that, under the hypothesis of uniformity of the sample of points, the asymptotic distribution is a complex stochastic integral with respect to a pinned Brownian sheet. On the other hand, if the points are not uniformly distributed, then the asymptotic distribution is Gaussian.

References [Enhancements On Off] (What's this?)

  • [Ang83] J.E. Angus, On the asymptotic distribution of Cramér-von Mises one-sample test statistics under an alternative, Comm. Statist. A--Theory Methods 12 (1983), no. 21, 2477-2482. MR 0715177 (85c:62040)
  • [AS87] R.J. Adler and G. Samorodnitsky, Tail behaviour for the suprema of Gaussian processes with applications to empirical processes, Ann. Probab. 15 (1987), no. 4, 1339-1351. MR 0905335 (88j:60073)
  • [CS05a] C. Choirat and R. Seri, The asymptotic distribution of quadratic discrepancies, Monte Carlo and quasi-Monte Carlo methods 2004, 61-76 (D. Talay and H. Niederreiter, eds.), Springer-Verlag, 2006. MR 2208702 (2006k:65006)
  • [CS05b] -, Statistical properties of quadratic discrepancies, Working paper (2005).
  • [Dav94] J. Davidson, Stochastic limit theory, Advanced Texts in Econometrics, The Clarendon Press, Oxford University Press, New York, 1994. MR 1430804 (97k:60002)
  • [Deh89] H. Dehling, Complete convergence of triangular arrays and the law of the iterated logarithm for $ U$-statistics, Statist. Probab. Lett. 7 (1989), no. 4, 319-321. MR 0980708 (90h:60028)
  • [Doo01] J.A. Doornik, Ox: An object-oriented matrix language, 4th ed., Timberlake Consultants Press, London, 2001.
  • [Fin71] H. Finkelstein, The law of the iterated logarithm for empirical distributions, Ann. Math. Statist. 42 (1971), 607-615. MR 0287600 (44:4803)
  • [FMW02] K.-T. Fang, C.-X. Ma, and P. Winker, Centered $ L\sb 2$-discrepancy of random sampling and Latin hypercube design, and construction of uniform designs, Math. Comp. 71 (2002), no. 237, 275-296 (electronic). MR 1863000 (2002h:65024)
  • [FW94] K.-T. Fang and Y. Wang, Number-theoretic methods in statistics, Monographs on Statistics and Applied Probability, vol. 51, Chapman & Hall, London, 1994. MR 1284470 (95g:65189)
  • [GKLZ01] E. Giné, S. Kwapien, R. Lata\la, and J. Zinn, The LIL for canonical $ U$-statistics of order 2, Ann. Probab. 29 (2001), no. 1, 520-557. MR 1825163 (2002k:60083)
  • [HHW03] H.S. Hong, F.J. Hickernell, and G. Wei, The distribution of the discrepancy of scrambled digital $ (t,m,s)$-nets, Math. Comput. Simulation 62 (2003), no. 3-6, 335-345. MR 1988381 (2004e:11080)
  • [Hic96] F.J. Hickernell, Quadrature error bounds with applications to lattice rules, SIAM J. Numer. Anal. 33 (1996), no. 5, 1995-2016. MR 1411860 (97m:65050)
  • [Hic97] -, Erratum: ``Quadrature error bounds with applications to lattice rules'' [SIAM J. Numer. Anal. 33 (1996), no. 5, 1995-2016;], SIAM J. Numer. Anal. 34 (1997), no. 2, 853-866. MR 1442941 (2000h:65042)
  • [Hic98a] -, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299-322. MR 1433265 (98c:65032)
  • [Hic98b] -, Lattice rules: how well do they measure up?, Random and quasi-random point sets, Lecture Notes in Statist., vol. 138, Springer, New York, 1998, pp. 109-166. MR 1662841 (2000b:65007)
  • [Hic99] -, Goodness-of-fit statistics, discrepancies and robust designs, Statist. Probab. Lett. 44 (1999), no. 1, 73-78.MR 1706366
  • [HJK98] J. Hoogland, F. James, and R. Kleiss, Quasi-Monte Carlo, discrepancies and error estimates, Monte Carlo and quasi-Monte Carlo methods 1996 (Salzburg), Lecture Notes in Statist., vol. 127, Springer, New York, 1998, pp. 266-276. MR 1644525 (99d:65070)
  • [HK96a] J. Hoogland and R. Kleiss, Discrepancy-based error estimates for quasi-Monte Carlo. I: General formalism, Comput. Phys. Comm. 98 (1996), no. 1-2, 111-127.
  • [HK96b] -, Discrepancy-based error estimates for quasi-Monte Carlo. II: Results in one dimension, Comput. Phys. Comm. 98 (1996), no. 1-2, 128-136.
  • [HK97] -, Discrepancy-based error estimates for quasi-Monte Carlo. III: Error distribution and central limits, Comput. Phys. Comm. 101 (1997), no. 1-2, 21-30.
  • [JHK97] F. James, J. Hoogland, and R. Kleiss, Multidimensional sampling for simulation and integration: Measures, discrepancies and quasi-random numbers, Comput. Phys. Comm. 99 (1997), no. 2-3, 180-220.
  • [Kal97] O. Kallenberg, Foundations of modern probability, Probability and its Applications (New York), Springer-Verlag, New York, 1997. MR 1464694 (99e:60001)
  • [Kie61] J. Kiefer, On large deviations of the empiric D. F. of vector chance variables and a law of the iterated logarithm, Pacific J. Math. 11 (1961), 649-660. MR 0131885 (24:A1732)
  • [KP90] J. Kim and D. Pollard, Cube root asymptotics, Ann. Statist. 18 (1990), no. 1, 191-219. MR 1041391 (91f:62059)
  • [KW58] J. Kiefer and J. Wolfowitz, On the deviations of the empiric distribution function of vector chance variables, Trans. Amer. Math. Soc. 87 (1958), 173-186. MR 0099075 (20:5519)
  • [Lee96a] H. Leeb, The asymptotic distribution of diaphony in one dimension, GERAD - École des Hautes Études Commerciales, Montréal (1996).
  • [Lee96b] -, A weak law for diaphony, RIST++, Research Institute for Software Technology, University of Salzburg (1996).
  • [Lee02] -, Asymptotic properties of the spectral test, diaphony, and related quantities, Math. Comp. 71 (2002), no. 237, 297-309 (electronic). MR 1863001 (2002j:11086)
  • [LFHL01] J.-J. Liang, K.-T. Fang, F.J. Hickernell, and R. Li, Testing multivariate uniformity and its applications, Math. Comp. 70 (2001), no. 233, 337-355. MR 1680903 (2001f:62032)
  • [LP03] G. Leobacher and F. Pillichshammer, Bounds for the weighted $ L\sp p$ discrepancy and tractability of integration, J. Complexity 19 (2003), no. 4, 529-547. MR 1991981 (2004f:65030)
  • [Nie92] H. Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997 (93h:65008)
  • [Rag73] M. Raghavachari, Limiting distributions of Kolmogorov-Smirnov type statistics under the alternative, Ann. Statist. 1 (1973), 67-73. MR 0346976 (49:11696)
  • [ST96] F. Schmid and M. Trede, An $ L\sb 1$-variant of the Cramér-von Mises test, Statist. Probab. Lett. 26 (1996), no. 1, 91-96. MR 1385667 (97a:62109)
  • [SW86] G.R. Shorack and J.A. Wellner, Empirical processes with applications to statistics, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1986. MR 0838963 (88e:60002)
  • [SW98] I.H. Sloan and H. Wozniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1-33. MR 1617765 (99d:65384)
  • [SWW04] I.H. Sloan, X. Wang, and H. Wozniakowski, Finite-order weights imply tractability of multivariate integration, J. Complexity 20 (2004), no. 1, 46-74. MR 2031558 (2004j:65034)
  • [vdV98] A.W. van der Vaart, Asymptotic statistics, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 1998. MR 1652247 (2000c:62003)
  • [vdVW96] A.W. van der Vaart and J.A. Wellner, Weak convergence and empirical processes, Springer Series in Statistics, Springer-Verlag, New York, 1996. MR 1385671 (97g:60035)
  • [vHKH97] A van Hameren, R. Kleiss, and J. Hoogland, Gaussian limits for discrepancies. I. Asymptotic results, Comput. Phys. Comm. 107 (1997), no. 1-3, 1-20. MR 1488791 (99k:65009)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65D30, 60F05, 68U20, 65C05, 11K45

Retrieve articles in all journals with MSC (2000): 65D30, 60F05, 68U20, 65C05, 11K45

Additional Information

Christine Choirat
Affiliation: Dipartimento di Economia, Università degli Studi dell’Insubria, Via Ravasi 2, 21100 Varese, Italy

Raffaello Seri
Affiliation: Dipartimento di Economia, Università degli Studi dell’Insubria, Via Ravasi 2, 21100 Varese, Italy

Keywords: Generalized discrepancies, testing uniformity, Monte Carlo, quasi--Monte Carlo, limit distribution.
Received by editor(s): October 22, 2004
Received by editor(s) in revised form: May 11, 2005
Published electronically: September 12, 2007
Additional Notes: We thank Peter Hellekalek, Søren Johansen, Peter E. Jupp for useful comments on a previous version of this paper and Kendall E. Atkinson and David E. Edmunds for useful references. We also thank an anonymous referee for comments and suggestions that led to improve the paper.
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society