10
$\begingroup$

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$ ?

$\endgroup$
  • $\begingroup$ Perhaps you find this paper and its references useful: analytic-combinatorics.org/index.php/ojac/article/view/26 $\endgroup$ – Moritz Firsching Nov 27 '14 at 21:13
  • $\begingroup$ Thanks Moritz, I'll look at it. At first glance it seems quite useful indeed. $\endgroup$ – Mathieu Baillif Nov 27 '14 at 21:18
  • $\begingroup$ mathoverflow.net/questions/145475 appears to be true in this case: D. L. Barrow and P. W. Smith, Spline notation applied to a volume problem, Amer. Math. Monthly, 86 (1979) (I haven't check this reference yet..) $\endgroup$ – Moritz Firsching Nov 27 '14 at 21:20
  • 1
    $\begingroup$ If you remove the condition that the $x_i$ are bounded above by 1 then the volume of this region is a standard result in algebraic number theory: the volume is $t^n/n!$. So that formula works if $t \leq 1$ when you insist $x_i \in [0,1]$. Details of the calculation can be found in Lemma 7.17 (p. 159) of Frazer Jarvis's Algebraic Number Theory and Lemma 3 of Section 3 of Chapter V of Lang's Algebraic Number Theory (set $r_2 = 0$ in both cases). $\endgroup$ – KConrad Nov 28 '14 at 1:11
  • 3
    $\begingroup$ This is the Irwin-Hall distribution; there are indeed formulas in Wikipedia. $\endgroup$ – Kevin O'Bryant Nov 28 '14 at 3:23
9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Which, in the language of a school kid, is just PIE: take the simplex $S=\{x_i>0, \sum x_i<t\}$ and its translates $S_j$ by $n$ unit vectors. We want $v(S\setminus\cup (S\cap S_j)$ and the volumes of $S\cap (S_{j_1}\cap\dots\cap S_{j_k})$ are exactly $\frac 1{n!}(t-k)_+^n$. $\endgroup$ – fedja Nov 28 '14 at 1:46
  • 1
    $\begingroup$ When I was a school kid, PIE was something to eat. Later when I took linguisitcs PIE was Proto-Indo-European. I don't think I've seen PIE as an abbreviation for the principle of inclusion-exclusion before. In what areas of math is that abbreviation widely used? $\endgroup$ – KConrad Nov 28 '14 at 1:52
  • 1
    $\begingroup$ btw, I also use PIE as short form of my personal name. $\endgroup$ – Pietro Majer Nov 28 '14 at 2:00
  • 1
    $\begingroup$ @KConrad Almost every English-speaking school kid who took part in some math olympiads would call it this way. Just go to AoPS and check if you do not want to take my word for it :-). $\endgroup$ – fedja Nov 28 '14 at 3:16
  • 2
    $\begingroup$ This is the Irwin-Hall distribution. $\endgroup$ – Kevin O'Bryant Nov 28 '14 at 3:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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