6
$\begingroup$

A mysterious result, probably by Euler himself, goes as follows:

If $n$ is a positive integer and $f:\mathbb R \rightarrow \mathbb C$ is integrable on the open interval $(0, n)$, then $$\int_0^1\int_0^1\ldots\int_0^1 f(\lfloor x_1 + x_2 + \ldots +x_n\rfloor) \, dx_1 \, dx_2\ldots dx_n = \sum_{k=1}^\infty A(n,k)\frac{f(k)}{k!}, $$ where the $A(n,k)$'s are the Eulerian numbers.

Is there an analogous result without the floor function ? Thats is, is there an analogous formula for the integral

$$ \int_0^1\int_0^1\ldots\int_0^1 f(x_1 + x_2 + \ldots + x_n)\,dx_1\,dx_2\ldots dx_n \; ? $$

$\endgroup$
  • $\begingroup$ @GabrielRomon Ya, that is indeed true and I considered it myself. It also provides a way to approximate the integral via statistical sampling. $\endgroup$ – dohmatob Nov 10 '17 at 9:39
3
$\begingroup$

Here is a detailed solution motivated by @Arthur's. Let $\mathbf w \in \mathbb R^n$, non of whose coordinates is $0$. For any real $z$, define

$$G_{\mathbf w,z} := \{\mathbf x \in \mathbb R^n | \mathbf w^T \mathbf x \le z\}, \;H_{\mathbf w,z} := \{\mathbf x \in \mathbb R^n | \mathbf w^T \mathbf x = z\}.$$

The sought-for integral is precisely $$\int_{[0,1]^n} f(\mathbf w^T\mathbf x)d\mathbf x= \mathbb E_{x_1,\ldots, x_n \sim \mathcal U[0, 1]} [f(\mathbf w^T \mathbf x)]$$ with the choice $w_1 = \ldots w_n = 1$.

Now, let $F_{\mathbf w}$ be the cdf of $\mathbf w^T\mathbf x$ for i.i.d $x_1,\ldots,x_n \sim \mathcal U[0,1]$. Then its not hard to see that $F_{\mathbf w}(z) = \operatorname{vol}_n (G_{\mathbf w,z} \cap[0,1]^n)$, with density $f_{\mathbf w}(z) = \|\mathbf w\|_2^{-1} \operatorname{vol}_{n-1} (H_{\mathbf w,z} \cap[0,1]^n)$. By elementary properties of expectations, one has

$$ \begin{split} \int_{[0,1]^n} f(\mathbf w^T\mathbf x)d\mathbf x &= \mathbb E_{x_1,\ldots, x_n \sim \mathcal U[0, 1]}f(\mathbf w^T\mathbf x) = \int_{-\infty}^\infty \mathbb E(f(\mathbf w^T\mathbf x) | \mathbf w^T\mathbf x = z)f_{\mathbf w}(z)dz\\ &= \int_{-(-\mathbf w)_+^T\mathbf 1_n}^{(\mathbf w)_+^T\mathbf 1_n} \|\mathbf w\|_2^{-1}\operatorname{vol}_{n-1} (H_{\mathbf w,z} \cap[0,1]^n)f(z)dz. \end{split} $$

Invoking Theorem 4 of this paper yields $$ \|\mathbf w\|_2^{-1}\operatorname{vol}_{n-1} (H_{\mathbf w,z} \cap[0,1]^n) = \frac{1}{(n-1)! \prod_{k=1}^n w_k}\sum_{K \subseteq [\![n]\!]}(-1)^{\#K}\left(z - \mathbf w^T\mathbf 1_K\right)_+^{n-1}, $$

where $\mathbf w^T \mathbf 1_K := \sum_{k \in K}w_k$. Putting things together gives

$$ \int_{[0,1]^n} f(\mathbf w^T\mathbf x)d\mathbf x= \frac{1}{(n-1)! \prod_{k=1}^n w_k}\sum_{K \subseteq [\![n]\!]}(-1)^{\#K}\sigma_{\mathbf w, K}(f), $$

where $\sigma_{\mathbf w, K}(f):= \Lambda_{-(-\mathbf w)_+^T\mathbf 1_n,(\mathbf w)_+^T\mathbf 1_n,\mathbf w^T\mathbf 1_K}(f)$ and $$\Lambda_{a,b,c}(f) := \int_{a}^b \left(z - c\right)_+^{n-1}f(z)dz. $$

Thus the whole game is about computing the numbers $\Lambda_{a,b,c}(f)$.

Examples

  • Volume of hypercube $[0,1]^n$. This is a pathologically simple example and is only here to act as a sanity check. Take $w_1 = \ldots = w_n = f = 1$, and for any $K \subseteq [\![n]\!]$ with $\#K = k$, one has

$$\sigma_{\mathbf w, K}(f) = \int_{k}^n (z-k)^{n-1} dz = \frac{1}{n}(n-k)^n. $$

Thus $$\int_{[0,1]^n} dx_1 \ldots dx_n = \frac{1}{n!}\sum_{k=0}^n C^n_k(-1)^k(n-k)^n = 1 $$

  • Expected value of sum of $n$ i.i.d uniform random variables. Take $w_1 = \ldots = w_n = 1$ and $f = \operatorname{id}$. For any $K \subseteq [\![n]\!]$ with $\#K = k$, one has

$$\sigma_{\mathbf w, K}(f) = \int_0^n(z-k)^{n-1}zdz = \frac{(n - k)^n(n^2 + k)}{n(n+1)} $$

$$ \begin{split} \int_{[0,1]^n}(x_1+ \ldots + x_n)dx_1 \ldots dx_n &= \frac{1}{(n+1)!}\sum_{k=0}^n (-1)^kC^n_k (n-k)^{n}(n^2 + k)\\ &= \frac{1}{(n+1)!}\frac{n}{2}(n+1)! = \frac{n}{2} \end{split} $$

$\endgroup$
2
$\begingroup$

I propose the following:

If $A(c)$ is the hyperarea of the region of the hyperplane $x_1+\cdots + x_n = c$ bounded by the hypercube $0\leq x_1, \ldots,x_n\leq 1$, the integral is equal to $\frac 1{\sqrt n} \int_0^{n}A(c)f(c)dc$.

I might have missed something, though, as I haven't done any general checking. It works for $n = 1,2$ and $f(x) = 1$, so I don't think I've missed any constant factors, at least. Comments and corrections are welcome.

$\endgroup$
  • $\begingroup$ Nice! I can derive your formula upto withing the $\frac{1}{\sqrt{n}}$ factor (mistake ?). Indeed, let $H_z := \{(x_1,\ldots,x_n) | \sum_i x_i = z\}$. Then, $$ \begin{split} \int_{[0,1]^n} f(\sum_i x_i)dx_1 \ldots dx_n &= \int_{z=0}^n \left(\int_{[0,1]^n \cap H_z}f(z)dx_1\ldots dx_n\right)dz\\ &= \int_{z=0}^n \left(\int_{[0,1]^n \cap H_z}dx_1\ldots dx_n\right)f(z)dz\\ = \int_{z=0}^n \operatorname{vol}([0,1]^n \cap H_z)f(z)dz \end{split} $$ $\endgroup$ – dohmatob Nov 10 '17 at 10:22
  • $\begingroup$ @dohmatob I needed the $\frac1{\sqrt n}$ factor to make the $n = 2, f(x) = 1$ case work, since the graph of $A(c)$ in that case is an isosceles triangle with height $\sqrt2$ and base $2$. It might not be the correct factor in the general case, but for the two simplest cases it works, so that's why I guessed it. However, it seems reasonable, since it represents the distance between the hyperplanes $x_1+\cdots +x_n = c$ and $x_1+\cdots x_n = c+1$ (in other words, the velocity at which the hyperplane "sweeps over" the hypercube) $\endgroup$ – Arthur Nov 10 '17 at 10:26
  • $\begingroup$ you're right about the strange $\sqrt{n}$ term in the denominator. Actually, this term is just the $\ell_2$ norm of the weighting vector $w = (1,\ldots,1)$ required to pass from volume of the polytope to the hyper-area of its boundary, via derivatives w.r.t $z$. See my post below. That is $\partial_z \operatorname{vol}(z) = \|w\|_2 \operatorname{surface}(z)$. $\endgroup$ – dohmatob Nov 13 '17 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.