Probabilistic discrepancy bound for Monte Carlo point sets
HTML articles powered by AMS MathViewer
- by Christoph Aistleitner and Markus Hofer PDF
- Math. Comp. 83 (2014), 1373-1381 Request permission
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
- Christoph Aistleitner, Covering numbers, dyadic chaining and discrepancy, J. Complexity 27 (2011), no. 6, 531–540. MR 2846704, DOI 10.1016/j.jco.2011.03.001
- 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, DOI 10.1515/MCMA.2008.007
- 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, DOI 10.1016/j.jco.2010.03.004
- 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, DOI 10.1016/j.jco.2011.09.001
- Michael Gnewuch, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, J. Complexity 24 (2008), no. 2, 154–172. MR 2400314, DOI 10.1016/j.jco.2007.08.003
- Michael Gnewuch, Construction of minimal bracketing covers for rectangles, Electron. J. Combin. 15 (2008), no. 1, Research Paper 95, 20. MR 2426158
- 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.
- 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, DOI 10.1016/j.jco.2008.10.001
- 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, DOI 10.1016/S0885-064X(03)00014-1
- 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, DOI 10.4064/aa96-3-7
- Aicke Hinrichs, Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy, J. Complexity 20 (2004), no. 4, 477–483. MR 2068153, DOI 10.1016/j.jco.2004.01.001
- A. Hinrichs. Discrepancy, Integration and Tractability. Preprint. Available at http://users.minet.uni-jena.de/~hinrichs/paper/50/article.pdf.
- 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, DOI 10.4171/026
- 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, DOI 10.4171/084
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] - © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3167462