A Lower Bound for the Discrepancy of a Random Point Set

Benjamin Doerr

Abstract

We show that there is a constant $K > 0$ such that for all $N, s \in \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(-Θ(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}$.
BibTeX
@article{doerr2012lower,
  author = {Benjamin Doerr},
  title = {{A Lower Bound for the Discrepancy of a Random Point Set}},
  journal = {J. Complex.},
  year = {2012},
  url = {https://openreview.net/forum?id=FYx9lzjYC6c},
}

Loading related content...

Figure