On the exponent of discrepancies
HTML articles powered by AMS MathViewer
- by Grzegorz W. Wasilkowski and Henryk Woźniakowski PDF
- Math. Comp. 79 (2010), 983-992 Request permission
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
- N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 51437, DOI 10.1090/S0002-9947-1950-0051437-7
- József Beck and William W. L. Chen, Irregularities of distribution, Cambridge Tracts in Mathematics, vol. 89, Cambridge University Press, Cambridge, 1987. MR 903025, DOI 10.1017/CBO9780511565984
- Bernard Chazelle, The discrepancy method, Cambridge University Press, Cambridge, 2000. Randomness and complexity. MR 1779341, DOI 10.1017/CBO9780511626371
- D. P. Dobkin and D. P. Mitchell, “Random-Edge Discrepancy of Supersampling Patterns,” Graphics Interface ’93, York, Ontario, 1993.
- Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
- K. K. Frolov, Upper bound of the discrepancy in metric $L_{p}$, $2\leq p<\infty$, Dokl. Akad. Nauk SSSR 252 (1980), no. 4, 805–807 (Russian). MR 580823
- Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299–322. MR 1433265, DOI 10.1090/S0025-5718-98-00894-1
- Fred Hickernell, Greg Wasilkowski, and Henryk Woźniakowski, Tractability of linear multivariate problems in the average case setting, Monte Carlo and quasi-Monte Carlo methods 2006, Springer, Berlin, 2008, pp. 461–493. MR 2479240, DOI 10.1007/978-3-540-74496-2_{2}7
- Jiří Matoušek, The exponent of discrepancy is at least $1.0669$, J. Complexity 14 (1998), no. 4, 448–453. MR 1659020, DOI 10.1006/jcom.1998.0485
- Jiří Matoušek, Geometric discrepancy, Algorithms and Combinatorics, vol. 18, Springer-Verlag, Berlin, 1999. An illustrated guide. MR 1697825, DOI 10.1007/978-3-642-03942-3
- Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, DOI 10.1090/S0002-9904-1978-14532-7
- Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
- Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
- 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.
- Klaus Ritter, Average-case analysis of numerical problems, Lecture Notes in Mathematics, vol. 1733, Springer-Verlag, Berlin, 2000. MR 1763973, DOI 10.1007/BFb0103934
- K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73–79. MR 66435, DOI 10.1112/S0025579300000541
- K. F. Roth, On irregularities of distribution. IV, Acta Arith. 37 (1980), 67–75. MR 598865, DOI 10.4064/aa-37-1-67-75
- I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994. MR 1442955
- S. Tezuka, “Uniform Random Numbers: Theory and Practice,” Kluwer Academic Publishers, 1995.
- J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691
- Grace Wahba, Spline models for observational data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442, DOI 10.1137/1.9781611970128
- G. W. Wasilkowski, Information of varying cardinality, J. Complexity 2 (1986), no. 3, 204–228. MR 922813, DOI 10.1016/0885-064X(86)90002-6
- G. W. Wasilkowski, Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure, Bull. Amer. Math. Soc. (N.S.) 28 (1993), no. 2, 308–314. MR 1184000, DOI 10.1090/S0273-0979-1993-00379-3
- Grzegorz W. Wasilkowski and Henryk Woźniakowski, The exponent of discrepancy is at most $1.4778\cdots$, Math. Comp. 66 (1997), no. 219, 1125–1132. MR 1397448, DOI 10.1090/S0025-5718-97-00824-7
- H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015, DOI 10.1090/S0273-0979-1991-15985-9
Additional Information
- Grzegorz W. Wasilkowski
- Affiliation: Department of Computer Science, University of Kentucky, Lexington, Kentucky 40506
- MR Author ID: 189251
- ORCID: 0000-0003-4727-7368
- Email: greg@cs.uky.edu
- Henryk Woźniakowski
- 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
- 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. - © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 79 (2010), 983-992
- MSC (2000): Primary 41A55; Secondary 11K38
- DOI: https://doi.org/10.1090/S0025-5718-09-02314-X
- MathSciNet review: 2600552