11
$\begingroup$

I need to compute probabilities of the form $P( \Vert X \Vert_\infty < r ),$ where $X$ is a random variable of dimension $n$, drawn with a uniform distribution on the unit sphere $\mathcal{S}_{n-1}$. Clearly, the distribution of $Z = \Vert X \Vert_\infty$ is supported by the interval $[\frac{1}{\sqrt{n}},1]$.

Any hint to get a simple formula (ideally a closed-form expression or a one-dimensional integral) will be greatly appreciated !

Note: Using the fact that $X \sim \frac{Y}{\Vert Y\Vert_2}$ for $Y \sim \mathcal{N}(0,1)$, at first I thought I could first compute the probabilities $P_i:=P( |X_i| < r \Vert X \Vert_2)$, which can be expressed as a quantile of the F-distribution, but then I realized that those events are not independent, so $P( \Vert X \Vert_\infty < r ) \neq \prod_{i=1}^n P_i$.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ If $r>\frac{1}{\sqrt{2}}$ we have $$P(\|X\|_\infty>r)=nP(X_1>r)=n\int_r^1 \sqrt{1-t^2}^{n-2}C(n)dt.$$ For $r<\frac{1}{\sqrt{2}}$ one could use inclusion-exclusion principle to compute probabilities. However I doubt there exist a closed form solution. $\endgroup$
    – user35593
    Commented Jul 6, 2015 at 12:12
  • $\begingroup$ Thanks ! This a a nice trick for the case $r>\frac{1}{\sqrt{2}}$ indeed. What is the function $C(n)$ in the integral ? $\endgroup$
    – guigux
    Commented Jul 7, 2015 at 8:44
  • $\begingroup$ $C(n)$ is the measure of the $n-2$-dimensionale unit sphere. $\endgroup$
    – user35593
    Commented Jul 7, 2015 at 19:41
  • $\begingroup$ @user35593 More precisely, twice your number, no? Because one also has to count $P(X_1<-r)$ $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Dec 10, 2022 at 18:37
  • $\begingroup$ @user35593 In fact, for the 1-sphere one must obtain $\frac4\pi\arccos(r)$ and I cannot obtain this from your formula? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Dec 10, 2022 at 19:08

2 Answers 2

Reset to default
-2
$\begingroup$

There is a trick to reduce these kinds of questions to questions about independent normals, as in my ancient preprint. For large $n,$ concentration of measure will presumably give you easy estimates.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I'm not sure how to use your result, because the function $\mathbf{1}_{\{\Vert x \Vert_\infty < r\}} (x)$ is not homogeneous of degree $d$ for any $d$ ? $\endgroup$
    – guigux
    Commented Jul 7, 2015 at 8:46
-3
$\begingroup$

Edit: As I write at the end. This is wrong for low dims, but approximately correct for more than a few hundreds, when I guess the coordinates become less dependent.

You can start by uniformly selecting points on the (n − 1)-sphere and then ask what is the infinity norm of such points.

Given a vector $Z$ with $n$ coordinates taken i.i.d. from the normal distribution $Z_i \sim \mathcal{N}(0, 1)$. The CDF of the absolute maximum of those is given by considering the CDF of $n$ points drawn from the half normal distribution $F_{||Z||_{\infty}}(x)={\operatorname{erf}\left( \frac{ x }{\sqrt 2} \right) }^{n}$. Now we need to normalize the points, so they'll be on the unit sphere. Given that the positive squared root of the sum of squared normal variables has a Chi distribution with $n$ degress of freedom, $||Z||_2\sim \chi_n$, we have:

$$P(||X||_{\infty} < r\;|\;||X||_2=1) = \\P(||Z||_{\infty}/||Z||_2 < r) = $$ [wrong transition! (Though it still works in high-dims)] $$\int_{0}^{\infty} P(||Z||_{\infty}/ ||Z||_2 < r\; |\; ||Z||_2 = x) f_{\chi_n}(x)\;dx = \\ \\\int_{0}^{\infty} F_{||Z||_{\infty}}(x \cdot r) f_{\chi_n}(x)\;dx = \\\int_{0}^{\infty} {\operatorname{erf}\left( \frac{ x \cdot r}{\sqrt 2} \right) }^{n} \cdot \dfrac{x^{n-1}e^{-x^2/2}}{2^{n/2-1}\Gamma\left(\frac{n}{2}\right)}\; dx$$

Update

Alternatively, I'm not entirely sure we can do this, but I think we can just consider the expected scale of $r$, instead of calculating it as above. It is the mean of $\chi_n$, so the above should be the same as:

$$ F_{||Z||_{\infty}}(\mu(\chi_n) \cdot r) $$

Update2

These formulations seem to be correct for large enough $n$, but not in general:

enter image description here enter image description here

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ It cannot be true for all values of $r$ because the last integral is certainly analytic when $r>0$, while the answer definitely isn't. $\endgroup$
    – fedja
    Commented Dec 9, 2022 at 23:54
  • 2
    $\begingroup$ The integral is defined over the normalization factor to get to the n-sphere so it is fine I don't understand the meaning of this phrase. Neither do I understand how it becomes constant $1$ for large $r$ (I mean the integral with $erf$, of course) $\endgroup$
    – fedja
    Commented Dec 10, 2022 at 2:32
  • 2
    $\begingroup$ Yes, the entire formula: the last one in the chain. If $r\ge 1$, the whole sphere is there, so the output should be $1$ regardless of $r$. $\endgroup$
    – fedja
    Commented Dec 10, 2022 at 2:42
  • 2
    $\begingroup$ Please be aware that every edit of a question or of one of its answers bumps the thread to the front page. This has happened for this thread already more than 20 times, and this is a nuisance for other users. Please refrain from unnecessary edits to your posts. -- Usually, the vast majority of minor edits can be avoided by writing and proofreading a question or an answer (or any update to such) carefully before posting it. $\endgroup$
    – Stefan Kohl ♦
    Commented Dec 10, 2022 at 15:09
  • 1
    $\begingroup$ @მამუკაჯიბლაძე Marsaglia (1972), en.m.wikipedia.org/wiki/… $\endgroup$
    – Amit Portnoy
    Commented Dec 10, 2022 at 15:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .