# 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. Dec 21, 2010 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." Dec 21, 2010 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$. Dec 21, 2010 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, 2010 at 22:03
• @Slowsolver: exactly. Dec 21, 2010 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. Dec 22, 2010 at 21:36
• Rough idea: With this change of variables there's a zero mean zero correlation gaussian. Expand facets to hyperplanes, each defines two halfspaces. All hyperplanes make a partition of the space, bounded polytope in the middle and some exterior regions. Each integral over a halfspace reduces to a 1D error function(I think) and is the sum of the integrals over some of the regions, and there are $2M$ such integrals and a sum-to-1 constraint. So $2M+1$ equations, not sure about the number of exterior regions;can this linear system be solved for the integral over each region including the polytope? Jul 7 at 20:24