Mathematics of Computation

Author(s): Hannes Leeb.
Journal: Math. Comp. 71 (2002), 297-309.
MSC (2000): Primary 65D30, 11K06, 11K45, 60F05, 60G35
Posted: August 2, 2001
Retrieve article in: PDF
This article is available free of charge

This paper presents the limit laws of discrepancies defined via exponential sums, and algorithms (with error bounds) to approximate the corresponding distribution functions. The results cover the weighted and the nonweighted spectral test of Hellekalek and various instances of the general discrepancies of Hickernell and Hoogland and Kleiss for the exponential function system, as well as classical quantities like the spectral test, diaphony, and the Zaremba figure of merit.

1.: M. J. Buckley and G. K. Eagleson. An approximation to the distribution of quadratic forms in normal random variables. Austral. J. Statist., 30A:150-159, 1988.
2.: R. R. Coveyou and R. D. MacPherson. Fourier analysis of uniform random number generators. J. Assoc. Comput. Mach., 14:100-119, 1967. MR 36:4779
3.: R. Cranley and T. N. L. Patterson. Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal., 13:904-914, 1976. MR 58:13605
4.: R. W. Farebrother. The distribution of a quadratic form in normal variables. J. Royal Statist. Soc. C, 39:294-309, 1990.
5.: H. Faure. Discrépance et diaphonie en dimension un. In Advances in number theory (Kingston, ON, 1991), Oxford Sci. Publ., pages 411-419. Oxford Univ. Press, New York, 1993. MR 97d:11115
6.: K. Frank and S. Heinrich. Computing discrepancies related to spaces of smooth periodic functions. In Monte Carlo and quasi-Monte Carlo methods 1996 (Harald Niederreiter et al., eds.), Lecture Notes in Stat., Vol. 127, pages 238-250. Springer, New York, 1997. MR 99g:65026
7.: V. S. Grozdanov. On the diaphony of two-dimensional finite sequences. C. R. Acad. Bulgare Sci., 48:15-18, 1995. MR 97d:11116
8.: S. Heinrich. Efficient algorithms for computing the ${L}\sb 2$ -discrepancy. Math. Comp., 65:1621-1633, 1996. MR 97a:65024
9.: P. Hellekalek. On the assessment of random and quasi-random point sets. In Random and quasi-random point sets (Peter Hellekalek et al., eds), Lecture Notes in Stat., Vol. 138, pages 49-108. Springer, New York, 1998. MR 2000c:11127
10.: P. Hellekalek and H. Leeb. Dyadic diaphony. Acta Arith., 80:187-196, 1997. MR 98g:11090
11.: P. Hellekalek and H. Niederreiter. The weighted spectral test: diaphony. ACM Trans. Modeling and Computer Simulation, 8:43-60, 1998.
12.: F. J. Hickernell. A generalized discrepancy and quadrature error bound. Math. Comp., 67:299-322, 1998. MR 98c:65032
13.: F. J. Hickernell. Lattice rules: how well do they measure up? In Random and quasi-random point sets (Peter Hellekalek et al., eds.), Lecture Notes in Stat., Vol. 138, pages 109-166. Springer, New York, 1998. MR 2000b:65007
14.: J. Hoogland and R. Kleiss. Discrepancy-based error estimates for quasi-Monte Carlo. I: general formalism. Comp. Phys. Comm., 98:111-127, 1996.
15.: J. Hoogland and R. Kleiss. Discrepancy-based error estimates for quasi-Monte Carlo. II: results for one dimension. Comp. Phys. Comm., 98:128-136, 1996.
16.: H. Leeb. Weak limits for diaphony. In Monte Carlo and quasi-Monte Carlo methods 1996 (Harald Niederreiter et al., eds.), Lecture Notes in Stat., Vol. 127, pages 330-339. Springer, New York, 1997. MR 99i:11062
17.: J. J. Liang, K. T. Fang, F. J. Hickernell, and R. Z. Li. Testing multivariate uniformity and its applications. Math. Comp. 70:337-355, 2001. MR 2001f:62032
18.: M. B. Marcus and G. Pisier. Random Fourier series with applications to harmonic analysis, volume 101 of Annals of Mathematics Studies. Princeton University Press, Princeton, N.J., 1981. MR 83b:60031
19.: A. B. Owen. Randomly permuted -nets and -sequences. In Monte Carlo and quasi-Monte Carlo methods in scientific computing (Harald Niederreiter et al., eds.), Lecture Notes in Stat., Vol. 106, pages 299-317. Springer, New York, 1995. MR 97k:65013
20.: A. B. Owen. Monte Carlo variance of scrambled equidistribution quadrature. SIAM J. Numer. Anal., 34:1884-1910, 1997. MR 98j:65006
21.: A. B. Owen. Scrambled net variance for integrals of smooth functions. Ann. Stat., 25:1541-1562, 1997. MR 98j:65004
22.: D. Pollard. Convergence of Stochastic Processes. Springer Series in Statistics. Springer, New York, 1984. MR 86i:60074
23.: A. van Hameren, R. Kleiss, and J. Hoogland. Gaussian limits for discrepancies. I: Asymptotic results. Comp. Phys. Comm., 107:1-20, 1997. MR 99k:65009
24.: P. Zinterhof. Über einige Abschätzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden. Sitzungsber. Österr. Akad. Wiss. Math.-Natur. Kl. II, 185:121-132, 1976. MR 58:19037
25.: P. Zinterhof and H. Stegbuchner. Trigonometrische Approximation mit Gleichverteilungsmethoden. Stud. Sci. Math. Hungar., 13:273-289, 1978. MR 83a:10088

Hannes Leeb
Affiliation: Department of Statistics, University of Vienna, Universitätsstrasse 5, A-1010 Vienna, Austria
Email: hannes.leeb@univie.ac.at

DOI: 10.1090/S0025-5718-01-01356-4
PII: S 0025-5718(01)01356-4
Keywords: Monte Carlo sequences, quasi-Monte Carlo sequences, equidistribution modulo one, limit distribution
Received by editor(s): September 9, 1999
Received by editor(s) in revised form: May 5, 2000
Posted: August 2, 2001
Additional Notes: Research supported by the Austrian Science Foundation (FWF), project no. P11143-MAT
Dedicated: I dedicate the present work to the memory of Hans Stegbuchner
Copyright of article: Copyright 2001, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS