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/