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.