4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I gather this is a practical problem, since you say you'd be interested in an algorithmic approach. How large is $n$ liable to be in practice? $\endgroup$ – saulspatz Jul 31 '18 at 16:56
  • $\begingroup$ In practice $n < 100$, and usually around $50$. $\endgroup$ – Naysh Jul 31 '18 at 17:11
  • $\begingroup$ Mike Earnest's great answer will be computationally impractical then. Too bad. $\endgroup$ – saulspatz Jul 31 '18 at 17:15
  • 1
    $\begingroup$ True. The result presented there is really pretty though. And, if I mainly cared about computational results, then probably the easiest approach would just be to use Central Limit Theorem. $\endgroup$ – Naysh Jul 31 '18 at 19:19
3
$\begingroup$

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.

$\endgroup$

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.