Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

On the exponent of discrepancies


Authors: Grzegorz W. Wasilkowski and Henryk Wozniakowski
Journal: Math. Comp. 79 (2010), 983-992
MSC (2000): Primary 41A55; Secondary 11K38
DOI: https://doi.org/10.1090/S0025-5718-09-02314-X
Published electronically: September 28, 2009
MathSciNet review: 2600552
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study various discrepancies with arbitrary weights in the $ L_2$ norm over domains whose dimension is proportional to $ d$. We are mostly interested in large $ d$. The exponent $ p$ of discrepancy is defined as the smallest number for which there exists a positive number $ C$ such that for all $ d$ and $ \varepsilon$ there exist $ C \varepsilon^{-p}$ points with discrepancy at most  $ \varepsilon$. We prove that for the most standard case of discrepancy anchored at zero, the exponent is at most $ 1.41274\dots $, which slightly improves the previously known bound $ 1.47788\dots $. For discrepancy anchored at $ \vec{\alpha}$ and for quadrant discrepancy at $ \vec\alpha$, we prove that the exponent is at most $ 1.31662\dots $ for $ \vec\alpha=[1/2,\dots,1/2]$. For unanchored discrepancy we prove that the exponent is at most $ 1.27113\dots $. The previous bound was $ 1.28898\dots $. It is known that for all these discrepancies the exponent is at least $ 1$.


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

  • 1. N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337-404. MR 0051437 (14:479c)
  • 2. J. Beck and W. W. Chen, ``Irregularities of Distributions,'' Cambridge Tracts in Mathematics 89, Cambridge University Press, 1987. MR 903025 (88m:11061)
  • 3. B. Chazelle, ``The Discrepancy Method: Randomness and Complexity.'' Cambridge Univ. Press, 2002. MR 1779341 (2002c:68002)
  • 4. D. P. Dobkin and D. P. Mitchell, ``Random-Edge Discrepancy of Supersampling Patterns,'' Graphics Interface '93, York, Ontario, 1993.
  • 5. M. Drmota and R. F. Tichy, ``Sequences, Discrepancies and Applications,'' Lecture Notes in Math. 1651, Springer-Verlag, Berlin, 1997. MR 1470456 (98j:11057)
  • 6. K. K. Frolov, Upper bounds on discrepancy in $ L_p$, $ 2\le p\le \infty$, Dokl. Akad. Nauk SSSR 252 (1980), 805-807. MR 580823 (81k:10087)
  • 7. F. J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), 299-322. MR 1433265 (98c:65032)
  • 8. F. J. Hickernell, G. W. Wasilkowski, H. Woźniakowski, Tractability of linear multivariate problems in the average case setting, in ``Monte Carlo and Quasi-Monte Carlo Methods 2006,'' (A. Keller, S. Heinrich, H. Niederreiter, eds.), pp. 359-381, Springer, 2008. MR 2479240
  • 9. J. Matoušek, The exponent of discrepancy is at least $ 1.0669$, J. of Complexity 14 (1998), 448-453. MR 1659020 (2000k:65245)
  • 10. J. Matoušek, ``Geometric Discrepancy,'' Algorithms and Combinatorics 18, Springer-Verlag, 1999. MR 1697825 (2001a:11135)
  • 11. H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), 957-1041. MR 508447 (80d:65016)
  • 12. H. Niederreiter, ``Random Number Generation and quasi-Monte Carlo Methods,'' CBMS-NSF Reg. Conf. Series Appl. Math., Vol. 63, SIAM, Philadelphia, 1992. MR 1172997 (93h:65008)
  • 13. E. Novak and H. Woźniakowski, ``Tractability of Multivariate Problems,'' European Mathematical Society, Vol. 6, Zürich, 2008. MR 2455266
  • 14. E. Novak and H. Woźniakowski, $ L_2$ discrepancy and multivariate integration, In ``Analytic Number Theory - Essays in Honor of Klaus Roth,'' Cambridge University Press, to appear.
  • 15. K. Ritter, ``Average-Case Analysis of Numerical Problems,'' Lecture Notes in Math. 1733, Springer-Verlag, Berlin, 2000. MR 1763973 (2001i:65001)
  • 16. K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73-79. MR 0066435 (16:575c)
  • 17. K. F. Roth, On irregularities of distribution, IV, Acta Arith. 37 (1980), 67-75. MR 598865 (82f:10063)
  • 18. I. H. Sloan and S. Joe, ``Lattice Methods for Multiple Integration,'' Oxford University Press, 1994. MR 1442955 (98a:65026)
  • 19. S. Tezuka, ``Uniform Random Numbers: Theory and Practice,'' Kluwer Academic Publishers, 1995.
  • 20. J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, ``Information-Based Complexity,'' Academic Press, New York, 1988. MR 958691 (90f:68085)
  • 21. G. Wahba, ``Spline Models for Observational Data,'' SIAM-NSF Regional Conference Series in Appl. Math., Vol. 59, 1990. MR 1045442 (91g:62028)
  • 22. G. W. Wasilkowski, Information of varying cardinality, J. of Complexity 2 (1986), 204-228. MR 922813 (88m:65099)
  • 23. G. W. Wasilkowski, Integration and approximation of multivariate functions: Average case complexity with isotropic Wiener measure, Bull. Amer. Math. Soc. 28 (1993), 308-314. Full version in: J. of Approx. 77 (1994), 212-227. MR 1184000 (93i:65136)
  • 24. G. W. Wasilkowski and H. Woźniakowski, The exponent of discrepancy is at most 1.4778..., Math. Comp. 66, (1997), 1125-1132. MR 1397448 (97i:11083)
  • 25. H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. 24 (1991), 185-194. MR 1072015 (91i:65224)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 41A55, 11K38

Retrieve articles in all journals with MSC (2000): 41A55, 11K38


Additional Information

Grzegorz W. Wasilkowski
Affiliation: Department of Computer Science, University of Kentucky, Lexington, Kentucky 40506
Email: greg@cs.uky.edu

Henryk Wozniakowski
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027 and Institute of Applied Mathematics, University of Warsaw, 02-097 Warsaw, Poland
Email: henryk@cs.columbia.edu

DOI: https://doi.org/10.1090/S0025-5718-09-02314-X
Keywords: Discrepancy, multivariate integration
Received by editor(s): April 26, 2008
Received by editor(s) in revised form: March 4, 2009
Published electronically: September 28, 2009
Additional Notes: The first author was supported in part by NSF Grant DMS-0609703.
The second author was supported in part by NSF Grant DMS-0608727.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society