A lower bound for the discrepancy of a random point set

DOI10.1016/J.JCO.2013.06.001zbMATH Open1295.60012arXiv1210.0572OpenAlexW2163000644MaRDI QIDQ2252138FDOQ2252138

Authors: Benjamin Doerr 

Publication date: 16 July 2014

Published in: Journal of Complexity (Search for Journal in Brave)

Abstract: We show that there is a constant $K>0$ such that for all $N,sinN$, $sleN$, 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 $KsqrtsN$ points more than expected. Consequently, the expected star discrepancy of a random point set is of order $sqrts/N$.

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

Recommendations

• Probabilistic discrepancy bound for Monte Carlo point sets
• The inverse of the star-discrepancy depends linearly on the dimension
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• An elementary proof of a lower bound for the inverse of the star discrepancy
• Entropy, Randomization, Derandomization, and Discrepancy

zbMATH Keywords

random pointsstar discrepancydependence on the dimension

Mathematics Subject Classification ID

Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D99)

Cites Work

• Weak convergence and empirical processes. With applications to statistics
• New concentration inequalities in product spaces
• Title not available (Why is that?)
• About the constants in Talagrand's concentration inequalities for empirical processes.
• Sequences, discrepancies and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometric discrepancy. An illustrated guide
• Analyzing randomized search heuristics: tools from probability theory
• Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
• Asymptotic behavior of average \(L_p\)-discrepancies
• The inverse of the star-discrepancy depends linearly on the dimension
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• Title not available (Why is that?)
• Entropy, Randomization, Derandomization, and Discrepancy

Cited In (23)

• The Lower Bound for Koldobsky’s Slicing Inequality via Random Rounding
• Probabilistic lower bounds for the discrepancy of Latin hypercube samples
• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• 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
• On negative dependence properties of Latin hypercube samples and scrambled nets
• Discrepancy of stratified samples from partitions of the unit cube
• Efficient algorithms for discrepancy minimization in convex sets
• Probabilistic discrepancy bound for Monte Carlo point sets
• Random sampling and reconstruction in multiply generated shift-invariant spaces
• On the discrepancy of jittered sampling
• Uniformity of point samples in metric spaces using gap ratio
• Matching random colored points with rectangles
• Proof techniques in quasi-Monte Carlo theory
• An elementary proof of a lower bound for the inverse of the star discrepancy
• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• A sharp discrepancy bound for jittered sampling
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
• The power of online thinning in reducing discrepancy
• Heuristic approaches to obtain low-discrepancy point sets via subset selection
• Some results on the complexity of numerical integration
• DYADIC SHIFT RANDOMIZATION IN CLASSICAL DISCREPANCY THEORY
• A nonlocal functional promoting low-discrepancy point sets

This page was built for publication: A lower bound for the discrepancy of a random point set

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