3

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)$.

Thanks for your help.

student_t
  • 141
  • 2
  • As a first pass, on the second part of your question concerning lower bounds only - I’m assuming that these are non-asymptotic. The general strategy is to ask what properties of the random variables we have at our disposal, and the degree to which this information can be put to use using a suitable concentration inequality. – microhaus May 05 '21 at 03:00
  • 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. – microhaus May 05 '21 at 03:11
  • https://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/chap1-high-dim-space.pdf 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. – Thomas Lumley May 05 '21 at 04: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). – student_t May 05 '21 at 05:15
  • 1
    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.](https://stats.stackexchange.com/questions/85916/) Its distribution function is the $n^\text{th}$ power of that Beta distribution function and (therefore) all results flow from there. – whuber May 05 '21 at 14:50
  • In light of Thomas's comment, just using a union bound, it seems like w.h.p any d sampled vectors would have an inner product of at most $O(1 / \sqrt{d})$ wrt $w$. I was hoping that at least one of them would have sizable inner product, but actually and more generally, it seems like in high dimensions for any $d$ randomly sampled vectors, all pairwise inner products are small w.h.p. – student_t May 06 '21 at 19:56

0 Answers0