1
$\begingroup$

It's been said that for high dimensions a hypersphere is "nearly all equator". The amount of space near the poles is just ridiculously small. This of course means that from a uniformly random sample from the surface, any given Cartesian coordinate is unlikely to be large. In $n$ dimensions this is just the standard weighting $\sim \sin^{n-2} \theta \, \text{d}\theta$.

I would like to know instead about the chances that all Cartesian coordinates are "small", under some $\epsilon$, to be concrete. They're identically distributed, of course, but not independent, which complicates things. I can't seem to get better bounds than Chebyshev/Markov and Union-Bound. I wouldn't expect the correlation to be so bad as to make the Union-Bound anywhere close either. Is there any sensible way to get out a less pessimistic bound on the distribution of the maximum? Failing that, does anyone have better suggestions for the individual bounds?

Edit adding unreasonably sloppy bound:

$\begin{align*} E[x^2] &= 1/n \\ P(x^2 > a) & \leq 1/na \\ P(\max_i \quad x_i^2 > a) &\leq 1/a \end{align*}$

  • 0
    It depends on the "small". Yes, at least one must be larger than $\epsilon = \sqrt{1/n}$, but how does that certainty fall as $\epsilon$ grows? Yes, my estimate is quite silly. That's why I'm asking if anyone has better approaches.2011-07-12

2 Answers 2

1

Some very crude estimates for the asymptotics can be obtained from the area of the spherical cap. Consider $P(\max |x_i| > \alpha)$ for $\alpha > \sqrt{1/2}$. Let $A(x,n)$ be the area of the spherical cap of height $x$ of $S^{n-1}\subset \mathbb{R}^n$, then you precisely have that

$ P(\max |x_i| > \alpha) = \frac{2n A(1-\alpha,n)}{\Omega_n} $

where $\Omega_n$ is the area of $S^{n-1}$. This you can estimate using whatever known asymptotics of the regularised incomplete beta functions you can find. (See the Wikipedia article on the expression for $A(x,n)$.)

But noting that the area of the spherical cap can be estimated below and above by area of the Euclidean disks:

$ (\cos^{-1}(1-x))^{n-1}V_{n-1} \geq A(x,n) \geq (1-(1-x)^2)^{(n-1)/2}V_{n-1} $

where $V_n$ is the volume of the unit $n$ dimensional disk. So we have that

$ \frac{2V_{n-1}}{V_n} (\cos^{-1}(\alpha))^{n-1} \geq P(\max |x_i| > \alpha) \geq \frac{2 V_{n-1}}{V_n} (1-\alpha^2)^{(n-1)/2} $

where the ratio $\frac{V_{n-1}}{V_n} = B(1/2, (n+1)/2)$ where $B$ is the Beta function.


For the other end point, note that (assuming $x_i \geq 0$) $n \max x_i \geq \sum x_i \geq \max x_i$. You get that, defining the vector $v_n = (1/\sqrt{n},\ldots, 1/\sqrt{n})$, that restricting to $x_i \geq 0$

$ P(x\cdot v_n \leq \frac{1}{\sqrt{n}}\alpha) \leq P(\max x_i \leq \alpha) \leq P( x\cdot v_n \leq \sqrt{n}\alpha) $

Now over the entire sphere, we can divide into $2^n$ orthants, and you can use the previous results to estimate. This estimate is not very good though. The upper bound can be easily sharpened if you replace the ball which we used by a simplex.

  • 0
    Now, the idea is that we can get an upper bound of the area of the spherical cap by the Euclidean disk of the same radius (spherical distance). If I am not mistaken, you can get an upper bound for the area of the "shape" by the area/volume of a simplex in Euclidean space whose circumscribing sphere has the appropriate radius ($\cos^{-1}(1/\sqrt{n}) - \cos^{-1}(1/\sqrt{n} + \epsilon)$).2011-07-12
0

An asympotic aproach for large $n$. This is quite informal, I believe it could be worked on.

Let's consider $n$ iid random variables ${ \bf y} = \{y_i\}$, gaussian with zero mean and variance $1/n$. Let $c=\sum y_i^2$. Then, $E(c)=1$, $Var(c)=2/n$

Comparing ${ \bf y}$ with ${ \bf x} = \{x_i\}$ (this one uniformily distributed over the unitary sphere surface: $\sum x_i^2=1$), we see that they are obviously not equivalent, but we also see that the probability density of ${ \bf y}$ conditioned on $c({ \bf y})=1$ is equal to the density of ${ \bf x}$. And, informally speaking, ${ \bf y}$ asymptotically concentrates around this region. Then we could use that as an aproximation, and evaluate the asked probability as

$ P(|x_i| < \epsilon) \approx P(|y_i| < \epsilon) = \left[erf \left( \epsilon \sqrt{\frac{n}{2}} \right) \right]^n$

  • 0
    Yes, this approximation is pretty good in the large $n$ limit, but can you bound the corrections?2011-07-12