1
$\begingroup$

I have an integral of the type: \begin{equation} I=\int_A f(x,y)\,dx\,dy \end{equation}

where \begin{equation} A=\{(x,y) : x\leq X,y\leq Y,x+y \geq W\} \end{equation}

Assuming that $f(x,y)$ has a closed-form anti-derivative, and that $A$ is not empty, I can handle this case by sketching the region $A$ (a triangle) and defining the limits of the double-integral to evaluate $I$.

With a 3-dimension problem maybe I can use the shadow method or the cross section method, but my problem is in dealing with higher dimensions, where I cannot sketch the region $A$. Being unable to define the limits of integration, the only way I know to evaluate $I$ is to use numerical integration methods (i.e. MonteCarlo), using an indicatory function $\mathbf{1}_A (x,y)$ so I can consider only values of $(x,y)$ actually in $A$.

So, I was wondering how to find the limits of integration given a set $A$ in the form: \begin{equation} A=\{(x_1,\dots,x_n) : x_i\leq X_i, \sum_{i=1}^n x_i \geq W\} \end{equation}

Since the equations defining $A$ are all linear inequalities, is there a general way to move from the set-notation to the limits of integration? As far as I understood, this is generally a hard problem, but I was wondering whether the specific structure of the inequalities can be exploited to simplify it.

Any hint is appreciated.

1 Answers 1

1

In your setup the $x_i$ are not apriori bounded from below, which makes things considerably simpler: When $S:=\sum_{i=1}^n X_i-W<0$ then $A$ is empty, and when $S>0$ then $A$ is an $n$-dimensional simplex with one vertex at ${\bf X}:=(X_1,\ldots, X_n)$ and the edges emanating from $X$ going "backwards" parallel to the axes, as in your two-dimensional example.

Maybe it helps to substitute $x_i:=X_i-y_i$, where now the $y_i$ are $\geq 0$, and $\sum_{i=1}^n y_i\leq S$. Therefore we now have to integrate the function $g(y_1,\ldots ,y_n):=f(X_1-y_1,\ldots, X_n-y_n)$ over the $n$-dimensional simplex $\Delta:=\left\{(y_1,\ldots,y_n)\ \biggm|y_i\geq 0\ (1\leq i\leq n),\ \sum_{i=1}^n y_i\leq S\right\}$ in $y$-space. As the Jacobian has absolute value $1$ we get $J:=\int_A f({\bf x})\ {\rm d}({\bf x})=\int_\Delta g({\bf y})\ {\rm d}({\bf y})\ .$ The integral on the right can be reduced recursively. Note that the projection of $\Delta$ to the plane of the first $n-1$ coordinates $y_i$ is an $(n-1)$-dimensional simplex $\Delta':=\left\{(y_1,\ldots,y_{n-1})\ \biggm|\ y_i\geq 0\ (1\leq i\leq n-1), \ \sum_{i=1}^{n-1} y_i\leq S\right\}$ with the same $S$. There is an "outer" integral over $\Delta'$ and an "inner" integral with respect to $y_n$: For each $(y_1,\ldots ,y_{n-1})\in \Delta'$ we have to integrate along a vertical "stalk" given by $0\leq y_n\leq S-(y_1 +\ldots+y_{n-1})$. The result of the "inner" integration is a function $g_1(y_1,\ldots,y_{n-1})$ depending only on the first $n-1$ variables $y_i$, and which then has to be integrated over $\Delta'$.

Therefore the first recursion step becomes $J=\int_{\Delta'}\left(\int_0^{S-(y_1+\ldots+y_{n-1})} g({\bf y})\ dy_n\right)\ {\rm d}({\bf y}')\ .$

  • 0
    @Libra: See my edit. The factor $(-1)^n$ was indeed wrong.2012-09-06