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$ – Serguei Popov Feb 7 '16 at 13:08
  • $\begingroup$ Thanks for your reply. I'm thinking treating $r$ as a fixed number. $\endgroup$ – Steve Feb 7 '16 at 21:43
  • 1
    $\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 Feb 8 '16 at 9:11
  • $\begingroup$ I find this as a relevant, interesting read: yaroslavvb.com/papers/koppen-curse.pdf $\endgroup$ – 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 (note that we do not need independence).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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