Probability that a stick randomly broken in three places can form a triangle

Question

I like questions about geometric probability, and two of my favourite questions here on math.SE are
Probability that a stick randomly broken in two places can form a triangle and
Probability that a stick randomly broken in five places can form a tetrahedron.

I wondered about the probability that a stick randomly broken in three places can form a triangle. More generally, we can ask for the probability distribution of the number of triangles that can be formed from the four pieces. Since each triple of the pieces has probability $\frac14$ of forming a triangle, the expected number of triangles we can form is $\frac14\cdot4=1$, which is already a rather nice result.

I tried various ways of applying inclusion–exclusion, with or without first ordering the segments by size, but it all seemed too complicated and unenlightening, and I ended up writing a program to output all the inequalities in order to let qhull compute the volumes of the polytopes they define.

The result (confirmed by simulations) is:

\begin{array}{c|c|c} &\text{probability}&\text{probability}\\ \#\triangle&\text{(reduced)}&\text{(unreduced)}\\\hline 0&\frac37&\frac{45}{105}\\ 1&\frac{11}{35}&\frac{33}{105}\\ 2&\frac{16}{105}&\frac{16}{105}\\ 3&\frac4{105}&\frac4{105}\\ 4&\frac1{15}&\frac7{105} \end{array}

You can check that the expected number of triangles comes out as $1$.

While the overall distribution is somewhat complicated, the probabilities that we can form
all triangles ($\frac1{15}$), any triangle ($\frac47$) and no triangles ($\frac37$) come out as nice low fractions, so I thought that maybe there's hope to find an elegant way to compute (one of) them after all. Do you see one? (The three places where the stick is broken are independently uniformly chosen along its length.)

Answer 1

The lengths of the broken stick pieces $(Y_1, Y_2, Y_3, Y_4)$ are spacings of ordered uniform. The joint distribution is equivalent to $$ \left(\frac {X_1} {\sum_{i=1}^4 X_i}, \frac {X_2} {\sum_{i=1}^4 X_i}, \frac {X_3} {\sum_{i=1}^4 X_i}, \frac {X_4} {\sum_{i=1}^4 X_i}\right)$$ where $X_i$ are iid exponential random variables. If we ordered the above spacings, the distribution of $(Y_{(1)}, Y_{(2)}, Y_{(3)}, Y_{(4)})$ is equivalent to

$$ \left(\frac {X_1/4} {\sum_{i=1}^4 X_i}, \frac {X_1/4 + X_2/3} {\sum_{i=1}^4 X_i}, \frac {X_1/4 + X_2/3 + X_3/2 } {\sum_{i=1}^4 X_i}, \frac {X_1/4 + X_2/3 + X_3/2 + X_4} {\sum_{i=1}^4 X_i}\right)$$

Any $3$ of the $4$ pieces cannot form a triangle if and only if $$ \begin{cases} Y_{(1)} + Y_{(2)} < Y_{(3)} \\ Y_{(1)} + Y_{(2)} < Y_{(4)} \\ Y_{(1)} + Y_{(3)} < Y_{(4)} \\ Y_{(2)} + Y_{(3)} < Y_{(4)} \end{cases}$$ Note that the second inequality is implied by the first, and the third inequality is implied by the fourth. So the probability of no triangle being formed is $$ \begin{align} &\Pr\{ Y_{(1)} + Y_{(2)} < Y_{(3)}, Y_{(2)} + Y_{(3)} < Y_{(4)}\} \\ =& \Pr\Bigg\{\frac {X_1} {4} + \frac {X_1} {4} + \frac {X_2} {3} < \frac {X_1} {4} + \frac {X_2} {3} + \frac {X_3} {2}, \\ & \frac {X_1} {4} + \frac {X_2} {3} + \frac {X_1} {4} + \frac {X_2} {3} + \frac {X_3} {2} < \frac {X_1} {4} + \frac {X_2} {3} + \frac {X_3} {2} + X_4\Bigg\} \\ =& \Pr\{X_1 < 2X_3, 3X_1 + 4X_2 < 12X_4\} \\ =& \int_0^{\infty} \Pr\{2X_3 > x\}\Pr\{12X_4 - 4X_2 > 3x\}e^{-x}dx \end{align}$$

Note that $$ \begin{align} &\Pr\{12X_4 - 4X_2 > 3x\} \\ =& \int_0^{\infty}\Pr\{12X_4 - 4u > 3x\}e^{-u}du \\ =& \int_0^{\infty} e^{-(3x+4u)/12} e^{-u}du \\ =& e^{-x/4}\int_0^{\infty} e^{-4u/3}du \\ =& \frac {3} {4}e^{-x/4} \end{align} $$

So the integral become $$ \int_0^{\infty} e^{-x/2}\frac {3} {4} e^{-x/4}e^{-x}dx = \frac {3} {4} \int_0^{\infty} e^{-7x/4} dx = \frac {3} {4} \times \frac {4} {7} = \frac {3} {7} $$

This is not a very elegant way but at least it is doable. Looking forward to someone to post a better solution.

Answer 2

While mulling over the excellent answer by @BGM, I thought of a way to adapt it to the "all triangles" case without calculus. However, I'm unsure about a Lemma I used - can someone please check it? Thanks!

---

First of all, let $X_i, Y_{(j)}$ etc be defined as in BGM's answer. All four triangles can be formed iff

$$Y_{(1)} + Y_{(2)} > Y_{(4)}$$

because the above implies the other three triangle inequalities. Using the technique of BGM, the above simplifies to

$${X_1 \over 4} > {X_3 \over 2} + X_4$$

At this point, I discovered an interesting little lemma that I didn't know before...

Lemma: Let $A, B, C$ be independent exponential variables, of arbitrary rates (not necessarily equal). Then $P(A > B + C) = P(A > B) P(A > C)$.

Informal Proof: Since $A, B, C$ are all non-negative, $A > B + C \implies A > B$, so:

$$P(A > B + C) = P(A > B + C \mid A > B) P(A > B)$$

Now informally, conditioned on $A> B$, and since $A$ is memoryless, the quantity $D = A-B$ is just distributed like the original $A$. So $P(D > C \mid A > B) = P(A > C). \square$

Question: Is my argument above valid? I never knew this equation before.

Anyway, assuming the lemma is valid, then the proof is immediate:

$$P({X_1 \over 4} > {X_3 \over 2} + X_4) = P({X_1 \over 4} > {X_3 \over 2}) P({X_1 \over 4} > X_4) = {2 \over 2+4} \times {1 \over 1+4} = {1 \over 15}$$