An elementary proof of a lower bound for the inverse of the star discrepancy
Let \(N^*_{\infty}(d,\varepsilon)\) is the smallest possible cardinality of a set \(x_1,\ldots,x_n\) in \(\mathbb{R}^d\) with star discrepancy \(D_n^*=\max_{y\in [0;1]^d} \left| \frac{1}{n}\sharp \{ 1\leq i\leq n: x_i\in [0;y] \}-\mathrm{vol}([0;y]) \right|\) less than \(\varepsilon\). In [\textit{A. Hinrichs}, J. Complexity 20, No. 4, 477--483 (2004; Zbl 1234.11101)] it was proved that there are universal \(c,\varepsilon_0>0\) such that for any \(\varepsilon, 0<\varepsilon<\varepsilon_0\) we have \(N^*_{\infty}(d,\varepsilon)\geq c\frac{d}{\varepsilon}\). The paper under review contains a more elementary proof of this result with \(N^*_{\infty}(d,\varepsilon)\geq \frac{d}{2}\left\lfloor \frac{1}{20\varepsilon} \right\rfloor\).
- The inverse of the star-discrepancy depends linearly on the dimension
- An improved bound for the star discrepancy of sequences in the unit interval
- Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
- On the inverse of the discrepancy for infinite dimensional infinite sequences
- On an explicit lower bound for the star discrepancy in three dimensions
- A combinatorial problem; stability and order for models and theories in infinitary languages
- A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
- A lower bound for the discrepancy of a random point set
- Covering numbers, dyadic chaining and discrepancy
- Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
- Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
- Improving a constant in high-dimensional discrepancy estimates
- Irregularities of distributions and extremal sets in combinatorial complexity theory
- On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence
- On the density of families of sets
- Probabilistic lower bounds for the discrepancy of Latin hypercube samples
- The inverse of the star-discrepancy depends linearly on the dimension
- An algorithm to compute bounds for the star discrepancy
- Computing bounds for the star discrepancy
- A lower bound for the discrepancy of a random point set
- Irregularities of distributions and extremal sets in combinatorial complexity theory
- A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
- An elementary proof of a lower bound for the inverse of the star discrepancy
- The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension
- The star discrepancy of a union of randomly shifted Korobov lattice point sets depends polynomially on the dimension
This page was built for publication: An elementary proof of a lower bound for the inverse of the star discrepancy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2685069)
