Randomly covering a sphere

Question

Let $S$ be the $n$-dimensional unit sphere in the Euclidean space. Further, let $X_1,\ldots,X_k$ and $Y_1,\ldots,Y_m$ be iid $S$-valued random variables with common (unknown) distribution $\mu$. With $k$ fixed, what is the tightest value of $$ \mathbb{P} \left(\bigcap_{i=1}^k \bigcup_{j=1}^m \{ d(X_i, Y_j) \leq \varepsilon \} \right) > 1 - \delta, $$ with regard to $\delta$ for $\varepsilon > 0$?

Answer 1

There's a simple way to get upper and lower bounds that are given by the solution to essentially the same combinatorial problem. In particular, we throw $k$ red balls and $m$ blue balls into some bins with iid probability distributions over the bins, and we ask for the maximal probability that a non-empty bin has all red balls. Our upper bound on $\delta$ will be this probability when the number of bins is given by the size $N$ of some minimal $(\varepsilon/2)$-net of the unit sphere, and our lower bound on $\delta$ will be given by this probability when the number of bins is given by the size $M$ of some maximal $\varepsilon$-packing of the unit sphere.

To see this, recall that an upper bound on $\delta$ corresponds to bounding the probability that some $X_i$ is not close to any $Y_j$. Let $a_1,\ldots, a_N$ be an $(\varepsilon/2)$-net of the sphere. I.e., for every point $x$ on the sphere, there exists an $i$ such that $\|a_i - x\| \leq \varepsilon/2$. Clearly to upper bound $\delta$, it suffices to upper bound the probability that there exists an $X_j$ closest to some $a_i$ but no $Y_\ell$ close to $a_i$. We can then bound this by the probability that there exists an $X_j$ closest to some $a_i$ but not $Y_\ell$ closest to $a_i$. Notice that this exactly corresponds to the balls and bins game from above, with the number of bins equal to the size $N$ of the net.

On the other hand, let $b_1,\ldots, b_M$ be vectors on the unit sphere such that $\|b_i - b_j\| >\varepsilon$ for all $i \neq j$. We take the $X_i, Y_j$ to be uniformly random elements from $b_1,\ldots, b_M$ and notice that $Y_j$ is $\varepsilon$-close to $X_i$ if and only if $X_i = Y_j$. Notice that this exactly corresponds to the balls and bins game from above with the number of bins equal to the size $M$ of the packing.

---

To finish the proof, we need to find an $(\varepsilon/2)$-net with small cardinality $N$, an $\varepsilon$-packing with large cardinality $M$, and then solve this balls and bins problem for the presumed answer. We'll handle the balls and bins problem last since it's least interesting. Constructing small nets and large packings is a deep problem, so if we wanted to analyze this to good accuracy, we'd be in trouble. (What I'm calling the size of a packing here is typically called a ``kissing number'' in the literature.)

But, if you just want to understand the asymptotics, then getting values of $N$ and $M$ that are good enough is pretty straightforward. In particular, a simple volume argument shows that we can take $N \leq V(1+\varepsilon/4) /V(\varepsilon/4) = (1+4/\varepsilon)^n$, where $V(r)$ is the volume of a ball of radius $r$. (See, e.g., http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf Lemma 5.2.) And, a similar volume argument shows that we can take $M \geq S(2)/S(\varepsilon) \geq \varepsilon^{-n}$, where $S(x)$ is the surface area of the spherical cap on the sphere of radius $1$ with maximal distance $x$.

---

Finally, let's study the combinatorial problem. I.e., let's approximate the maximal probability that a non-empty bin has all red balls when we throw $k$ red balls and $m$ blue balls into $Q$ bins with iid probability distributions over the bins. We first observe that the maximum is achieved when the distribution is uniform over the bin. To see this, it suffices to compute this directly in the case $Q = 2$ and then to note that this implies the general case. (In the general case, we can isolate any pair of bins and argue that they must have the same probability by reducing to the $Q = 2$ case.)

For the $j$th bin, we have $$\Pr[\text{$j$ is non-empty and red}] = \Pr[\text{no blue balls in $j$}] \cdot \Pr[\text{at least one red ball in $j$}] = (1-1/Q)^m \cdot (1-(1-1/Q)^k) \approx e^{-m/Q} \cdot \min\{ 1, k/Q\} \; ,$$ where $\approx$ here means that the approximation is good up to a constant factor in, say, $m$, $k$, and the probability.

Similarly, $$ \Pr[\text{exists a non-empty red bin}] \approx \min\Big\{1,\ \sum_j \Pr[\text{$j$ is non-empty and red}] \Big\} \\ \approx \min \Big\{1,\ Q e^{-m/Q} \cdot \min\{ 1, k/Q\} \Big\} \; . $$

---

Putting everything together gives

$$ C_1 \min \Big\{1,\ \varepsilon^{-n} e^{-C_2 m/\varepsilon^{-n}} \cdot \min\{ 1, k\varepsilon^n\} \Big\} \\ \leq \delta \leq \\ C_3 \min \Big\{1,\ (1+4/\varepsilon)^n e^{-C_4 m/(1+4/\varepsilon)^n} \cdot \min\{ 1, k(1+4/\varepsilon)^{-n} \} \Big\} \;. $$

Assuming we're in the more interesting case when the minima are not 1, then $$ C_1 k e^{-C_2 m/\varepsilon^{-n}} \leq \delta \leq C_3 k e^{-C_4m/(1+4/\varepsilon)^n} \;. $$

(Edit: On rereading this answer, I noticed that my approximations in the combinatorial case failed in the extreme case when $m$ is very large, so I added additional constants.)