Probabilistic discrepancy bound for Monte Carlo point sets

2012/11/05 by Christoph Aistleitner, Aistleitner, Christoph, Markus Hofer +1 · 4 citations
Mathematics · #Mathematical Approximation and Integration #Analytic Number Theory Research

paper · pdf · doi:10.48550/arxiv.1211.1058

Abstract

By a profound result of Heinrich, Novak, Wasilkowski, and Woźniakowski the inverse of the star-discrepancy n^*(s,\ve) satisfies the upper bound n^*(s,\ve) ≤ c_abs s \ve^-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_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 ∈ (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.

Cited by

• Sharp Non-Asymptotic Bounds for the Star Discrepancy of Double-Infinite Random Matrices via Optimal Covering Numbers
• The L₁-Discrepancy with Nonnegative Weights Suffers from the Curse of Dimensionality
• Generalized Discrepancy of Random Points
• The inverse of the star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension

Related

• Probabilistic Star Discrepancy Bounds for Lacunary Point Sets
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
• On the inverse of the star-discrepancy
• Irregularities of distributions and extremal sets in combinatorial complexity theory
• Generalized Discrepancy of Random Points