==> 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 <==
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} 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.
------------------------------------------------------------------------
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)