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$
6
  • $\begingroup$ Perhaps you find this paper and its references useful: analytic-combinatorics.org/index.php/ojac/article/view/26 $\endgroup$ Commented Nov 27, 2014 at 21:13
  • $\begingroup$ Thanks Moritz, I'll look at it. At first glance it seems quite useful indeed. $\endgroup$ Commented Nov 27, 2014 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$ Commented Nov 27, 2014 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
    Commented Nov 28, 2014 at 1:11
  • 3
    $\begingroup$ This is the Irwin-Hall distribution; there are indeed formulas in Wikipedia. $\endgroup$ Commented Nov 28, 2014 at 3:23

1 Answer 1

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$
10
  • 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
    Commented Nov 28, 2014 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
    Commented Nov 28, 2014 at 1:52
  • 1
    $\begingroup$ btw, I also use PIE as short form of my personal name. $\endgroup$ Commented Nov 28, 2014 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
    Commented Nov 28, 2014 at 3:16
  • 2
    $\begingroup$ This is the Irwin-Hall distribution. $\endgroup$ Commented Nov 28, 2014 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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