Irregularities of distributions and extremal sets in combinatorial complexity theory

2016/12/02 by Christoph Aistleitner, Aistleitner, Christoph, Aicke Hinrichs +1 · 1 citation
Mathematics · #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.1612.00617

Abstract

In 2004 the second author of the present paper proved that a point set in [0,1]^d which has star-discrepancy at most ε must necessarily consist of at least c_abs d ε^-1 points. Equivalently, every set of n points in [0,1]^d must have star-discrepancy at least c_abs d n^-1. The original proof of this result uses methods from Vapnik--Chervonenkis theory and from metric entropy theory. In the present paper we give an elementary combinatorial proof for the same result, which is based on identifying a sub-box of [0,1]^d which has approximately d elements of the point set on its boundary. Furthermore, we show that a point set for which no such box exists is rather irregular, and must necessarily have a large star-discrepancy.

Cited by

• Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

Related

• An elementary proof of a lower bound for the inverse of the star discrepancy
• Probabilistic discrepancy bound for Monte Carlo point sets
• Probabilistic Star Discrepancy Bounds for Lacunary Point Sets
• On the inverse of the star-discrepancy
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers