Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Published electronically: September 10, 2013
Full-text PDF

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_{\textup {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_{\textup {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?)


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

DOI: http://dx.doi.org/10.1090/S0025-5718-2013-02773-1
PII: S 0025-5718(2013)02773-1
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.