1
$\begingroup$

I was solving the following probability problem yesterday:

Given a rod of length L, find the number of ways to cut the rod into thre parts s.t. these parts form a triangle.

Now, it's a standard problem and multiple solutions can be found online. Added a few links in solutions (Feel free to go and explore). Obviously, all of them arrive at the same conclusion that the required probability is 1 / 4 = 0.25.

Then, I decided to conduct an experiment and write a python script to simulate the experiment. I perform the experiment 10^7 times (takes a while to calculate the result) but always comes up with ~0.19 no matter what I choose number of experiments and length of rod to be.

I would like to find out why theoretical and practical result doesn't match?

Here is my python script:

import numpy as np

def rod_cut(L):
    x = np.random.uniform(0, L)
    y = np.random.uniform(0, L - x)
    z = L - (x + y)
    return (x, y, z)


def is_triangle(datapoint):
    a, b, c = datapoint
    return a + b >= c and \
           b + c >= a and \
           a + c >= b

def perform_experiment():
    N = 10000000
    L = 1.0
    datapoints = [rod_cut(L) for _ in range(N)]
    successes = sum([is_triangle(datapoint) for datapoint in datapoints])
    print("Probability of cutting rod s.t it makes a triangle = ", successes / N)

perform_experiment()

Note: I tried making a frequency distribution graph of the random numbers that numpy generates and it comes out to be uniform. So I trust that numpy.random.uniform is generating a uniform distribution of random numbers as expected.

Solution based on algebraic inequalities:
1. (From quora) [https://www.quora.com/A-rod-is-broken-into-three-parts-what-is-the-probability-that-the-three-parts-can-be-arranged-to-form-a-triangle]

$\endgroup$
  • 1
    $\begingroup$ This looks like a different problem. Your $y$ is not chosen uniformly on $[0,1]$. $\endgroup$ – lulu May 11 '18 at 12:32
  • $\begingroup$ @lulu, the way I cut the rod is this: x is the length of first cut. (can be between 0 to L) y is the length of second cut. (can be between 0 to L - x because x is already taken from the rod) z is rest of the rod (which is L - (x + y)) I think it covers all the possible cases. $\endgroup$ – Deepak gupta May 11 '18 at 12:37
  • $\begingroup$ Ok, but then you require that the second cut be to the right of $x$. The original problem has $x,y$ both uniform on $[0,1]$. If instead of "first" you require $x$ to be the left most cut, then $x$ is no longer uniform. (knowing that $x$ is leftmost is evidence for the fact that $x$ is small). $\endgroup$ – lulu May 11 '18 at 12:39
  • $\begingroup$ x and y aren't the cut-positions on the rod but the length of the rod because I later use them as length of sides of triangle formed. $\endgroup$ – Deepak gupta May 11 '18 at 12:40
  • 1
    $\begingroup$ here is a link which discusses some standard variants of the stick breaking problem. Yours is discussed in Problem $3$ and the theoretical answer is shown to be $\ln(2)-\frac 12\approx 0.193147181$ which, of course, is in line with your simulation. $\endgroup$ – lulu May 11 '18 at 13:54
0
$\begingroup$

There are 2 cases:-

Case -I : you select 2 random points (X,Y) and then break the sticks at these two joints.

Then your r.v's: $X\sim Uni(0,l) \qquad Y\sim Uni(0,l) , \text{ are independent}$

Now you have got 3 pieces, $X,Y,L-(X+Y)$

If you remember there is a basic property of a triangle Sum of two sides should be more than the third side.

SO you need work these 3 subcases : $$ P(X+Y \ge l-(X+Y));\quad P(X+ l-(X+Y)\ge Y) ;\quad P(l-(X+Y)+Y \ge X)$$

$\Rrightarrow P(X+Y \ge l-(X+Y))= P(2X+2Y \ge l)=0.5 $

$\Rrightarrow P( P(X+ l-(X+Y)\ge Y))= P(l\ge 2Y)=\frac{1}{2} $

$\Rrightarrow P( P(Y+ l-(X+Y)\ge X))= P(l\ge 2X)=\frac{1}{2} $

and similarly i hope that you can do the rest of the problem.The answer shall be the product of the subcases.

Case-II: You select a random point X on the stick and cut out the piece of length X . Then you take another random point Y on the cut out piece of X and break it at that point.

Then your random variables are :$X\sim Uni(0,l) \quad Y|X=x \sim Uni(0,x)$

Then the the length of the pieces you get:$Y,X-Y,L-X$

Work it out in the similar way as mentioned above and you will get the results.

Hope this helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.