4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.