The exponent of discrepancy is at most
Authors:
Grzegorz W. Wasilkowski and Henryk Woźniakowski
Journal:
Math. Comp. 66 (1997), 11251132
MSC (1991):
Primary 11K38, 41A55
MathSciNet review:
1397448
Fulltext 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
(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. 392399. CMP 95:11
 4.
D. P. Dobkin and D. P. Mitchell, Randomedge 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
(81k:10087)
 6.
S. Heinrich, Efficient algorithms for computing the discrepancy, Math. Comp. 65 (1996), 16211633. CMP 96:01
 7.
S. Heinrich and A. Keller, QuasiMonte Carlo methods in computer graphics, Part I: The QMCbuffer, 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, QuasiMonte Carlo methods and
pseudorandom numbers, Bull. Amer. Math.
Soc. 84 (1978), no. 6, 957–1041. MR 508447
(80d:65016), http://dx.doi.org/10.1090/S000299041978145327
 9.
Harald
Niederreiter, Random number generation and quasiMonte Carlo
methods, CBMSNSF Regional Conference Series in Applied Mathematics,
vol. 63, Society for Industrial and Applied Mathematics (SIAM),
Philadelphia, PA, 1992. MR 1172997
(93h:65008)
 10.
K.
F. Roth, On irregularities of distribution, Mathematika
1 (1954), 73–79. MR 0066435
(16,575c)
 11.
K.
F. Roth, On irregularities of distribution. IV, Acta Arith.
37 (1980), 67–75. MR 598865
(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
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
(90e:00007)
 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
(95k:65138), http://dx.doi.org/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
(91i:65224), http://dx.doi.org/10.1090/S027309791991159859
 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. 392399. CMP 95:11
 4.
 D. P. Dobkin and D. P. Mitchell, Randomedge 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), 805807. MR 81k:10087
 6.
 S. Heinrich, Efficient algorithms for computing the discrepancy, Math. Comp. 65 (1996), 16211633. CMP 96:01
 7.
 S. Heinrich and A. Keller, QuasiMonte Carlo methods in computer graphics, Part I: The QMCbuffer, 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, QuasiMonte Carlo methods and pseudorandom numbers, Bull. Amer. Math. Soc. 84 (1978), 9571041. MR 80d:65016
 9.
 , Random number generation and quasiMonte Carlo methods, CBMSNSF Reg. Conf. Series Appl. Math., vol. 63, SIAM, Philadelphia, 1992. MR 93h:65008
 10.
 K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 7379. MR 16:575c
 11.
 , On irregularities of distribution, IV, Acta Arith. 37 (1980), 6775. 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), 156. MR 95k:65138
 15.
 H. Wo\'{z}niakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), 185194. MR 91i:65224
Similar Articles
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, 02097 Warszawa, Poland
Email:
henryk@cs.columbia.edu
DOI:
http://dx.doi.org/10.1090/S0025571897008247
PII:
S 00255718(97)008247
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 CCR9420543, and the second by the National Science Foundation and the Air Force Office of Scientific Research
Article copyright:
© Copyright 1997
American Mathematical Society
