Broken stick probability problem

Question

We have all heard the old problem about forming a triangle from breaking a stick into three pieces, with the breaks randomly distributed. Some variations make the second break contingent on the first in some way. I present a new variation (not original to me).

Problem: Take a stick and break it at a location selected with uniform density along its length. Throw away the left-hand piece and break the right-hand one at a location selected with uniform density along its length. Continue forever. What is the probability that one of the discarded left-hand pieces is more than half as long as the original stick?

I do not have a particularly elegant to solution to this one, and was wondering if one exists. Of course, any answers that solve the problem are welcome.

Answer 1

Let $f(x)$ be the probability that we eventually cut off at least $x$ from a stick of length $1$, with $1\ge x\ge1/2$. We can either succeed by immediately cutting off at least $x$, with probability $1-x$, or by leaving $t\ge x$ and then cutting off $x$ from a stick of length $t$. Thus we have

$$ f(x)=1-x+\int_x^1f(x/t)\mathrm dt\;. $$

Substituting $u=x/t$ yields

$$f(x)=1-x+x\int_x^1f(u)/u^2\mathrm du\;.\tag1$$

Then differentiating with respect to $x$ yields

$$f'(x)=-1-f(x)/x+\int_x^1f(u)/u^2\mathrm du\;,$$

and differentiating again yields

$$f''(x)=-f'(x)/x+f(x)/x^2-f(x)/x^2=-f'(x)/x\;,$$

so

$$ \frac{f''(x)}{f'(x)}=-\frac1x $$

and thus

$$ \begin{align} \log f'(x)&=-\log x +c\;,\\ f'(x)&=a/x\;,\\ f(x)&=a\log x+b\;. \end{align} $$

Now $f(1)=0$ yields $b=0$, and then substituting into $(1)$ yields $a=-1$, so $f(x)=-\log x$ and

$$f(1/2)=\log2\approx0.693\;.$$

Answer 2

Here is a solution using series – much longer than joriki's differential-based solution, but closer to first principles of probability.

Let the original stick have unit length and let $X_n$ be the random variable describing the length of this stick after $n$ breaks. It is easy to see that this is the product of $n$ iid $U(0,1)$ variates, and thus it is known (see here for example) that $$f_x(X_n)=\frac{(-\ln x)^{n-1}}{(n-1)!}$$ The probability that after $n$ breaks, the next broken-off piece will have sufficient length is $$P(X_n-U(0,1)X_n>1/2)=P((1-U(0,1))X_n>1/2)=P(U(0,1)X_n>1/2)$$ which can be written as the double integral $$\int_{x=1/2}^1\int_{u=1/(2x)}^1f_x(X_n)f_u(U(0,1))\,du\,dx=\int_{1/2}^1\int_{1/(2x)}^1\frac{(-\ln x)^{n-1}}{(n-1)!}\,du\,dx$$ We now need to evaluate the integral: $$\int_{1/2}^1\int_{1/(2x)}^1\frac{(-\ln x)^{n-1}}{(n-1)!}\,du\,dx =\int_{1/2}^1\left[\frac{(-\ln x)^{n-1}}{(n-1)!}u\right]_{u=1/(2x)}^1\,dx$$ $$=\int_{1/2}^1\left(\frac{(-\ln x)^{n-1}}{(n-1)!}-\frac{(-\ln x)^{n-1}}{2x(n-1)!}\right)\,dx$$ $$=\int_{1/2}^1\frac{(-\ln x)^{n-1}}{(n-1)!}\,dx-\frac12\int_{1/2}^1\frac{(-\ln x)^{n-1}}{x(n-1)!}\,dx$$ It is relatively easy to show (by induction, for example) that the antiderivative of the left integral is $x\sum_{k=0}^{n-1}\frac{(-1)^k\ln^kx}{k!}$ and even simpler to show that that of the right integral is $-\frac{(-\ln x)^n}{n!}$: $$=\left[x\sum_{k=0}^{n-1}\frac{(-1)^k\ln^kx}{k!}\right]_{1/2}^1-\frac12\left[-\frac{(-\ln x)^n}{n!}\right]_{1/2}^1$$ $$=1-\frac12\sum_{k=0}^{n-1}\frac{\ln^k2}{k!}-\frac12\cdot\frac{\ln^n2}{n!}$$ $$=1-\frac12\sum_{k=0}^n\frac{\ln^k2}{k!}=\frac12\sum_{k=n+1}^\infty\frac{\ln^k2}{k!}$$ The desired probability is then the sum of all $P(U(0,1)X_n>1/2)$ for $n\in[0,\infty)$, with the value for $n=0$ as the obvious $\frac12$: $$P=\frac12\sum_{n=0}^\infty\sum_{k=n+1}^\infty\frac{\ln^k2}{k!}=\frac12\sum_{k=1}^\infty\frac{k\ln^k2}{k!}$$ $$=\frac{\ln2}2\sum_{k=0}^\infty\frac{\ln^k2}{k!}=\frac{\ln2}2\cdot2=\color{red}{\ln2}$$

---

By replacing each $2$ above with an arbitrary $1\le1/a\le2$, we also see that the probability of getting a piece of length at least $1/2\le a\le1$ is $-\ln a$, just as in joriki's answer.

Answer 3

If you ask for an elegant solution. Then you should totally check this out.

Any point within the triangle can represent how the stick is broken into three pieces. For instance, if point P is selected, that represents that the stick is being broken into pieces with length a, b, and c. By the altitude theorem, it is known that a + b + c = x. Here x is the altitude

In this example it would not be possible to make a triangle, because a + b < c.

To find the probability that the two smaller sides will sum to be larger than the third side it is helpful to divide the equilateral triangle into four smaller equilateral triangles, by connecting the midpoints of the sides.

As long as point P is selected in the middle triangle, it will be possible to create a triangle from the three pieces.

The probability that randomly selected P is in the middle triangle is 1/4 so the probability that a triangle can be formed.

This is a beautiful Geometric approach.