Another variant of a classic

[radosr]

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.\)

 

[pratikpoddar]

Another interesting solution at http://pratikpoddarcse.blogspot.com/2011/04/smallest-number-in-decreasing-sequence.html

 

[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.
The answer is e
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.
The answer is e
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.

 

[roni]

Found it.

Hey AlexandreH,

Can you please post the link?

Thanks.

 

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