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

  • $\begingroup$ On the surface of the sphere? (And a 1-dimensional sphere = circle right?) $\endgroup$
    – kennytm
    Aug 2 '10 at 14:01
  • $\begingroup$ @KennyTM: The circle is the two dimensional sphere, I think. Otherwise the answer would be 0. $\endgroup$
    – Jens
    Aug 2 '10 at 14:09
  • $\begingroup$ @Jens fixed, thanks (for 1-dimensional sphere should be 3 points, of course) $\endgroup$
    – Grigory M
    Aug 2 '10 at 14:17
  • 1
    $\begingroup$ @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).) $\endgroup$ Aug 2 '10 at 19:02
  • 1
    $\begingroup$ Related: video from 3Blue1Brown $\endgroup$
    – Grigory M
    Dec 20 '17 at 13:26

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.

  • $\begingroup$ interesting generalization, thanks $\endgroup$
    – Grigory M
    Aug 2 '10 at 17:23

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.

  • $\begingroup$ 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). $\endgroup$
    – Grigory M
    Aug 2 '10 at 16:10
  • $\begingroup$ thanks for detailed answer $\endgroup$
    – Grigory M
    Aug 3 '10 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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