Randomly Breaking a Stick to Form a Triangle

Here’s a cute problem in probability I learned in Joe Blitzstein’s Stat 110 class. Suppose you have a stick of unit length. You choose two points A,B on the stick at random and then break the stick at those two points, resulting in three pieces whose lengths add up to one. What is the probability that you can form a triangle with the three pieces?

We first need to clarify what it means to choose the points A and B randomly. Let A,B be independent \text{Unif}(0,1) random variables on a probability space (\Omega,\mathcal{F},\mathbb{P}). So the lengths of the three pieces created after breaking the stick are

\displaystyle L_{1}:=\min\left\{A,B\right\},\indent L_{2}:=\left|B-A\right|,\indent L_{3}:=1-\max\left\{A,B\right\}

We know that a necessary condition for L_{1},L_{2},L_{3} to form a triangle is that the length of any two sides is greater than the length of the remaining side–this is the well-known triangle inequality. Mathematically, for any permutation \sigma\in S_{3},

\displaystyle L_{\sigma(1)}+L_{\sigma(2)}>L_{\sigma(3)}

Is this also a sufficient condition? The answer is yes, and it follows quickly from the law of cosines. Fix one vertex at the origin and another vertex at (L_{1},0). Where do place the third vertex P=(P_{1},P_{2}), so that

\displaystyle P_{1}^{2}+P_{2}^{2}=L_{2}^{2} and \displaystyle (P_{1}-L_{1})^{2}+P_{2}^{2}=L_{3}^{2}

Well, by the law of cosines, we can choose \theta\in(0,\pi) so that

\displaystyle (L_{1}-L_{2})^{2}<L_{3}^{2}=L_{1}^{2}+L_{2}^{2}-2 L_{1} L_{2}\cos(\theta)<(L_{1}+L_{2})^{2}

We define P=(L_{2}\cos\theta,L_{2}\sin\theta).

Since L_{1}+L_{2}+L_{3}=1, we see that these lengths do form the sides of a triangle if and only if

\displaystyle\max\left\{L_{1},L_{2},L_{3}\right\}<\frac{1}{2}

We consider two cases. First, suppose that 0<A<\frac{1}{2}. Then L_{1},L_{2},L_{3} are the lengths of the sides of a triangle if and only if \frac{1}{2}<B<A+\frac{1}{2}. Since A,B are independent, conditioning on A, we obtain

\begin{array}{lcl}\displaystyle\mathbb{P}\left(0<A<\frac{1}{2},\frac{1}{2}<B<A+\frac{1}{2}\right)&=&\displaystyle\int_{0}^{\frac{1}{2}}\mathbb{P}\left(\frac{1}{2}<B<A+\frac{1}{2}\vert A=x\right)dx\\[.7 em]&=&\displaystyle\int_{0}^{\frac{1}{2}}\mathbb{P}\left(\frac{1}{2}<B<\frac{1}{2}+x\right)dx\\[.7 em]&=&\displaystyle\int_{0}^{\frac{1}{2}}xdx\\[.7 em]&=&\displaystyle\frac{1}{8}\end{array}

If \frac{1}{2}<A<1, then L_{1},L_{2},L_{3} are the lengths of the sides of a triangle if and only if A-\frac{1}{2}<B<\frac{1}{2}. By symmetry, we also have that

\displaystyle\mathbb{P}\left(\frac{1}{2}<A<1,A-\frac{1}{2}<B<\frac{1}{2}\right)=\frac{1}{8}

Since a continuous random variable takes values in a countable set with probability zero, we conclude that the probability a triangle can be formed is \frac{1}{4}.

Now suppose that you don’t have a ruler. Moreover, your sight isn’t good enough to eyeball A to be \frac{1}{3} units distance from one endpoint and B to be \frac{1}{3} units distance from the other endpoint, so that you can’t form an equilateral triangle. You want to form a triangle, so you decide to keep breaking sticks, as described above, until you can form a triangle. On average, how many sticks must you go through before achieving success?

The answer to this question is an exercise in the geometric probability distribution. Recall that a random variable N is said to be geometrically distributed with parameter p\in(0,1) if

\displaystyle\mathbb{P}(N=k)=(1-p)^{k-1}p,\indent\forall k\in\mathbb{N}

and we write N\sim\text{Geom}(p). The expectation of N can be found by evaluating an infinite series. Since a uniformly convergent series can be differentiated term by term, we see that

\begin{array}{lcl}\displaystyle\mathbb{E}[N]=\sum_{k=1}^{\infty}k\mathbb{P}(N=k)&=&\displaystyle\sum_{k=1}^{\infty}k(1-p)^{k-1}p\\[.9 em]&=&\displaystyle(-p)\frac{d}{dp}\sum_{k=1}^{\infty}(1-p)^{k}\\[.9 em]&=&\displaystyle(-p)\frac{d}{dp}\left[\frac{1-p}{p}\right]\\[.7 em]&=&\displaystyle\frac{1}{p}\end{array}

If N denotes the number of sticks you break until a triangle can be formed and p=\frac{1}{4}, then we see that, on average, you have to break four sticks until a triangle can be formed with the three pieces.

Advertisements
This entry was posted in Problem Solving and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s