What are the odds that n random points on a sphere lie in the same hemisphere?

Additional material

[ Editor: Torsten Sillke sent the following proposal in January 1998,
writing that the formula given above is wrong, that he had looked up
all the references to the problem, and that these problems are better
located in the probability section.  For n = 3 the formula above gives
1 - (1/2)^3 = 7/8, but three points always lie in some hemisphere (the
one bounded by the great circle through two of them that contains the
third). ]

The probability is (n*n-n+2)/2^n for n>=1.

A much simpler is the corresponding problem: What are the odds that
n random points on the circumference of a circle lie in the same
semicircle?  The probability is (2*n)/2^n for n>=1.

Let's calculate the probability p(n,t) that n random points on the
circumference of the unit circle lie in an arc of length 2*pi*t.

For t<=1/2 we have:
  p(n,t) = p(n,t|1) + p(n,t|2) + ... + p(n,t|n) = n*p(n,t|1)
where p(n,t|i) is the probability that the first n points are
contained in an arc of length 2*pi*t with the left endpoint is
the i-th point. This is the case as
  p(n,t|i,j) = 0    (for i != j)
which is the probability that the first n points are in an
arc beginning at the i-th and at the j-th point. This is not
the case for t>1/2. We see that
  p(n,t|1) = t^(n-1)   for 0<=t<=1 and n>=1.
Therefore we have
  p(n,t) = n t^(n-1) = d/dt t^n    for t<=1/2 and n>=1
  p(0,t) = 1.

The case t>1/2 can be found by William Feller, "An Introduction to
Probability Theory and Its Applications", Vol 2, on pages 28 and 29
(Section I.9).

The k-dimensional case was first solved by J. G. Wendel.
------------------------------------------------------------------------
J. G. Wendel; A Problem in Geometric Probability,
  Mathematica Scandinavica 11 (1962) 109-111.
  (Univ. Michigan, Ann Arbor, Michigan, USA and Univ. Aarhus, Denmark)

Let N points be scattered at random on the surface of the unit sphere in
n-space. The problem of the title is to evaluate p(n,N), the probability
that all the points lie on some hemisphere. I shall show that

(1)   p(n,N)  =  2^(-N+1) Sum_{0<=k<=n-1} BinomialCoefficient(N-1,k).

I first heard of the problem from L. J. Savage, who had been challenged
by R. E. Machol to evaluate p(3,4). Savage showed that p(3,4) = 7/8,
and more generally that

(2)   p(n,n+1)  =  1 - 2^(-n).

Then I was able to obtain the relation

(3)   p(n,n+2)  =  1 - (n+2) 2^(-n-1),

and D. A. Darling proved that p(2,N) = N 2^(-N+1), which on setting N=n+2
became

(4)   p(2,n+2)  =  (n+2) 2^(-n-1).

Equations (3) and (4) suggested the attractive "duality relation"

(5)   p(m,m+n) + p(n,m+n)  =  1.

which was found to hold generally. The results (2), (3) and (5) then led
to the conjecture (1).  Since (5) is a corollary to (1) it seems superfluous
to give a separate proof; instead I proceed now to the proof of (1), and
in a slightly more general setting.

Let x_1, x_2, ..., x_N be random vectors in E^n whose joint distribution is
invariant under all reflections through the origin and is such that with
probability one all subsets of size n are linearly independent; for example,
the x_j may be uniformly and independently distributed over the surface of
the unit sphere. The probability p(n,N) is now interpreted as the
probability that all x_j lie in a half-space, i. e. that for some vector y
the inner products (y,x_j) are all positive. I shall show that p(n,N)
satisfies the recurrence relation

(6)   p(n,N)  =  1/2 * (p(n,N-1) + p(n-1,N-1)).

Since the right member of (1) also satisfies (6), together with the evident
boundary conditions p(1,N) = 2^(-N+1), p(n,N) = 1 if (N <= n), this will
complete the proof of (1).

PROOF of (6). It is sufficient to evaluate the corresponding conditional
probability when the x_j are non-zero and lie on fixed lines through the
origin. Suppose that y is perpendicular to none of these lines. Then the
sequence s(y) = {sgn(y,x_j)} is a random point in the set S = {s} of all
ordered N-tuples consisting of plus and minus signs. A specific s is said
to occur if there is a y such that s(y) = s. Let A(s) be the event that s
occurs, and let I(s) be the indicator of A(s). By definition
p(n,N) = Pr{A(s0)}, where s0 = (+,+,...,+). Since any s can be changed into
any other by reflecting appropriate x_j through the origin it follows that
all A(s) are equally likely. Hence

      2^N p(n,N)  =  Sum_{s} Pr{A(s)}  =  E( Sum_{s} I(s) )  =  E(Q),

say, with Q = Q(n,N) = Sum_{s} I(s) being the number of different s that
occur.

Ostensibly Q is a random variable, but in fact a simple argument now shows
that Q is a constant not depending on the directions of the fixed lines,
providing of course that they are linearly independent in sets of n.
Let X_j be the hyperplane perpendicular to x_j. Then Q is just the number
of components (maximal connected subsets) complementary to all the X_j in
E^n, because each component consists of all the vectors y for which s(y)
has a fixed value.

In order to count the components, consider the effect of deleting one
hyperplane, say X_N. There remain N-1 hyperplanes, with complementary
set composed of Q(n,N-1) components. These components are of two kinds:
(i) those which meet X_N, and (ii) those not meeting X_N. In an obvious
notation we have Q(n,N-1) = Q^(i) + Q^(ii). When X_N is restored it cuts
each component of type (i) into two and does not disturb the others.
Therefore Q(n,N) = 2 Q^(i) + Q^(ii). It follows that

(7)   Q(n,N)  =  Q(n,N-1) + Q^(i).

I claim now that Q^(i) = Q(n-1,N-1). In fact, the sets X_j cap X_N are
hyperplanes in the (n-1)-dimensional space X_N, and their normals are
linearly independent in sets of n-1. Therefore
X_N - Cup_{1<=j<=N-1} (X_j cap X_N) has Q(n-1,N-1) components in X_N,
and it is easy to see that these are just the intersections of the
original type (i) components with X_N, establishing the claim.
Substituting into (7) and recalling that Q(n,N) = 2^N p(n,N) we obtain (6).
This completes the proof.

The argument given above is essentially the same as that presented by
Schläfli [Abh. I, pp 209-212], but is included here for the sake of
completeness. I am obliged to H. S. M. Coxeter for the reference. It may
also be remarked that the form of the result (1) shows that p(n,N) equals
the probability that in tossing an honest coin repeatedly the n'th "head"
occurs on or after the N'th toss. But it does not seem possible to find
an isomorphism between coin-tossing and the given problem that would
make the result immediate.

------------------------------------------------------------------------
Random Polygons Inscribed in a Circle,
  American Math. Monthly, 71 (1964) 1135-36, Problem E1658 [1964, 91]
  (Solution by F. G. Schmitt, Jr., Ann Arbor, Michigan. [like Wendel])

Problem (David L. Silverman)
  Points are selected at random on the circumference of a circle until
  they form the vertices of an inscribed polygon which encloses the
  center of the circle. Prove that the "expected polygon" is a pentagon.

[...]

II. Solution by F. G. Schmitt, Jr.
One may as well solve Problem E1658 in n dimensions: Let x_1, x_2, ...
be a sequence of points scattered at random on an (n-1)-sphere in E^n.
The random variable N_n is defined to be the smallest number m such that
the convex hull of the points x_1, ..., x_m contains the center of the
sphere. Find the expected value E(N_n).
  Solution. N_n > k iff the points x_1, ..., x_k are contained in some
hemisphere. J. G. Wendel [A Problem in Geometric Probability, Mathematica
Scandinavica 11 (1962) 109-111] has observed that this event has the same
probability as that of obtaining the nth head on or after the kth toss of
an honest coin. Thus if M_n denotes the total number of tails before the
nth head, then Pr(N_n > k) = Pr(M_n + n >= k) = Pr(M_n + n+1 > k). Hence
M_n and N_n - n - 1 have the same negative binomial distribution with
p=1/2, for which the mean is n.
Thus E(N_n) = E(M_n + n+1) = 2n+1. In particular E(N_2) = 5.
Remark. Var(N_n) = Var(M_n) = 2n. Hence Var(N_2) = 4.

------------------------------------------------------------------------
References:

Kevin Brown;
  Points on sphere problem, 1996
  http://www.seanet.com/~ksbrown/kmath327.htm

William Feller;
  An Introduction to Probability Theory and Its Applications, Vol 2,
  on pages 28 and 29 (Section I.9)
  (Gives the probability that n arcs of length A chosen independently
   and randomly on the perimeter of a circle of circumference C cover
   the whole circle.)

Martin Gardner;
  Time Travel and Other Mathematical Bewilderments,
  Freeman (1988) New York.
  Chapter 15: Curious Maps
  (cites E. N. Gilbert with the probability of n random points lying
   in the same hemisphere as p(n) = (n*n-n+2)/2^n)

E. N. Gilbert;
  The Probability of Covering a Sphere With N Circular Caps,
  Biometrika 52, 1965, p323
  (calculates bounds for caps of given central angle. Cites Wendel's
  result.)

David L. Silverman; (Proposer)
  Random Polygons Inscribed in a Circle,
  American Math. Monthly, 71 (1964) 1135-36, Problem E1658 [1964, 91]
  (Solution by F. G. Schmitt, Jr., Ann Arbor, Michigan. [like Wendel])
  (Expected number of points that the convex hull contains the center,
   n-dim case, E(X) = 2n+1, Var(X) = 2n, negative binomial distribution.
   Wendel's result is used.)

Ludwig Schläfli;
  Theorie der vielfachen Kontinuität, 1852,
  Teil 1: Lehre von den linearen Kontinuen,
  Sektion 16: Über die Zahl der Teile, in welche die n-fache Totalität
  durch eine beliebige Menge (n-1)-facher linearer Kontinuen geteilt wird.
  Gesammelte Math. Abh. I, Basel, 1950, 209-212

J. G. Wendel;
  A Problem in Geometric Probability,
  Mathematica Scandinavica 11 (1962) 109-111.
  Zbl 108.31603
  (Univ. Michigan, Ann Arbor, Michigan, USA and Univ. Aarhus, Denmark)
  (Random points on a hemisphere, n-dim case)

-- Torsten Sillke <TORSTEN.SILLKE@LHSYSTEMS.COM>

[ Editor: two earlier rec.puzzles discussions of the formula above: a
May 1996 thread "POINTS ON SPHERE : wrong solution in the archive?"
(summarized by Douglas Zare, crossposted to sci.math), and a November
1997 posting by Torsten Sillke with a reply by John Rickard. ]

One of the problems in the rec.puzzles archive was to find the
probability that n points chosen on a sphere will be contained in some
hemisphere.  The archive's answer is unjustified and wrong in particular
cases.

David Karr <karr@cs.cornell.edu> wrote:
>[...]
>Interesting.  Computing the probability for n=4 independently
>(not using that formula), I find it is 7/8.  Could it be that
>our "n" is called "n+1" in the archive?

Note that there exists a hemisphere containing a set if and only if the
convex hull does not contain the center of the sphere.  So, the n=4 case
is (the complement of) problem A6 on the 1992 Putnam.

S. Gadgil pointed out to me that allowing the points to be in some other
distribution with spherical symmetry does not change the answer.  This
makes it a more natural question, so I suspect it must have been
studied elsewhere.

>Here's an abbreviated summary of my reasoning for n=4:
>
>First place three points A, B, C randomly.  The fourth point is in the
>same hemisphere as these *unless* it happens to land in the spherical
>triangle A'B'C' where A', B', and C' are the antipodal points of A, B,
>and C (exactly opposite them on the sphere).
>
>So given three points A, B, C, the probability that the fourth point
>will *fail* is proportional to the area of the spherical triangle ABC.
>But that area is (A + B + C - pi)R^2, where in this formula A is the
>measure in radians of the angle at vertex A, etc.
>
>But the angle A is uniformly distributed over the range 0 to pi, with
>expected value pi/2.  Same for B and C.  So the expected area is the
>area of a spherical triangle with three right angles, i.e., an octant
>of the sphere, 1/8 of the total area.
>[...]

That's cleaner than my solution during the competition, but I don't see
that the computation of the average area will generalize nicely to
higher dimensions.

I think the intended solution there was as follows:

Given 4 points A, B, C, and D, in general position, consider the 16
quadruples {+-A, +-B, +-C, +-D}.  The convex hull of 2 of these will
contain the origin (*).  Any choice of +-'s represents the same
distribution, so this gives a "combinatorial" proof that the probability
that the convex hull contains the origin is 1/8.

Proof of (*) for n+2 points on the n-sphere:

The convex hull of a set of points is the set of nonnegative linear
combinations whose total weight is 1.  So we want a linear combination
of the points which is 0, plus other conditions.  N+2 points in an
N+1-dimensional vector space are linearly dependent.  Because we assume
they are in general position, the set of coefficients corresponding to
a sum of 0 is a 1-dimensional space.  Getting to choose a point or its
antipode means that we just want the sum of the absolute values of the
coefficients to be 1; clearly that happens at precisely 2 points on the
line.

Another way of looking at this is that one wants to count the number of
quadrants through which the space of n-tuples with 0 sum passes.

>Anyone for n=5?

I think the above proof should generalize, but I have not been able to
do so.  It seems to be a natural question how many (hyper)quadrants of
the dual space a random flat passes through, although I don't think
that the flats are chosen uniformly.

However, the following works just for d+3 points on a d-sphere, relying
on the solved case of d+2 points.  For points in general position on
the sphere, the convex hull of d+3 points forms a bipyramid, i.e., 2
simplices stuck together.  It is not hard to see that a generic point in
the interior of a bipyramid is contained in precisely 2 of the simplices
formed by choosing d+2 of the d+3 points.  So the expected number of
d+2-tuples whose convex hull contains the origin over-counts by a factor
of 2.  There are d+3 ways of choosing the d+2 points, and any such
choice results in the standard distribution, so the probability is
(d+3)/2 times the answer to the d+2 point case, or (d+3)/2^(d+2).  So
the probability that 5 points on the 2-sphere are contained in some
hemisphere is 1-(5/16) or 11/16.

Note that for more points, the number of simplices containing a point
will not be constant, so more ideas are needed.

In this thread, the case of 4 points on a circle was skipped.  The above
implies the answer there is 1/2, which is easy to check directly.  I
think this case, and perhaps higher ones, can be done by projecting a
uniform distribution on a higher dimension sphere down to the interior
of the sphere; the result will still be symmetric so the second comment
above will apply.  Perhaps n points on a circle is also reasonable by
direct computation.

-- Douglas Zare <zare@cco.caltech.edu>  (May 1996)

The given answer is wrong!!!  As p(n) = 1 - [1-(1/2)^(n-2)]^n gives

 p(3) = 7/8.

but it should be 1.  Then I looked up Martin Gardner.

Martin Gardner;
  Time Travel and Other Mathematical Bewilderments,
  Freeman (1988) New York.
  Chapter 15: Curious Maps
  (cites E. N. Gilbert's result as p(n) = (n*n-n+2)/2^n)

Why is this question in the geometry section and not in the probability
one?  Is the generalization for the d-dim case known (or given by
Gilbert)?

I need this for the following question:

  How many points must be generated in the average on the sphere, such
  that their convex hull contains the center of the sphere?

The probability p3(n) that the n random points lie in the same
hemisphere is (E. N. Gilbert, 65)

  p3(n) = (n*n-n+2)/2^n
        = (Binomial(n-1,2)+Binomial(n-1,1)+Binomial(n-1,0))/2^(n-1)
  p3(0) = 1

The expected waiting time E3 is

  E3 = Sum_{n>=0} p3(n)
     = 1 + Sum_{n>=1} p3(n)
     = 1 + Sum_{n>=0} Binomial(n,2)/2^n
         + Sum_{n>=0} Binomial(n,1)/2^n
         + Sum_{n>=0} Binomial(n,0)/2^n
     = 1 + 2 + 2 + 2
     = 7

The binomial sums have been calculated with the relation

  Sum_{n>=k} Binomial(n,k) x^(n-k) = 1/k! d^k/dx^k (1-x)^(-1)
                                   = (1-x)^(-1-k)

<= Generalizations to d-spheres =>

Looking at the probabilities for the dimensions we calculated so far

  p1(n) = (Binomial(n-1,0))/2^(n-1)
  p2(n) = (Binomial(n-1,1)+Binomial(n-1,0))/2^(n-1)
  p3(n) = (Binomial(n-1,2)+Binomial(n-1,1)+Binomial(n-1,0))/2^(n-1)

it is not far to conjecture for p4(n)

  p4(n) = (Binomial(n-1,3)+Binomial(n-1,2)+Binomial(n-1,1)
           +Binomial(n-1,0))/2^(n-1)

  This would give E4 = 9 and E(d) = 2d+1.

-- Torsten Sillke <Torsten.Sillke@lhsystems.com>  (November 1997)

Torsten Sillke <Torsten.Sillke@lhsystems.com> wrote:
: What are the odds that n random points on a sphere lie in the same
: hemisphere?

: The given answer is wrong!!!

Yes -- try looking in DejaNews for a thread in rec.puzzles in May 1996
with the subject "POINTS ON SPHERE : wrong solution in the archive?".
The result you quote from Gilbert of (n*n-n+2)/2^n is correct.

: Is the generalization for the d-dim case known (or given by Gilbert)?

Yes; it was derived in the thread.  As you guess, for a sphere in
d-dimensional space the probability is

  ((n-1)C0 + (n-1)C1 + ... + (n-1)C(d-1)) / 2^(n-1)

where aCb is the binomial coefficient (aCb = a!/(b!(a-b)!) if
0 <= b <= a; aCb = 0 if b > a).

-- John Rickard <jrr@atml.co.uk>