From: elkies@brauer.harvard.edu (Noam Elkies)
Newsgroups: rec.puzzles
Date: 2 Oct 1997 16:51:27 GMT
Organization: Harvard Math Department
In article <3433C1C8.1CA5@cic-mail.lanl.gov> ttw@lanl.gov writes:
>A process generates points randomly around the circumference of a
>circle. The points are uniform on the circumference. The process stops
>when the polygon with vertices defined by the points encloses the center
>of the circle. How many sides does the expected polygon have?
>
>No tricks here. The polygons are all convex.
>
> Tony
Neat puzzle. I didn't find an elementary solution, or one that
generalizes nicely to random points on a sphere or higher dimension;
but the following, though not elementary (it uses calculus), is
at least simple:
To find the expected number of points (which is of course the same
as the number of sides), we determine for each n the probability
that the polygon has at least n points, and sum this from n=1 to
infinity. That probability, in turn, is the probability that the
first n-1 points do *not* enclose the center in their convex hull.
For that to happen, the n-1 points must be contained in an arc of length
2*pi*t for some t<1/2. Let 2*pi*x be the shortest arc containing the
points. We assume that n>2, else the probability is 1; we also assume
that the 1st and 2nd points are the left and right endpoints of the arc
-- since in fact any pair of points can play this role we'll multiply
at the end by (n-1)(n-2) to obtain the correct probability.
Now the chance that the 1st and 2nd point form an arc of length
between x and x+dx is dx, and the chance that a further point
falls in that arc is x+c for 01/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 Expectation for the number of points that are not contained
in an arc of length 2*pi*t (for t<=1/2) is:
E(t) = c(1,t) + c(2,t) + c(3,t) + c(4,t) + ...
= p(0,t) + p(1,t) + p(2,t) + p(3,t) + ...
= 1 + (t^0 + 2t^1 + 3t^2 + 4t^3 + ...)
= 1 + d/dt (t^1 + t^2 + t^3 + t^4 ...)
= 1 + d/dt 1/(1-t)
= 1 + 1/(1-t)^2
The special case t=1/2 gives E(1/2) = 5.
Discete Version:
----------------
If the points are randomly generated on a disc, we will get the same result.
The radial distribution is almost of no importance.
Let the random process generates points X_k = (R_k, Phi_k) in plane with
- The angle distributions Phi_k are equidistributed and independent.
- The probability Prob(R_k=0) is zero for all k.
Then the expected waiting time until the convex hull of the points (R_k, Phi_k)
contain the center is the same as for the points (1, Phi_k).
This follows from the following observation:
Let R_k>0 (for all k) then we have
the convex hull of the points (R_k, Phi_k) contains the center
iff the convex hull of the points ( 1, Phi_k) contains the center.
Short pointless t-args:
-----------------------
The case of t>1/2 was left open. It is better to change variables and
let s=1-t. So we are waiting until no arg of length at least s is left.
Another interpretation is selecting randomly s-args on the circumference
until it is covered.
Let p(n,s|A) with A a subset of {1,..,n} be the probability that for
n generated points for each i in A there is at the left of point i
an free s-arg. The notation (x)+ is defined as x for x>0 and 0 otherwise.
p(n,s|A) = (1 - #A*s)+^(n-1) defined if A is a subset of {1,..,n}.
Be the inclusion-exclusion principle we get
p(n,s) = Sum_{1<=k<=n} Binomial(n,k) (-1)^(k-1) (1 - k s)+^(n-1) for n>=1
p(0,s) = 1.
Note that Sum_{0<=k<=n} Binomial(n,k) (-1)^k (1 - k s)^(n-1) = 0 which
is checks that p(n,s) = 1 if s <= 1/n.
The expected waiting time E(s) can now be calculated using
Sum_{n>=k} Binomial(n,k) x^(n-k) = 1/k! d^k/dx^k (1-x)^(-1) = (1-x)^(-1-k)
E(s)
= p(0,s) + p(1,s) + p(2,s) + p(3,s) + ...
= 1 + Sum_{k>=1} (-1)^(k+1) Sum_{n>=k} Binomial(n,k) (1 - k s)+^(n-1)
= 1 + 1/s^2 - (1-2s)+/(2s)^3 + (1-3s)+^2/(3s)^4 - (1-4s)+^3/(4s)^5 + ...
Some special values are: E(1/2) = 5, E(1/3) = 8 7/8, E(1/4) = 13 16/81.
Discrete Version:
-----------------
The random process generates points at the vertices of a regular k-gon.
Let p(n,k,t) be the probability that the first n points generated for
the k-gon are contained in t vertices in a series.
If we define p(n,k,t|i) in the same way we will have more complicate
formulars as p(n,k,t|i,j) is not zere as the probability the the i-th
and the j-th point are equal is not zero.
Therefore define p(n,k,t|i) as the probability that the first n points
generated for k-gon are contained in set of vertices {i, i+1, ..., i+t-1}
(cyclic numbering) and vertex i is selected.
p(n,k,t|i) = (t/k)^n - ((t-1)/k)^n independent of i.
Then we have for 2t - 1 <= k and n>=1
p(n,k,t) = k p(n,k,t|1) = k ((t/k)^n - ((t-1)/k)^n)
p(0,k,t) = 1.
The expected waiting time for 2*t - 1 <= k is therefore:
E(k,t) = p(0,k,t) + p(1,k,t) + p(2,k,t) + p(3,k,t) + ...
= 1 + k \Sigma_{k>=1} (t/k)^n - ((t-1)/k)^n
= 1 + k \Sigma_{k>=0} (t/k)^n - ((t-1)/k)^n
= 1 + k ( \Sigma_{k>=0} (t/k)^n - \Sigma_{k>=0} ((t-1)/k)^n )
= 1 + k ( 1/(1 - t/k) - 1/(1 - (t-1)/k) )
= 1 + k^2/((k-t)(k-t+1))
Now evaluate the special cases:
case k odd:
E(2m + 1, m + 1) = 5 + 1/(m(m+1))
case k even: (the boarder is allowed)
E(2m, m) = 5 - 4/(m+1)
case k even: (the boarder is not allowed)
As in this case 2t - 1 <= k is not sattisfied, the
p(n,k,t|i,j) have to taken into account. In this case
p(n,2m,m+1|i,i+m) have to be subtracted to get p(n,2m,m+1).
The final result is
E(2m, m+1) = 5 + 7/(2m-2) - 1/((2m-2)(2m-1))
The special case E(k, k-1) is covered by the coupon collector problem
and can be checked in this way. (E(k,k) is infinity by definition.)
E(2,1) = 2*H(2) = 3
E(3,2) = 3*H(3) = 5 1/2
E(4,3) = 4*H(4) = 8 1/3
where H(n) is the harmonic series 1 + 1/2 + 1/3 + ... + 1/n.
Question: What is E(k,t) for 2t - 1 > k?
--
Torsten Sillke
------------------------------------------------------------------
The 3-dim generalization can be found in the rec.puzzles archive.
The given answer is wrong!!! p(3) = 1 and not 7/8.
The formular given by M. Gardner is (n*n-n+2)/2^n.
>> A request to archive-request@questrel.com on 25. Nov 97 gives a wrong result. <<
==> geometry/points.on.sphere.p <==
What are the odds that n random points on a sphere lie in the same hemisphere?
==> geometry/points.on.sphere.s <==
1 - [1-(1/2)^(n-2)]^n <= WRONG = WRONG = WRONG =>
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.
------------------------------------------------------------------
How many points must be generated in the average on the sphere,
such that there 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 =>
Locking at the 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.
-- I send this to rec.puzzles, and get the following answer --
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
------------------------------------------------------------------
Subject: Re: POINTS ON SPHERE : wrong solution in the archive?
From: ksbrown@ksbrown.seanet.com (Kevin Brown)
Date: 1996/05/26
Message-ID: <4oap57$lkg@kaleka.seanet.com>
Newsgroups: rec.puzzles,sci.math
Douglas J. Zare 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:
>> =========> 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
> 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)).
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/
=====================================================================
Subject: Re: POINTS ON SPHERE : wrong solution in the archive?
From: ksbrown@ksbrown.seanet.com (Kevin Brown)
Date: 1996/05/28
Message-ID: <4oe968$hqo@kaleka.seanet.com>
Newsgroups: rec.puzzles,sci.math
zare@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-1,d-1) + P(n-1,d)
> P(n,d) = -----------------------
> 2
>
[...nice proof deleted]
>
> 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/
=======================================================================
------------------------------------------------------------------------
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} BinomialCoeffiecient(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 superflous
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 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 be 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 varibale, 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"afli [Abh. I, pp 209-212], but is included here for the sake of
completeness. I am abliged 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.
------------------------------------------------------------------------
Subject: Re: Another Geometric Probability Problem
Date: Tue, 21 Apr 1998 21:02:05 -0500
From: callan@stat.wisc.edu (David Callan)
Organization: University of Wisconsin - Madison
Newsgroups: sci.math.research
Xref: news.doit.wisc.edu sci.stat.math:19603 sci.math:192472
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
------------------------------------------------------------------------
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 lieing
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.)
rec.puzzles archive;
==> geometry/points.on.sphere <==
What are the odds that n random points on a sphere lie in the same hemisphere?
A request to archive-request@questrel.com on 25. Nov 97 gives a wrong prob.
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"afli;
Theorie der vielfachen Kontinuit"at, 1852,
Teil 1: Lehre von den linearen Kontinuen,
Sektion 16: "Uber die Zahl der Teile, in welche die n-fache Totalit"at 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)
Raph Howard and Paul Sisson;
Capturing the Origin with Random Points: Generalizations of a Putnam Problem,
College Mathematics Journal 27:3 (1996) 186-192
--
mailto:Torsten.Sillke@uni-bielefeld.de
http://www.mathematik.uni-bielefeld.de/~sillke/