N Points On Sphere all in One Hemisphere

 

What is the probability that n randomly chosen points on a sphere will all lie in a single hemisphere?  More generally, we can consider the same question for points chosen randomly from a uniform distribution on a d-dimensional spherical surface, denoted as Sd. The trivial case is S0, which consists of the points in a one-dimensional space (i.e., a line) equi-distant from a given point. This 0-sphere surface consists of just two points, so the probability that all n randomly placed points would all be in the same “hemisphere” is simply 2/2n = 1/2n-1. (The “2” in the numerator is due to the fact that all the points can be in either of the two hemispheres.)

 

This “binary” approach can be extended to higher dimensions, if we realize that the selection of n points randomly on the surface of a d-sphere can be performed in two separate steps. First, we can select n axes through the center of the d-sphere. The directions of these axes are taken from a uniform distribution of directions. Each axis strikes the surface at two opposite points, so we need to make a binary choice for each axis to determine the position of the point. Thus, regardless of the directions of the axes, there are 2n possible configurations, each of which is equally probable. A certain number of these configurations have all the points in a single hemisphere. The key insight is that this number is the same, regardless of the angles of the axes. Once we have established this, it follows that the probability of all n randomly placed points being in a single hemisphere is this number divided by 2n.

 

Each “polar” axis corresponds to a partitioning of the d-sphere into two hemispheres. By choosing n axes, we partition the surface into a certain number of subsets. (We can exclude special cases such as axes the coincide or points where more than two slices coincide, because those have zero probability.) Each of these subsets lies entirely inside or entirely outside the hemisphere centered on each of the n points. So, each subset can be uniquely assigned an n-bit binary number signifying whether it is inside or outside the hemisphere centered on each of the n selected points. By changing the pole selections as needed, we make cause any one of these regions to be inside the hemispheres centered on all n points, which implies that all n points are within a single hemisphere. Thus, each subset corresponds uniquely to a set of pole choices (for a given set of axes) that place all n points in a single hemisphere. We only need to determine the number of subsets into which the surface is partitioned by n general slices into hemispheres.

 

For a 0-sphere, which consists of just two points, the answer is trivially 2. For a 1-sphere (i.e., a circle), it’s easy to see that cutting it into n semi-circles results in 2n segments. In general, if we let fd(n) denote the number of subsets of a d-sphere produced by n bisections, we can say that fd(n) is a polynomial in n of degree d. (See below for a sketch of a proof of this assertion.) As noted above, the probability of n points all lying within a single hemisphere is fd(n)/2n. For any given d we know that this probability equals unity for n = 1, 2, …, d+1. For example, with d = 0, a single point obviously has probability 1 of being in a single hemisphere. Likewise with d = 1 it’s clear that any one or two points lie in a single hemisphere (since the special case of opposite polar points has probability zero). With d = 2 we can see that any one, two, or three points lie in a single hemisphere, because any two points define a “great circle” and the third point is in one of the two bounded hemispheres. In the same way, for arbitrary d, any d points define a d-dimensional slice through the origin, and the (d+1)th point must then lie in one of the bounding hemispheres.

 

This information is sufficient to determine all the functions fd(n). For example, with d = 2, we know f2(n) is a polynomial in n of degree 2, so we have

 

 

We also have the three conditions f2(1) = 21, f2(2) = 22, and f2(3) = 23, so we can solve for the three coefficients with the system of equations

 

 

This gives c0 = 2, c1 = -1, and c2 = 1, so we have f2(n) = n2 – n + 2, and therefore the probability of n points chosen randomly from a uniform distribution on the surface of a 2-sphere all lying on a single hemisphere is

 

 

Likewise for a 3-sphere (embedded in a 4-dimensional space) we can determine the coefficients of the cubic polynomial f3(n) by solving the system of equations

 

 

This gives c0 = 0, c1 = 8/3, c2 = -1, and c3 = 1/3, so the probability of n points chosen randomly from a uniform distribution on the surface of a 3-sphere all lying on a single hemisphere is

 

 

In the same way we can determine the probabilities

 

 

and so on. Using the recurrence relation for binomial coefficients we can replace each C(n,d) with C(n-1,d) + C(n-1,d-1) and express all these results as

 

 

Notice that if d = (n-2)/2 where n is even, the terms cover half of the row of binomial coefficients, and the sum of alternate coefficients over this half-row is (2n)/4, so we have  Pr{2d+2,d} = 1/2.  For example, the probability that four point placed randomly on a circle will all lie in a single semi-circle is 1/2, as is the probability that six points placed randomly on the surface of a 2-sphere will all lie in a single hemisphere. Also, from the recurrence property for binomial coefficients, we have

 

 

The same recurrence also applies to the complementary function 1 – Pr{n,d}.

 

Incidentally, the above formula for S2 disagrees with the formula given in the rec.puzzles FAQ, which is 1 - [ 1 - (1/2)n-2 ] n.  To double-check the validity of the formula derived above, I wrote a “Monte Carlo” simulation 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:

 

      n    simulation     Pr{n,2}     FAQ(n,2)    FAQ(n-1,2)

    ----   ----------    --------    ---------    ----------

      1      1.0000       1.0000       2.0000       0.0000

      2      1.0000       1.0000       1.0000       2.0000

      3      1.0000       1.0000       0.8750       1.0000

      4      0.8742       0.8750       0.6835       0.8750

      5      0.6862       0.6875       0.4871       0.6835

      6      0.4954       0.5000       0.3211       0.4871

      7      0.3365       0.3438       0.1993       0.3211

      8      0.2295       0.2266       0.1183       0.1993

      9      0.1508       0.1445       0.0681       0.1183

     10      0.0889       0.0898       0.0384       0.0681

 

These results (10000 samples per n) seem to agree well with the formula for Pr{n,2} derived above, but disagree with the FAQ formula. If we adjust the FAQ formula by replacing n with n-1 the discrepancy is reduced (and actually agrees exactly with the correct formula for n = 3 and 4), but it still does not give the correct results in general.

 

The general overall solution given above rests on the assertion that fd(n) has a definite value independent of the chosen axes (assuming no special coincidences), and that it is a polynomial in n of degree d. This was only presented as plausible, but without a rigorous proof. To prove these assertions for the case d = 2, notice that any two great circles intersect each other at two points, so there are four “edges”, and they partition the spherical surface into four regions. (Again, we can neglect repeated circles, and points where more than two circles intersect, because these have zero probability.) If we then add another great circle to n given circles, the number of vertices will increase by 2n. Each vertex is the meeting point of four edges, but each edge meets at two vertices, so there are twice as many edges as vertices. Hence, the number of vertices increases by 4n. The Euler characteristic of a spherical polyhedron is 2 = V – E + F, where V, E, and F are the numbers of vertices, edges, and faces, respectively. It follows that the number of faces must increase by 2n when adding the (n+1)th great circle. Thus we have the two conditions F(2) = 4 and F(n+1) = F(n) + 2n. It follows that F(n) is a quadratic polynomial, so F(n) = An2 + Bn + C, and the condition implies 2n(A-1) = -(A+B). This must hold for all n, so we must have A = 1, and so B = -1. Combining these with the first condition gives C = 2, so we get F(n) = n2 – n + 2, and therefore the probability of all n points falling in a single hemisphere is (n2 – n + 2) / 2n, in agreement with the previous derivation. Similar arguments can be made for higher dimensions.

 

The preceding derivations are quite satisfactory, but it’s interesting to explore other possible methods. One approach can be based on a result contained in William Feller's book "An Introduction to Probability Theory and Its Applications", which 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

 

 

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

 

 

In particular, with x = 1/2 (meaning all n points fall in some half of the circle) this gives again the result Pr{1/2; n} = n / 2n-1. It isn’t obvious how this approach can be generalized to higher dimensions.

 

Another approach is to proceed by “brute force”, splitting the surface of Sd in half along various axes, and using inclusion-exclusion to compute the probability of all the points falling into one of those discrete halves. We can then carry this over to the limit as the number of halves approaches all possible halves. This is admittedly not very elegant, but some of the results for the finite numbers of discrete halves are interesting. To illustrate, consider the simple case of S1, i.e., points distributed on a circle.  Divide the perimeter into 2k equal arcs denoted sequentially by a1, a2,..., a2k, and let Ai denote the event of all n randomly placed points lying on the semi-circle composed of the arcs ai, ai+1,... ai+k-1.  To determine the probability that at least one Ai is true, apply the inclusion-exclusion principle step-by-step as follows:

 

and so on.  As each additional Ai up to Ak+1 is included in the union, the probability of the union is increased by

 

 

so we have

 

As each of the remaining terms Ak+i, i = 2 to k, is added to the union, the probability is increased by

 

 

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

 

 

Expanding the binomial, we have

 

 

which gives the result n / 2n-1 in the limit as k increases to infinity. 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 (S1) that has been divided into 2k equal arcs.  This was given previously as

 

 

It's almost as if, as k approaches 1, this probability on the discretized circle approaches

 

 

for sufficiently large j.  It's also interesting that the formula for Pr{n,d} is fundamentally different - but complementary - for odd and even dimensions, somewhat like sine and cosine functions.

 

Since the discretized “brute force” approach to the original 1-sphere problem yielded such interesting results, we might also investigate the application of the discretized approach to the 2-sphere problem. In principle it's certainly possible to draw several great circles on a sphere and then use inclusion-exclusion to find the probability of all n points falling in one of those hemispheres. However, it isn’t obvious how to add more great circles in a uniform way, except for certain special configurations, i.e., normal to the axes of Platonic solids.

 

With just one great circle the probability of all n points falling in one of the two hemispheres bounded by that circle is obviously (1/2)n-1. We can write this as

 

 

We can also choose the three mutually orthogonal axes of a regular octahedron, and draw the corresponding great circles normal to those three axes. These circles divide the surface into 8 identical "triangular" regions that define six distinct hemispheres. By inclusion-exclusion we find that the probability of all n points falling in one of these six hemispheres is exactly

 

 

In the case of four great circles, drawn 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

 

 

where t = 0.043869914... and s = 0.108173448... Incidentally, noting that the spherical angle at each corner of the triangular regions is , this probability can also be expressed as

 

 

where

 

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 "icosidodeca-hedron", which has six great circles, one normal to each of the six axes of the icosahedron. These circles partition the surface into triangular and pentagonal regions with fractional areas t and p respectively. Carrying out the same kind of analysis for this case, we find

 

 

where  t = 0.014312286762175… and  p = 0.059479522063042…

 

The next case to consider is with ten great circles on a sphere, normal to the ten axes of a dodecahedron. This gives 20 distinct hemispheres. (The corresponding solid is not one of the Archimedean solids, because it has two distinct kinds of vertices.) These ten 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

 

 

where the normalized areas are p = 0.013028988120384…, h = 0.029670196644958…, and t = 0.004170754471287….

 

The coefficients for each of the discrete cases are listed in the table below. The solids listed 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/tetrahedron                     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

 

The hexahedron (cube) and tetrahedron give the same set of axes, because the four "axes" of the tetrahedron, taken to be the lines from the center to each vertex, coincide with the four axes of the cube, where each axis goes through two vertices. Notice that the sum of the coefficients is always 2.  In contrast, the sum of the coefficients on S1 is always 0. This sum is apparently equal to the Euler topological invariant of the surface, the same quantity appearing in the formula V – E + F = 2 discussed previously.

 

Return to MathPages Main Menu