Probability – Breaking a Stick at Two Random Points and Longest Piece Probability

geometric-probabilitygeometryintuitionprobability

Choose two independent uniformly random points on a stick, and break the stick at that those points. The probability that the longest piece is at least twice as long as each of the other pieces is $1/2$.

My proof below is fairly technical. Given the simplicity of the final answer, I am looking for a more intuitive explanation that does not involve so much calculation, possibly based on symmetry.

(Here is another question of mine about a breaking a stick at random points, that has an intuitive explanation. And here is one with a simple answer but perhaps no intuitive explanation.)


My non-intuitive proof:

Assume the stick has length $1$. Hold the stick horizontally.

$x=$ first chosen point's distance from left end.
$y=$ second chosen point's distance from left end.

In the graph, the blue regions contain combinations that meet the condition in the question. The red region contains combinations that do not meet the condition. The regions can be reflected across the diagonal, by symmetry.

enter image description here

I worked out the lines by considering $x$-values one by one, starting from $x=0$ and going up in small increments. Critical points emerged: $(0,\frac13),(0,\frac23),(\frac14,\frac12),(\frac14,\frac34),(\frac13,\frac13),(\frac13,1),(\frac12,\frac34),(\frac23,\frac23),(\frac23,1)$.

The areas of the blue and red regions are equal, so the probability that the condition is met is $1/2$.


Related fact: The probability that the longest piece is at least twice as long as the shortest piece is exactly $90\text{%}$ (an amusing geometrical probability).

Best Answer

Nice question!

Here is quite a short method, making use of some basic properties of exponential random variables. It generalises nicely to other related questions (including the one mentioned at the bottom of the post).

The following fact is very useful. Let $S_1, S_2, \dots, S_n$ be the lengths (from left to right) when a unit stick is broken at $n-1$ independent and uniform points. That is, $(S_1, S_2, \dots ,S_n)$ is uniformly distributed on the simplex $\{(s_1, s_2, \dots, s_n)\in[0,1]^n: s_1+\dots+s_n=1\}$.

Then $S_1, S_2, \dots, S_n$ has the same distribution as $$ \frac{X_1}{X_1+X_2+\dots+X_n}, \frac{X_2}{X_1+X_2+\dots+X_n}, \dots, \frac{X_n}{X_1+X_2+\dots+X_n}, $$ where $X_1, X_2, \dots, X_n$ are i.i.d. uniform Exp($1$) random variables. See for example Chapter V.2 of Luc Devroye's book. $\newcommand{\Exp}{{\operatorname{Exp}}}$

Since we only care about ratios, we can ignore the denominators above. Let's take the original case $n=3$ for the moment. The question of whether one of $S_1, S_2, S_3$ is more than twice as big as each of the others becomes:

What is the probability that one of $X_1, X_2, X_3$ is more than twice as big as each of the others, where $X_1, X_2, X_3$ are i.i.d. $\Exp(1)$ random variables.

Rewrite $X_1, X_2, X_3$ in increasing order as $X_{(1)}\leq X_{(2)}\leq X_{(3)}$. These order statistics for an i.i.d. exponential sample have a very nice structure. The minimum of $n$ i.i.d. $\Exp(1)$ random variables has $\Exp(n)$ distribution. Applying this repeatedly, along with the memoryless property, we get that $(X_{(1)}, X_{(2)}-X_{(1)}, X_{(3)}-X_{(2)})=(E_3, E_2, E_1)$, where $E_3\sim\Exp(3)$, $E_2\sim\Exp(2)$, $E_1\sim\Exp(1)$, and $E_3, E_2, E_1$ are independent.

Rewriting, $(X_{(1)}, X_{(2)}, X_{(3)})=(E_3, E_2+E_3, E_1+E_2+E_3)$.

We want the probability that $X_{(3)}> 2 X_{(2)}$. This is the event $E_1>E_2+E_3$.

So finally we can rewrite the question as:

What is the probability that $E_1>E_2+E_3$, where $E_1, E_2, E_3$ are independent with $E_i\sim\Exp(i)$?

Now we get to calculate, applying the memoryless property yet again, along with the fact that if $Y\sim\Exp(\lambda)$ and $Z\sim\Exp(\mu)$, then $P(Y<Z)=\lambda/(\lambda+\mu)$: $$\begin{align} P(X_{(3)}>2X_{(2)})&= P(E_1>E_2+E_3) \\ &=P(E_1>E_3)P(E_1>E_2+E_3|E_1>E_3)\\ &=P(E_1>E_3)P(E_1>E_2)\\ &=\frac{3}{4}\times\frac{2}{3}\\ &=\frac{1}{2}, \end{align}$$ giving the desired answer!


Now for some generalisations. Using the same method, the probability that the largest of $n$ pieces is more than twice as large as each of the others is $$ \begin{align*} P(X_{(n)}>2X_{(n-1)})&= P(E_1>E_2+\dots+E_n) \\ &= \dots\\ & = \frac{n}{n+1}\times\dots\times\frac{3}{4}\times \frac{2}{3} \\ &= \frac{2}{n+1}. \end{align*} $$ (Again we had $E_i\sim \Exp(i)$ independently for different $i$.) For any $r>0$, we can also ask for the probability that the largest piece is more than $(1+r)$ times as large as each of the others. This comes out as $$ \begin{align*} P(\frac{1}{r}E_1>E_2+\dots+E_n) &= \frac{n}{n+r}\times\dots\times\frac{3}{3+r}\times\frac{2}{2+r}. \end{align*} $$ If $r$ is an integer, you get some nice cancellations. For example, for the probability that one piece is more than 3 times each of the others is $6/(n+1)(n+2)$. For general integer $r$ this seems to give $r!n!/(n+r-1)!$. (Are there nice geometric explanations of these facts?!)

More generally, what's the probability that the $k$th largest of $n$ is at least $(1+r)$ times as long as the $(k+1)$st largest? This seems to come out as $$ P(\frac{1}{r}E_k > E_{k+1} +\dots + E_n) = \prod_{i=k+1}^n \frac{i}{i+rk}. $$

At the other end we can also look at the nice $9/10$ fact mentioned in passing in the question! What's the probability that the $k$th largest is at least $(1+r)$ times the smallest? Looks like one gets $$ \begin{align*} P(E_n+\dots+E_k > (1+r)E_n) &=1-P(E_n > \frac{1}{r}(E_{n-1}+\dots+E_k))\\ &=1-\prod_{i=k}^{n-1}\frac{ri}{n+ri}. \end{align*} $$ For example putting in $r=1$, $n=3$, $k=1$, you get $9/10$ as expected.

Related Question