Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Probabilistic discrepancy bound for Monte Carlo point sets


Authors: Christoph Aistleitner and Markus Hofer
Journal: Math. Comp. 83 (2014), 1373-1381
MSC (2010): Primary 65C05, 11K38, 65D32, 62G30
DOI: https://doi.org/10.1090/S0025-5718-2013-02773-1
Published electronically: September 10, 2013
MathSciNet review: 3167462
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: By a profound result of Heinrich, Novak, Wasilkowski, and Woźniakowski the inverse of the star-discrepancy $n^*(s,\varepsilon )$ satisfies the upper bound $n^*(s,\varepsilon ) \leq c_{\mathrm {abs}} s \varepsilon ^{-2}$. This is equivalent to the fact that for any $N$ and $s$ there exists a set of $N$ points in $[0,1]^s$ whose star-discrepancy is bounded by $c_{\mathrm {abs}} s^{1/2} N^{-1/2}$. The proof is based on the observation that a random point set satisfies the desired discrepancy bound with positive probability. In the present paper we prove an applied version of this result, making it applicable for computational purposes: for any given number $q \in (0,1)$ there exists an (explicitly stated) number $c(q)$ such that the star-discrepancy of a random set of $N$ points in $[0,1]^s$ is bounded by $c(q) s^{1/2} N^{-1/2}$ with probability at least $q$, uniformly in $N$ and $s$.


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

References

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65C05, 11K38, 65D32, 62G30

Retrieve articles in all journals with MSC (2010): 65C05, 11K38, 65D32, 62G30


Additional Information

Christoph Aistleitner
Affiliation: Graz University of Technology, Institute of Mathematics A, Steyrergasse 30, 8010 Graz, Austria
Email: aistleitner@math.tugraz.at

Markus Hofer
Affiliation: Graz University of Technology, Institute of Mathematics A, Steyrergasse 30, 8010 Graz, Austria
Email: markus.hofer@tugraz.at

Received by editor(s): April 18, 2012
Received by editor(s) in revised form: November 5, 2012, and December 6, 2012
Published electronically: September 10, 2013
Additional Notes: The first author’s research was supported by the Austrian Research Foundation (FWF), Project S9603-N23.
The second author’s research was supported by the Austrian Research Foundation (FWF), Project S9603-N23 and by the DOC [Doctoral Fellowship Programme of the Austrian Academy of Sciences]
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.