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
Published electronically: September 28, 2009
MathSciNet review: 2600552
Full-text PDF Free Access

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?)


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.