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 ddimensional spherical surface, denoted as S^{d}. The trivial case is S^{0}, which consists of the points in a onedimensional space (i.e., a line) equidistant from a given point. This 0sphere 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/2^{n} = 1/2^{n1}. (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 dsphere can be performed in two separate steps. First, we can select n axes through the center of the dsphere. 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 2^{n} 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 2^{n}. 

Each “polar” axis corresponds to a partitioning of the dsphere 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 nbit 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 0sphere, which consists of just two points, the answer is trivially 2. For a 1sphere (i.e., a circle), it’s easy to see that cutting it into n semicircles results in 2n segments. In general, if we let f_{d}(n) denote the number of subsets of a dsphere produced by n bisections, we can say that f_{d}(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 f_{d}(n)/2^{n}. 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 ddimensional 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 f_{d}(n). For example, with d = 2, we know f_{2}(n) is a polynomial in n of degree 2, so we have 

_{} 

We also have the three conditions f_{2}(1) = 2^{1}, f_{2}(2) = 2^{2}, and f_{2}(3) = 2^{3}, so we can solve for the three coefficients with the system of equations 

_{} 

This gives c_{0} = 2, c_{1} = 1, and c_{2} = 1, so we have f_{2}(n) = n^{2} – n + 2, and therefore the probability of n points chosen randomly from a uniform distribution on the surface of a 2sphere all lying on a single hemisphere is 

_{} 

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

_{} 

This gives c_{0} = 0, c_{1} = 8/3, c_{2} = 1, and c_{3} = 1/3, so the probability of n points chosen randomly from a uniform distribution on the surface of a 3sphere 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(n1,d) + C(n1,d1) and express all these results as 

_{} 

Notice that if d = (n2)/2 where n is even, the terms cover half of the row of binomial coefficients, and the sum of alternate coefficients over this halfrow is (2^{n})/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 semicircle is 1/2, as is the probability that six points placed randomly on the surface of a 2sphere 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 S^{2} disagrees with the formula given in the rec.puzzles FAQ, which is 1  [ 1  (1/2)^{n}^{2 }] ^{n}. To doublecheck 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(n1,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 n1 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 f_{d}(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) = An^{2} + Bn + C, and the condition implies 2n(A1) = (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) = n^{2} – n + 2, and therefore the probability of all n points falling in a single hemisphere is (n^{2} – n + 2) / 2^{n}, 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 CA. Thus, the probability that all points fall on an arc of length less than CA is just 1  Pr{cover}. Letting x denote the fraction (CA)/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 / 2^{n}^{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 S^{d} in half along various axes, and using inclusionexclusion 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 S^{1}, i.e., points distributed on a circle. 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 semicircle 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 inclusionexclusion principle stepbystep as follows: 

_{} 
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 

_{} 

so we have 
_{} 

As each of the remaining terms A_{k+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 [(k1) / (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 / 2^{n}^{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 (S^{1}) 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 1sphere problem yielded such interesting results, we might also investigate the application of the discretized approach to the 2sphere problem. In principle it's certainly possible to draw several great circles on a sphere and then use inclusionexclusion 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 inclusionexclusion 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 nonzero overlaps between two hemispheres come in two types: there are 12 of area 2t + 2s and 12 of area 2t + s. The nonzero overlaps between three hemispheres also come in two types: there are 24 of area t + s and 8 of area t. Finally, the nonzero 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 semiregular Archimedean solids. The only other Archimedian solid whose projected edges are great circles is the "icosidodecahedron", 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 inclusionexclusion 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 612+8 = 2 
4 hexahedron/tetrahedron 81212+246 = 2 
6 icosahedron 1230+2030+6030 = 2 
10 dodecahedron 203060+60+606060+1206030+6030+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 S^{1} 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. 
