A Lower Bound for the Discrepancy of a Random Point Set
Lists
Only you see this
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...