I have two points $x\_1,x\_2 \in \mathbb S^n $ which are distant $d$ from each other, where $d<<1$.
I also have a vector $v$ sampled uniformly at random from $\mathbb S^n$.


What is the probability that $x\_1$ and $x\_2$ lie on different sides of the hyperplane perpendicular to $v$?


Thank you!



Probability of two Points being divided by an high-Dimensional Hyperplane
Let us change notation somewhat: Let $x=(x\_1,\dots,x\_n)$ and $y=(y\_1,\dots,y\_n)$ be points in $\mathbb R^n$ such that $|x|=|y|=1$ and $|x-y|=d\in(0,1)$, where $|\cdot|$ is the Euclidean norm. Let $v$ be a random vector uniformly distributed on the unit sphere $S^{n-1}$ in $\mathbb R^n$. The probability in question is 
\begin{equation}
 p:=P(x\cdot v<0<y\cdot v)+P(y\cdot v<0<x\cdot v)=2P(x\cdot v<0<y\cdot v), 
\end{equation}
where $\cdot$ is the dot product. 


The key note is that the random vector $v$ equals in distribution the random vector $(Z\_1,\dots,Z\_n)/\sqrt{\sum\_1^n Z\_i^2}$, where $Z\_1,\dots,Z\_n$ are independent standard normal random variables (r.v.'s). Hence,
\begin{equation}
 p=2P(X<0<Y), 
\end{equation}
where $X:=\sum\_1^n x\_i Z\_i$ and $Y:=\sum\_1^n y\_i Z\_i$. The r.v.'s $X$ and $Y$ are jointly normal with zero means, unit variances, and correlation 
\begin{equation}
 r=EXY=x\cdot y=\tfrac12\,(|x|^2+|y|^2-|x-y|^2)=1-d^2/2. 
\end{equation}
So, the pair $(X,Y)$ equals $(X,rX+\sqrt{1-r^2}\,Z)$ in distribution, where $Z$ is a standard normal r.v. independent of the standard normal r.v. $X$. 


So, 
\begin{equation}
 p=2P(X<0<rX+\sqrt{1-r^2}\,Z)=2P(X<0,Z>-kX)=2P\big((X,Z)\in A\big), 
\end{equation}
where 
\begin{equation}
 k:=r/\sqrt{1-r^2} 
\end{equation}
and $A$ is the angle between the rays $\{(x,0)\colon x\le0\}$ and $\{(x,-kx)\colon x\le0\}$, emanating from the origin. 
Since the distribution of the random vector $(X,Z)$ in $\mathbb R^2$ is rotation invariant, we conclude that the probability in question is
\begin{equation}
 p=\frac\theta{\pi}, 
\end{equation} 
where 
\begin{equation}
 \theta:=\text{arccot}\,k=\arccos r=\arccos(1-d^2/2) 
\end{equation}
is the measure of the angle $A$. 


In particular, it follows that $p=2d/\pi+O(d^3)\sim 2d/\pi$ as $d\downarrow0$, which agrees with the intuition. 


