A lower bound for the discrepancy of a random point set

DOI10.1016/j.jco.2013.06.001zbMath1295.60012arXiv1210.0572OpenAlexW2163000644MaRDI QIDQ2252138

Benjamin Doerr

Publication date: 16 July 2014

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

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

zbMATH Keywords

random pointsstar discrepancydependence on the dimension

Mathematics Subject Classification ID

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

Related Items (17)

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 ⋮ Uniformity of Point Samples in Metric Spaces Using Gap Ratio ⋮ A sharp discrepancy bound for jittered sampling ⋮ The Inverse of the Star-Discrepancy Problem and the Generation of Pseudo-Random Numbers ⋮ Some Results on the Complexity of Numerical Integration ⋮ An elementary proof of a lower bound for the inverse of the star discrepancy ⋮ Probabilistic Lower Bounds for the Discrepancy of Latin Hypercube Samples ⋮ Random sampling and reconstruction in multiply generated shift-invariant spaces ⋮ On negative dependence properties of Latin hypercube samples and scrambled nets ⋮ Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples ⋮ Matching random colored points with rectangles ⋮ A nonlocal functional promoting low-discrepancy point sets ⋮ Discrepancy of stratified samples from partitions of the unit cube ⋮ On the discrepancy of jittered sampling ⋮ A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy ⋮ Proof techniques in quasi-Monte Carlo theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic behavior of average \(L_p\)-discrepancies
• Sequences, discrepancies and applications
• Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• About the constants in Talagrand's concentration inequalities for empirical processes.
• Weak convergence and empirical processes. With applications to statistics
• The inverse of the star-discrepancy depends linearly on the dimension
• Entropy, Randomization, Derandomization, and Discrepancy
• Geometric discrepancy. An illustrated guide
• New concentration inequalities in product spaces

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