Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

A Lower Bound for the Discrepancy of a Random Point Set

MPG-Autoren
/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1210.0572.pdf
(Preprint), 107KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0024-48AF-0
Zusammenfassung
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}$.