2
$\begingroup$

An old man is walking with a stick with initial length 1. Every time he steps the stick breaks with uniform distribution along its (remaining) length. He holds the stick at the very end and holds on to the remaining piece. What is the expected number of steps before the stick has length less than $\epsilon$, for some $0 < \epsilon < 1$?

I've done some computation and I believe the answer is $1-\log(\epsilon)$ but I'm not sure how to go about proving it.

$\endgroup$
  • $\begingroup$ Can you include you computations, and a summary of how you found the answer to be $-\log(\epsilon)$? $\endgroup$ – amWhy Mar 24 '17 at 14:17
  • $\begingroup$ Have I seen this before? It is equivalent to "probability that product(n iid U(0,1) distributions) < epsilon"... $\endgroup$ – Parcly Taxel Mar 24 '17 at 14:18
  • $\begingroup$ I ran a simple simulation for specific values of $\epsilon$ and noticed in particular for $1/2$, the average number of steps was very close to log(2). $\endgroup$ – Oliver Clarke Mar 24 '17 at 14:21
  • $\begingroup$ I think this is equivalent to a problem about the product of n iid U(0,1) distributions. I'm not sure how to deal with them and I'd be interested in seeing a solution $\endgroup$ – Oliver Clarke Mar 24 '17 at 14:22
  • $\begingroup$ Sorry I made a mistake, my guess is that the answer is $1-\log(\epsilon)$ $\endgroup$ – Oliver Clarke Mar 25 '17 at 10:17
2
$\begingroup$

Let $X_i$ the proportion of the remaining stick that goes away after step $i$. So if after 1 step, his stick measures $0.5$ and then he takes a step and loses half of that (which means it now measures $0.25$ after two steps), then $X_2 = 1/2$.

So the length $L$ of the stick after $n$ step is $L = \prod_{i=1}^n X_i$ and the $X_i$'s are iid $\sim U(0,1)$.

Since $X_i$'s are independent $(*)$ $$E[L] \overset{(*)}{=} \prod_{i=1}^n E[X_i] = \prod_{i=1}^n \frac12 = \frac{1}{2^n} $$

Solving $$ \frac{1}{2^n} \leq \epsilon \implies 2^n \geq 1/\epsilon \implies n \geq -\log_2(\epsilon) $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ if $n$ is the expected number of steps, I believe $n \ge -\log_2(\epsilon)$ is a correct lower bound. But for the true value take for example $\epsilon = 1/2$, for sure we expect $n \ge 1$ but $n \neq 1$. Half the time we expect the stick to break to a length less than $1/2$ which contributes $1/2$ to $n$. The other half the time the stick is longer than $\epsilon$ so we have to wait for another break which which contributes more than $(1/2) * 2 = 1$ to $n$. So we expect $n > 3/2$. From simulations I believe the value is $n = 1 + \log(2)$ in this case. $\endgroup$ – Oliver Clarke Mar 25 '17 at 10:27

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.