The exponent of discrepancy is at most

Authors:
Grzegorz W. Wasilkowski and Henryk Woźniakowski

Journal:
Math. Comp. **66** (1997), 1125-1132

MSC (1991):
Primary 11K38, 41A55

MathSciNet review:
1397448

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study discrepancy with arbitrary weights in the norm over the -dimensional unit cube. The exponent of discrepancy is defined as the smallest for which there exists a positive number such that for all and all there exist points with discrepancy at most . It is well known that . We improve the upper bound by showing that

This is done by using relations between discrepancy and integration in the average case setting with the Wiener sheet measure. Our proof is *not* constructive. The known constructive bound on the exponent is .

**1.**József Beck and William W. L. Chen,*Irregularities of distribution*, Cambridge Tracts in Mathematics, vol. 89, Cambridge University Press, Cambridge, 1987. MR**903025****2.**V. A. Bykovskij,*On exact order of optimal quadrature formulas for spaces of functions with bounded mixed derivatives*, Report of the Dalnevostochnoi Center of Academy of Sciences, Vladivostok, USSR (in Russian), 1985.**3.**B. Chazelle,*Geometric discrepancy revisited*, 34th Annual Symposium on Foundations of Computer Science, 1993, pp. 392-399. CMP**95:11****4.**D. P. Dobkin and D. P. Mitchell,*Random-edge discrepancy of supersampling patterns*, Graphics Interface '93, York, Ontario, 1993.**5.**K. K. Frolov,*Upper bound of the discrepancy in metric 𝐿_{𝑝}, 2≤𝑝<∞*, Dokl. Akad. Nauk SSSR**252**(1980), no. 4, 805–807 (Russian). MR**580823****6.**S. Heinrich,*Efficient algorithms for computing the discrepancy*, Math. Comp.**65**(1996), 1621-1633. CMP**96:01****7.**S. Heinrich and A. Keller,*Quasi-Monte Carlo methods in computer graphics*, Part I:*The*QMC-*buffer*, Report, Univ. of Kaiserslautern, Dept. Computer Science, Report No.242/1994; Part II: The radiance equation, Report, Univ. of Kaiserslautern, Dept. Computer Science, Report No.243/1994.**8.**Harald Niederreiter,*Quasi-Monte Carlo methods and pseudo-random numbers*, Bull. Amer. Math. Soc.**84**(1978), no. 6, 957–1041. MR**508447**, 10.1090/S0002-9904-1978-14532-7**9.**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****10.**K. F. Roth,*On irregularities of distribution*, Mathematika**1**(1954), 73–79. MR**0066435****11.**K. F. Roth,*On irregularities of distribution. IV*, Acta Arith.**37**(1980), 67–75. MR**598865****12.**I. H. Sloan and S. Joe,*Lattice methods for multiple integration*, Oxford Science Publication, Oxford, 1994.**13.**V. N. Temlyakov,*Approximation of functions with bounded mixed derivative*, Proc. Steklov Inst. Math.**1(178)**(1989), vi+121. A translation of Trudy Mat. Inst. Steklov 178 (1986) [ MR0847439 (87j:42006)]; Translated by H. H. McFaden. MR**1005898****14.**Grzegorz W. Wasilkowski and Henryk Woźniakowski,*Explicit cost bounds of algorithms for multivariate tensor product problems*, J. Complexity**11**(1995), no. 1, 1–56. MR**1319049**, 10.1006/jcom.1995.1001**15.**H. Woźniakowski,*Average case complexity of multivariate integration*, Bull. Amer. Math. Soc. (N.S.)**24**(1991), no. 1, 185–194. MR**1072015**, 10.1090/S0273-0979-1991-15985-9

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
11K38,
41A55

Retrieve articles in all journals with MSC (1991): 11K38, 41A55

Additional Information

**Grzegorz W. Wasilkowski**

Affiliation:
Department of Computer Science, University of Kentucky, Lexington, Kentucky 40506

Email:
greg@cs.engr.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, ul. Banacha 2, 02-097 Warszawa, Poland

Email:
henryk@cs.columbia.edu

DOI:
https://doi.org/10.1090/S0025-5718-97-00824-7

Keywords:
Discrepancy,
multivariate integration,
average case

Received by editor(s):
December 20, 1995

Received by editor(s) in revised form:
May 1, 1996

Additional Notes:
The first author was partially supported by the National Science Foundation under Grant CCR-9420543, and the second by the National Science Foundation and the Air Force Office of Scientific Research

Article copyright:
© Copyright 1997
American Mathematical Society