POINTS ON SPHERE : wrong solution in the archive?
Douglas J. Zare
I've added sci.math , so let me summarize.
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 <ka...@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
http://www.cco.caltech.edu/~zare
Douglas J. Zare
Douglas J. Zare <za...@cco.caltech.edu> wrote:
>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.
>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.
>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.
>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.
>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,
>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.
I'm surprised that I haven't seen any followups. I still find this problem
fascinating.
A few minutes after I posted, I realized that it is also easy to do the
case of n points on S^1 by direct computation. If one mods out by
rotation, n points are defined by the arcs between them, which will still
be uniformly distributed under the condition that their sum is 2pi. The
intersection of X1+...+Xn=2pi with the positive quadrant is a simplex of
dimension n-1. That some Xi > pi is equivalent to the condition that the
points do not contain the origin in their convex hull, and these may be
thought of as the n 1/2-size corners of the simplex. So, the probability
that the convex hull contains the origin is 1-(n/2^(n-1)).
The case of the 0-sphere is worth including; the probability that the
convex hull contains the origin is 1-(1/2^(n-1)).
Let me tabulate what has been established:
S^d
n 0 1 2 3 4 5 6 7 8
points-------------------------------------------------
1
2 --- 0 0 0 0 0 0 0 0
2
3 1
3 --- --- 0 0 0 0 0 0 0
4 4
7 4 1
4 --- --- --- 0 0 0 0 0 0
8 8 8
15 11 5 1
5 ---- ---- ---- ---- 0 0 0 0 0
16 16 16 16
31 26 6 1
6 ---- ---- ---- ---- 0 0 0 0
32 32 32 32
63 57 7 1
7 ---- ---- ---- ---- 0 0 0
64 64 64 64
Let P(n,d) be the probability that the convex hull of n points on the S^d
contains the origin.
Conjecture:
P(n-1,d-1) + P(n-1,d)
P(n,d) = -----------------------
2
This would imply that the numerators above are partial sums of rows of
Pascal's triangle. Further, it implies that P(n,d)+P(n,n-d-2)=1.
This should be doable by the subspace argument, because every quadrant is
has a representative in a space or its orthogonal complement. In
particular, it would be nice to get a bijective proof that P(2d+2,d)=1/2.
The conjecture suggests that there should be some nice argument relating
the condition to binary vectors of weight greater than d.
Douglas Zare
http://www.cco.caltech.edu/~zare
Andrew Lord
Douglas Zare wrote:
>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
>http://www.cco.caltech.edu/~zare
Solving points on a circle is easy to do directly. The result (which is
just a series of integrals) is:
1 for N = 1,2
3/4 for N = 3
1/(2**N-1) where N > 3.
This gives 1/2 for N = 4.
Cheers
Andrew Lord
Andrew Lord
Sorry folks - missed a typo - previous post was meant to read:
>Solving points on a circle is easy to do directly. The result (which is
>just a series of integrals) is:
>
>1 for N = 1,2
****
N/(2**N-1) where N > 2.
****
>
>This gives 1/2 for N = 4.
Andrew Lord
Andrew Lord
Easy circle solution:
Order N points on a circle. Rotate circle until point A is at a fixed
reference point. Probability of each of the remaining N-1 points being in
the semicircle following A is simply 1/2**(N-1). But, we can do the same
thing we each of the N points in turn. Total probability is therefore:
N/2**(N-1). (see previous post).
Sphere problem using same approach:
Pick two points from N and draw a great circle through them. Probability
of the remaining N-2 being on one side or the other is 1/2**(N-3). Number
of ways of choosing our first two points from N is N(N-1)/2. This gives:
N(N-1)/2**(N-2). This result is incorrect because it counts solutions
twice.
This is most easily seen in the case of four points. We choose a great
circle through A and B. We then assume C and D both lie either to one
side or the other of A and B (prob. = 1/2). We can choose A and B in 6
ways. However, once a great circle through A and B fixes C and D on one
side, then it is easy to see that a great circle through B-C, C-D and D-A
(assuming we label them that way) also fixes the remaining points on one
side or the other. In other words the four point solution needs to be
reduced by a factor of four. The result is 3/4 as in previous mails.
The problem is not so simple for 5 points and above. The problem seems
however to reduce to another related issue: given N points on a
hemisphere - what is the average number of great circles drawn through
two of the points that forms the border of the ensemble?
With four points, the answer is always 4. With 5 points it is either 4 or
5 - but with what weighting? Is this a known problem (either on a
hemisphere or on a flat surface)? Is this problem a reduction of the
previous one or even harder?
Cheers
Andrew Lord
Kevin Brown
> probability that n points chosen on a sphere will be contained in
> some hemisphere. The archive's answer is unjustified and wrong
>> =========> rec.puzzles FAQ: geometry/points.on.sphere.p <=======
>>
>> PROBLEM: What are the odds that n random points on a sphere lie
>> in the same hemisphere?
>>
>> SOLUTION: The probability is 1 - [1 - (1/2)^(n-2)]^n , where n
>> is the # of points on the sphere. The question will become a
>> lot easier if you restate it as the following:
>>
>> What is the probability in finding at least one point such
>> that all the other points on the sphere are on one side of
>> the great circle going through this point.
>>
>> When n=2, the probability = 1; when n=infinity, it becomes 0.
>> In his Scientific American column which was titled "Curious Maps",
>> Martin Gardner ponders the fact that most of the land mass of
>> the Earth is in one hemisphere and refers to a paper which models
>> continents by small circular caps. He gives the above result.
>> See "The Probability of Covering a Sphere With N Circular Caps"
>> by E. N. Gilbert in Biometrika 52, 1965, p323.
>> ======================= end of FAQ article =======================
>
> ...it is...easy to do the case of n points on S^1 by direct
> arcs between them, which will still be uniformly distributed under the
> condition that their sum is 2pi. The intersection of X1+...+Xn=2pi with
> the positive quadrant is a simplex of dimension n-1. That some Xi > pi
> is equivalent to the condition that the points do not contain the
> origin in their convex hull, and these may be thought of as the n
> hull contains the origin is 1-(n/2^(n-1)).
William Feller's book "An Introduction to Probability Theory and
Its Applications" 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 as
m / n \ / A \ n-1
Pr{cover} = SUM (-1)^k ( ) ( 1 - k --- )
k=0 \ k / \ C /
where m is the greatest integer less than C/A. The negation of this
covering event is that the arcs leave at least one gap, meaning that
the largest separation between the center points of two neighboring
arcs is greater than A. This is equivalent to the condition that
all n center points fall on an arc of length less than C-A. Thus,
the probability that all points fall on an arc of length less than
C-A is just 1 - Pr{cover}. Letting x denote the fraction (C-A)/C
we have
m / n \ / \ n-1
Pr{x;n} = - SUM (-1)^k ( ) ( 1 - k (1-x) )
k=1 \ k / \ /
In particular, with x = 1/2 (meaning all n points fall in some half of
the circle) this gives Pr{1/2,n} = n/2^(n-1). I wouldn't be surprised
if Feller's book also covers higher dimensional cases, but I don't
remember.
Another way of approaching this problem is to split the surface
of S^k in half along various axes, and use inclusion-exclusion to
compute the probability of all the points falling into one of those
discrete halves. Then carry this over to the limit as the number
of halves approaches all possible halves. This is admittedly not
very efficient, but some of the results for the discrete cases are
interesting.
To illustrate, consider the simple case of S^1. Divide the perimeter
into 2k equal arcs denoted sequentially by a_1, a_2,..., a_(2k), and
let A_i denote the event of all n randomly placed points lying on
the semi-circle composed of the arcs a_i, a_(i+1),...a_(i+k-1). To
determine the probability that at least one A_i is true, apply the
inclusion-exclusion principle step-by-step as follows:
Pr{A_1} = (1/2)^n
Pr{A_1 U A_2} = (1/2)^n + (1/2)^n - ((k-1)/2k)^n
Pr{A_1 U A_2 U A_3}
= Pr{A_1 U A_2} + Pr{A_3} - Pr{(A_1 U A_2) AND A_3}
and so on. As each additional A_i up to A_(k+1) is included in the
union, the probability of the union is increased by
/ 1 \ n / k-1 \ n
( --- ) - ( ----- )
\ 2 / \ 2k /
so we have
/ 1 \ n // 1 \ n / k-1 \ n\
Pr{A_1 U A_2 U...U A_(k+1)} = ( --- ) + k (( --- ) - ( ----- ) )
\ 2 / \\ 2 / \ 2k / /
As each of the remaining terms A_(k+i), i=2 to k, is added to the
union, the probability is increased by
/ 1 \ n / k-1 \ n / i-1 \ n / i-2 \ n
( --- ) - ( ----- ) - ( ----- ) + ( ----- )
\ 2 / \ 2k / \ 2k / \ 2k /
The 3rd and 4th terms in these quantities cancel on consecutive values
of i, so their net effect is just a single term -((k-1)/(2k))^n.
Thus, the probability of all n points falling in k contiguous arcs
is _ _
| / 1 \ n / k-1 \ n |
Pr{A_1 U ... U A_(2k)} = 2k | ( --- ) - ( ----- ) |
|_ \ 2 / \ 2k / _|
_ _
k | / 1 \ n |
= ------- | 1 - ( 1 - --- ) |
2^(n-1) |_ \ k / _|
Expanding the binomial, we have
Pr{A_1 U ... U A_(2k)}
_ _
n | n-1 /1\ (n-1)(n-2) /1\ 2 |
= ------- | 1 - --- ( - ) + ---------- ( - ) - ... |
2^(n-1) |_ 2! \k/ 3! \k/ _|
which gives the result n/2^(n-1) in the limit as k -> inf. It's
interesting that if our circle is not infinitely divisible, but
is really composed of a large number of discrete segments (as
may actually be the case in some quantum sense), then the true
probability is given by the above discrete formula (with some
suitable k) rather than the continuous limit.
So much for the trivial S^1 case. Can we apply this same method to
the S^2 case? In principle it's certainly possible; simply draw
several great circles on the sphere and then use inclusion-exclusion
to find the probability of all n points falling in one of those
hemispheres. However, it's not so easy to come up with a nice metric
for the surface of a sphere consisting entirely of symmetrical great
circles such that the resolution can be increased indefinitely.
Choosing just a single axis and drawing the corresponding great
circle, it's clear that the probability of all n points falling in
one of these two specific hemispheres is (1/2)^(n-1). Now suppose we
choose three orthogonal axes and draw the corresponding great circles.
This divides the surface into 8 identical "triangular" regions that
define 6 distinct hemispheres. By inclusion-exclusion we find that
the probability of all n points falling in one of these 6 hemispheres
is exactly
/ 1 \ n / 1 \ n / 1 \ n
Pr{n;3} = 6 ( --- ) - 12 ( --- ) + 8 ( --- )
\ 2 / \ 4 / \ 8 /
In the case of FOUR great circles (normal to the four axes of a cube)
the derivation is a bit more challenging. In this case the surface
is divided into 6 "square" regions and 8 "triangular" regions. If we
let s and t denote the areas of these two types of regions as a
fraction of the total area, then each of the 8 hemispheres has area
4t+3s = 1/2. The non-zero overlaps between two hemispheres come in
two types: there are 12 of area 2t+2s and 12 of area 2t+s. The non-
zero overlaps between three hemispheres also come in two types: there
are 24 of area t+s and 8 of area t. Finally, the non-zero overlaps
between four hemispheres come in two types: there are 8 of area t and
6 of area s. Thus, the probability of all n points falling within
one of these 8 hemispheres is
Pr{n;4} =
8(4t+3s)^n - 12(2t+2s)^n - 12(2t+s)^n + 24(t+s)^n - 6(s)^n
Noting that the spherical angle at each corner of the triangular
regions is 2invtan(1/sqrt(2)) we have
t = 0.043869914...
s = 0.108173448...
and the probability can be expressed as
_ _
/ 1 \ n | n n / 1-q \ n n |
Pr{n;4} = 2( --- ) | 4 - 6(1-q) - 6q + 12( ----- ) - 3(1-2q) |
\ 2 / |_ \ 2 / _|
where q = 2invtan(1/sqrt(2))/PI.
By the way, the four great circles in this example are the projections
of the edges of an inscribed "cuboctahedron", which is one of the
13 semi-regular Archimedean solids. The only other Archimedian solid
whose projected edges are great circles is the "icosidodecahedron",
which has 6 great circles (one normal to each of the 6 axes of the
icosahedron). I started working out the details of that case, but
then I decided to tackle the harder case of 10 great circles on a
sphere, normal to the 10 axes of a dodecahedron. This gives 20
distinct hemispheres. (Interestingly, the corresponding solid is
not one of the Archimedean solids, because it has two distinct
kinds of verticies.)
These 10 great circles divide the surface of the sphere into a total
of 92 regions: 60 triangles, 20 hexagons, and 12 pentagons. Letting
t, h, and p denote these individual areas as fractions of the total
sphere's area, each hemisphere has area 6p + 10h + 30t = 1/2. The
inclusion-exclusion formula gives the overall probability that all
n points fall in one of these 20 hemispheres as
Pr{n;10} = 20(6p+10h+30t)^n - 30(4p+8h+22t)^n - 60(4p+6h+18t)^n
+ 60(3p+6h+16t)^n + 60(3p+5h+14t)^n - 60(2p+5h+12t)^n
- 60(2p+4h+12t)^n + 120(2p+4h+11t)^n - 60(2p+4h+10t)^n
- 30(2p+2h+8t)^n + 60(2p+2h+7t)^n - 30(2p+2h+6t)^n
+ 12(p+5h+10t)^n
At this point it's interesting to review the sums of the coefficients
in each of these cases for S^2:
6-12+8 = 2
8-12-12+24-6 = 2
20-30-60+60+60-60-60+120-60-30+60-30+12 = 2
In contrast, note that the sum of the coefficients on S^1 is
always 0. This seems to be the Euler topological invariant of
the surface. It's tempting to think this topological invariance
could somehow be exploited to simplify the extrapolation to
progressively more Great Circles, but I don't see how right now.
Another (simpler) variation on the circle problem is to determine
the probability that n points uniformly distributed on a unit interval
will all fall within some interval of length q. In this case the
probability is nq^(n-1) - (n-1)q^n. This problem also has many
fascinating geometrical interpretations.
=====================================================================
MathPages at --> http://www.seanet.com/~ksbrown/
=====================================================================
Douglas J. Zare
Let P(n,d) be the probability that the origin is contained in the convex
hull of n points chosen uniformly and independently on the surface of the
d-sphere.
>The case of the 0-sphere is worth including; the probability that the
>convex hull contains the origin is 1-(1/2^(n-1)).
Further, there are natural reasons to think of P(n,-1) as 1, for n>=1.
The other boundary condition may be taken to be P(1,d)=0 for d>=0.
>[...]
>Conjecture:
>
> P(n-1,d-1) + P(n-1,d)
>P(n,d) = -----------------------
> 2
Proof:
From previous articles, the P(n,d) equals the expected number of quadrants
in R^n through which a random subspace S of dimension n-(d+1) passes,
divided by 2^n. I still don't know what that random variable really is,
but with probability 1 the space is in general position.
S. Smirnov had the idea that one should consider the intersection of the
coordinate hyperplanes with the subspace instead of counting the
quadrants. (Call the hyperplane Xi=0 the ith coordinate hyperplane.) Each
quadrant of R^n is convex, hence it intersects S in at most one connected
region. So, we want to count the number of components of S\{coordinate
hyperplanes}.
If we remove one of those hyperplanes, H, we would decrease the number of
components by the number of regions in H\{other coordinate hyperplanes}.
By induction, this number is P(n-1,d-1)2^(n-1), and the result of the
subtraction is P(n-1,d)2^(n-1), hence
P(n,d)2^n = P(n-1,d-1)2^(n-1) + P(n-1,d)2^(n-1)
P(n-1,d-1) + P(n-1,d)
P(n,d) = ----------------------- .
2
This implies that the values are partial sums of rows of Pascal's
triangle, normalized. I do not yet have a combinatorial proof that
P(2d+2,d)=1/2.
I get the feeling this should all be known from the theory of arrangements
of hyperplanes, although I have always seen that applied to hyperplanes
very much not in general position. Anyway, the above proof works not just
for spherically symmetric distributions but for any other centrally
symmetric distribution such that the points end up in general position
with probability 1.
Douglas Zare
http://www.cco.caltech.edu/~zare
Kevin Brown
za...@cco.caltech.edu (Douglas J. Zare) wrote:
> Let P(n,d) be the probability that the origin is contained in the
> convex hull of n points chosen uniformly and independently on the
> surface of the d-sphere.
>
> P(n,d) = -----------------------
> 2
>
>
> This implies that the values are partial sums of rows of Pascal's
> triangle, normalized. I do not yet have a combinatorial proof that
> P(2d+2,d)=1/2.
This is a nice result. I've been focusing on the complementary
problem of finding the probability Pr{n,d} that n randomly chosen
points on S^d all fall within some "hemisphere". I found the
following explicit formulas, which agree exactly with your
recurrence relation:
2^(n-1) Pr{n,0} = 1
2^(n-1) Pr{n,1} = n
n(n-1)
2^(n-1) Pr{n,2} = 1 + ------
2!
n(n-1)(n-2)
2^(n-1) Pr{n,3} = n + -----------
3!
n(n-1) n(n-1)(n-2)(n-3)
2^(n-1) Pr{n,4} = 1 + ------ + ----------------
2! 4!
and so on. The terms in the numerator of Pr{n,d} are alternating
binomial coefficients from the nth row of Pascal's triangle, and if
d=(n-2)/2 (where n is even), the formula covers just half of the row.
The sum of alternating coefficients over this half-row is (2^n)/4,
so we have Pr{2d+2,d} = 1/2.
The above formula for S^2 certainly disagrees with the formula
given in the rec.puzzles FAQ, which is 1-[1-(1/2)^(n-2)]^n. As
was pointed out earlier in this thread, the FAQ's formula would
more reasonable if n was replaced with n-1, but it still seems to
differ from the correct answer for n>4. As a confidence builder
I wrote a little program to randomly pick n points on a sphere
and check to see if they are all in one hemisphere. The results
are summarized below:
rec.puzzles FAQ
n simulation Pr{n,2} (with n-1 for n)
---- ---------- -------- ---------------
1 1.0000 1.0000 0.0000
2 1.0000 1.0000 2.0000
3 1.0000 1.0000 1.0000
4 0.8742 0.8750 0.8750
5 0.6862 0.6875 0.6835
6 0.4954 0.5000 0.4871
7 0.3365 0.3438 0.3211
8 0.2295 0.2266 0.1993
9 0.1508 0.1445 0.1183
10 0.0889 0.0898 0.0681
These results (10000 samples per n) definitely support the formula
Pr{n,2}, which also agrees with Doug Zare's analysis.
Anyway, it's interesting that the formulas for Pr{n,d} seem to be
closely related to the formula for the probability of n points all
falling within some k contiguous arcs of a circle (S^1) that has
been divided into 2k equal arcs. This was given in an earlier post
as _ _
1 | n(n-1) 1 n(n-1)(n-2) 1 |
Pr{n;k} = ------- | n - ------ - + ----------- --- - ... |
2^(n-1) |_ 2! k 3! k^2 _|
It's almost as if, as k->1, this probability on the discretized
circle approaches Pr{n,2j+1} - Pr{n,2j} + 1/2^(n-1) for sufficiently
large j. It's also interesting that the formula for Pr{n,d} is
fundamentally different - but complementary - for odd dimensions
and for even dimensions, sort of like sine and cosine functions.
By the way, regarding the discrete cases on S^2, I filled in the
case of 6 great circles (normal to the axes of an icosahedron). To
summarize all the discrete results I've found, here are the
formulas for the probability that n random points will all fall
on one side of one of a G great circles. (The solids listed here
indicate that the great circles are normal to the axes of that
solid.)
G
----
1 2 = 2
3 octahedron 6-12+8 = 2
4 hexahedron 8-12-12+24-6 = 2
6 icosahedron 12-30+20-30+60-30 = 2
10 dodecahedron 20-30-60+60+60-60-60+120-60-30+60-30+12 = 2
P1{n} = 2(t)^n
where t = 0.50000000
P3{n} = 6(4t)^n - 12(2t)^n + 8(t)^n
where t = 0.125000
P4{n} = 8(4t+3s)^n - 12(2t+2s)^n - 12(2t+s)^n + 24(t+s)^n - 6(s)^n
where t = 0.043869914, s = 0.108173448
P6{n} = 12(6p+10t)^n - 30(4p+6t)^n + 20(3p+4t)^n
- 30(2p+4t)^n + 60(2p+3t)^n - 30(2p+2t)^n
where t = 0.014312286762175, p = 0.059479522063042
P10{n} = 20(6p+10h+30t)^n - 30(4p+8h+22t)^n - 60(4p+6h+18t)^n
+ 60(3p+6h+16t)^n + 60(3p+5h+14t)^n - 60(2p+5h+12t)^n
- 60(2p+4h+12t)^n + 120(2p+4h+11t)^n - 60(2p+4h+10t)^n
- 30(2p+2h+8t)^n + 60(2p+2h+7t)^n - 30(2p+2h+6t)^n
+ 12(p+5h+10t)^n
where p = 0.013028988120384
h = 0.029670196644958
t = 0.004170754471287
=======================================================================
MathPages at --> http://www.seanet.com/~ksbrown/
=======================================================================
Douglas J. Zare
John Rickard e-mailed that he attempted to post a solution. With his
permission, I am reposting the following exerpts from his article, dated
May 19th, which seems much clearer than mine:
-------------------
[T]he points can be chosen by first choosing (uniformly and independently)
n pairs of opposite points, and then choosing one from each pair. I claim
that no matter what the n pairs are, provided only that (as happens with
probability 1) no three pairs lie on a great circle, n^2 - n + 2 of the
2^n ways of choosing one point from each pair result in n points in a
hemisphere.
For a hemisphere contains the n points iff the centre of the
hemisphere (in the sense in which the north pole is the centre of the
northern hemisphere) is contained in the intersection of the
n hemispheres centred on the n points. If one considers the n great
circles centred on the n pairs of points, one can see that each of the
regions into which these circles divide the sphere corresponds to a
way of choosing a point from each pair so that the points lie in a
hemisphere (and any point in the corresponding region can be chosen as
the centre of that containing hemisphere).
The result now follows from the fact that n great circles, no three of
which intersect at a point (in other words, the centres of no three of
which lie on a great circle), divide the sphere into n^2 - n + 2
regions. [...]
The same argument generalizes to a d-sphere[...]