Which threshold maximizes the expected size of the final sample?

I will write $f(c) = \mu_c$ to make it more clearly a function of $c$. For now I will only investigate $c \in [0,1]$. It turns out (if my math is correct) there is a unique max within $c \in [0,1]$, at:

$$c = \ln 2, ~~~~~~~f(c) = \mu_c = \ln 2$$

But frankly I would only trust my own math below with about 80% confidence... :)

First of all, $c$ can be considered as the amount "still to go". I.e., starting with $c$, if the next sample is $x < c$, then you effectively have a new problem with a new threshold of $c-x$, and the expected value becomes $f(c-x)$. We can build a recurrence from this observation.

Let $X \sim Unif(0,1)$. We have:

• Law of total expectation: $f(c) = P(X > c) E[X \mid X > c] + P( X < c) E[f(c-X) \mid X < c]$

• $P(X>c) = 1-c$

• $E[X \mid X > c] = {1+ c \over 2}$ because conditioned on $X > c$ then $X\sim Unif(c,1)$

• $P(X < c) = c$

• Conditioned on $X < c$, we have $c-X \sim Unif(0, c)$.

So the most trouble term becomes:

$$E[f(c - X) \mid X < c] = \int_0^c \frac1c f(u) ~du$$

And the overall equation is:

$$f(c) = {1 - c^2 \over 2} + c \int_0^c \frac1c f(u) ~du$$

Differentiate w.r.t. $c$:

$$f'(c) = -c + f(c)$$

which is an ODE with this solution (credit: wolfram alpha!): for some integration constant $K$,

$$f(c) = K e^c + c + 1$$

Substitute in $f(0) = 1/2$ (as observed by OP) and solving, we have $K = -1/2$ and so:

$$f(c) = -\frac12 e^c + c + 1$$

Now we just need to find the max:

$$f'(c) = -\frac12 e^c + 1 = 0 \iff e^c = 2 \iff c = \ln 2$$

at which point we have $f(c) = c = \ln 2$ which is just slightly $> 2/3$.

---

Further thoughts:

(1) I am pretty rusty (and that's a charitable description!) with "continuous" math, so if someone can critique / verify the above, that'd be much appreciated.

(2) This answer does not cover the case of $c > 1$ so far. For $c> 1$, there is no chance the next sample is enough, and the recurrence becomes:

$$f(c) = \int_{c-1}^c f(u) ~du$$

where $f(u) = -\frac12 e^u + u + 1$ whenever $u < 1$. I don't know how to do this integration. However, intuitively, since $f(c)$ is based on averaging of values of $f(u)$ (or average of averages, etc), the max of $f(c)$ cannot $>$ the max of $f(u)$, and in fact, since the max $f(u)$ is unique within $u \in (0,1)$, the max of $f(c)$ cannot even $=$ the max of $f(u)$ within $u \in (0,1)$. This is not a rigorous proof, but rather an intuitive argument why the max I found within $(0,1)$ is also the global max.