Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.