Probabilistic Star Discrepancy Bounds for Lacunary Point Sets

Abstract

By a result of Heinrich, Novak, Wasilkowski and Woźniakowski the inverse of the star discrepancy $n(d,\epsilon )$ satisfies $n(d,\varepsilon)\leq c_{\abs}d\varepsilon^{-2}$. Equivalently for any $N$ and $d$ there exists a set of $N$ points in $[0,1{)}^d$ with star discrepacny bounded by $\sqrt{c_{\abs}\cdot d/N}$. They actually proved that a set of independent uniformly distributed random points satisfies this upper bound with positive probability. Although Aistleitner and Hofer later refined this result by proving a precise value of $c_{\abs}$ depending on the probability with which the inequality holds, so far there is no general construction for such a set of points known. In this paper we consider the sequence $(x_n{)}_{n\ge 1}=(⟨2^{n-1}{x}_1⟩{)}_{n\ge 1}$ for a uniformly distributed point $x_1\in [0,1{)}^d$ and prove that the star discrepancy is bounded by $C\sqrt{d{\log }_{2}d/N}$. The precise value of $C$ depends on the probability with which this upper bound holds.