13
$\begingroup$

Consider an $n$-dimensional Euclidean Space. Consider orthants in that space. Each orthant occupies $\frac{1}{2^n}$ of the volume of an $n$-dimensional unit sphere. Let's call that a spherical orthant. Let's index spherical orthants by a binary $n$-tuple, e.g. for $n=4$, $(+,+,-,+)$ is the spherical orthant given by

$$x_1 > 0, \qquad x_2 > 0, \qquad x_3 < 0, \qquad x_4 > 0.$$

Now consider the "upper diagonal halfspace" given by

$$x_1 + x_2 + ... + x_n > 0.$$

What is the volume of the intersection of this "upper diagonal halfspace" with a spherical orthant, given as a fraction of the volume of that spherical orthant?

$\newcommand{\Vol}{\mathrm{Vol}}$

Let's see some examples. $D_n$ will be the upper diagonal half-space in $\mathbb{R}^n$. $\Vol(O_n)$ will be the volume of a spherical orthant.

$$(n= 2)$$

We have:

\begin{align*} \frac{\Vol((+,+)\cap D_2)}{\Vol(O_2)}=1 && \frac{\Vol((+,-)\cap D_2)}{\Vol(O_2)}=\frac12 \\ \frac{\Vol((-,+)\cap D_2)}{\Vol(O_2)}=\frac12 && \frac{\Vol((-,-)\cap D_2)}{\Vol(O_2)}=0. \end{align*}

$$(n=3)$$

We have:

\begin{align*} \frac{\Vol((+,+,+)\cap D_3)}{\Vol(O_3)}={}&1 & \frac{\Vol((+,+,-)\cap D_3)}{\Vol(O_3)}={}&y \simeq 0.78 \\ \frac{\Vol((+,-,+)\cap D_3)}{\Vol(O_3)}={}&y\simeq 0.78 & \frac{\Vol((-,+,+)\cap D_3)}{\Vol(O_3)}={}&y \simeq 0.78 \\ \frac{\Vol((+,-,-)\cap D_3)}{\Vol(O_3)}={}&1-y \simeq 0.22 & \frac{\Vol((-,+,-)\cap D_3)}{\Vol(O_3)}={}&1-y \simeq 0.22 \\ \frac{\Vol((-,-,+)\cap D_3)}{\Vol(O_3)}={}&1 - y \simeq 0.22 & \frac{\Vol((-,-,-)\cap D_3)}{\Vol(O_3)}={}&0, \end{align*}

with $y = 2 - \frac4\pi\arccos(\frac{1}{\sqrt3}) \simeq 0.78$.

$$(n= 4)$$

We have:

\begin{align*} \frac{\Vol((+,+,+,+)\cap D_4)}{\Vol(O_4)}={}&1 & \frac{\Vol((+,+,+,-)\cap D_4)}{\Vol(O_4)}={}&\frac{11}{12} \simeq 0.92\,\, \text{(3 pluses)} \\ \frac{\Vol((+,+,-,-)\cap D_4)}{\Vol(O_4)}={}&\frac12\,\, \text{(2 pluses)} & \frac{\Vol((+,-,-,-)\cap D_4)}{\Vol(O_4)}={}& \frac{1}{12} \simeq 0.08\,\, \text{(1 plus)}\\ \end{align*} $$\frac{\Vol((-,-,-,-)\cap D_4)}{\Vol(O_4)}=0.$$

Can you give the result for general $n$, and spherical orthants with $k$ times "+" ($0\leq k\leq n$) ?

Thank you,

Andreas

$\endgroup$
  • $\begingroup$ @MickG : thanks a lot for editing! Cheers, Andreas $\endgroup$ – Andreas Feb 26 '16 at 19:17
  • $\begingroup$ Reference for MathJax. You surely ought to read that. I won't be always there to edit your posts :). In case you haven't already been welcomed, Welcome to Math.SE!. Did I get the pluses and minuses right? What sequences are the (etc.)s implying? Why "spherical orthant" and not "coordinate orthant", where "coordinate" stresses that it's delimited by portions of coordinate planes? $\endgroup$ – MickG Feb 26 '16 at 19:23
  • $\begingroup$ @MickG : thanx. As to your questions: pluses and minuses are fine. The etc.s imply the same number of pluses and minuses. "Orthant" may be underspecified since people may be misled to consider a n-dimensional (unit)cube and intersect its orthants with the upper diagonal plane which leads to different (actually simpler) results of the volume fractions. Hence the explicit reference to the sphere. $\endgroup$ – Andreas Feb 26 '16 at 20:36
  • $\begingroup$ Tried to explicit the (etc.)s, did I get something wrong? What are the missing volumes? $\endgroup$ – MickG Feb 26 '16 at 21:48
  • $\begingroup$ I explained the number of pluses, instead of enumerating them all explicitely. $\endgroup$ – Andreas Feb 26 '16 at 23:17
0
$\begingroup$

This can be solved with the probabilistic method. The probability we want is, if you sample a random point from a particular orthant, what is the probability that the sum of the coordinates is at least 0? In fact, it suffices to work with the surface of the orthant instead: the sign of the sum doesn't change if you scale the point to the surface.

Why should we use the surface of the orthant? Because you can sample a random point from the orthant by picking from standard normal distributions for each coordinate, using the correct signs, then normalizing. Call a random point generated in this way $(x_1, x_2, \dots, x_n)$.

The quantity you have been computing for various $k$ and $n$ is

$$\Pr[x_1 + x_2 + \cdots + x_n \geq 0]$$ Following your notation and letting $k$ be the number of plus signs for this orthant, there are $k$ positive terms here and $n-k$ negative terms. Again, actually we can ignore the normalizing factor and just assume $x_i$ are either folded normal distributions or their negations (depending on which orthant you want to be in).

Let $F_m$ represent a random variable that is the sum of $m$ i.i.d folded normal distributions. We need to compute the CDF by computing $\Pr[F_m \leq t]$ for fixed $t$. Geometrically, thinking of one dimension for each of the $m$ summands as normal variables, for $m=2$ this is a rotated square and for $m=3$ the region is an octahedron. I don't know this integral off the top of my head so I made a question for it here.

All that remains is to compute

$$\Pr[F_k \geq F_{n-k}]$$

Once we have the CDF and PDF of $F_m$, call them $F_m(t)$ and $f_m(t)$, the answer is $$\int_{0}^\infty f_{k}(t) F_{n-k}(t) dt$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Dear Chris - yes this is a way to compute it. The difficulty is then migrated to the evaluation of the restricted Gaussian integrals which doesn't make it much easier, I'm afraid. $\endgroup$ – Andreas Aug 5 '18 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.