Broken Stick Revisited.

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

  1. 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
    in advance for any repies. :)
     
    Patrick D. Rockwell, Aug 21, 2010
    #1
    1. Advertisements

  2. Patrick D. Rockwell

    Tim Little Guest

    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
    #2
    1. Advertisements

  3. 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
    #3
  4. Patrick D. Rockwell

    Mike Terry Guest

    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
    #4
  5. 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
    #5
  6. Patrick D. Rockwell

    bill Guest

    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
    #6
  7. Patrick D. Rockwell

    Macavity Guest

    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
    #7
  8. Patrick D. Rockwell

    Macavity Guest

    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
    #8
  9. Patrick D. Rockwell

    Macavity Guest

    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
    #9
  10. 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
    sure that my answer
    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
    #10
  11. 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
    sure that my answer
    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
  12. Patrick D. Rockwell

    Macavity Guest

    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
    #12
  13. Patrick D. Rockwell

    Nick Guest

    I don't understand your answer.

    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
    #13
  14. Patrick D. Rockwell

    Macavity Guest

    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
    #14
  15. Patrick D. Rockwell

    Old Earl Guest

    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
    #15
  16. 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
    #16
  17. 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
    #17
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.