Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

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

Author(s): Grzegorz W. Wasilkowski; Henryk Wozniakowski.
Journal: Math. Comp. 66 (1997), 1125-1132.
MSC (1991): Primary 11K38, 41A55
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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:

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 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 Wozniakowski
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: 10.1090/S0025-5718-97-00824-7
PII: S 0025-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
Copyright of article: Copyright 1997, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google