1
$\begingroup$

As the title says, How to find the probability of vectors a, b, c, on some unit sphere, all lies on same side of some hyperplane passing through the origin. Information present are the angles between vectors a and b, b and c, c and a.

I am trying to bound the area of sphere in which the normal of hyperplane can reside but I feel stuck. Any hints or directions?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Any three linearly independent vectors lie on one side of some hyperplane $\endgroup$
    – Saúl RM
    Commented Apr 16, 2022 at 20:07
  • $\begingroup$ But this is not given that the vectors are linearly independent or not $\endgroup$
    – hans
    Commented Apr 16, 2022 at 20:11
  • $\begingroup$ They are linearly dependent if and only if the angles add up to $2\pi$ or the largest angle equals the sum of the other two. $\endgroup$
    – Timothy Budd
    Commented Apr 17, 2022 at 5:05
  • $\begingroup$ In one dimension, if all angles are zero, the vectors are all on the same side of the hyperplane, otherwise, not. $\endgroup$
    – Michael Engelhardt
    Commented Apr 17, 2022 at 15:39
  • $\begingroup$ But i want to bound the probability in 3-D $\endgroup$
    – hans
    Commented Apr 17, 2022 at 16:59

1 Answer 1

Reset to default
5
$\begingroup$

$\newcommand\al\alpha\newcommand\be\beta\newcommand\ga\gamma$It appears that the question is as follows: Given unit vectors $a,b,c$ with angles $$\al:=\cos^{-1}(b\cdot c),\quad \be:=\cos^{-1}(a\cdot c),\quad \ga:=\cos^{-1}(b\cdot a)$$ (where $\cdot$ denotes the dot product), find the probability, say $p$, that the vectors $a,b,c$ are to the same side of a hyperplane through the origin chosen uniformly at random.

The answer is $$p=\frac{2\pi-\al-\be-\ga}{2\pi}. \tag{1}\label{1}$$

Indeed, $$p=P(a\cdot U>0,b\cdot U>0,c\cdot U>0) +P(a\cdot U<0,b\cdot U<0,c\cdot U<0) =2P(a\cdot U>0,b\cdot U>0,c\cdot U>0),$$ where $U$ is a random vector uniformly distributed on the unit sphere. Next, the random vector $U$ equals $G/|G|$ in distribution, where $G$ is a standard Gaussian random vector and $|G|$ is the Euclidean norm of $G$. So, $$p=2P(X>0,Y>0,Z>0),$$ where $$X:=a\cdot G,\quad Y:=b\cdot G,\quad Z:=c\cdot G,$$ so that $X,Y,Z$ are zero-mean, unit-variance jointly normal random variables with correlations $$\rho_{X,Y}=a\cdot b=\cos\ga,\quad \rho_{Y,Z}=b\cdot c=\cos\al,\quad \rho_{X,Z}=a\cdot c=\cos\be.$$ Now \eqref{1} follows from the known formula $$P(X>0,Y>0,Z>0)=\frac{\cos^{-1}(-\rho_{X,Y})+\cos^{-1}(-\rho_{Y,Z})+\cos^{-1}(-\rho_{X,Z})-\pi}{4\pi}\tag{2}\label{2}$$ -- see e.g. the second display in Section 6 on p. 355 of Plackett.

Note that \eqref{1} holds for any dimensions $\ge3$.

Another way to derive \eqref{2} and hence \eqref{1} is, of course, to note that the numerator of the ratio in \eqref{2} is the area of the spherical triangle on the unit sphere with angles $\pi-\al,\pi-\be,\pi-\ga$. This area can be expressed as a double integral in spherical coordinates. Yet other ways to find this area can be found e.g. on this page. The formula for this area is Girard's theorem.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Shouldn't you get $p=1$ for $\alpha = \beta = \gamma =0$? $\endgroup$
    – Michael Engelhardt
    Commented Apr 18, 2022 at 2:17
  • $\begingroup$ @MichaelEngelhardt : Thank you for your comment. Instead of the "on the same side" probability, I previously gave the "on the positive side" probability, forgetting to double that. Now this is fixed. $\endgroup$
    – Iosif Pinelis
    Commented Apr 18, 2022 at 2:23
  • $\begingroup$ Thank you for your detailed answer!! Your probability is correct. I do not know much about variance, therefore, can't verify your claims. But, there is another way to deduce this from basic principles given in Goemans and Williamson (Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming). They say there is another way to do this using spherical geometry. Do you have an idea on how to give a probability of the above question using spherical geometry? $\endgroup$
    – hans
    Commented Apr 18, 2022 at 9:15
  • 1
    $\begingroup$ @hans : I have added a remark on other ways to derive this result, including ones using spherical geometry. $\endgroup$
    – Iosif Pinelis
    Commented Apr 18, 2022 at 12:34
  • $\begingroup$ @IosifPinelis : Thank you Iosif! I am not much familiar with spherical geometry either but I will try to understand the references you have provided. Thanks again :) $\endgroup$
    – hans
    Commented Apr 18, 2022 at 12:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .