Another variant of a classic

radosr

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?
 
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.\)
 
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\]
 
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.
 
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.\)
 
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.
 
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....
 
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.
 
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.
 
Top