Mixing
Probability that a sum of uniformly distributed random variables is large
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
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 Stext ?$$
Progress
If $S > ell_2 + ell_3 + dots + ell_n$, it seems that the answer is just $$fracleft(ell_1 + ell_2 + dots + ell_n - S right)^nn!cdot ell_1ell_2cdots 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.
probability geometry probability-theory probability-distributions volume
asked Jul 31 at 15:50
Anonymous Reindeer
31928
add a comment |Â
up vote
4
down vote
favorite
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 Stext ?$$
Progress
If $S > ell_2 + ell_3 + dots + ell_n$, it seems that the answer is just $$fracleft(ell_1 + ell_2 + dots + ell_n - S right)^nn!cdot ell_1ell_2cdots 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.
probability geometry probability-theory probability-distributions volume
asked Jul 31 at 15:50
Anonymous Reindeer
31928
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?
– saulspatz
Jul 31 at 16:56
In practice $n < 100$, and usually around $50$.
– Anonymous Reindeer
Jul 31 at 17:11
Mike Earnest's great answer will be computationally impractical then. Too bad.
– saulspatz
Jul 31 at 17:15
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.
– Anonymous Reindeer
Jul 31 at 19:19
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
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 Stext ?$$
Progress
If $S > ell_2 + ell_3 + dots + ell_n$, it seems that the answer is just $$fracleft(ell_1 + ell_2 + dots + ell_n - S right)^nn!cdot ell_1ell_2cdots 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.
probability geometry probability-theory probability-distributions volume
asked Jul 31 at 15:50
Anonymous Reindeer
31928
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 Stext ?$$
Progress
If $S > ell_2 + ell_3 + dots + ell_n$, it seems that the answer is just $$fracleft(ell_1 + ell_2 + dots + ell_n - S right)^nn!cdot ell_1ell_2cdots 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.
probability geometry probability-theory probability-distributions volume
asked Jul 31 at 15:50
Anonymous Reindeer
31928
asked Jul 31 at 15:50
Anonymous Reindeer
31928
asked Jul 31 at 15:50
Anonymous Reindeer
31928
asked Jul 31 at 15:50
Anonymous Reindeer
31928
31928
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?
– saulspatz
Jul 31 at 16:56
In practice $n < 100$, and usually around $50$.
– Anonymous Reindeer
Jul 31 at 17:11
Mike Earnest's great answer will be computationally impractical then. Too bad.
– saulspatz
Jul 31 at 17:15
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.
– Anonymous Reindeer
Jul 31 at 19:19
add a comment |Â
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?
– saulspatz
Jul 31 at 16:56
In practice $n < 100$, and usually around $50$.
– Anonymous Reindeer
Jul 31 at 17:11
Mike Earnest's great answer will be computationally impractical then. Too bad.
– saulspatz
Jul 31 at 17:15
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.
– Anonymous Reindeer
Jul 31 at 19:19
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?
– saulspatz
Jul 31 at 16:56
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?
– saulspatz
Jul 31 at 16:56
In practice $n < 100$, and usually around $50$.
– Anonymous Reindeer
Jul 31 at 17:11
In practice $n < 100$, and usually around $50$.
– Anonymous Reindeer
Jul 31 at 17:11
Mike Earnest's great answer will be computationally impractical then. Too bad.
– saulspatz
Jul 31 at 17:15
Mike Earnest's great answer will be computationally impractical then. Too bad.
– saulspatz
Jul 31 at 17:15
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.
– Anonymous Reindeer
Jul 31 at 19:19
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.
– Anonymous Reindeer
Jul 31 at 19:19
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
It is a little easier to think about $mathbb P( a_1+dots+a_nle S)$, then subtract from $1$.
It turns out that
$$P( a_1+dots +a_nle S)=frac1n!ell_1cdots ell_nsum_Isubseteq 1,dots,n(-1)^IBig(Big(S-sum_iin Iell_iBig)^+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_ige 0,sum_i a_ile 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_ige 0 forall i,a_jge ell_j ,sum_i a_ile S$ will be a part of the first simplex extending outside the box, which is nonempty $Sge ell_j$. The volume of this simplex is the same as that of $S_j'=a_ige 0 forall i ,sum_i a_ile 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_ige 0forall i,a_jge ell_j,a_kge ell_k,sum_i a_ile S$. This overlap is nonempty whenever $Sge 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.
answered Jul 31 at 17:00
Mike Earnest
14.7k11644
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
It is a little easier to think about $mathbb P( a_1+dots+a_nle S)$, then subtract from $1$.
It turns out that
$$P( a_1+dots +a_nle S)=frac1n!ell_1cdots ell_nsum_Isubseteq 1,dots,n(-1)^IBig(Big(S-sum_iin Iell_iBig)^+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_ige 0,sum_i a_ile 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_ige 0 forall i,a_jge ell_j ,sum_i a_ile S$ will be a part of the first simplex extending outside the box, which is nonempty $Sge ell_j$. The volume of this simplex is the same as that of $S_j'=a_ige 0 forall i ,sum_i a_ile 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_ige 0forall i,a_jge ell_j,a_kge ell_k,sum_i a_ile S$. This overlap is nonempty whenever $Sge 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.
answered Jul 31 at 17:00
Mike Earnest
14.7k11644
add a comment |Â
up vote
3
down vote
accepted
It is a little easier to think about $mathbb P( a_1+dots+a_nle S)$, then subtract from $1$.
It turns out that
$$P( a_1+dots +a_nle S)=frac1n!ell_1cdots ell_nsum_Isubseteq 1,dots,n(-1)^IBig(Big(S-sum_iin Iell_iBig)^+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_ige 0,sum_i a_ile 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_ige 0 forall i,a_jge ell_j ,sum_i a_ile S$ will be a part of the first simplex extending outside the box, which is nonempty $Sge ell_j$. The volume of this simplex is the same as that of $S_j'=a_ige 0 forall i ,sum_i a_ile 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_ige 0forall i,a_jge ell_j,a_kge ell_k,sum_i a_ile S$. This overlap is nonempty whenever $Sge 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.
answered Jul 31 at 17:00
Mike Earnest
14.7k11644
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
It is a little easier to think about $mathbb P( a_1+dots+a_nle S)$, then subtract from $1$.
It turns out that
$$P( a_1+dots +a_nle S)=frac1n!ell_1cdots ell_nsum_Isubseteq 1,dots,n(-1)^IBig(Big(S-sum_iin Iell_iBig)^+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_ige 0,sum_i a_ile 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_ige 0 forall i,a_jge ell_j ,sum_i a_ile S$ will be a part of the first simplex extending outside the box, which is nonempty $Sge ell_j$. The volume of this simplex is the same as that of $S_j'=a_ige 0 forall i ,sum_i a_ile 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_ige 0forall i,a_jge ell_j,a_kge ell_k,sum_i a_ile S$. This overlap is nonempty whenever $Sge 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.
answered Jul 31 at 17:00
Mike Earnest
14.7k11644
It is a little easier to think about $mathbb P( a_1+dots+a_nle S)$, then subtract from $1$.
It turns out that
$$P( a_1+dots +a_nle S)=frac1n!ell_1cdots ell_nsum_Isubseteq 1,dots,n(-1)^IBig(Big(S-sum_iin Iell_iBig)^+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_ige 0,sum_i a_ile 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_ige 0 forall i,a_jge ell_j ,sum_i a_ile S$ will be a part of the first simplex extending outside the box, which is nonempty $Sge ell_j$. The volume of this simplex is the same as that of $S_j'=a_ige 0 forall i ,sum_i a_ile 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_ige 0forall i,a_jge ell_j,a_kge ell_k,sum_i a_ile S$. This overlap is nonempty whenever $Sge 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.
answered Jul 31 at 17:00
Mike Earnest
14.7k11644
answered Jul 31 at 17:00
Mike Earnest
14.7k11644
answered Jul 31 at 17:00
Mike Earnest
14.7k11644
answered Jul 31 at 17:00
Mike Earnest
14.7k11644
14.7k11644
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868199%2fprobability-that-a-sum-of-uniformly-distributed-random-variables-is-large%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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?
– saulspatz
Jul 31 at 16:56
In practice $n < 100$, and usually around $50$.
– Anonymous Reindeer
Jul 31 at 17:11
Mike Earnest's great answer will be computationally impractical then. Too bad.
– saulspatz
Jul 31 at 17:15
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.
– Anonymous Reindeer
Jul 31 at 19:19