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.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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}')\ .$$

share|improve this answer
    
@C.Blatter, thanks for your answer. I understand the first paragraph but, actually, it is hard for me to understand the second part about the recursion. I don't get, for example, where the $(-1)^n$ term comes from. I know I am asking a lot, but I would appreciate if you could give me further details about the steps of your solution, or point me to useful resources. Thanks. –  Libra Sep 6 '12 at 18:46
    
@Libra: See my edit. The factor $(-1)^n$ was indeed wrong. –  Christian Blatter Sep 6 '12 at 20:21

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.