1
$\begingroup$

I have a line that has initially length one. A process reduces the length of the line.

During each step of the process 2 points $x_1$ and $x_2$ on the remaining line are selected. The part of the line between the left side and the maximum of $x_1$ and $x_2$ is cut off.

What is the expected number of times $E(x)$ the process should be repeated such that a fraction x of the initial line has disappeared.

I would like to solve this problem using a differential equation.

I did allready some work on this problem, but I am not sure of the correct DE to solve the problem. More precisely I would like to know if the correct DE to solve this problem is

$E(x) = 1-x^2 + \int_0^x 2y+2yE(\frac{x-y}{1-y}) dy$

or

$E(x) = 1-x^2 + \int_0^x 1+2yE(\frac{x-y}{1-y}) dy$

As you see my problem is that I don't know whether the first term of the integrand should be 1 or 2y.

Some additional info to make it easier to understand the DE's:

  • $1-x^2$ = probability 1 step is enough to make disappear more than x

  • $E(\frac{x-y}{1-y})$ = expected number of times the process should be repeated such that a fraction x has disappeared, starting from length y < x

  • $2y$ = probability distribution function for the maximum of x_1 and x_2 with 0<=y<=1

1 Answers 1

2

Option 1.

Either one understands what is going on and this is direct, or one finds an alternative proof. Here is one: one needs at least one step. When does one need more? If less than $x$ disappears on the first step. The portion which disappears during the first step has density $2y$. If a portion of exactly $y\leqslant x$ disappears at the first step, the stick has now length $\ell=1-y$ and one asks that a proportion $p=x-y$ of the original stick disappears. The expected number of steps this takes is $E(p/\ell)$. Hence, $ E(x)=1+\int_0^yE\left(\frac{x-y}{1-y}\right)\,2y\,\mathrm dy. $