29
$\begingroup$

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:

  1. Pick a random number $x$ between $0$ and $1$. This is the first side length.
  2. Pick a random number $y$ between $0$ and $1 - x$ (the remaning part of the stick). This is the second side length.
  3. The third side length is $1 - x - y$.
  4. 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)

Improve this question
$\endgroup$
  • 1
    $\begingroup$ See: mathoverflow.net/questions/2014/… $\endgroup$ – BlueRaja - Danny Pflughoeft Jul 25 '10 at 6:17
  • $\begingroup$ It seems the problem with the simulation has to be in Step 4 - But I would have assumed a failure to account for duplicates would have caused inaccuracy to be higher than 1/4 rather than lower. $\endgroup$ – Tom Stephens Jul 25 '10 at 6:25
  • $\begingroup$ @BlueRaja: The question and its top few answers only address the original question, not the incorrect Monte Carlo simulation. The accepted answer was written by someone I knew a few years before I saw this problem. Ilya Nikokoshev's answer is essentially the same as my suggested solution to the original question. $\endgroup$ – Isaac Jul 25 '10 at 6:32
  • $\begingroup$ @Tom: The testing done in Step 4 was correct; the issue is elsewhere. $\endgroup$ – Isaac Jul 25 '10 at 6:35
  • 2
    $\begingroup$ @Ben: I explained that part poorly, in particular using x and y differently there. Without loss of generality, let x<y, so we're actually working with half of the unit square. The three side lengths are x, y-x, and 1-y, so the inequalities are different than those you wrote (because of the different use of x and y), but the region where a triangle can be formed is the triangle with vertices at the midpoints of the sides of the half-unit-square triangle that is our whole region, giving 1/4. $\endgroup$ – Isaac Jul 25 '10 at 7:01
29
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Nice. Your visualization (and the substitution of y(1-x) for y) is much nicer than the way that I'd solved the problem. $\endgroup$ – Isaac Jul 25 '10 at 6:40
  • 1
    $\begingroup$ Thanks! I was about to go to sleep but then I stumbled upon your question and the opportunity to solve it and figure out the mystery was just too great to pass up. :P $\endgroup$ – Sophie Alpert Jul 25 '10 at 6:42
  • $\begingroup$ It's a favorite problem of mine because it starts with a classic geometric probability problem and ends up in calculus and with a ln(2). $\endgroup$ – Isaac Jul 25 '10 at 6:43
  • 3
    $\begingroup$ It's probably obvious to most, but the correct way to simulate the problem is to generate two unequal random numbers in (0,1) and treat them as your cutting points. $\endgroup$ – BlueRaja - Danny Pflughoeft Jul 25 '10 at 7:19
  • 2
    $\begingroup$ @hlapointe If the first break gives a stick with length $x$, then the remaining length is $1-x$. Splitting that randomly is the same as multiplying by a random number $y$ between $0$ and $1$, so we get $y(1-x)$. $\endgroup$ – Sophie Alpert Oct 18 '15 at 20:31
11
$\begingroup$

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:

  1. choose two random numbers from 0 to 1, or
  2. 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.

Improve this answer
$\endgroup$
  • 8
    $\begingroup$ Could you include an explanation of what the different answers are, as well as a derivation if possible? As it stands, I think this seems more appropriate for the comments section, as it does not provide an answer to the question. $\endgroup$ – Zev Chonoles Nov 5 '11 at 1:16
  • $\begingroup$ Not everybody has access to SciAm, so it'd be neat if you could quote what Gardner wrote in his column. $\endgroup$ – J. M. isn't a mathematician Nov 6 '11 at 3:47
  • $\begingroup$ In the first way, the two points are independent. While they are not in the second way. $\endgroup$ – Tengerye Feb 4 '20 at 8:59

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.