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