A Lower Bound for the Discrepancy of a Random Point Set

Abstract

We show that there is a constant $K>0$ such that for all $N,s\in \mathbb{N}$, $s\le N$, the point set consisting of $N$ points chosen uniformly at random in the $s$-dimensional unit cube $[0,1{]}^s$ with probability at least $1-\exp (-\Theta (s))$ admits an axis parallel rectangle $[0,x]\subseteq [0,1{]}^s$ containing $K\sqrt{sN}$ points more than expected. Consequently, the expected star discrepancy of a random point set is of order $\sqrt{s/N}$.

7 pages

References in corpus (1)

• On Wavelet-Galerkin methods for Semilinear Parabolic Equations with Additive Noise

Cited by in corpus (17)

• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
• Discrepancy Bounds for a Class of Negatively Dependent Random Points Including Latin Hypercube Samples
• A Sharp Discrepancy Bound for Jittered Sampling
• On the power of iid information for linear approximation
• Probabilistic Lower Bounds for the Discrepancy of Latin Hypercube Samples
• A Generalized Faulhaber Inequality, Improved Bracketing Covers, and Applications to Discrepancy
• On Negative Dependence Properties of Latin Hypercube Samples and Scrambled Nets
• Proof Techniques in Quasi-Monte Carlo Theory
• On a partition with a lower expected ${\mathcal{L}}_2$-discrepancy than classical jittered sampling
• The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension
• Uniformity of point samples in metric spaces using gap ratio
• Some Results on the Complexity of Numerical Integration
• Fully explicit large deviation inequalities for empirical processes with applications to information-based complexity
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
• A Nonlocal Functional Promoting Low-Discrepancy Point Sets
• MOFA: Modular Factorial Design for Hyperparameter Optimization
• On the Discrepancy of Jittered Sampling