Probabilistic discrepancy bound for Monte Carlo point sets

DOI10.1090/S0025-5718-2013-02773-1zbMATH Open1285.65002arXiv1211.1058MaRDI QIDQ5401705FDOQ5401705

Authors: Christoph Aistleitner, Markus Hofer 

Publication date: 12 March 2014

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: By a profound result of Heinrich, Novak, Wasilkowski, and Wo{'z}niakowski the inverse of the star-discrepancy $n^{\ast }(s,ve)$ satisfies the upper bound $n^{\ast }(s,ve)leq{c}_{mathrmabs}sv{e}^{-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_{mathrmabs}{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 $qin(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$.

Full work available at URL: https://arxiv.org/abs/1211.1058

Recommendations

• A lower bound for the discrepancy of a random point set
• Probabilistic star discrepancy bounds for double infinite random matrices
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• The inverse of the star-discrepancy depends linearly on the dimension
• On the inverse of the discrepancy for infinite dimensional infinite sequences

zbMATH Keywords

star-discrepancyMonte Carlo point sets

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Irregularities of distribution, discrepancy (11K38)

Cites Work

• Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Discrepancy, integration and tractability
• Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• The inverse of the star-discrepancy depends linearly on the dimension
• Covering numbers, dyadic chaining and discrepancy
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• Construction of minimal bracketing covers for rectangles
• Component-by-component construction of low-discrepancy point sets of small size
• Some open problems concerning the star-discrepancy
• Entropy, Randomization, Derandomization, and Discrepancy

Cited In (22)

• Probabilistic star discrepancy bounds for double infinite random matrices
• Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets
• The inverse of the star-discrepancy depends linearly on the dimension
• Tractability properties of the discrepancy in Orlicz norms
• Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions
• Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
• Upper bounds in discrepancy theory
• Low-discrepancy point sets for non-uniform measures
• Secure pseudorandom bit generators and point sets with low star-discrepancy
• Title not available (Why is that?)
• A lower bound for the discrepancy of a random point set
• Expected integration approximation under general equal measure partition
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• A sharp discrepancy bound for jittered sampling
• Bounds for the average \(L^p\)-extreme and the \(L^\infty\)-extreme discrepancy
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
• WAFOM over abelian groups for quasi-Monte Carlo point sets
• Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy
• Some results on the complexity of numerical integration
• Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration
• Tractability results for the weighted star-discrepancy

This page was built for publication: Probabilistic discrepancy bound for Monte Carlo point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5401705)