Probability bound on existence of highly covered vector in high dimensions

26 Views Asked by At

Let $x_1,\ldots,x_n\sim S^{d-1}$ be randomly vectors on the $d$-dimensional hypersphere. I am working within the high dimensional setting, so let $n=\gamma d$.

Let us have an angle $\theta$ that is very close to $\pi/2$. I'm mostly interested in the case of $\theta=\pi/2-O(1/\sqrt d)$, but others will be interesting too.

Can I say with high probability that there does not exist a vector $v\in S^{d-1}$ that is within $\theta$ of more than $k$ of the original $n$ vectors for some constant $k$? Another way to interpret this is to ask whether any $\theta$ spherical caps at $x_1,\ldots,x_n$ have an intersection with more than $k$ of them. Intuitively the fact that vectors are highly orthogonal in higher dimensions should make this true.

If the above is not true, then what if $k=O(\log(d)), k=O(\sqrt d)$ or some other (sublinear) function?