Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

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

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

  • [1] Christoph Aistleitner, Covering numbers, dyadic chaining and discrepancy, J. Complexity 27 (2011), no. 6, 531-540. MR 2846704 (2012j:11149), https://doi.org/10.1016/j.jco.2011.03.001
  • [2] Benjamin Doerr, Michael Gnewuch, Peter Kritzer, and Friedrich Pillichshammer, Component-by-component construction of low-discrepancy point sets of small size, Monte Carlo Methods Appl. 14 (2008), no. 2, 129-149. MR 2431686 (2009e:11144), https://doi.org/10.1515/MCMA.2008.007
  • [3] Benjamin Doerr, Michael Gnewuch, and Magnus Wahlström, Algorithmic construction of low-discrepancy point sets via dependent randomized rounding, J. Complexity 26 (2010), no. 5, 490-507. MR 2719644 (2011j:11139), https://doi.org/10.1016/j.jco.2010.03.004
  • [4] Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner, Hardness of discrepancy computation and $ \epsilon $-net verification in high dimension, J. Complexity 28 (2012), no. 2, 162-176. MR 2900826, https://doi.org/10.1016/j.jco.2011.09.001
  • [5] Michael Gnewuch, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, J. Complexity 24 (2008), no. 2, 154-172. MR 2400314 (2009e:11145), https://doi.org/10.1016/j.jco.2007.08.003
  • [6] Michael Gnewuch, Construction of minimal bracketing covers for rectangles, Electron. J. Combin. 15 (2008), no. 1, Research Paper 95, 20. MR 2426158 (2009e:52034)
  • [7] M. Gnewuch.
    Entropy, randomization, derandomization, and discrepancy.
    In Monte Carlo and quasi-Monte Carlo methods 2010. Springer Proceedings in Mathematics and Statistics, Vol. 23, L. Plaskota; H.Woźniakowski (Eds.), Springer, p. 43 - 78, 2012.
  • [8] Michael Gnewuch, Anand Srivastav, and Carola Winzen, Finding optimal volume subintervals with $ k$-points and calculating the star discrepancy are NP-hard problems, J. Complexity 25 (2009), no. 2, 115-127. MR 2513611 (2010i:68156), https://doi.org/10.1016/j.jco.2008.10.001
  • [9] Stefan Heinrich, Some open problems concerning the star-discrepancy, J. Complexity 19 (2003), no. 3, 416-419. Numerical integration and its complexity (Oberwolfach, 2001). MR 1984123 (2004b:11112), https://doi.org/10.1016/S0885-064X(03)00014-1
  • [10] Stefan Heinrich, Erich Novak, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, The inverse of the star-discrepancy depends linearly on the dimension, Acta Arith. 96 (2001), no. 3, 279-302. MR 1814282 (2002b:11103), https://doi.org/10.4064/aa96-3-7
  • [11] Aicke Hinrichs, Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy, J. Complexity 20 (2004), no. 4, 477-483. MR 2068153 (2005e:11098), https://doi.org/10.1016/j.jco.2004.01.001
  • [12] A. Hinrichs.
    Discrepancy, Integration and Tractability. Preprint.
    Available at http://users.minet.uni-jena.de/~hinrichs/paper/50/article.pdf.
  • [13] Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266 (2009m:46037)
  • [14] Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032 (2011h:46093)

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: https://doi.org/10.1090/S0025-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.

American Mathematical Society