Expected number of cuts before a stick is halved

Solution 1:

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)$$

Solution 2:

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)

Solution 3:

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.