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

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

MathSciNet review:
1397448

Full-text PDF

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. Beck and W. W. L. Chen,*Irregularities of distribution*, Cambridge University Press, Cambridge, 1987. MR**88m:11061****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 bounds of the discrepancy in metric ,*, Dokl. Akad. Nauk SSSR**252**(1980), 805-807. MR**81k:10087****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.**H. Niederreiter,*Quasi-Monte Carlo methods and pseudo-random numbers*, Bull. Amer. Math. Soc.**84**(1978), 957-1041. MR**80d:65016****9.**-,*Random number generation and quasi-Monte Carlo methods*, CBMS-NSF Reg. Conf. Series Appl. Math., vol. 63, SIAM, Philadelphia, 1992. MR**93h:65008****10.**K. F. Roth,*On irregularities of distribution*, Mathematika**1**(1954), 73-79. MR**16:575c****11.**-,*On irregularities of distribution*, IV, Acta Arith.**37**(1980), 67-75. MR**82f:10063****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 derivatives*, Proc. Steklov Inst. Math., Moscow, 1989. MR**90e:00007****14.**G. W. Wasilkowski and H. Wo\'{z}niakowski,*Explicit cost bounds of algorithms for multivariate tensor product problems*, J. Complexity**11**(1995), 1-56. MR**95k:65138****15.**H. Wo\'{z}niakowski,*Average case complexity of multivariate integration*, Bull. Amer. Math. Soc. (N.S.)**24**(1991), 185-194. MR**91i:65224**

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