What's the volume of $\{x\in[0,1]^n|\sum x_i\le t\}$ for real $t$?

Question

EDIT: Thanks for your answers and comments. There is indeed a classical easy formula, given by Pietro Majer (with a simple nice proof) in his answer below.

---

Given $x\in\mathbb{R}^n$, $x_i$ denotes its $i$-th coordinate. My question is:

• What is $Vol(\{x\in[0,1]^n|\sum_{i=1}^n x_i\le t\})$ for $t\in\mathbb{R}$ ? Is there some kind of "easily computable" formula for it ?

A colleague asked me this in relation to a problem in applied mathematics, and I thought that the answer was going to be easy to find, but after trying to compute it by hand in dimension $3$ and then generalizing, I just surrendered. I am pretty sure that it should be somehow classical, but I could not track down a formula or a reference in the general case. I should specify that I know next to nothing about section of convex bodies, and I might be missing something easy. With some browsing, I found the following partial answers (which I hope I do not mix-up):

• If $t$ is an integer, then the volume is the sum of the $t$ first Eulerian numbers divided by $n!$.

• Between and integer $t<n$ and the next, the volume function is a polynomial of degree $n$. The polynomials corresponding to two consecutive intervals must have the same first derivative at their common point. For instance, for $n=2$ the volume is given by $\frac{t^2}{2}$ if $t\in[0,1]$, $1 - \frac{(2-t)^2}{2}$ for $t\in[1,2]$ and constant elsewhere.

• There is a Fourier-analysis approach for the problem of finding the $n-1$-volume of the section of a convex body by an hyperplane, but the formulas I found did not seem to me easily computable (my knowledge of Fourier analysis is approximatively equivalent to that of convex bodies, I must say).

• We can use some probability theory to find an approximation: each $x_i$ is seen as a random variable following a law of mean $\mu$ and variance $\nu$, then $S=\sum x_i$ follows (approximatively and for large $n$) the normal law with mean $n\mu$ and variance $n^2\nu$, and the probability of $S\le t$ is then easy to compute. I presume that the meaning of "$n$ is large" and "approximate" can be made explicit by looking more closely at the central limit theorem. (This idea comes from Michael Lugo's answer to this related question. Another answer by Andrey Rekalo points to the Fourier-analysis method mentioned above.)

The last point brings a more general question: given a probability distribution on $[0,1]$ (perhaps in some well behaved class), are there some good estimates for $P(\sum_{i=1}^n x_i\le t)$ for smaller $n$ ?

Answer 1

The volume $V_n(t)$ is the cdf of the sum of $n$ independent random variables, uniformly distributed on $[0,1]$. So the density $V_n'(t)$ is the $n$-fold convolution of the characteristic function of the unit interval, $\chi_{[0,1]}$. (In particular $V_n'\in C^{n-2,1}(\mathbb{R})$, with support in $[0,n]$, and polynomial of degree less than $ n $ on any interval between consecutive integers). It is convenient to write $\chi_{[0,1]}(t)=H(t)-H(t-1)$, where $H(t):=\chi_{\mathbb{R_+}}(t)$ is the Heaviside function, or $\chi_{[0,1]}=H-\tau^1 H$ where $\tau^s:f\mapsto f(\cdot-s)$ is the translation semigroup on functions. Recall that convoluting with $H$ is taking a primitive: $(H*f)(x)=\int_{-\infty}^xf(t)dt$, so in particular $H^{*(n+1)}(t)=t_+^n/n!$, and that $\tau^s(f*g)=\tau^sf*g= f* \tau^s g$.

Thus $$V_n=H*V'_n=H*(H-\tau^1H)^{*n}=\sum_{k=0}^n(-1)^k{n\choose k}H*H^{*(n-k)}*(\tau^1H)^{*k}$$ $$=\sum_{k=0}^n(-1)^k{n\choose k} \tau^kH^{*(n+1)},$$ that is $$V_n(t)=\sum_{k=0}^n\frac{(-1)^k}{k!(n-k)!} {(t-k)_+}{^n}\, .$$