18
$\begingroup$

Suppose we have a ($n-1$ dimensional) unit sphere centered at the origin: $$ \sum_{i=1}^{n}{x_i}^2 = 1$$ Given some some $d \in [0,1]$, what is the probability that a randomly selected point on the sphere, $ (x_1,x_2,x_3,...,x_n)$, has coordinates such that $$|x_i| \leq d$$ for all $i$?

This is equivalent to finding the intersection of the $(n-1)$-hypersphere with the $n$-hypercube of side $2d$ centered at origin, and then taking the ratio of that $(n-1)$-volume over the $(n-1)$-volume of the $(n-1)$-hypersphere.

As there are closed-form formulas for the volume of a hypersphere, the problem reduces to finding the $(n-1)$-volume of the aforementioned intersection.

All attempts I've made to solve this intersection problem have led me to a series of nested integrals, where one or both limits of each integral depend on the coordinate outside that integral, and I know of no way to evaluate it. For example, using hyperspherical coordinates, I have obtained the following integral: $$ 2^n n! \int_{\phi_{n-1}=\tan^{-1}\frac{\sqrt{1-(n-1)d^2}}{d}}^{\tan^{-1}1} \int_{\phi_{n-2}=\tan^{-1}\frac{\sqrt{1-(n-2)d^2}}{d}}^{\tan^{-1}\frac{1}{\cos\phi_{n-1}}}\ldots\int_{\phi_1=\tan^{-1}\frac{\sqrt{1-d^2}}{d}}^{\tan^{-1}\frac{1}{\cos\phi_2}} d_{S^{n-1}}V$$ where $$d_{S^{n-1}}V = \sin^{n-2}(\phi_1)\sin^{n-3}(\phi_2)\cdots \sin(\phi_{n-2})\ d\phi_1 \ d\phi_2\ldots d\phi_{n-1}$$ is the volume element of the $(n-1)$–sphere. But this is pretty useless as I can see no way of integrating this accurately for high dimensions (in the thousands, say).

Using cartesian coordinates, the problem can be restated as evaluating: $$ \int_{\sum_{i=1}^{n-1}{x_i}^2\leq1, |x_i| \leq d} \frac{1}{\sqrt{1-\sum_{i=1}^{n-1}{x_i}^2}}dx_1 dx_2 \ldots dx_{n-1}$$ which, as far as I know, is un-integrable.

I would greatly appreciate any attempt at estimating this probability (giving an upper bound, say) and how it depends on $n$ and $d$. Or, given a particular probability and fixed $d$, to find $n$ which satisfies that probability.

Edit: This question leads to two questions that are slightly more general:

  1. I think part of the difficulty is that neither spherical nor Cartesian coordinates work very well for this problem, because we're trying to find the intersection between a region that is best expressed in spherical coordinates (the sphere) and another that is best expressed in Cartesian coordinates (the cube). Are there other problems that are similar to this? And how are their solutions usually formulated?

  2. Also, the problem with the integral is that the limits of each of the nested integrals is a function of the "outer" variable. Is there any general method of solving these kinds of integrals?

$\endgroup$
7
  • 2
    $\begingroup$ What kind of accuracy are you aiming for? Approximating the surface measure of the sphere by a standard Gaussian would give results not worse than deviating ~1/n^{1/2} in d, and would probably be much better than that in most cases. $\endgroup$
    – Thorny
    Jun 18, 2010 at 11:10
  • $\begingroup$ Have you considered approximating with a Monte-Carlo method? $\endgroup$
    – S. Carnahan
    Jun 18, 2010 at 14:02
  • $\begingroup$ I agree with the above questions: do you think of d as fixed and n quite large (in which case the probability will go to 1 quite rapidly even for small d)? Or is n considered quite small (in which case one could find a numerical answer, but probably no simple closed form)? $\endgroup$ Jun 19, 2010 at 1:46
  • 1
    $\begingroup$ For $d > 1/\sqrt{2}$ you "just" need to figure out how much a bunch of spherical caps contribute to the total surface area. For $d < 1/\sqrt{2}$ there are a bunch of identical disconnected regions of the cube outside the sphere, and at first glance it seems like computing their areas is the harder part of the problem. But here it seems like inclusion-exclusion should render this doable. $\endgroup$ Jun 19, 2010 at 3:59
  • $\begingroup$ Thanks for the comments. I am not familiar with the methods mentioned by Thorny and Scott, and will read about them first and report back on the results. I should perhaps add that this question was first posed to me by a software engineer who's been using experimental estimates on large n. His method involves randomly selecting large numbers of points on an n-sphere and then checking the proportion of points that fulfill the conditions, and this sounds a lot like (the little I know of) the Monte-Carlo method. If this is indeed the best method, I guess there isn't much more to be said. $\endgroup$
    – L.Z. Wong
    Jun 19, 2010 at 8:33

1 Answer 1

16
$\begingroup$

Denote the median of $\max_{i=1,\dots,n}|x_i|$ on the sphere by $M_n$. It is known that the ratio between $M_n$ and $\sqrt{\log n/n}$ is universally bounded and bounded away from zero. If you take $d=M_n$ then the quantity you are looking for is exactly $1/2$. It is also known that the $\infty$-norm ($\max_{i=1,\dots,n}|x_i|$) is ``well concentrated" on the sphere meaning in particular that for any $\epsilon>0$, if you take $d<(1-\epsilon)M_n$ the probability you're interested in tends to zero and if you take $d>(1+\epsilon)M_n$, it tends to 1. Quite precise estimates are known.

The way these things are estimated is by relating the uniform distribution on the sphere to the distribution of a standard Gaussian vector: If $g_1,\dots,g_n$ are independent standard Gaussian variables then the distribution of $$ \frac{(g_1,\dots,g_n)}{(\sum g_i^2)^{1/2}} $$ is equal to the uniform distribution on the sphere. So the quantity you're looking for is the probability that $\max_{i=1,\dots,n}|g_i|\le d (\sum g_i^2)^{1/2}$. Since $(\sum g_i^2)^{1/2}$ is very well concentrated near the constant $\sqrt n$, this is asymptotically the same as the probability that $\max_{i=1,\dots,n}|g_i|\le d \sqrt n$.

For general reference in a much more general setting you can look here: Milman, Schechtman, Asymptotic theory of finite-dimensional normed spaces. For a finer treatment of the special case of the $\infty$-norm, look here: G. Schechtman: The random version of Dvoretzky's theorem in $\ell_n^\infty$.

$\endgroup$

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.