# Item

ITEM ACTIONSEXPORT

Released

Paper

#### A Lower Bound for the Discrepancy of a Random Point Set

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1210.0572.pdf

(Preprint), 107KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Doerr, B. (2012). A Lower Bound for the Discrepancy of a Random Point Set. Retrieved from http://arxiv.org/abs/1210.0572.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-48AF-0

##### 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(-\Theta(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}$.