# Stochastic Covering Number of a Convex Set

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?

• You are mostly interested in the case $r\to0$? Or is $r$ just fixed? – Serguei Popov Feb 7 '16 at 13:08
• Thanks for your reply. I'm thinking treating $r$ as a fixed number. – Steve Feb 7 '16 at 21:43
• A useful start might be Svante Janson, Random coverings in several dimensions, Acta Mathematica July 1986, Volume 156, Issue 1, pp 83-118. – ET3 Feb 8 '16 at 9:11
• I find this as a relevant, interesting read: yaroslavvb.com/papers/koppen-curse.pdf – Mai Mar 10 '16 at 0:24

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.