Broken Stick Problem: Many Answers?

[MikeAThon]

This post is inspired by a comment from Nuzzle in “Glass Rod Problem”, http://forums.codeguru.com/showthrea...47#post2073747. Internet searches show that the problem is more often called the “Broken Stick Problem”, which is what I’ve called it here.

The basic problem: If a stick is broken randomly into three pieces, what is the probability that the three pieces can be arranged end-to-end to form a triangle?

My issue is that I get different answers depending on how I phrase the problem:

Problem Statement #1: break a stick into three pieces by randomly selecting two break points. What is the probability that the three pieces can be arranged end-to-end to form a triangle?

Answer to #1: 0.25, as verified by countless answers on the web, and by the attached Excel spreadsheet showing a Monte Carlo simulation. The spreadsheet uses the same basic logic as that given by Nuzzle in his above post.

Problem Statement #2: break a stick into two pieces and then randomly select one of the pieces. Break the selected piece again, to form a total of three pieces. What is the probability that the three pieces can be arranged end-to-end to form a triangle?

Answer to #2: 0.193147 which is equal to ln(2) - 0.5 (which is the integral of (1-x)/x from .5 to 1 -- don’t ask).

Huh? Problems #1 and #2 seem identical to me, but they give dramatically different answers. Why is that?

And to confuse matters even more ...

Problem Statement #3: break a stick into two pieces and then select one of the pieces, but not randomly. Instead, select a piece with probability proportional to length, so that the longer piece is selected more often than the shorter one. Break the selected piece again, to form a total of three pieces. What is the probability that the three pieces can be arranged end-to-end to form a triangle?

Answer to #3: 0.25.

Once again, the result is puzzling. Problems #1 and #3 seem completely different, yet they both yield the exact same answer. Why is that?

The attached Excel spreadsheet shows Monte Carlo simulations of all three statements of the problem. To determine whether a triangle can be formed, we use the triangle inequality, which (in one form) basically says that in a triangle, the longest side is smaller than the sum of the two shorter sides. In the spreadsheet, the length of the stick is taken as “1”, so with a little algebra, we can determine that a triangle can be formed so long as MAX(all three sides) < 0.5.

Can anyone explain the reasons for the above results?

Mike

Broken-Stick-Problem.zip

[superbonzo]

now, this is a common issue in naive probability; the problem is that many people think the expression "randomly choose from a set" has a meaning, whereas it has not, in general.

It's just that sometimes the "random" set is equipped with a notion of symmetry that enables you to define a symmetric probability measure, that in turn gives a meaning to the expression "uniform random distribution on" that set. For example, the translational symmetry of the real line translates into the uniform probability measure of a closed interval, the permutation group of a finite set generates the uniform probability measure on it ( aka the chance ), the permutation group of energy levels in a gas generates the Boltzmann distribution and so on ...

when there's no specified ( or implied or evident from the context ) notion of probability uniformity, then saying to "randomly [do something]" is just meaningless.

so, in order to answer the “Glass Rod Problem” you have to fix how that rod is broken, otherwise you'll get as many different answers as there are ways to break it; clearly, this also includes the possibility that different formulations give the same answer ( this is not suprising, considering that they will more or less all derive from the same geometrical properties, that of a closed real line interval ... ).

focusing on the case in question, one could speculate on the physical interpretation of the problem; now, supposing the rod is made of some brittle amorphous material like glass, the fracture dynamics essentially depends on the material defects; in turn, supposing them uniformly and isotropically distributed on the rod volume, you'll end up with a situation in between problem statement 1 or 2, depending on whether the impact stress is uniformly distributed on the sample or not, respectively. Hence, clearly, the actual probability will also depends on the probability distribution of the impact geometry ...

[superbonzo]

just to be more specific,

>> Huh? Problems #1 and #2 seem identical to me, but they give dramatically different answers. Why is that?
>> Once again, the result is puzzling. Problems #1 and #3 seem completely different, yet they both yield the exact same answer. Why is that?

as we said, the problem depends on specifing the 3-variate probability distribution of the lengths of the ordered broken parts, or equivalently of the fracture points ( or any other parametrization of the broken rod configuration ): let f1, f2 with 0<=f1<=f2<=1 be the fracture points on the rod, we are given a probability density p(f1,f2) defined on the triangle { 0<=f1<=f2<=1 }.

the answer to the problem simply equals the integral I of p over the intersection of { 0<=f1<=f2<=1 } and { max( f1, f2-f1, 1-f2 ) <= 1/2 }

the #1 problem statement has p(f1,f2) = 2 and I = 1/4

in the #2 problem statement you have a uniform random variable u1 in [0,1] ( break the rod ), a uniform random variable s in {0,1} ( select a piece ), a uniform random variable u2 in [0,1] ( take a fraction of the piece ); they're all indipendent, so, the fracture points are

f1 = (1-s)*u1 + s*u1*u2
f2 = (1-s)*(u1 + (1-u1)*u2) + s*u1 = u1 + (1-s)(1-u1)u2

and p(f1,f2) = (1/2) * 1/(1-f1) + (1/2) * 1/f2 with I = ln(2) - 1/2

as you can see the two probability densities are different so the two problems are not identical.

as far as the 3# problem statement is concerned, this time s is not indipendent: but we know the conditional probabilities P(s=1|u1) = 1 - P(s=0|u1) = u1. Hence the prob. density is

p(f1,f2) = (1-f1) * 1/(1-f1) + f2 * 1/f2 = 2

therefore problem #3 is identical to problem #1. The formula above also explains why it's identical: the conditional probability based on the length of the first piece is the exact amount needed to balance the correlation induced on the fracture points by the double breaking process in problem #2.

[nuzzle]

Can anyone explain the reasons for the above results?

To continue with the more informal reasoning I used in the other thread:

In #1 the two breaks are completely independent.

In #2 a dependency has snuck in. By selecting with equal probability which of the two pieces should have the second break you're actually favouring the shorter piece making a triangle more unlikely.

In #3 you correct the dependency in #2 by selecting the two pieces in relation to their lengths. The shorter piece is no longer favoured and the two breaks are again independent so #3 is the same as #1.

[nuzzle]

... and in addition there's the case #4. Instead of breaking a stick into three pieces it deals with the opposite scenario namely building a stick from tree pieces of random lengths. It was introduced by the OP in the thread he refers to.

In my view it's identical to case #1. The rod lengths will vary but it doesn't matter because the two breaks will be independent over the length of the rod.

This means the chance the pieces will form a triangle will be the same in cases #1, #3 and #4.