Probabilidad de que una suma de variables aleatorias uniformemente distribuidas sea grande

Question

Problema

Deje $\ell_1 \le \ell_2 \le \dots \ell_n$ ser no negativo de los números reales, y $S$ un número real no negativo que es menor que la suma de los $\ell_i$.

Supongamos que para $i = 1, 2, \dots, n$, un número $a_i$ es recogida del intervalo de $[0, \ell_i]$ uniformemente al azar.

¿Cuál es la probabilidad de que $$a_1 + a_2 + \dots + a_n \ge S\text{ ?}$$

El progreso

Si $S > \ell_2 + \ell_3 + \dots + \ell_n$, parece que la respuesta es solo $$\frac{\left(\ell_1 + \ell_2 + \dots + \ell_n - S \right)^n}{n!\cdot \ell_1\ell_2\cdots \ell_n}.$$ Tengo esta calculando el volumen de la región asociada, que en este caso se forma un simplex.

No estoy seguro de cuál es la respuesta en el caso general, sin embargo. Si no hay una buena forma cerrada, yo todavía me gustaría encontrar una aproximación algorítmica que podrían determinar la respuesta rápidamente.

Answer 1

Es un poco más fácil pensar en $\mathbb P( a_1+\dots+a_n\le S)$, luego de restar de $1$.

Resulta que

$$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,$$ donde la notación $x^+$$\max(x,0)$.

En esencia, el argumento es la inclusión a la exclusión. Comenzamos considerando el volumen del simplex definido por $\{a_i\ge 0,\sum_i a_i\le S\}$. Esto es $S^n/n!$.

Sin embargo, esta tabla puede extender fuera de la caja. Para cada una de las $j$, el simplex definido por $S_j=\{a_i\ge 0 \forall i,a_j\ge \ell_j ,\sum_i a_i\le S\}$ será parte de la primera simplex se extiende fuera de la caja, que es no vacío $S\ge \ell_j$. El volumen de esta tabla es la misma que la de $S_j'=\{a_i\ge 0 \forall i ,\sum_i a_i\le S-\ell_j\}$,$(S-\ell_j)^n/n!$.

Sin embargo, para cualquier $j,k$, los dos simplexes $S_j$ $S_k$ nos resta podrían, en realidad, se superponen. Su superposición es el volumen de $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\}$. Esta superposición es no vacío siempre $S\ge \ell_j+\ell_k$, y el volumen es $(S-\ell_j-\ell_k)^n/n!$. Este volumen debe ser añadido de nuevo, ya que es la que se ha deducido a cabo dos veces al restar el solo desbordamiento simplexes en el último párrafo.

Continuando de esta manera, se obtiene la fórmula que se muestra. El $(\cdot)^+$ notación se ocupa de todo el trabajo automáticamente.

Hay probabilidad de una manera más simple de derivar esta encontrando la función característica de a $a_1+\dots+a_n$ y el uso de la inversión de la fórmula, pero yo no he sido capaz de conseguir que funcione.