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?

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

1 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.

  • $\begingroup$ could you explain why $N\leq N^{\sim}$? $\endgroup$
    – tony
    Commented Jul 8, 2023 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.