From: bwallet@nswc.navy.mil (Brad Wallet)
Newsgroups: sci.stat.math,sci.math,sci.math.research
Subject: Another Geometric Probability Problem
Date: Fri, 27 Mar 1998 13:09:54 GMT

Wendell (Math. Scand. 11, 1962, 109-111) calculated the probability
that n points uniformly distributed on a d dimensional hypersphere
lie on some hemisphere.  Does anyone know if anyone has calculated
the probability that given N points, at least n of those points lie
on some hemisphere?

Brad
==============================================================================

From: callan@stat.wisc.edu (David Callan)
Newsgroups: sci.math.research
Subject: Re: Another Geometric Probability Problem
Date: Tue, 21 Apr 1998 21:02:05 -0500

sci.math.research:9116

>Wendell (Math. Scand. 11, 1962, 109-111) calculated the probability
>that n points uniformly distributed on a d dimensional hypersphere
>lie on some hemisphere.  Does anyone know if anyone has calculated
>the probability that given N points, at least n of those points lie
>on some hemisphere?

>Brad


I can give a generating function answer to your question in two dimensions
(points on a circle). I have some ideas for a proof but haven't been able
to push them through yet.

For  k points P_i, 1<=i<=k, on a circle, let Q_1(=P_1), Q_2,...,Q_k denote
the points in clockwise order. Let nu(Q_i) denote the number of these
points in the (open) semicircle extending clockwise from Q_i and let nu be
the vector (nu(Q_i))_{1<=i<=k}. Then nu has 2^(k-1) possible values and is
uniformly distributed on them when the P_i are random. This reduces the
problem to a discrete one.

Now let X denote the size of the largest subset of the k (random) points
lying on a semicircle.  Then for  0 <= n <= (k-1)/2

                  P(X >= k-n) = (k-2n) p(k-2n-2,n) / 2^(k-1)

where p(k,n) is the coefficient of x^n in the series expansion of

                     p(k) := 1/( (1-4x) q(k) )  

with 

          q(k) = sum_{j>=0} (-1)^j Binomial(k+1-j,j) x^j.

Thus q(-1) = q(0) = 1, q(1) = 1-x, q(2) = 1-2x, q(3) = 1-3x+x^2,... , and
the q(k) polynomials satisfy the recurrence relation  q(k) = q(k-1) - x
q(k-2) (and are virtually Chebychev polynomials of the second kind).

The case n = 0 yields the known probability that all k points lie on a
semicircle: k/2^(k-1). If n = Floor[(k-1)/2], then some k-n points must
lie on a semicircle, as reflected by the last entry in each row of the
following table for P(X >= k-n) (omitting the 1/2^(k-1) factor)
  
     n
  \  
   \  0     1      2     3      4 
k   \  
1     1
2     2
3     3     4
4     4     8
5     5    15     16
6     6    24     32
7     7    35     63    64
8     8    48    112   128
9     9    63    180   255    256
10   10    80    270   480    512



David Callan  
Department of Statistics  
University of Wisconsin-Madison  
1210 W. Dayton Street  
Madison, WI 53706-1693

callan@stat.wisc.edu