Statistical properties of generalized discrepancies

Choirat, Christine; Seri, Raffaello

doi:10.1090/S0025-5718-07-01839-X

Statistical properties of generalized discrepancies
HTML articles powered by AMS MathViewer

by Christine Choirat and Raffaello Seri;

Math. Comp. 77 (2008), 421-446

DOI: https://doi.org/10.1090/S0025-5718-07-01839-X

Published electronically: September 12, 2007

PDF | Request permission

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

John 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 715177, DOI 10.1080/03610928308828614
Robert J. Adler and Gennady Samorodnitsky, Tail behaviour for the suprema of Gaussian processes with applications to empirical processes, Ann. Probab. 15 (1987), no. 4, 1339–1351. MR 905335
Christine Choirat and Raffaello Seri, The asymptotic distribution of quadratic discrepancies, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 61–76. MR 2208702, DOI 10.1007/3-540-31186-6_{5}
—, Statistical properties of quadratic discrepancies, Working paper (2005).
James Davidson, Stochastic limit theory, Advanced Texts in Econometrics, The Clarendon Press, Oxford University Press, New York, 1994. An introduction for econometricians. MR 1430804, DOI 10.1093/0198774036.001.0001
Herold 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 980708, DOI 10.1016/0167-7152(89)90115-6
J.A. Doornik, Ox: An object-oriented matrix language, 4th ed., Timberlake Consultants Press, London, 2001.
Helen Finkelstein, The law of the iterated logarithm for empirical distributions, Ann. Math. Statist. 42 (1971), 607–615. MR 287600, DOI 10.1214/aoms/1177693410
Kai-Tai Fang, Chang-Xing Ma, and Peter Winker, Centered $L_2$-discrepancy of random sampling and Latin hypercube design, and construction of uniform designs, Math. Comp. 71 (2002), no. 237, 275–296. MR 1863000, DOI 10.1090/S0025-5718-00-01281-3
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, DOI 10.1007/978-1-4899-3095-8
Evarist Giné, Stanislaw Kwapień, RafałLatała, and Joel Zinn, The LIL for canonical $U$-statistics of order 2, Ann. Probab. 29 (2001), no. 1, 520–557. MR 1825163, DOI 10.1214/aop/1008956343
Hee Sun Hong, Fred J. Hickernell, and Gang Wei, The distribution of the discrepancy of scrambled digital $(t,m,s)$-nets, Math. Comput. Simulation 62 (2003), no. 3-6, 335–345. 3rd IMACS Seminar on Monte Carlo Methods—MCM 2001 (Salzburg). MR 1988381, DOI 10.1016/S0378-4754(02)00238-0
Fred J. Hickernell, Quadrature error bounds with applications to lattice rules, SIAM J. Numer. Anal. 33 (1996), no. 5, 1995–2016. MR 1411860, DOI 10.1137/S0036142994261439
Fred J. Hickernell, Erratum: “Quadrature error bounds with applications to lattice rules” [SIAM J. Numer. Anal. 33 (1996), no. 5, 1995–2016; MR1411860 (97m:65050)], SIAM J. Numer. Anal. 34 (1997), no. 2, 853–866. MR 1442941, DOI 10.1137/S0036142997974001
Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299–322. MR 1433265, DOI 10.1090/S0025-5718-98-00894-1
Fred J. Hickernell, Lattice rules: how well do they measure up?, Random and quasi-random point sets, Lect. Notes Stat., vol. 138, Springer, New York, 1998, pp. 109–166. MR 1662841, DOI 10.1007/978-1-4612-1702-2_{3}
Fred J. Hickernell, Goodness-of-fit statistics, discrepancies and robust designs, Statist. Probab. Lett. 44 (1999), no. 1, 73–78. MR 1706366, DOI 10.1016/S0167-7152(98)00293-4
Jiri Hoogland, Fred James, and Ronald Kleiss, Quasi-Monte Carlo, discrepancies and error estimates, Monte Carlo and quasi-Monte Carlo methods 1996 (Salzburg), Lect. Notes Stat., vol. 127, Springer, New York, 1998, pp. 266–276. MR 1644525, DOI 10.1007/978-1-4612-1690-2_{1}7
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.
—, Discrepancy-based error estimates for quasi–Monte Carlo. II: Results in one dimension, Comput. Phys. Comm. 98 (1996), no. 1–2, 128–136.
—, Discrepancy-based error estimates for quasi–Monte Carlo. III: Error distribution and central limits, Comput. Phys. Comm. 101 (1997), no. 1–2, 21–30.
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.
Olav Kallenberg, Foundations of modern probability, Probability and its Applications (New York), Springer-Verlag, New York, 1997. MR 1464694
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 131885
JeanKyung Kim and David Pollard, Cube root asymptotics, Ann. Statist. 18 (1990), no. 1, 191–219. MR 1041391, DOI 10.1214/aos/1176347498
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 99075, DOI 10.1090/S0002-9947-1958-0099075-1
H. Leeb, The asymptotic distribution of diaphony in one dimension, GERAD - École des Hautes Études Commerciales, Montréal (1996).
—, A weak law for diaphony, RIST++, Research Institute for Software Technology, University of Salzburg (1996).
Hannes Leeb, Asymptotic properties of the spectral test, diaphony, and related quantities, Math. Comp. 71 (2002), no. 237, 297–309. MR 1863001, DOI 10.1090/S0025-5718-01-01356-4
Jia-Juan Liang, Kai-Tai Fang, Fred J. Hickernell, and Runze Li, Testing multivariate uniformity and its applications, Math. Comp. 70 (2001), no. 233, 337–355. MR 1680903, DOI 10.1090/S0025-5718-00-01203-5
Gunther Leobacher and Friedrich Pillichshammer, Bounds for the weighted $L^p$ discrepancy and tractability of integration, J. Complexity 19 (2003), no. 4, 529–547. MR 1991981, DOI 10.1016/S0885-064X(03)00009-8
Harald 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, DOI 10.1137/1.9781611970081
M. Raghavachari, Limiting distributions of Kolmogorov-Smirnov type statistics under the alternative, Ann. Statist. 1 (1973), 67–73. MR 346976
Friedrich Schmid and Mark Trede, An $L_1$-variant of the Cramér-von Mises test, Statist. Probab. Lett. 26 (1996), no. 1, 91–96. MR 1385667, DOI 10.1016/0167-7152(95)00256-1
Galen R. Shorack and Jon 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 838963
Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33. MR 1617765, DOI 10.1006/jcom.1997.0463
Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Finite-order weights imply tractability of multivariate integration, J. Complexity 20 (2004), no. 1, 46–74. MR 2031558, DOI 10.1016/j.jco.2003.11.003
A. W. van der Vaart, Asymptotic statistics, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 3, Cambridge University Press, Cambridge, 1998. MR 1652247, DOI 10.1017/CBO9780511802256
Aad W. van der Vaart and Jon A. Wellner, Weak convergence and empirical processes, Springer Series in Statistics, Springer-Verlag, New York, 1996. With applications to statistics. MR 1385671, DOI 10.1007/978-1-4757-2545-2
André van Hameren, Ronald Kleiss, and Jiri Hoogland, Gaussian limits for discrepancies. I. Asymptotic results, Comput. Phys. Comm. 107 (1997), no. 1-3, 1–20. MR 1488791, DOI 10.1016/S0010-4655(97)00105-7