3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – microhaus
    May 5 at 3:00
  • $\begingroup$ 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. $\endgroup$
    – microhaus
    May 5 at 3:11
  • $\begingroup$ 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. $\endgroup$ May 5 at 4:08
  • $\begingroup$ 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). $\endgroup$
    – student_t
    May 5 at 5:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – whuber
    May 5 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.