Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

On the exponent of discrepancies

Author(s): Grzegorz W. Wasilkowski; Henryk Wozniakowski.
Journal: Math. Comp.
MSC (2000): Primary 41A55; Secondary 11K38
Posted: September 28, 2009
Retrieve article in: 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:

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: 10.1090/S0025-5718-09-02314-X
PII: S 0025-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
Posted: 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.
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google