Suppose we have $n$ uniform i.i.d. random vectors $\mathbf x_1,\cdots,\mathbf x_n \in \mathbb S^{n-1}$, i.e. on a unit ball of $\mathbb R^n$. Do we have any results on the following:
With some high probablity, for all unit vector $\mathbf y \in \mathbb S^{n-1}$, there is at most $O(1)$ indices $i$ such that $$|\mathbf x_i^\top \mathbf y|>\epsilon$$ when $n \to \infty$? I know in high dimension two random vectors are nearly perpendicular. What is the best possible $\epsilon$ to ensure the "w.h.p" condition?
Yes. Where $O(1) = O(\epsilon^{-2})$. This is a SKETCH. Assume WLOG that $x=(1,0,0,\ldots, 0)$ i.e., every coordinate except one is 0 and that one coordinate is 1. We can do so by symmetry on the unit sphere.
We next show that for $y$ chosen the following holds: $P[x^Ty \ge \epsilon]$ $\le$ $O(n^{-1}\epsilon^{-2})$. This implies the result.
To show this, we first observe that $x^Ty$ is at least $\epsilon$ iff the first coordinate of $y$ is at least $\epsilon$. However, for each $\epsilon > 0$ and each $y$ on the unit sphere, at most a $\frac{1}{\epsilon^2}$ coordinates of $y$ are larger than $\epsilon$. So let $P_i$ be the probability that the $-$-th coordinate of $y$ is at least $\epsilon$. Then $\sum_i P_i = O(\epsilon^{-2})$. Furthermore, for a $y$ picked at random on the unit sphere, the probability $P_j$ that the $j$-th coordinate is at least $\epsilon$ is the same that the probability $P_1$ that the 1st coordinate is at least $\epsilon$. So $P_1$ is $O(n^{-1}\epsilon^{-2})$. However, as observed above, $P_1$ is $P[x^Ty \ge \epsilon]$ the probability that a $y$ so chosen satisfies $x^Ty \ge \epsilon$. And so the result follows.