Bounds and constructions for the star-discrepancy via \(\delta\)-covers (Q2576276): Difference between revisions

The (\(L^{\infty}\)-) star-discrepancy is a well known measure for the irregularity of distribution of \(n\) points in the \(d\)-dimensional unit cube. In addition, for certain classes of functions, point sets with small star discrepancy yield cubature formulas with low error of multivariate integration. Many of the known bounds on the star discrepancy of well-chosen point sets of size \(n\) are of the form \(C_d (\log n)^{d-1} n^{-1}\), which is not very helpful for large \(d\) since the number of points \(n\) needs to be extremely high if one wants to obtain small star discrepancy. For this reason, it is of great interest to find bounds on the discrepancy which depend only polynomially on \(d\). By the use of so-called \(\delta\)-covers, which are certain finite sets of points in the unit cube \([0,1]^d\), and a probabilistic argument, the authors show the existence of point sets of size \(n\) in \([0,1]^d\) such that their discrepancy is bounded by \(Cd^{1/2}n^{-1/2}(\log n)^{1/2}\), where \(C\) is a constant (independent of \(d\) and \(n\)). One of the main tools in the proof of this result is Hoeffding's inequality. Furthermore, the paper contains an algorithm for the construction of such point sets by a derandomization of the probabilistic argument.