Random spherical caps cover a spherical cap

Question

Let $S^{n-1}$ be the unit sphere in $n$ dimensional Euclidean space. Define the spherical cap at $x \in S^{n-1}$ with angle $\theta$ to be $C(x,\theta) = \{z \in S^{n-1} \mid z^\top x \geq \cos(\theta)\}$.

Let $x,y \in S^{n-1}$ be two unit vectors with angle $\alpha \in (\frac{\pi}{2}, \frac{3\pi}{4})$. Choose $m$ unit vectors $\{a_i\}_{i=1}^m$ independent and uniform over $C(x,\frac{\pi}{2})$, what is the probability that $C(y,\beta) \subseteq \bigcup_{i=1}^{m}C(a_i, \frac{\pi}{2})$ for some $\beta \in (0, \frac{\pi}{4})$?

This is similar to the classical sphere covering problem in geometric probability. The two differences here are that: first the vectors are chosen from $C(x,\frac{\pi}{2})$ rather than the whole sphere, second, it only need to cover a small spherical cap rather than the whole sphere.

Answer 1

Here's one heuristic. First, I'll just imagine the $m$ picks as independent attempts to cover the small cap, and settle for a lower bound.

Now the probability is twice the area of $C(y, \pi/2 - \beta) \cap C(x, \pi/2)$, so let's estimate this area. WLOG $x = e_1$ and $C(x, \pi/2)$ is just the space of vectors with positive first coordinate. A vector $z \in S^{n-1}$ is in this set if

$$z_1 \geq 0, \qquad \qquad z_1y_1 + z_2y_2 + \cdots + z_ny_n \geq 1 -\cos(\beta)$$

Generate $z$ by picking an $n$-dimensional normal random variable $\tilde z$ and normalizing $z = \tilde z / \|\tilde z\|$. The normalizing factor is $\Theta(\sqrt{n})$ with high probability. The right term of the above looks much better like this,

$$\tilde z_2y_2 + \cdots + \tilde z_ny_n \geq (1 - \cos(\beta))\cdot\|\tilde z\| - \tilde z_1y_1$$ because now the left-hand side is just a univariate normal random variable $\mathcal{N}(0, \sum_{i = 2}^n y_i^2)$. On the right hand side, the term $-\tilde z_1 y_1$ is $O(\sqrt{\log n})$ with high probability and is probably dominated by the $\|\tilde z\| = \Theta(\sqrt{n})$ term depending on the exact relationship of $\beta$ and $n$. You do get something exponential from the gaussian tail bound, $$\exp(-\Theta(n))$$ but it's a little messy to work out what exactly the constants are. Let me know if you would like a few more details.