# Another variant of a classic

##### Baruch MFE Faculty
You pick random numbers between 0 and 1 (uniformly at random) x_1, x_2, x_3, ..., as long as they keep decreasing x_1 > x_2 > x_3 > ... What is the expected value of the smallest number you pick?

#### yongge

Using your method of differential equation, this problem should be easy. The answer should be 3-e.

Let f(x) be the expected value of the smallest number when the initial number is x.
Say $$x_1>x_2>...>x_n=x$$,
for $$x_{n+1}$$, consider the two cases: either $$x_{n+1}\ge x$$ or $$x_{n+1}<x$$, We can build the equation
$$f(x)=(1-x)x+\int_0^x f(y)dy$$
Using the initial value f(0)=0, we get $$f(x)=1+2x-e^x$$, and we have $$f(1)=3-e.$$

#### Novak

or directly,
$E[\text{the last one}] = \sum_{k=1}^{\infty} \int_0^1 \int_0^{x_1} \dots \int_0^{x_{k-1}} \int_{x_k}^1 x_k\; d x_{k+1} d x_k \dots d x_1$
and this is
$\sum_{k=1}^{\infty} \frac{1}{(k+1)!} - \frac{2}{(k+2)!} = (e-2) - 2(e - 2 - 1/2) = 3-e$

#### pruse

I really like that differential equation trick! It's the continuous version of another trick you see a lot on this forum...

Here's a related question, which can also indirectly be used to solve this one: Pick numbers (x_1, x_2, x_3, ...) in (U[0,1]) as long as the running sum is (\leq 1). Find the expected value of the last running sum.

#### pratikpoddar

Which method of differential equation are you referring to?

Using your method of differential equation, this problem should be easy. The answer should be 3-e.

Let f(x) be the expected value of the smallest number when the initial number is x.
Say $$x_1>x_2>...>x_n=x$$,
for $$x_{n+1}$$, consider the two cases: either $$x_{n+1}\ge x$$ or $$x_{n+1}<x$$, We can build the equation
$$f(x)=(1-x)x+\int_0^x f(y)dy$$
Using the initial value f(0)=0, we get $$f(x)=1+2x-e^x$$, and we have $$f(1)=3-e.$$

#### AlexandreH

Using your method of differential equation, this problem should be easy. The answer should be 3-e.

Let f(x) be the expected value of the smallest number when the initial number is x.
Say $$x_1>x_2>...>x_n=x$$,
for $$x_{n+1}$$, consider the two cases: either $$x_{n+1}\ge x$$ or $$x_{n+1}<x$$, We can build the equation
$$f(x)=(1-x)x+\int_0^x f(y)dy$$
Using the initial value f(0)=0, we get $$f(x)=1+2x-e^x$$, and we have $$f(1)=3-e.$$
Could you explain this: $$f(x)=(1-x)x+\int_0^x f(y)dy$$?
Thank you.

#### AlexandreH

Could you explain this: $$f(x)=(1-x)x+\int_0^x f(y)dy$$?
Thank you.
Found it.

#### lordvid

I haven't seen this ODE approach before, but it is very cute!

I really like that differential equation trick! It's the continuous version of another trick you see a lot on this forum...

Here's a related question, which can also indirectly be used to solve this one: Pick numbers $$x_1, x_2, x_3, ...$$ in $$U[0,1]$$ as long as the running sum is $$\leq 1$$. Find the expected value of the last running sum.

I first saw this problem exactly 1 year ago, and it defeated me.
But I am having trouble solving it using the ODE approach.
I got this far:

We condition the expected value of the sum on the first value obtained (what you called $$x_1$$).

Let f(S) be the expected value, given that the first value obtained is S.

Then $$f(S)=S^2+\int_0^{1-S} (S+f(y))dy$$ subject to the initial condition f(1)=1.

f(0) is the expected value of the sum.

Differentiating this to get an ODE, we get:

$$f'(S)=1-f(1-S)$$

I don't know how to solve this analytically.

If I'm doing something wrong, please correct....

#### pratikpoddar

I haven't seen this ODE approach before, but it is very cute!

I first saw this problem exactly 1 year ago, and it defeated me.
But I am having trouble solving it using the ODE approach.
I got this far:

We condition the expected value of the sum on the first value obtained (what you called $$x_1$$).

Let f(S) be the expected value, given that the first value obtained is S.

Then $$f(S)=S^2+\int_0^{1-S} (S+f(y))dy$$ subject to the initial condition f(1)=1.

f(0) is the expected value of the sum.

Differentiating this to get an ODE, we get:

$$f'(S)=1-f(1-S)$$

I don't know how to solve this analytically.

If I'm doing something wrong, please correct....

Looks correct to me. Good one.

#### AlexandreH

It is the link posted by @pratikpoddar. I would not take credit for it .

#### lordvid

Looks correct to me. Good one.

Actually, this ODE is a (linear discrete) delay differential equation:

http://en.wikipedia.org/wiki/Delay_differential_equation

and I presume it can be solved in terms of Lambert W functions (if I can only understand what they are)

For our practical purposes though, we only need to evaluate f(0), which is our desired expected value. So in principle, we could do a Taylor series approximation around S=0 and try for a series solution. But this approach shouldn't work, because we need an approximation valid around both S=0 and S=1, to satisfy the DDE. Maybe we could try a linear combination of two Taylor series (around S=0 and s=1) scaled appropriately, but I haven't tried that...

Maybe we can try blasting it with forward Euler or something, but I don't know under what conditions that would be valid (or even if it is valid for a delayed DE)...

I think this problem is more mysterious than it looks. I can't find an answer to this question. If anyone knows of a solution, can they share (a link, etc)? I don't even have an intuitive guess of what the answer would be, other than 0<f(o)<1 of course, or even whether the expected number of terms in the final sum is 1 or >1.

#### lordvid

sorry, not linear.

Replies
7
Views
4K
Replies
0
Views
1K
Replies
2
Views
2K
Replies
0
Views
1K
Replies
1
Views
1K