Expected number of cuts before a stick is halved A stick of unit length is put horizontally from left to right. Cut this stick at a uniformly randomly chosen position at each step and keep the left remaining part. Keep cutting until the length of the remaining part is smaller than 1/2 of the original length. Find the expected number of cuts.
 A: The length of the remaining part is the product $Z_n = \prod_{k=1}^n X_k$ of i.i.d. random variables $X_1, X_2, \ldots$, each of which is uniformly distributed on $(0,1)$, and $N=\min\{n \geq 1 : Z_n < 1/2\}$ is a stopping time with respect to the natural filtration.
Then

*

*$Z_N$ is uniformly distributed on $(0,1/2)$

*$\log(X_n)$ is integrable with expected value $-1$

*$N \leq \min\{n \geq 1 : X_n < 1/2\}$ which is a geometric random variable and therefore integrable.

The above justifies the use of Wald's equation for stopping times, so that $$\mathbb{E}[N] = \frac{\mathbb{E}[\log(Z_N)]}{\mathbb{E}[\log(X_1)]} = -2\int_0^{1/2}\log x\,dx = 1 + \log(2)$$
A: Let $E_{r}$ be the expected number of cuts before the remainder is smaller than $r$ times the original length. We have the following recurrence relationship:
$$E_{r} = r  + \int_{r}^{1} (1+ E_{(r/x)}) \;dx= \\=1 + \int_{r}^{1}  E_{(r/x)}  \;dx $$
With $E_{0} = \infty $ and $E_{1} = 1$.
Explanation: Assuming the first cut gives a remainder of length $r$ or less  gives expected number of cuts $1$. Assuming the remainder is of length  $x \in [r,1]$ gives the expected number of cuts $1$ + the number of cuts required to reach $r/x$ times the remaining length.
This gives us: $$E_{r} = 1 - \log(r)\\ E_{\frac{1}{2}} = 1 + \log(2)$$

Proof that the solution $E_{r} = 1-\log(r)$ is uniquely determined by the recurrence and constraints:
Let $F_{r}$ be defined by $F_{\log(r)} = E_{r}$. We have $$F_{\log(r)} = 1 + \int_{r}^{1}  F_{\log(r)-\log(x)} dx $$ By changing variables as: $\log(r)\rightarrow r$, $\log(x)\rightarrow x\;$
(or  $r\rightarrow e^r$, $x\rightarrow e^x$) the equation becomes:
$$F_{r} = 1 + \int_{r}^{0}  e^x F_{(r-x)} dx $$
An additional change of $x \rightarrow (r-x)$ gives:
$$F_{r} = 1 + \int_{0}^{r}  -F_{x} \;e^{r-x} \; dx $$
with our constraints becoming $F_{-\infty} = \infty$ and $F_{0} = 1$. Assume this has more than one solution (as our solution gives $F_{r} = 1 - r$). Then the difference between the two solutions satisfies:
$$D_{r} =  \int_{0}^{r}  -D_{x} \;e^{r-x} \; dx \\
D_0 = 0 $$
Differentiating the equation by $r$ we get:
$$D_{r}' = -D_r \; e^{r-r} +  \int_{0}^{r}  -D_{x} \;e^{r-x} \; dx = \\=-D_{r} + D_{r} = 0 $$
From this we get $D_{r} = c$, which combined with $D_{0} = 0 $ gives $D_{r} = 0$. Therefore, our solution is unique.
A: The simulation results (with R) also support the above results:
set.seed(1)
cuts <- replicate(100000, 
               {
                 x <- 1
                 i <- 0
                 while (x >= 1/2) {
                   x <- runif(1, 0, x) # keep the left part
                   i <- i + 1                   
                 }
                 i
               }
               )
 mean(cuts)
 # [1] 1.69461
 1 + log(2)
 # [1] 1.693147

It's interesting to observe how the distribution of cuts looks like:
hist(cuts)


