# Broken Stick Revisited.

Discussion in 'Probability' started by Patrick D. Rockwell, Aug 21, 2010.

1. ### Patrick D. RockwellGuest

Ok, the broken stick problem reads as follows.

If you break a stick into N pieces, what is the probabilty that the
largest piece will
be no more than 0.5 of the lengh of the original stick?

For N pieces, the general formula is

1-(N * (0.5^(N-1))).

So, if you break the stick into 3 pieces, the probability is going to
be 25%, and if
you break it into 4 pieces, it will be 50%.

But what if you ask for the probability of the largest piece being
less than D where
D can be greater than 0.5? I think that it would be the following.

1-(N * ((1-D)^(N-1)))

so that if you asked what the probability is for the largest piece
being 60% of the original
stick, if you broke it into 3 pieces, it would be

1-(3 * (0.4^2)) = 0.52 or 52%. Does everyone agree?

After I get a reply to this, I'm going to post my thoughts on how to
calculate
the probability that the largest piece is less than 50% of the
original stick. Thanks

Patrick D. Rockwell, Aug 21, 2010

2. ### Tim LittleGuest

That may be a little vague. I presume you mean to select N-1 points
independently and uniformly, restarting if any points coincide (with
probability 0), and break at all selected points?

Or another method: make a break at a uniformly random point. Select
one of the pieces at random and break it, repeat until the desired
number of pieces is reached.

Or something else again?

- Tim

Tim Little, Aug 21, 2010

3. ### Patrick D. RockwellGuest

Yes, if you break the stick into N pieces, you select the N-1 points
at which\
you break it randomly. In this case, is my formula correct?

Patrick D. Rockwell, Aug 21, 2010
4. ### Mike TerryGuest

I do. As only one piece could be larger than D, the calculation follows the
same pattern as for D=1/2.

Mike.

Mike Terry, Aug 21, 2010
5. ### Patrick D. RockwellGuest

Ok, now let's suppose that I break a stick into 3 pieces, and I want
to compute the probability
that the largest piece is less than or equal to 0.4 of the original
stick

The original stick problem where D=0.5 can be graphically ilistrated
by taking an equilateral triangle
and drawing inside of it another equilater triangle whose sides are
1/2 the length of the outer triangle.
This illistration is shown on this link.
https://www.math.duke.edu/education/webfeatsII/gdrive/Team D/project/brokenstick.htm

The inner triangle is rotated 180 degrees in relation to the outer
triangle and its area is
0.5 * 0.5 = 0.25 the area of the outer triange.

Now, if you have an equilateral triange whose area is 1 and whose
altitude is H, to solve for
D=0.5 I would draw 3 lines inside the triangle. The first one would be
parallel to the bottime line
and a distance of 0.4 X H from it. The other two lines would be
parallel to the other two lines of
the triangle and also be 0.4 * H from them forming a smaller triangle
inside of the larger triangle.

Since each line is 0.4 * H distance away from the lines that they are
parallel to, they are also
0.6 * H distance away from the vertices of the larger triangle. So,
the smaller triangle in the center
would be surrounded on each side by 3 triangles, each with an area of
0.6 * 0.6 = 0.36

But these triangles would intersect with each other forming 3 other
triangles whose sides are
equal to (0.6s +0.6s -1) =0.2s where s is the length of the outer
triangle. These triangles
formed by the intersection wold have an area of 0.2 * 0.2 = 0.04.

So the total probability of the largest piece being 0.6 times the
length of the original stick which
was broken into 3 pieces should be if I'm right

1 - 3*(1 - D)^2 + 3*(2D-1)^2

which is also

1 - (3 * 0.36) + (3 * 0.04) = 1 - 1.08 + 0.12 = 0.04. Does everyone
agree? Does everyone follow
my reasoning?

Patrick D. Rockwell, Aug 23, 2010
6. ### billGuest

1-(3*((1-D)^(3-1))) is < 0 for 1/3<=D<=1-1/Sqrt[3] ~= .42265

1-3*(1-D)^2+3*(2D-1)^2 is > 1 for 2/3<=D<=1

Both those probabilities worry me

bill, Aug 24, 2010
7. ### MacavityGuest

I have not seen this before. How are you sure of this? For e.g. for
N = 5, this suggests probability of about 69%, whereas a quick
simulation suggests 87.5%.

Macavity, Aug 29, 2010
8. ### MacavityGuest

For N = 3, I get (3D-1)^2 for D < 0.5. Explanation follows -
------------------------------------------------------------

Let 0 < d < 0.5, and let x, y denote the random break points. Then,
for the largest broken stick to have length less than d, we must have
simultaneously,
min(x,y) < d
1- max(x,y) < d
|x-y| < d

Additionally d > 1/N is implicit, otherwise the largest piece is
always bigger than d.

A simple way to get at this probability is to plot the region covered
by the inequalities on a unit square, and calculate the area within. I
am omitting an ascii diagram, which may prove more than I can do
legibly. This gives two equal right triangles, one of which is
defined by the equations
x < d, y > 1-d, x > y - d, or the coordinates
(d, 1-d), (d, 2d), (1-2d, 1-d)

Thus the probability = (3d-1)^2

For N > 3, geometry becomes more complicated and I am not sure if the
region can be integrated simply.

HTH.

Macavity, Aug 29, 2010
9. ### MacavityGuest

Its right, sorry my first simulation was too rough. For 0.5 <= d < 1,
we can have only at most one piece larger than d.
Now, prob (xi > r) = 1-r, for any breakpoint xi.
If min(xi) = Y (which determines the first segment)
prob(Y > r) = Prod{ prob(xi > r)} = (1-r)^(n-1)
prob (first segment > d)
= (1 - d)^(n-1)

Now the first segment need not be the largest, it can be in any of the
n segments, but these events are mutually exclusive. Hence,
prob (largest segment > d) = n(1- d)^(n-1)

So the probability that largest segment is d or less
= 1 - n (1-d)^(n-1), as stated.

Mac.

Macavity, Aug 29, 2010
10. ### Patrick D. RockwellGuest

Well, I forgot where I got my general formula, but I found it
somewhere on the web. It
might have been a .PDF file. If I find it again, I'll post it.

Anyway, what I'm looking for is a way to compute the probability that
the largest stick
is between 0.4 and (1/3) the length of the original stick. I'm pretty
of .04 is right. You have a triangle of area 1. You subtract 3 smaller
triangles of area 0.36 each.

So far, that's 1-1.08 = -.08. However, each of thise 3 lines made
intersections along the sides of the original
triangle. Two cuts, both a distance of 0.4s away from the vertices,
were s is the length of the sides of the\
original triange. So, inbetween those cuts is a length of .2s and so
the lines interect creating 3 smalller trianges
of 0.04 in area each.

By inclusion-excusion these areas have to be added into the previouse
amount, so you have

1-1.08+0.12=0.04.

If we all agree with this, I'd like to discuss the problem I'm having
with doing the same thing with
the tetrahedron.

Patrick D. Rockwell, Sep 2, 2010
11. ### Patrick D. RockwellGuest

For those of you who have asked, I got my formula from this
page.

http://www.cut-the-knot.org/triangle/geoprobability.shtml

Anyway, what I'm looking for is a way to compute the probability that
the largest stick
is between 0.4 and (1/3) the length of the original stick. I'm pretty
of .04 is right. You have a triangle of area 1. You subtract 3
smaller
triangles of area 0.36 each.

So far, that's 1-1.08 = -.08. However, each of thise 3 lines made
intersections along the sides of the original
triangle. Two cuts, both a distance of 0.4s away from the vertices,
were s is the length of the sides of the\
original triange. So, inbetween those cuts is a length of .2s and so
the lines interect creating 3 smalller trianges
of 0.04 in area each.

By inclusion-excusion these areas have to be added into the previouse
amount, so you have

1-1.08+0.12=0.04.

If we all agree with this, I'd like to discuss the problem I'm having
with doing the same thing with
the tetrahedron.

Patrick D. Rockwell, Sep 2, 2010
12. ### MacavityGuest

If you are looking at the case of 3 pieces, and th probability of
having the largest piece between 0.4 and 1/3 the total lenghth, you
could use the formula given in the earlier posts, viz. (3D-1)^2. The
answer is 3/4, NOT as small as the 0.04 you get.

HTH.

Macavity, Sep 5, 2010
13. ### NickGuest

If the stick has three pieces we know the largest is >= 1/3. So the
problem reduces to the largest piece being less than 0.4.

We know the chance of the largest piece being greater than 1/2 is 3/4.
So we already have an upper bound of 1/4.

So you seem to have made a mistake. 0.04 looks feasible.

Didn't you do a similar problem to this many years ago?

Nick, Sep 8, 2010
14. ### MacavityGuest

I was out for several weeks and missed this. I don't recall exactly
what went on with my last post - it looks very confusing to me in
retrospect, but your answer of 0.04 is certainly correct. This is in
fact the answer by the formula I mentioned, i.e.
(3D-1)^2 = (3 * 0.4 - 1)^2 = (1.2-1)^2 = (0.2)^2 = 0.04

Best, Mac.

Macavity, Oct 1, 2010
15. ### Old EarlGuest

Hi, all
I took a few moments to think about the three piece case, and realized
there
was a simple way to answer the questions about the length of the three
pieces.
A simple convolution shows the length of the shortedt piece has a
probability
distribution that is a straight line from 6 at zero to zero at 1/3.
The middle piece is also
a triangle, zero at zero, rising to 4 at length 1/3, and back to zero
at legnth 1/2
Finally, the longest piece is also a triangle which starts a zero at
1/3, rises to a maximum
of 3 at length 1/2 and back to zero a unity.

For sticks with more pieces, the convolutions become very complicated,
and
beyond my aging mind to show.

Earl

Old Earl, Oct 1, 2010
16. ### Patrick D. RockwellGuest

I wonder what's going on with Google Groups. I've found a solution to
this
problem, posted it twice, and it hasn't shown up yet.

Patrick D. Rockwell, Oct 8, 2010
17. ### Patrick D. RockwellGuest

Yes, I posted a similar thing years ago. I finally
figured out the answer that I wanted for any
value of N.

First of all, if you break the stick into 3 pieces,
the answer is 0.04 for d=0.4. The original intent of
my post was to solve this problem for any value of N
where N is the number of pieces that the stick in being
broken into.

If you have a triangle whose altitude H is 1 and
you draw 3 lines within it, each a distance of 0.4
from the side of the triangle to which they are parallel,
then they form a smaller triangle whose altitude is 0.2 H,
therefore it's area is 0.2*0.2=.04 of the original triangle.
The reason why is because the original triangle has its
center at H/3 or 1/3. It shares this center with the smaller
triangle and since the other triangle has its lines at a
distance of 0.4 from the lines of the larger one, so the
center is a distance of (0.4-1/3)/(1/3)=0.2 from each line
of the smaller one.

In trying to solve the broken stick problem for higher
dimensions, and larger values of N, I discovered this.

N as stated is the number of pieces that the stick is
being broken into. In this example, N=4. K is the
dimensionality of the simplex we are working with. For
this example, the simplex is a tetrahedron so, K=3
(K always equals N-1). For information on what a simplex
is, go to http://en.wikipedia.org/wiki/Simplex

So, if you break the stick into 4 pieces and want to know
the probability that the largest piece will be no more than
d of the length of the original stick, where 1/n<=d<1 then
there are 3 regions of interest.

(2/N)<=d<1
(1/k)<=d<(2/N)
(1/N)<=d<(1/k)

This problem can be modeled with two tetrahedrons, one inside
the other with its vertices pointing toward the faces of the
other. If my terminology is correct, one of these represents
all of the ways that the stick can be broken into 4 pieces
while the other represents all of the ways in which the stick
can be broken into 4 pieces so that the largest piece is say,
0.4 the size of the original stick. The first tetrahedron I call
the sample tetrahedron, and the second one I call the event
tetrahedron. For brevity's sake throughout this post I should
refer to the sample tetrahedron as tetrahedron A and the
event tetrahedron as tetrahedron B.

If you ask the question "What is the probability that the largest
piece is between 2/n and 1 times the length of the original stick"
then tetrahedron B is larger then tetrahedron A, but tetrahedron
A still has its 4 vertices poking outside the faces of tetrahedron
B. So you can solve that probability with

1-N*(1-d)^(N-1) where N=4. If d=0.51 then the answer is 1-4*0.49^3
=0.529404.

If d is between 1/N and 1/k then tetrahedron B has NONE of its
vertices poking out of the faces of tetrahedron A and so, you
just take its volume and that will be the answer. For example,

if you break a stick into 4 pieces, what is the probability that
the largest piece is no more than 0.3 of the original stick?

Both of these tetrahedra share the same center. The distance
between the center and one face of tetrahedron A is 1/N or 0.25.
The distance between the center and one face of tetrahedron B is
0.3-0.25 so the tetrahedron B has an altitude equal to (0.3-0.25)/0.25
= 0.2 of tetrahedron A, therefore 0.2^3 of its volume and the answer
is 0.008.

Now, if d falls into the range of (1/k)<=d<(2/N) then it gets just
a little bit more tricky. If I break a stick into 4 pieces, I want
to know the probability that the largest piece is no more than 0.4
of the original stick.

0.4 is between 1/3 and 2/4. Tetrahedron B is smaller than the
tetrahedron A, but its 4 vertices are sticking through its faces. We
want to know what the volume shared by both is in relation to
tetrahedron A.

First, lets determine their respective altitudes. (0.4-.25)/0.25=0.6
so tetrahedron B has 0.6 the altitude of the other, and 0.216 of
its volume. If you draw a line from each face to the vertex of
tetrahedron B, 2/3 of it's length is inside of tetrahedron A and 1/3
is outside so we can determine the proportion of tetrahedron B is
shared with tetrahedron A.

1-4*(1/3)^3=1-4/27=23/27

So 23/27 of tetrahedron B is shared with tetrahedron A but we want to
know want proportion of tetrahedron A this is. To find out we multiply
the above answer times 0.216 (the volume of tetrahedron B) and we get
0.184.

As I typed this I realized that you could just get the answer with

..216-4*(0.2^3)=0.216-4*0.008=0.184

Patrick D. Rockwell, Oct 8, 2010