14
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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\;.$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But what if $x<\frac12$? $\endgroup$ – Parcly Taxel Aug 8 '19 at 7:48
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.