34
$\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)

$\endgroup$
10
  • 1
    $\begingroup$ See: mathoverflow.net/questions/2014/… $\endgroup$ Commented Jul 25, 2010 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$ Commented Jul 25, 2010 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$ Commented Jul 25, 2010 at 6:32
  • $\begingroup$ @Tom: The testing done in Step 4 was correct; the issue is elsewhere. $\endgroup$ Commented Jul 25, 2010 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$ Commented Jul 25, 2010 at 7:01

2 Answers 2

Reset to default
35
$\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.

$\endgroup$
6
  • 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$ Commented Jul 25, 2010 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$ Commented Jul 25, 2010 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$ Commented Jul 25, 2010 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$ Commented Jul 25, 2010 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$ Commented Oct 18, 2015 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.

$\endgroup$
4
  • 10
    $\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$ Commented Nov 5, 2011 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$ Commented Nov 6, 2011 at 3:47
  • 1
    $\begingroup$ In the first way, the two points are independent. While they are not in the second way. $\endgroup$ Commented Feb 4, 2020 at 8:59
  • $\begingroup$ In fact, in his original article Gardner gave an incorrect answer (1/6) for method 2; he corrected this in an addendum in The Colossal Book of Mathematics (p 278) using an argument similar to the accepted answer here, with a couple of other references: Sokolnikoff & Redheffer, Mathematics of Physics and Modern Engineering p 636; Graham, Ingenious Mathematical Problems and Methods problem 32. $\endgroup$ Commented Apr 14, 2024 at 23:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.