Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The exponent of discrepancy is at most $1.4778\dotsc $

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

Abstract | References | Similar Articles | Additional Information

Abstract: We study discrepancy with arbitrary weights in the $L_2$ norm over the $d$-dimensional unit cube. The exponent $p^*$ of discrepancy is defined as the smallest $p$ for which there exists a positive number $K$ such that for all $d$ and all $\varepsilon \le 1$ there exist $K\varepsilon ^{-p}$ points with discrepancy at most $\varepsilon $. It is well known that $p^*\in (1,2]$. We improve the upper bound by showing that

\begin{displaymath}p^*\le 1.4778842.\end{displaymath}

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 $p^*$ is $2.454$.

References [Enhancements On Off] (What's this?)

  • 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 $L_p$, $2\le p\le \infty $, Dokl. Akad. Nauk SSSR 252 (1980), 805-807. MR 81k:10087
  • 6. S. Heinrich, Efficient algorithms for computing the $L_2$ 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

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

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

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

American Mathematical Society