Hidden low-discrepancy structures in random point sets

Abstract

We study the probabilistic existence of point configurations satisfying the $(0,m,d)$-net property in base $b$ within a randomly generated point set of size $N$ in the $d$-dimensional unit cube. We first derive an upper bound on the number of geometric patterns for $(0,m,d)$-nets in base $b$. By applying the elementary probability bounds together with this counting result, we then give scaling conditions on $N$ as a function of $m$ such that this probability converges to $1$ and $0$, respectively.

revision, 7 pages