# Bounding maximum inner product out of $n$ randomly sampled unit norm vectors

Let $$w \in \mathbb{R}^d$$ have unit norm and $$x_1, ..., x_n \in \mathbb{R}^d$$ be $$n$$ randomly sampled vectors from the uniform distribution over the $$d$$-dimensional unit sphere. Can one obtain a lower bound of

$$\max_{i} |w \cdot x_i|$$

as a function of $$n$$ and $$d$$ with high probability?

It seems like given symmetry, we can WLOG $$w = e_1$$ and just work with the first coordinate. However, I'm not sure how to lower bound the max absolute value of $$n$$ draws from distribution $$\frac{Z_1}{\sqrt{Z_1^2+...+Z_d^2}}$$ for iid $$Z_i \sim N(0, 1)$$.

• As a provisional starting point, note that $Y = Z_1^2 + \dots + Z_d^2 \sim \chi^2_d$. Using Hoeffding’s inequality or Chernoffs method on $Z_i$ should give you what us known as a $\chi^2$ tail bound. Further, $\chi^2$ random variables are sub-exponential. This is the best I can do currently whilst typing on a tiny screen. Perhaps you might consider searching for the terms in italics in the meantime as there are lots of results on those terms. May 5 at 3:11
• cs.cmu.edu/~venkatg/teaching/CStheory-infoage/… gives upper bounds for the proportion of the surface of a $d$-sphere more than $c/\sqrt{d-2}$ from the equation, as $(2/c)\exp(-c^2/2)$. It might be possible to modify the argument to get lower bounds. May 5 at 4:08
• Thanks all for the feedback! I'm after some result that is like with probability $\geq 1 - f(n, d)$, $\max_i y^1_i \geq g(n, d)$ for some function $f(n, d)$ and $g(n,d)$. Note here that $y^1_i$ denotes the first coordinate of some randomly sampled vector $y_i$ on the sphere and I'm interested in the max of $n$ such $y$'s (and not just how one $y^1_i$ is distributed). May 5 at 5:15
• After a simple change of units, you are asking for a quantity closely related to the distribution of the maximum of $n$ iid Beta$((d-1)/2,(d-1)/2)$ variables. Its distribution function is the $n^\text{th}$ power of that Beta distribution function and (therefore) all results flow from there.