Average number of turns to shorten stick to less than some length

74 Views Asked by At

Let $0 < c < 1$ be fixed and suppose there is a stick of length 1. You play a game as follows: at each turn, you break the stick in half at a point randomly chosen on the stick and throw away the left half. On average, how many turns does it take to shorten your stick to a length less than c?

The way I came to a "solution" was very hand wavy but this is how I did it:

First off, whether you discard the left half or the right half shouldn't matter due to symmetry. So instead throw away the right half (then the problem becomes choosing a valid $c$ and the value of $c$ itself will be the length of the new stick instead of having to deal with $1-c$).

Then, $$\mathbb{E}(c) = \sum_{\alpha=0}^{\infty} \mathbb{P}(X > \alpha)$$ where $X$ is the random variable that counts the number of successful turns.

Then, to evaluate $\mathbb{P}(X > n)$ for some $n$, we imagine choosing a sequence of $x_i$ with $x_0 = 1, c < x_{i+1} < x_i$, we get $$c < x_n < x_{n-1} < \dotsc < x_1 < x_0 = 1$$ Then, to find the average probability of making it to turn n, we evaluate $$\mathcal{I}_n = \int_{c}^1 \int_{c}^{x_1} \int_{c}^{x_2} \dotsc \int_{c}^{x_{n-1}}\frac{x_n - c}{x_n x_{n-1} x_{n-2} \dotsc x_2 x_1} \text{d}x_n\text{d}x_{n-1}\dotsc\text{d}x_1$$ and originally I tried using Cauchy's repeated integration formula but since the integrand is a function of all the variables, I just resorted to pattern hunting.

I found that $\mathcal{I}_n = 1 - c\left(1 - \log(c) + \frac{1}{2}\log^2(c) - \frac{1}{6}\log^3(c) \dotsc + (-1)^{n-1} \frac{1}{(n-1)!}\log^{n-1}(c)\right)$ (I have no proof for this)

And so I just evaluate $\sum_{n=0}^{\infty} \mathcal{I}_n$ but I can't find a closed form for this. Not even Wolfram evaluates it (at least for me). Also, I'm not sure if this is all correct. Any help would be greatly appreciated!