Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the probability that the convex hull of n+2 random points on n-dimensional sphere contains sphere's center?

share|improve this question
    
On the surface of the sphere? (And a 1-dimensional sphere = circle right?) –  KennyTM Aug 2 '10 at 14:01
    
@KennyTM: The circle is the two dimensional sphere, I think. Otherwise the answer would be 0. –  Jens Aug 2 '10 at 14:09
    
@Jens fixed, thanks (for 1-dimensional sphere should be 3 points, of course) –  Grigory M Aug 2 '10 at 14:17
    
@KennyTM Yes (to both questions) –  Grigory M Aug 2 '10 at 14:18
1  
@Noldorin: What makes you think this question is not suitable here? (Unrelated comment: this result (Wendel's theorem) is also proved (similar to the answers below) in The art of mathematics: coffee time in Memphis by Béla Bollobás, p. 315-317 (currently inaccessible).) –  ShreevatsaR Aug 2 '10 at 19:02

2 Answers 2

up vote 7 down vote accepted

This is one of those old chestnuts that come up again and again. To be precise, the probability that the convex hull of $n+2$ points in $S^n$ (the unit sphere in $\mathbb{R}^{n+1}$) contains the origin is $2^{-n-1}$.

There's a brief argument at Wolfram's mathworld which I don't find entirely convincing but which certainly can be patched to form a convincing argument. In brief, show that for random points $P_1,\ldots,P_{n+2}$ on the sphere, then with probability one, exactly one choice of signs will put the centre in the convex hull of $\pm P_1,\pm P_2,\ldots,\pm P_{n+1}$ and $P_{n+2}$.

Added (3/8/2010) Thanks to Grigory for his comment. Changing the notation slightly, one can show that under some fairy weak hypotheses, if we choose $m+1$ points randomly and indepedently in $\mathbb{R}^m$ the probability their convex hull contains the origin is $2^{-m}$.

Take a probability distribution on $\mathbb{R}^m$ and choose a sequence of points (which we identify with vectors) independently from that distribution. Our first condition on this distribution is that $m$ vectors $v_1,\ldots,v_m$ chosen independently from it are linearly independent with probability one. This can fail if say some point occurs with nonzero probability or the distribution lies in a hyperplane through the origin. Assume this condition.

Now a sequence $v_0,v_1,\ldots,v_m$ of random points chosen according to our distribution are linearly independent: there are reals $a_i$ not all zero with $\sum_i a_i v_i=0$. By our condition, with probability one, the sequence $(a_0,\ldots,a_m)$ is unique up to constant multiple, and moreover all the $a_i$ are nonzero. So we may assume $a_0=1$ and $a_1,\ldots,a_m$ are nonzero and uniquely determined. Then the convex hull of the $v_i$ contains the origin if an only if all the $a_i$ are positive.

Now we introduce another condition: that the distribution is centrally symmetric; in detail the probability that a random vector $v$ lies in a set $A$ equals the probability that $-v$ lies in $A$. A condition like this is clearly necessary; it stops the distribution being supported on a small region far from the origin. This condition shows that all the $2^m$ possibilities of signs for $a_1,\ldots,a_m$ are equiprobable; since changing the sign of some $v_i$ changes the sign of $a_i$.

To conclude, if our probability distribution on $\mathbb{R}^m$ satisfies these two condition, the probability that the convex hull of $m+1$ indepdendently chosen points contains the origin is $2^{-m}$. These conditions are satisfied by the uniform distribution on a sphere with centre at the origin, but also by many others.

share|improve this answer
    
To make it more convincing one may add some words about barycentric coordinates: a point O lies inside a convex hull of $P_1,...,P_{n+2}$ iff all of its barycentric coordinates (w.r.t. these points) are positive (and switching sign of $P_i$ is almost the same thing as switching sign of i-th barycentric coordinate of O). –  Grigory M Aug 2 '10 at 16:10
    
thanks for detailed answer –  Grigory M Aug 3 '10 at 17:19

This problem is discussed in J. G. Wendel; A Problem in Geometric Probability, Mathematica Scandinavica 11 (1962) 109-111. Wendel showed, that the probability of $N$ random points lying on the surface of the unit sphere in dimension $n$ all lie on one hemisphere is

$2^{-N+1}\sum_{k=0}^{n-1} {{n-1}\choose k}$

I've found this here.

share|improve this answer
    
interesting generalization, thanks –  Grigory M Aug 2 '10 at 17:23
    
@Jens: I am reading J. G. Wendel, A Problem in Geometric Probability mscand.dk/article.php?id=1647. I understand all the other parts, including the part leading up to the equation, except the equation $2^N p_{n,N} = \sum_s \text{Pr}{A_s}$. Could any of you explicate this step? Thank you. –  Hansen Nov 17 '13 at 20:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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