Stochastic Covering Number of a Convex Set

Question

Consider a convex set, say $S = [0,1]^d$. Let $X_1, X_2,\ldots,X_n, \ldots$ be i.i.d. random variables that are uniformly distributed on $S$. Denote the Euclidean ball centered at $x \in \mathbb{R}^d$ with radius $r$ as $B(x, r) \colon = \{ y\in \mathbb{R}^d, \| y - x\|_2 \leq r \} .$ We want to use the Euclidean balls centered at $X_1, \ldots,X_n \ldots$ to cover $S$. Define the random covering number $N$ as $$ N = \inf \bigl\{ n\colon S \subset \cup_ {i=1}^n B(X_i, r) \big\} , $$ where $r\in (0,1)$.

I was wondering if there is a way to derive the distribution of $N$. If this is too hard, can we at least derive some bound on the tail probability of $N$? And how does $N$ depends on the dimensionality $d$ and the radius $r$?

If we can characterize $N$ for $S = [0,1]^d$, can we do similar things for general sets in Banach spaces?

Answer 1

Concerning bounds on tail probabilities, it should be possible to derive an exponential estimate of the form $$ P \{ N > t \} \leq C e^{-\gamma t}, $$ where $C, \gamma$ are some positive constants. Indeed, we can split $[0,1]^d$ into $2^{kd}$ cubes with side length $\frac{1}{2^k} < \frac r2$ and note that $N \leq \tilde N$, where $\tilde N$ is the minimum time when each of our small cubes contains at least one $X_n$. Since $\tilde N$ is the maximum of hitting times for individual cubes, the exponential estimate follows from the corresponding estimate for the hitting time of a single cube.