Probability that a stick randomly broken in two places can form a triangle
Randomly break a stick (or a piece of dry spaghetti, etc.) in two places, forming three pieces. The probability that these three pieces can form a triangle is $\frac14$ (coordinatize the stick form $0$ to $1$, call the breaking points $x$ and $y$, consider the unit square of the coordinate plane, shade the areas that satisfy the triangle inequality edit: see comments on the question, below, for a better explanation of this).
The other day in class*, my professor was demonstrating how to do a Monte Carlo simulation of this problem on a calculator and wrote a program that, for each trial did the following:
- Pick a random number $x$ between $0$ and $1$. This is the first side length.
- Pick a random number $y$ between $0$ and $1 - x$ (the remaning part of the stick). This is the second side length.
- The third side length is $1 - x - y$.
- Test if the three side lengths satisfy the triangle inequality (in all three permutations).
He ran around $1000$ trials and was getting $0.19$, which he said was probably just random-chance error off $0.25$, but every time the program was run, no matter who's calculator we used, the result was around $0.19$.
What's wrong with the simulation method? What is the theoretical answer to the problem actually being simulated?
(* the other day was more than $10$ years ago)
The three triangle inequalities are
\begin{align} x + y &> 1-x-y \\ x + (1-x-y) &> y \\ y + (1-x-y) &> x \\ \end{align}
Your problem is that in picking the smaller number first from a uniform distribution, it's going to end up being bigger than it would if you had just picked two random numbers and taken the smaller one. (You'll end up with an average value of $1/2$ for the smaller instead of $1/3$ like you actually want.) Now when you pick $y$ on $[0, 1-x]$, you're making it smaller than it should be (ending up with average value of $1/4$). To understand this unequal distribution, we can substitute $y (1-x)$ for $y$ in the original inequalities and we'll see the proper distribution.
(Note that the $y$-axis of the graph doesn't really go from $0$ to $1$; instead the top represents the line $y=1-x$. I'm showing it as a square because that's how the probabilities you were calculating were being generated.) Now the probability you're measuring is the area of the strangely-shaped region on the left, which is $$\int_0^{1/2}\frac1{2-2x}-\frac{2x-1}{2x-2}\,dx=\ln 2-\frac12\approx0.19314$$ I believe that's the answer you calculated.
FYI: This question was included in a Martin Gardner 'Mathematical Games' article for Scientific American some years ago. He showed that there were 2 ways of randomly choosing the 2 'break' points:
- choose two random numbers from 0 to 1, or
- choose one random number, break the stick at that point, then choose one of the two shortened sticks at random, and break it at a random point.
The two methods give different answers.