Probability that a stick randomly broken in three places can form a triangle
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I like questions about geometric probability, and two of my favourite questions here on math.SE are
Probability that a stick randomly broken in two places can form a triangle
and
Probability that a stick randomly broken in five places can form a tetrahedron.
I wondered about the probability that a stick randomly broken in three places can form a triangle. More generally, we can ask for the probability distribution of the number of triangles that can be formed from the four pieces. Since each triple of the pieces has probability $frac14$ of forming a triangle, the expected number of triangles we can form is $frac14cdot4=1$, which is already a rather nice result.
I tried various ways of applying inclusion–exclusion, with or without first ordering the segments by size, but it all seemed too complicated and unenlightening, and I ended up writing a program to output all the inequalities in order to let qhull compute the volumes of the polytopes they define.
The result (confirmed by simulations) is:
beginarrayc
&textprobability&textprobability\
#triangle&text(reduced)&text(unreduced)\hline
0&frac37&frac45105\
1&frac1135&frac33105\
2&frac16105&frac16105\
3&frac4105&frac4105\
4&frac115&frac7105
endarray
You can check that the expected number of triangles comes out as $1$.
While the overall distribution is somewhat complicated, the probabilities that we can form
all triangles ($frac115$), any triangle ($frac47$) and no triangles ($frac37$) come out as nice low fractions, so I thought that maybe there's hope to find an elegant way to compute (one of) them after all. Do you see one? (The three places where the stick is broken are independently uniformly chosen along its length.)
probability alternative-proof inclusion-exclusion geometric-probability
add a comment |Â
up vote
2
down vote
favorite
I like questions about geometric probability, and two of my favourite questions here on math.SE are
Probability that a stick randomly broken in two places can form a triangle
and
Probability that a stick randomly broken in five places can form a tetrahedron.
I wondered about the probability that a stick randomly broken in three places can form a triangle. More generally, we can ask for the probability distribution of the number of triangles that can be formed from the four pieces. Since each triple of the pieces has probability $frac14$ of forming a triangle, the expected number of triangles we can form is $frac14cdot4=1$, which is already a rather nice result.
I tried various ways of applying inclusion–exclusion, with or without first ordering the segments by size, but it all seemed too complicated and unenlightening, and I ended up writing a program to output all the inequalities in order to let qhull compute the volumes of the polytopes they define.
The result (confirmed by simulations) is:
beginarrayc
&textprobability&textprobability\
#triangle&text(reduced)&text(unreduced)\hline
0&frac37&frac45105\
1&frac1135&frac33105\
2&frac16105&frac16105\
3&frac4105&frac4105\
4&frac115&frac7105
endarray
You can check that the expected number of triangles comes out as $1$.
While the overall distribution is somewhat complicated, the probabilities that we can form
all triangles ($frac115$), any triangle ($frac47$) and no triangles ($frac37$) come out as nice low fractions, so I thought that maybe there's hope to find an elegant way to compute (one of) them after all. Do you see one? (The three places where the stick is broken are independently uniformly chosen along its length.)
probability alternative-proof inclusion-exclusion geometric-probability
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I like questions about geometric probability, and two of my favourite questions here on math.SE are
Probability that a stick randomly broken in two places can form a triangle
and
Probability that a stick randomly broken in five places can form a tetrahedron.
I wondered about the probability that a stick randomly broken in three places can form a triangle. More generally, we can ask for the probability distribution of the number of triangles that can be formed from the four pieces. Since each triple of the pieces has probability $frac14$ of forming a triangle, the expected number of triangles we can form is $frac14cdot4=1$, which is already a rather nice result.
I tried various ways of applying inclusion–exclusion, with or without first ordering the segments by size, but it all seemed too complicated and unenlightening, and I ended up writing a program to output all the inequalities in order to let qhull compute the volumes of the polytopes they define.
The result (confirmed by simulations) is:
beginarrayc
&textprobability&textprobability\
#triangle&text(reduced)&text(unreduced)\hline
0&frac37&frac45105\
1&frac1135&frac33105\
2&frac16105&frac16105\
3&frac4105&frac4105\
4&frac115&frac7105
endarray
You can check that the expected number of triangles comes out as $1$.
While the overall distribution is somewhat complicated, the probabilities that we can form
all triangles ($frac115$), any triangle ($frac47$) and no triangles ($frac37$) come out as nice low fractions, so I thought that maybe there's hope to find an elegant way to compute (one of) them after all. Do you see one? (The three places where the stick is broken are independently uniformly chosen along its length.)
probability alternative-proof inclusion-exclusion geometric-probability
I like questions about geometric probability, and two of my favourite questions here on math.SE are
Probability that a stick randomly broken in two places can form a triangle
and
Probability that a stick randomly broken in five places can form a tetrahedron.
I wondered about the probability that a stick randomly broken in three places can form a triangle. More generally, we can ask for the probability distribution of the number of triangles that can be formed from the four pieces. Since each triple of the pieces has probability $frac14$ of forming a triangle, the expected number of triangles we can form is $frac14cdot4=1$, which is already a rather nice result.
I tried various ways of applying inclusion–exclusion, with or without first ordering the segments by size, but it all seemed too complicated and unenlightening, and I ended up writing a program to output all the inequalities in order to let qhull compute the volumes of the polytopes they define.
The result (confirmed by simulations) is:
beginarrayc
&textprobability&textprobability\
#triangle&text(reduced)&text(unreduced)\hline
0&frac37&frac45105\
1&frac1135&frac33105\
2&frac16105&frac16105\
3&frac4105&frac4105\
4&frac115&frac7105
endarray
You can check that the expected number of triangles comes out as $1$.
While the overall distribution is somewhat complicated, the probabilities that we can form
all triangles ($frac115$), any triangle ($frac47$) and no triangles ($frac37$) come out as nice low fractions, so I thought that maybe there's hope to find an elegant way to compute (one of) them after all. Do you see one? (The three places where the stick is broken are independently uniformly chosen along its length.)
probability alternative-proof inclusion-exclusion geometric-probability
asked Jul 25 at 16:33
joriki
164k10180328
164k10180328
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
7
down vote
The lengths of the broken stick pieces $(Y_1, Y_2, Y_3, Y_4)$ are spacings of ordered uniform. The joint distribution is equivalent to
$$ left(frac X_1 sum_i=1^4 X_i,
frac X_2 sum_i=1^4 X_i,
frac X_3 sum_i=1^4 X_i,
frac X_4 sum_i=1^4 X_iright)$$
where $X_i$ are iid exponential random variables. If we ordered the above spacings, the distribution of $(Y_(1), Y_(2), Y_(3), Y_(4))$ is equivalent to
$$ left(frac X_1/4 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 + X_4 sum_i=1^4 X_iright)$$
Any $3$ of the $4$ pieces cannot form a triangle if and only if
$$ begincases
Y_(1) + Y_(2) < Y_(3) \
Y_(1) + Y_(2) < Y_(4) \
Y_(1) + Y_(3) < Y_(4) \
Y_(2) + Y_(3) < Y_(4)
endcases$$
Note that the second inequality is implied by the first, and the third inequality is implied by the fourth. So the probability of no triangle being formed is
$$ beginalign
&Pr Y_(1) + Y_(2) < Y_(3), Y_(2) + Y_(3) < Y_(4) \
=& PrBiggfrac X_1 4 + frac X_1 4 + frac X_2 3 <
frac X_1 4 + frac X_2 3 + frac X_3 2, \
& frac X_1 4 + frac X_2 3 + frac X_1 4 + frac X_2 3
+ frac X_3 2 <
frac X_1 4 + frac X_2 3 + frac X_3 2 + X_4Bigg \
=& PrX_1 < 2X_3, 3X_1 + 4X_2 < 12X_4 \
=& int_0^infty Pr2X_3 > xPr12X_4 - 4X_2 > 3xe^-xdx
endalign$$
Note that
$$ beginalign
&Pr12X_4 - 4X_2 > 3x \
=& int_0^inftyPr12X_4 - 4u > 3xe^-udu \
=& int_0^infty e^-(3x+4u)/12 e^-udu \
=& e^-x/4int_0^infty e^-4u/3du \
=& frac 3 4e^-x/4
endalign
$$
So the integral become
$$ int_0^infty e^-x/2frac 3 4 e^-x/4e^-xdx
= frac 3 4 int_0^infty e^-7x/4 dx = frac 3 4 times frac 4 7 = frac 3 7 $$
This is not a very elegant way but at least it is doable. Looking forward to someone to post a better solution.
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
The lengths of the broken stick pieces $(Y_1, Y_2, Y_3, Y_4)$ are spacings of ordered uniform. The joint distribution is equivalent to
$$ left(frac X_1 sum_i=1^4 X_i,
frac X_2 sum_i=1^4 X_i,
frac X_3 sum_i=1^4 X_i,
frac X_4 sum_i=1^4 X_iright)$$
where $X_i$ are iid exponential random variables. If we ordered the above spacings, the distribution of $(Y_(1), Y_(2), Y_(3), Y_(4))$ is equivalent to
$$ left(frac X_1/4 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 + X_4 sum_i=1^4 X_iright)$$
Any $3$ of the $4$ pieces cannot form a triangle if and only if
$$ begincases
Y_(1) + Y_(2) < Y_(3) \
Y_(1) + Y_(2) < Y_(4) \
Y_(1) + Y_(3) < Y_(4) \
Y_(2) + Y_(3) < Y_(4)
endcases$$
Note that the second inequality is implied by the first, and the third inequality is implied by the fourth. So the probability of no triangle being formed is
$$ beginalign
&Pr Y_(1) + Y_(2) < Y_(3), Y_(2) + Y_(3) < Y_(4) \
=& PrBiggfrac X_1 4 + frac X_1 4 + frac X_2 3 <
frac X_1 4 + frac X_2 3 + frac X_3 2, \
& frac X_1 4 + frac X_2 3 + frac X_1 4 + frac X_2 3
+ frac X_3 2 <
frac X_1 4 + frac X_2 3 + frac X_3 2 + X_4Bigg \
=& PrX_1 < 2X_3, 3X_1 + 4X_2 < 12X_4 \
=& int_0^infty Pr2X_3 > xPr12X_4 - 4X_2 > 3xe^-xdx
endalign$$
Note that
$$ beginalign
&Pr12X_4 - 4X_2 > 3x \
=& int_0^inftyPr12X_4 - 4u > 3xe^-udu \
=& int_0^infty e^-(3x+4u)/12 e^-udu \
=& e^-x/4int_0^infty e^-4u/3du \
=& frac 3 4e^-x/4
endalign
$$
So the integral become
$$ int_0^infty e^-x/2frac 3 4 e^-x/4e^-xdx
= frac 3 4 int_0^infty e^-7x/4 dx = frac 3 4 times frac 4 7 = frac 3 7 $$
This is not a very elegant way but at least it is doable. Looking forward to someone to post a better solution.
add a comment |Â
up vote
7
down vote
The lengths of the broken stick pieces $(Y_1, Y_2, Y_3, Y_4)$ are spacings of ordered uniform. The joint distribution is equivalent to
$$ left(frac X_1 sum_i=1^4 X_i,
frac X_2 sum_i=1^4 X_i,
frac X_3 sum_i=1^4 X_i,
frac X_4 sum_i=1^4 X_iright)$$
where $X_i$ are iid exponential random variables. If we ordered the above spacings, the distribution of $(Y_(1), Y_(2), Y_(3), Y_(4))$ is equivalent to
$$ left(frac X_1/4 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 + X_4 sum_i=1^4 X_iright)$$
Any $3$ of the $4$ pieces cannot form a triangle if and only if
$$ begincases
Y_(1) + Y_(2) < Y_(3) \
Y_(1) + Y_(2) < Y_(4) \
Y_(1) + Y_(3) < Y_(4) \
Y_(2) + Y_(3) < Y_(4)
endcases$$
Note that the second inequality is implied by the first, and the third inequality is implied by the fourth. So the probability of no triangle being formed is
$$ beginalign
&Pr Y_(1) + Y_(2) < Y_(3), Y_(2) + Y_(3) < Y_(4) \
=& PrBiggfrac X_1 4 + frac X_1 4 + frac X_2 3 <
frac X_1 4 + frac X_2 3 + frac X_3 2, \
& frac X_1 4 + frac X_2 3 + frac X_1 4 + frac X_2 3
+ frac X_3 2 <
frac X_1 4 + frac X_2 3 + frac X_3 2 + X_4Bigg \
=& PrX_1 < 2X_3, 3X_1 + 4X_2 < 12X_4 \
=& int_0^infty Pr2X_3 > xPr12X_4 - 4X_2 > 3xe^-xdx
endalign$$
Note that
$$ beginalign
&Pr12X_4 - 4X_2 > 3x \
=& int_0^inftyPr12X_4 - 4u > 3xe^-udu \
=& int_0^infty e^-(3x+4u)/12 e^-udu \
=& e^-x/4int_0^infty e^-4u/3du \
=& frac 3 4e^-x/4
endalign
$$
So the integral become
$$ int_0^infty e^-x/2frac 3 4 e^-x/4e^-xdx
= frac 3 4 int_0^infty e^-7x/4 dx = frac 3 4 times frac 4 7 = frac 3 7 $$
This is not a very elegant way but at least it is doable. Looking forward to someone to post a better solution.
add a comment |Â
up vote
7
down vote
up vote
7
down vote
The lengths of the broken stick pieces $(Y_1, Y_2, Y_3, Y_4)$ are spacings of ordered uniform. The joint distribution is equivalent to
$$ left(frac X_1 sum_i=1^4 X_i,
frac X_2 sum_i=1^4 X_i,
frac X_3 sum_i=1^4 X_i,
frac X_4 sum_i=1^4 X_iright)$$
where $X_i$ are iid exponential random variables. If we ordered the above spacings, the distribution of $(Y_(1), Y_(2), Y_(3), Y_(4))$ is equivalent to
$$ left(frac X_1/4 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 + X_4 sum_i=1^4 X_iright)$$
Any $3$ of the $4$ pieces cannot form a triangle if and only if
$$ begincases
Y_(1) + Y_(2) < Y_(3) \
Y_(1) + Y_(2) < Y_(4) \
Y_(1) + Y_(3) < Y_(4) \
Y_(2) + Y_(3) < Y_(4)
endcases$$
Note that the second inequality is implied by the first, and the third inequality is implied by the fourth. So the probability of no triangle being formed is
$$ beginalign
&Pr Y_(1) + Y_(2) < Y_(3), Y_(2) + Y_(3) < Y_(4) \
=& PrBiggfrac X_1 4 + frac X_1 4 + frac X_2 3 <
frac X_1 4 + frac X_2 3 + frac X_3 2, \
& frac X_1 4 + frac X_2 3 + frac X_1 4 + frac X_2 3
+ frac X_3 2 <
frac X_1 4 + frac X_2 3 + frac X_3 2 + X_4Bigg \
=& PrX_1 < 2X_3, 3X_1 + 4X_2 < 12X_4 \
=& int_0^infty Pr2X_3 > xPr12X_4 - 4X_2 > 3xe^-xdx
endalign$$
Note that
$$ beginalign
&Pr12X_4 - 4X_2 > 3x \
=& int_0^inftyPr12X_4 - 4u > 3xe^-udu \
=& int_0^infty e^-(3x+4u)/12 e^-udu \
=& e^-x/4int_0^infty e^-4u/3du \
=& frac 3 4e^-x/4
endalign
$$
So the integral become
$$ int_0^infty e^-x/2frac 3 4 e^-x/4e^-xdx
= frac 3 4 int_0^infty e^-7x/4 dx = frac 3 4 times frac 4 7 = frac 3 7 $$
This is not a very elegant way but at least it is doable. Looking forward to someone to post a better solution.
The lengths of the broken stick pieces $(Y_1, Y_2, Y_3, Y_4)$ are spacings of ordered uniform. The joint distribution is equivalent to
$$ left(frac X_1 sum_i=1^4 X_i,
frac X_2 sum_i=1^4 X_i,
frac X_3 sum_i=1^4 X_i,
frac X_4 sum_i=1^4 X_iright)$$
where $X_i$ are iid exponential random variables. If we ordered the above spacings, the distribution of $(Y_(1), Y_(2), Y_(3), Y_(4))$ is equivalent to
$$ left(frac X_1/4 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 sum_i=1^4 X_i,
frac X_1/4 + X_2/3 + X_3/2 + X_4 sum_i=1^4 X_iright)$$
Any $3$ of the $4$ pieces cannot form a triangle if and only if
$$ begincases
Y_(1) + Y_(2) < Y_(3) \
Y_(1) + Y_(2) < Y_(4) \
Y_(1) + Y_(3) < Y_(4) \
Y_(2) + Y_(3) < Y_(4)
endcases$$
Note that the second inequality is implied by the first, and the third inequality is implied by the fourth. So the probability of no triangle being formed is
$$ beginalign
&Pr Y_(1) + Y_(2) < Y_(3), Y_(2) + Y_(3) < Y_(4) \
=& PrBiggfrac X_1 4 + frac X_1 4 + frac X_2 3 <
frac X_1 4 + frac X_2 3 + frac X_3 2, \
& frac X_1 4 + frac X_2 3 + frac X_1 4 + frac X_2 3
+ frac X_3 2 <
frac X_1 4 + frac X_2 3 + frac X_3 2 + X_4Bigg \
=& PrX_1 < 2X_3, 3X_1 + 4X_2 < 12X_4 \
=& int_0^infty Pr2X_3 > xPr12X_4 - 4X_2 > 3xe^-xdx
endalign$$
Note that
$$ beginalign
&Pr12X_4 - 4X_2 > 3x \
=& int_0^inftyPr12X_4 - 4u > 3xe^-udu \
=& int_0^infty e^-(3x+4u)/12 e^-udu \
=& e^-x/4int_0^infty e^-4u/3du \
=& frac 3 4e^-x/4
endalign
$$
So the integral become
$$ int_0^infty e^-x/2frac 3 4 e^-x/4e^-xdx
= frac 3 4 int_0^infty e^-7x/4 dx = frac 3 4 times frac 4 7 = frac 3 7 $$
This is not a very elegant way but at least it is doable. Looking forward to someone to post a better solution.
answered Jul 25 at 17:35
BGM
3,530148
3,530148
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%2f2862590%2fprobability-that-a-stick-randomly-broken-in-three-places-can-form-a-triangle%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