# Integrating a $k$-dimensional (multivariate) Gaussian over a convex $k$-polytope

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?

-
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

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).
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