2014/08/10 by Löbbe, Thomas
#11K31 #11K38 #11K45 #42A55 #65D30 #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1408.2216
In 2001 Heinrich, Novak, Wasilkowski and Woźniakowski proved that the inverse of the star discrepancy satisfies n(d,ε)≤ c\absd ε-2 by showing that there exists a set of points in [0,1)d whose star-discrepancy is bounded by c\abs√(d/N). This result was generalized by Aistleitner who showed that there exists a double infinite random matrix with elements in [0,1) which partly are coordinates of elements of a Halton sequence and partly independent uniformly distributed random variables such that any N× d-dimensional projection defines a set \x1,…,xN\⊂ [0,1)d with D^*N(x1,…,xN)≤ c\abs√(d/N). In this paper we consider a similar double infinite matrix where the elements instead of independent random variables are taken from a certain multivariate lacunary sequence and prove that with high probability each projection defines a set of points which has up to some constant the same upper bound on its star-discrepancy but only needs a significantly lower number of digits to simulate.