19 replies to this topic

[CaptainEd]

Thank you, bonanova. I've been feeling dumb and behaving lazy. You've prodded me, so I have an answer for the first of the two.

Spoiler for Two random breaks

OK, I see how to analyze "two random breaks", with the following meaning:
pick two random numbers between 0 and 1, call them p and q.
If the stick were broken at those two points, it would become three sticks (assuming p=q is unlikely) of lengths
* min(p,q)
* 1-max(p,q)
* max(p,q) - min(p,q)
For what range of p and q would these three lengths satisfy the requirement that the largest is less than the sum of the smaller two?
The answer is two regions:
1) (q < 0.5) AND (p > 0.5) AND (q > (p - 0.5))
2) (p < 0.5) AND (q > 0.5) AND (p > (q - 0.5))
Their area totals 1/4 of the area from (0,0) to (1,1), so I claim the probability of two random breaks resulting in lengths that can make a triangle is 0.25.
I assume that it is NOT the same as that formed by one random break, followed by a random choice of sides and a random break confined to that side.
But I haven't analyzed that yet.

[bonanova]

Thank you, bonanova. I've been feeling dumb and behaving lazy. You've prodded me, so I have an answer for the first of the two.

Spoiler for Two random breaks

OK, I see how to analyze "two random breaks", with the following meaning:
pick two random numbers between 0 and 1, call them p and q.
If the stick were broken at those two points, it would become three sticks (assuming p=q is unlikely) of lengths
* min(p,q)
* 1-max(p,q)
* max(p,q) - min(p,q)
For what range of p and q would these three lengths satisfy the requirement that the largest is less than the sum of the smaller two?
The answer is two regions:
1) (q < 0.5) AND (p > 0.5) AND (q > (p - 0.5))
2) (p < 0.5) AND (q > 0.5) AND (p > (q - 0.5))
Their area totals 1/4 of the area from (0,0) to (1,1), so I claim the probability of two random breaks resulting in lengths that can make a triangle is 0.25.
I assume that it is NOT the same as that formed by one random break, followed by a random choice of sides and a random break confined to that side.
But I haven't analyzed that yet.

Good one. Yes and yes.
Your approach should serve well for the second case as well.

[CaptainEd]

Spoiler for Step 2 of my catching up to Bonanova's carrot--breaking the stick and then breaking it again

If we break the stick and then choose either piece for a further break: let's call the original break point P. and the length of the other piece is (1-P).
We can break the short end or the long end.
(a) If we break the short end (that is, if p < 0.5) , we are guaranteed to have no triangle, as the long end would be larger than the sum of the other two sides.
So half the time, we will certainly have NO triangle.
(b) If we break the long end (that is, if p > 0.5), we will have a triangle exactly when neither piece is as long as half the original length.

Let's grab a random number Q from 0 to P,
So the left end of the long end is of length Q, the right end of the long end is P-Q.
To compute this, for each P between 1/2 and 1, we need to evaluate
(i) the range of possible Q
(ii) in what fraction of that range is neither piece as long as 1/2.

Q ranges from 0 to P the acceptable range is (P - 1/2 , 1/2), because
If Q is less than P-1/2, then P-Q > 1/2, so no triangle.
Similarly, if Q is greater than 1/2, then no triangle.

More concretely,
when P is nearly 1 (let's say 1 - eps), then this range is (1 - eps - 1/2, 1/2) = (1/2 - eps, 1/2).
In other words, Q ranges from 0 to 1-eps, but the acceptable range is of length eps.
On the other hand, when P is nearly 1/2 (let's say 1/2 + eps), then this range is (1/2 + eps - 1/2, 1/2) = (eps, 1/2).
In other words, Q ranges from 0 to 1/2 + eps, and the acceptable range is of length 1/2 - eps)

So as P goes from 1/2 to 1, the area of Q forms a trapezoid with altitudes ranging from 1/2 to 1 => average altitude of 3/4.
And the acceptable range (the range where the sides could form a triangle) ranges from 0 to 1/2 => average altitude of 1/4.
So the probability of making a triangle by breaking the long end is (1/4) / (3/4) = 1/3.
And, since we only break the long end half the time, the probability of making a triangle is 1/6.

So now I have to figure out the OP--randomly break the stick, then randomly break each piece. Discard one piece. Next time...

[bonanova]

Spoiler for Step 2 of my catching up to Bonanova's carrot--breaking the stick and then breaking it again

If we break the stick and then choose either piece for a further break: let's call the original break point P. and the length of the other piece is (1-P).
We can break the short end or the long end.
(a) If we break the short end (that is, if p < 0.5) , we are guaranteed to have no triangle, as the long end would be larger than the sum of the other two sides.
So half the time, we will certainly have NO triangle.
(b) If we break the long end (that is, if p > 0.5), we will have a triangle exactly when neither piece is as long as half the original length.

Let's grab a random number Q from 0 to P,
So the left end of the long end is of length Q, the right end of the long end is P-Q.
To compute this, for each P between 1/2 and 1, we need to evaluate
(i) the range of possible Q
(ii) in what fraction of that range is neither piece as long as 1/2.

Q ranges from 0 to P the acceptable range is (P - 1/2 , 1/2), because
If Q is less than P-1/2, then P-Q > 1/2, so no triangle.
Similarly, if Q is greater than 1/2, then no triangle.

More concretely,
when P is nearly 1 (let's say 1 - eps), then this range is (1 - eps - 1/2, 1/2) = (1/2 - eps, 1/2).
In other words, Q ranges from 0 to 1-eps, but the acceptable range is of length eps.
On the other hand, when P is nearly 1/2 (let's say 1/2 + eps), then this range is (1/2 + eps - 1/2, 1/2) = (eps, 1/2).
In other words, Q ranges from 0 to 1/2 + eps, and the acceptable range is of length 1/2 - eps)

So as P goes from 1/2 to 1, the area of Q forms a trapezoid with altitudes ranging from 1/2 to 1 => average altitude of 3/4.
And the acceptable range (the range where the sides could form a triangle) ranges from 0 to 1/2 => average altitude of 1/4.
So the probability of making a triangle by breaking the long end is (1/4) / (3/4) = 1/3.
And, since we only break the long end half the time, the probability of making a triangle is 1/6.

So now I have to figure out the OP--randomly break the stick, then randomly break each piece. Discard one piece. Next time...

You are in the right ball park, but a little low.
Ask where the longer stick must be broken given the first break was at f < .5.
Then average the probability of that second break for 0 < f < .5.

[brifri238]

I have run two simulations, each over 1,000,000 runs.

The first simulates the scenario where one stick is randomly broken and then one of the resulting two sticks is randomly choosen and then randomly broken.

The second scenario simulates where the stick is randomly broken and each of the two resulting sticks are then randomly broken and then one of the resulting four sticks is randomly choosen and thrown away:

Scenario 1: Probability of Sucessful Triangle: 0.19378

Scenario 2: Probability of Sucessful Triangle: 0.19371


Assuming my simulations are correct, it practically makes no difference which scenario is choosen

Edited by brifri238, 09 November 2012 - 05:33 PM.

[CaptainEd]

You are in the right ball park, but a little low.
Ask where the longer stick must be broken given the first break was at f < .5.
Then average the probability of that second break for 0 < f < .5.

Some day, when I look back on this, I'll laugh. But right now, my ability to do word problems is not very satisfying. I believe I did exactly what you advised, I clearly graphed some points randomly generated according to this approach, I saw a graph in which the probability is exactly 1/3, yet my Excel spreadsheet continues to show numbers larger than 1/3, as you said (and presumably, as brifri238 says). Thanks in advance for my education in mathematical thinking!

[CaptainEd]

Spoiler for Break once, pick a piece, break again

I think I've calculated the second case properly, though it would be gilding the lily to call my calculus proficiency merely "rusty".
Rather than randomly generating a place to break the stick, I'll integrate over all break points.
However, we don't want to break the short stick, as it will never lead to a triangle.
So, let p be the length of the long half of the stick. That is, 1/2 < p < 1.
Then break p at q.

The possible range of q is 0 < q < p, but the admissible range of q is (p-1/2) < q < 1/2, because
if q > 1/2, then q is too long, and
if q < p-1/2, then p-q is too long.
So the admissible fraction is of length (1/2 - (p-1/2)) / p.

So we want integral (1/2 - (p - 1/2))/p from p = 1/2 to 1.
= integral (1-p)/p from p = 1/2 to 1.
= integral (1/p) - integral (1), from p=1/2 to 1
= [ integral (1/p) from p=1/2 to 1 ] - 1/2
= ln(1) - ln(1/2) - 1/2
= 0 +.69315 -.5 = .19315

I sort of expected it to be twice this, so I may have either missed a factor of two, or done something totally irrelevant. Please let me know.

But .19315 fits in with my crude probabilistic simulations, and is close (but not close enough, I fear) to brifri238's results.

Edited by CaptainEd, 20 November 2012 - 05:40 PM.

[bonanova]

You got it.
Kudos for hanging in with it.

The missing factor 2 comes when you recognize the integration range is 1/2.
You have to divide by that to get the average over that range.

I didn't notice till now that grifri238's result is a little high..

I got:

After a first break at point a <.5. the second break must be in the central region of width a within the larger [1-a] piece. If you average a/(1-a) over all values of a from 0 to .5 you get
-1 + 2log2 = -1 + 1.386294361... = 0.386294361... Half that is 0.1931471806...

I have not analyzed the variant mentioned in OP.
I'm waiting for the 'aha!' Moment that reduces it to this case.. http://brainden.com/..._DIR#/smile.png

[CaptainEd]

Spoiler for Observation about OP--Break once, break both pieces, discard one

The conditions for trianglehood are that

for sticks of lengths a, b, and c, a triangle results if

(a < b+c) AND (b < a+c) AND (c < a+b)

but you can rework that into

(2a < a+b+c) AND (2b < a+b+c) AND (2c < a+b+c)

let s be the sum a+b+c, then

(a < s/2) AND (b < s/2) AND (c < s/2)

 

In the case at hand, we have four sticks:

First, we pick p between 0 and 1.
Then, we pick q between 0 and p.
FInally, we pick r between 0 and (1-p).

Thus we have four sticks, of lengths q, (p-q), r, (1-p-r).

 

When we discard a stick of length x, the sum "s" is (1-x), so the triangle conditions become:

Discard       Condition (each remaining stick must satisfy)
   q          < (1-q)/2
  p-q         < (1-(p-q))/2
   r          < (1-r)/2
 1-p-r        < (p+r)/2

As Bonanova said, I don't get the "Aha!" that causes this to look like the case of "Break once, break again."

[bonanova]

Spoiler for Observation about OP--Break once, break both pieces, discard one

The conditions for trianglehood are thatfor sticks of lengths a, b, and c, a triangle results if

(a < b+c) AND (b < a+c) AND (c < a+b)

but you can rework that into

(2a < a+b+c) AND (2b < a+b+c) AND (2c < a+b+c)

let s be the sum a+b+c, then

(a < s/2) AND (b < s/2) AND (c < s/2)

 

In the case at hand, we have four sticks:First, we pick p between 0 and 1.Then, we pick q between 0 and p.FInally, we pick r between 0 and (1-p).Thus we have four sticks, of lengths q, (p-q), r, (1-p-r). When we discard a stick of length x, the sum "s" is (1-x), so the triangle conditions become:Discard       Condition (each remaining stick must satisfy)   q          < (1-q)/2  p-q         < (1-(p-q))/2   r          < (1-r)/2 1-p-r        < (p+r)/2As Bonanova said, I don't get the "Aha!" that causes this to look like the case of "Break once, break again."

Very nice Cap'n!