|
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 norm over domains whose dimension is proportional to . We are mostly interested in large . The exponent of discrepancy is defined as the smallest number for which there exists a positive number such that for all and there exist points with discrepancy at most . We prove that for the most standard case of discrepancy anchored at zero, the exponent is at most , which slightly improves the previously known bound . For discrepancy anchored at and for quadrant discrepancy at , we prove that the exponent is at most for . For unanchored discrepancy we prove that the exponent is at most . The previous bound was . It is known that for all these discrepancies the exponent is at least .
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
, , 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
, 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,
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.
|