A Lower Bound for the Discrepancy of a Random Point Set

Abstract

We show that there is a constant $K>0$ such that for all $N,s\in \mathbb{N}$, $s\le N$, the point set consisting of $N$ points chosen uniformly at random in the $s$-dimensional unit cube $[0,1{]}^s$ with probability at least $1-\exp (-\hat{I}˜(s))$ admits an axis parallel rectangle $[0,x]\subseteq [0,1{]}^s$ containing $K\sqrt{sN}$ points more than expected. Consequently, the expected star discrepancy of a random point set is of order $\sqrt{s/N}$.

7 pages