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

$\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
    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
    Jul 7, 2015 at 8:44
  • $\begingroup$ $C(n)$ is the measure of the $n-2$-dimensionale unit sphere. $\endgroup$
    – user35593
    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$ 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$ Dec 10, 2022 at 19:08

2 Answers 2

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

$\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
    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

$\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
    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
    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
    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
    Dec 10, 2022 at 15:09
  • 1
    $\begingroup$ @მამუკაჯიბლაძე Marsaglia (1972), en.m.wikipedia.org/wiki/… $\endgroup$ Dec 10, 2022 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.