Probability that a sum of uniformly distributed random variables is large

Question

Problem

Let $\ell_1 \le \ell_2 \le \dots \ell_n$ be nonnegative real numbers, and $S$ a nonnegative real number that is smaller than the sum of the $\ell_i$.

Suppose that for $i = 1, 2, \dots, n$, a number $a_i$ is picked from the interval $[0, \ell_i]$ uniformly at random.

What is the probability that $$a_1 + a_2 + \dots + a_n \ge S\text{ ?}$$

Progress

If $S > \ell_2 + \ell_3 + \dots + \ell_n$, it seems that the answer is just $$\frac{\left(\ell_1 + \ell_2 + \dots + \ell_n - S \right)^n}{n!\cdot \ell_1\ell_2\cdots \ell_n}.$$ I got this by computing the volume of the associated region, which in this case forms a simplex.

I'm not sure what the answer is in the general case however. If there isn't a nice closed form, I'd still like to find an algorithmic approach that could determine the answer quickly.

Answer 1

It is a little easier to think about $\mathbb P( a_1+\dots+a_n\le S)$, then subtract from $1$.

It turns out that

$$P( a_1+\dots +a_n\le S)=\frac{1}{n!\ell_1\cdots \ell_n}\sum_{I\subseteq \{1,\dots,n\}}(-1)^{|I|}\Big(\Big(S-\sum_{i\in I}\ell_i\Big)^+\Big)^n,$$ where the notation $x^+$ means $\max(x,0)$.

Essentially, the argument is inclusion exclusion. We start by considering the volume of the simplex defined by $\{a_i\ge 0,\sum_i a_i\le S\}$. This is $S^n/n!$.

However, this simplex might extend outside of the box. For each $j$, the simplex defined by $S_j=\{a_i\ge 0 \forall i,a_j\ge \ell_j ,\sum_i a_i\le S\}$ will be a part of the first simplex extending outside the box, which is nonempty $S\ge \ell_j$. The volume of this simplex is the same as that of $S_j'=\{a_i\ge 0 \forall i ,\sum_i a_i\le S-\ell_j\}$, which is $(S-\ell_j)^n/n!$.

However, for any $j,k$, the two simplexes $S_j$ and $S_k$ we subtracted might actually overlap. Their overlap is the volume of $S_{j,k}=\{a_i\ge 0\forall i,a_j\ge \ell_j,a_k\ge \ell_k,\sum_i a_i\le S\}$. This overlap is nonempty whenever $S\ge \ell_j+\ell_k$, and the volume is $(S-\ell_j-\ell_k)^n/n!$. This volume must be added back in, since is was subtracted out twice when subtracting the singly overflow simplexes in the last paragraph.

Continuing in this fashion, you get the displayed formula. The $(\cdot)^+$ notation takes care of all the casework automatically.

There is probability a simpler way to derive this by finding the characteristic function of $a_1+\dots+a_n$ and using the inversion formula, but I haven't quite been able to get that to work out.