Skip to main content
29 of 29
added 61 characters in body

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