Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the integral of a $k$-dimensional (multivariate) Gaussian over a convex $k$-polytope?

Here I am specifically interested in $k\in\{2,3\}$, but insight on the general problem would also be appreciated. I am guessing that there is no closed form in the general case, but what if we restrict the number of vertices of the polytope to at most $k+1$? If no closed form exists even under this constraint, are there efficient ways to approximate the integral?

share|improve this question
    
Could you please clarify what do you mean by k-dimensional Gaussian. If it is random $k\times 1$ vector with multivariate normal distribution, I do not see how can you define the integral. –  mpiktas Dec 21 '10 at 21:25
    
By "$k$-dimensional Gaussian" I mean: "A distribution in $k$-dimensional Euclidean space that is composed of univariate normal distributions in each dimension." –  ESultanik Dec 21 '10 at 21:34
    
The base case, when $k=1$, is simple: It is just asking to find the area under a univariate normal distribution in some subset of $\mathbb{R}$. When $k=2$, the problem I am trying to solve is finding the volume under the distribution in the region defined by a convex polygon in $\mathbb{R}^2$. When $k=3$, the problem boils down to integrating the distribution over some convex polyhedron in $\mathbb{R}^3$. –  ESultanik Dec 21 '10 at 21:36
    
so in other words, you are looking to compute the volume of the polytope, but with respect to the Gaussian measure? –  user1709 Dec 21 '10 at 22:03
    
@Slowsolver: exactly. –  ESultanik Dec 21 '10 at 22:59

1 Answer 1

up vote 1 down vote accepted

So you want to compute the following integral:

\begin{align*} \frac{1}{(2\pi|\Sigma|)^{n/2}}\int_{V_k}\exp\left(-\frac{1}{2}(x-a)^T\Sigma^{-1}(x-a)\right)dx \end{align*}

where $V_k\subset \mathbb{R}^k$ is a $k$-polytope, $a\in \mathbb{R}^k$ is the mean and $\Sigma$ is the $k\times k$ covariance matrix of $k$-variate normal vector.

My approach would be doing a change of variables $y=\Sigma^{1/2}(x-a)$ and then integrate by one variable at a time, since the integrand function will be a product of one-variable functions. If $\Sigma^{1/2}V_k$ is a $k$-cube then the integration is straightforward. For the general case it will not be easy. Take $k=2$, normal with zero mean and unit covariance matrix, and $V_2$ a triangle with vertices in $(0,0)$, $(1,0)$, $(0,1)$. Then your integral will be \begin{align} \frac{1}{2\pi}\int_{V_2}e^{-\frac{x_1^2}{2}}e^{-\frac{x_2^2}{2}}dx_1dx_2&=\frac{1}{2\pi}\int_{0}^{1}e^{-\frac{x_1^2}{2}}dx_1\int_{0}^{1-x_1}e^{-\frac{x_2^2}{2}}dx_2\\ &=\frac{1}{\sqrt{2\pi}}\int_0^1e^{-\frac{x_1^2}{2}}(\Phi(1-x_1)-\Phi(0))dx_1 \end{align} which I do not think has closed formula. (I might be wrong).

As for approximation, I do not see why standard numerical integral solving methods would not work.

share|improve this answer
    
Thanks! I was basically throwing this question out there in the hopes that there are some relaxations that make it closed form. By "approximation" I really meant something like bounding the polytope by a $k$-cube convex hull and using its integration as an upper bound on the polytope's integration. –  ESultanik Dec 22 '10 at 21:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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