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 Free Access

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?)

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