Picking points on a sphere at random

Question

Suppose we pick up $N$ points uniformly at random on a sphere. The probability that these points lie within a 'fixed' hemisphere is easily calculated to be $1/2^N$. But what is the probability that all the points lie within any hemisphere on the sphere? I am actually interested in this question for $d$-dimensional hypersphere as well, so method of computation that extends to higher dimensions will be much appreciated.

Answer 1

I've wondered about this problem too, and it's a bit difficult to find information on it. Seeing as this is one of the main search results for this problem, I'll put some information here. This problem is known as Wendel's Theorem. As mentioned before, Brown proves the formula here, but he uses arguments on the polynomial degree of the solution and lacks in geometrical arguments. Wendel's proof is more geometrical in nature and can be found here. However, an alternative proof which I find more geometrically intuitive is given below.

Let $P(n,d)$ be the probability that $n$ points chosen uniformly at random on $S^d$ lie within a hemisphere. A hemisphere can be parametrized by its apex point $x$, so that the hemisphere is given by $H(x)=\{s\in S^d:s\cdot x>0\}$. While $H(x)$ is defined for $x\in S^d$, we may extend this to $x\in\mathbb{R}^{d+1}-0$ by the same definition, noting $H(x)=H(x/|x|)$. We will need the following lemma, which says that if a set lies in two hemispheres, then it is contained within any hemisphere whose apex lies along the (shortest) great arc between the apices of the two hemispheres.

Lemma. If $A\subseteq H(x)\cap H(x')$, then $A\subseteq H(tx+(1-t)x')$ for $t\in[0,1]$.

Proof. Let $p\in H(x)\cap H(x')$. Then $p\cdot x>0$ and $p\cdot x'>0$, so $p\cdot(tx+(1-t)x')=tp\cdot x+(1-t)p\cdot x'>0$. Thus, $p\in H(tx+(1-t)x')$. Q.E.D.

Now, label the $n$ points $p_1,\ldots,p_n$. We can assume $p_1,\ldots,p_{n-1},\pm p_n$ are distinct since it is a.s. true. Let $A_n=\{p_1,\ldots,p_{n-1},p_n\}$, and let $A_n'=\{p_1,\ldots,p_{n-1},-p_n\}$. If either $A_n$ or $A_n'$ lie within a hemisphere, then so does $A_{n-1}$. On the other hand, if $A_{n-1}$ lies in a hemisphere then a.s. one of $p_n,-p_n$ lie within the same hemisphere. Thus, the probability that one of $A_n,A_n'$ lie within a hemisphere is $P(n-1,d)$.

If $A_n\subseteq H(x)$ and $A_n'\subseteq H(x')$, then by the lemma above, $A_{n-1}\subseteq H(tx+(1-t)x')$ for $t\in[1,0]$. Since $p_n\cdot x>0$ and $-p_n\cdot x'>0$, there is some $z\in\{tx+(1-t)x':t\in[0,1]\}$ such that $p_n\cdot z=0$. On the other hand, if $A_{n-1}\subseteq H(z)$ where $p_n\cdot z=0$, then by perturbing $z$ above or below the equator, we can choose $x,x'$ such that $A_n\subseteq H(x)$ and $A_n'\subseteq H(x')$ since $A_{n-1}$ is closed. Thus, both $A_n$ and $A_n'$ lie within hemispheres iff $A_{n-1}\in H(z)$ for some $p_n\cdot z=0$.

Let $f:S^d-\{\pm p_n\}\rightarrow S^{d-1}$ be projection onto the equator $\{s\in S^d:p_n\cdot s=0\}$ (explicitly, this is projection along the axis through $p_n$ to $D^d-0$, followed by radial projection onto $S^{d-1}$). Then the points of $f(A_{n-1})$ have a uniform distribution, and the hemispheres of $S^{d-1}$ correspond to hemispheres $H(z)$ on $S^d$ with $p_n\cdot z=0$. Thus, the probability that both $A_n,A_n'$ lie within hemispheres is $P(n-1,d-1)$.

The probability that $A_n$ lies in a hemisphere is the same as the probability that $A_n'$ lies in a hemisphere, which is $P(n,d)$. By the addition rule, \begin{equation} P(n,d)=\frac{P(n-1,d)+P(n-1,d-1)}{2}. \end{equation} Now obviously, $P(n,0)=\frac{1}{2^{n-1}}$ and $P(1,d)=1$. By the recurrence relation above, $P(n,d)$ is determined solely by these values. Comparing with \begin{equation} \frac{1}{2^{n-1}}\sum_{k=0}^d\binom{n-1}{k} \end{equation} we see that they obey the same recurrence relation and have the same values when $d=0$ and when $n=1$, so they are equal.