Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(e) ISSN 0025-5718(p)

     

On the exponent of discrepancies

Author(s): Grzegorz W. Wasilkowski; Henryk Wozniakowski.
Journal: Math. Comp. 79 (2010), 983-992.
MSC (2000): Primary 41A55; Secondary 11K38
Posted: September 28, 2009
MathSciNet review: 2600552
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 and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia