Take the 2-minute tour ×

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


