Skip to main content
1 of 3

Precise probability that $m$ random vectors in $n$ dimensional space are nearly-orthogonal

Consider $m$ vectors $v_1,\dots,v_m$ in $\mathbb R^n$, drawn uniformly and independetly from unit sphere. It is pretty straightforward from Chebyshev inequality that $$ \mathrm P (\forall i, j \ |v_i \cdot v_j|\leq \varepsilon) \to 1\ \text{as} \ n \to \infty. $$

But what about quantitative version of this limit, i.e. if we define $$ f(m, \varepsilon, \delta) = \inf_n \{n : \mathrm P(\forall i, j\ |v_i \cdot v_j| \leq \varepsilon)\geq 1 - \delta\} $$

what can we say about asymptotic behavior of $f$?