Let $\mathbb{S}^{n-1}=${$ x\in \mathbb{R}^n| \sum_{k=1}^n x_k^2 =1 $} be the $n-1$ sphere and $n_i\in\mathbb{R}^n$ with components $n_{ij}\in${$-1,1$}$\ \forall\ j=1,2,\dots,n$. There are obviously $2^n$ such distinct "binary" vectors $n_i$. Now define for every binary vector $n_i$ a Hemisphere $H_i=${$x \in \mathbb{S}^{n-1}\ |\ (x,n_i)\geq0$} where $(.,.)$ means the usual inner product $(x,y)=\sum_{k=1}^n x_k y_k$.
What is the Probability that $p$ uniformly distributed vectors on $\mathbb{S}^{n-1}$ are all on the same of those $H_i$?
EDIT, Will Jagy: evidently these really are hemispheres, Tom Goodwillie pointed out that for $n=3$ they are
$$ x + y + z \geq 0, \; \; \; x + y -z \geq 0, \; \; \; x – y + z \geq 0, \; \; \; x – y – z \geq 0 , $$ and their complements.
$$ -x – y – z \geq 0, \; \; \; -x – y +z \geq 0, \; \; \; -x + y – z \geq 0, \; \; \; -x + y + z \geq 0 . $$
EDIT,problem poser:
Here is a solution for $n=3$:
The problem is much easier, if you see the similarity of the sphere with the great arcs that define the $8$ hemispheres and a cuboctahedron (www.wikipedia.org/wiki/Cuboctahedron).
As you can see the cuboctahedron actually consists only of $2$ distinct kinds of faces, these are $8$ triangles and $6$ squares. It is not difficult to see, that the intersections of the hemispheres consists of only these triangles and squares projected on the sphere and that these spherical triangles and “spherical” squares are the smallest parts you can get by the intersection of some hemispheres (except the empty set of course). Unfortunately the area is not preserved under this projection. But what is preserved is of course the fact that one hemisphere consists of $3$ spherical triangles and $4$ “spherical” squares (Lets call the triangles $T$ and the squares $S$ from now on).
It is also pretty obvious that the intersection of two hemispheres with hamming distance $2$ (that means two hemispheres with binary vectors with only two different components) consists of two $T$ and one $S$. That gives us the two equations $2T+S=I_2$ and $4T+3S=2\pi$ where $I_2$ is the intersection of two hemispheres with hamming-distance $2$.
To calculate $I_2$ we use the fact that the angle between two binary vectors of hamming distance $2$ is given by $\varphi_2=arccos−\frac{1}{3}$ and therefor $I_2=\frac{\pi-\varphi_2}{2\pi}4\pi=2(\pi-\varphi_2)$.
Now we have from the equations above $$T=\frac{3I_2-2\pi}{2}=2\pi-3\varphi_2$$ and $$S=2(\pi-I_2))=4\varphi_2-2\pi.$$Now, that we know the smallest parts $T$ and $S$ we have to understand what kinds of intersections we have and how they consist of $T$ and $S$. To do that we only need to care wlog about the hemisphere $H_1$ with binary vector $n_1=(1,1,1)^T$. Lets call $I_{ijk}$ the intersection of $H_1$ and hemispheres with hamming distance $i,j,k$(relatively to $n_1$). It is obvious, that there cant be more than intersections of $4$ hemispheres. (If there would be more, there would be a pair of disjoint hemispheres with vanishing intersection.) So there are the non vanishing intersections $I_1,I_2,I_{11},I_{12},I_{22},I_{111},I_{211},I_{221}$ (note that i mean here that you can find hemispheres with hamming distances $i,j,k$ so that $I_{ijk}$ doesnt vanish. For $n=3$ I think it is obvious, that in this case the value of the intersection is either $0$ or $I_{ijk}$ depending on which hemispheres of the given hamming distances you chose.). As you can easily check we have $I_{221}=I_{111}=I_{22}=T$, $I_{211}=S$, $I_{12}=I_{11}=S+T$, $I_2=2T+S$ and $I_1=2T+2S$. I think everyone sees now, that we just have to use the inclusion exclusion principle to get the desired probability $P(3,p)$. I won't do this now because i think that this doesnt give more insights.
The big question that arises now is, whether there are similarities in higher dimensions. If we could find the smallest parts of intersections on $\mathbb{S}^3$ without too much effort (like having to integrate) we could use a similar strategy I used for $n=3$. Then, if we could find some further symmetries, we may even be able to get some kind of recursion and solve it for arbitrary dimensions.
EDIT, problem poser:
Here is a little summary of the progress I made for n>3:
My aim is to find the smallest pieces of intersections of the hemispheres. If you look at the case n=3, you recognize that one of the smallest pieces is a spherical triangle with equal angles (the equal angles come from the symmetry of the problem). The good thing is, as Will Jagy pointed out, that you can get the area by the method Marco Radeschi describes in his comment of Proofs without words . Even more great is the fact, that we can always apply this method if we have a set of hemispheres, that all have the same distance to each other (that means that all have binary vectors with same hamming distance to each other) and for that the intersections of all these hemispheres do not vanish. For example for n=3 the intersection of the hemispheres with binary vectors (1,1,1), (1,-1,-1) and (-1,1,-1) is such a spherical triangle mentioned above. If you add the hemisphere (-1,-1,1) now to that set, all binary vectors still have the same distance, but the intersection of all four vanishes. That shows that the vanishing property is important to apply the method.
Now it seems logical to search for such a set for n=4 and to hope that the intersection (that you could easily calculate by the method mentioned above) is a smallest piece.
What really concerns me is the fact that there is no such set for n=4. For example a set with the maximum number of hemispheres that all have hamming distance 2 to each other and for that the intersection of all hemispheres does not vanish is {(1,1,1,1), (1,-1,-1,1), (1,1,-1,-1), (1,-1,1,-1)}. (It is easy to prove this, because there are only 3 possible hemispheres left and each of them is the negative one of a hemisphere in the set. ) Now you can add for example the hemisphere (1,-1,-1,-1) and you will still have a non vanishing intersection of all hemispheres. This proves that for n=4 the intersection of hemispheres that all have hamming distance 2 to each other and that have a non vanishing intersection is not a smallest piece. The same argumentation proves that there also can't be such sets with hamming distance 1 and 3.
But I also found a positive result: For all dimensions the intersection of hemispheres with the same given component, is a smallest piece.(To avoid confusion I mean hemispheres that for example all have the same first component) For example for n=3 these intersections are the spherical squares. The problem for n>3 is to find the volume of such intersection.
Any ideas?
Best Answer
A good way to think about a uniformely random point on the sphere is to think of it as the normalization of a vector of normally distributed i.i.d random variables. In fact, you don't even need to normalize. Consider hemisphere $v_i$ and $v_j$, form the $2 \times N$ matrix $V$, $v_i$ and $v_j$ being the rows of $V$. Let $X$ be a random Gaussian vector with covariance matrix $I$ (identity). $V.X$ is a vector with two components, whose sign represent membership in the hemisphere $i$ and $j$... $V.X$ follows a multivariate normal distribution with mean $\left(\begin{array}{cc}0\\\0\end{array}\right)$ and covariance matrix $n \left[\begin{array}{cc}1 & 1-2h/n\\\1-2h/n & 1\end{array}\right]$ where $h$ is the hamming distance. Notice that any covariance matrix can be approximated, up to a multiplicative factor, for $n$ large enough. The measure of the intersection of the two hemispheres is the integral of the the probability density over an orthant.
For the intersection of two hemispheres, the orthant is a quartant and the intersection is given as
$$\frac{1}{4} + \frac{\sin^{-1}(1-2h/n)}{2\pi}$$
(note that this is not the area but the fraction of the $(n-1)$ sphere area that is in the intersection)
There is also a formula for the trivariate case, i.e. if you're considering the intersection of three hemispheres
$$\frac{1}{8} + \frac{1}{4\pi}( \sin^{-1}(1-2h_{12}/n) + \sin^{-1}(1-2h_{23}/n) + \sin^{-1}(1-2h_{13}/n) )$$
Unfortunately, it is known that there is no closed-form expression of the probability of the orthants of a general multivariate normal distribution above the trivariate case. In your case, the covariance matrix have a certain structure, so it is not definite evidence that there is no formula for the area of the intersection of more than three hemispheres, but it is pretty good evidence.