# Which threshold maximizes the expected size of the final sample?

For $$c>0$$, sample repeatedly and independently from $$(0, 1)$$ until the sum of the samples exceeds $$c$$. Let $$\mu_c$$ be the expected size of the final sample.

For which $$c$$ is $$\mu_c$$ maximised?

It is clear that as $$c$$ tends to $$0$$, $$\mu_c$$ tends to $$\frac{1}{2}$$ and this is its minimum value.

• The final sample is the last number you draw, right? Interesting question! – Vincent Dec 27 '19 at 22:02
• @Vincent Yes, it's the sample that pushes the sum of the samples over $c$. – felipa Dec 27 '19 at 22:03
• Very neat question! where did it come from? Is this homework / quiz / etc? What kind of HINT vs actual solution is allowed? Also, I assume you're sampling uniformly in $(0,1)$? – antkam Dec 27 '19 at 22:16
• @antkam It's just for mathematical interest. I was playing around with simulating the setup. A full solution would be very welcome. Yes it's uniform from $(0, 1)$. – felipa Dec 27 '19 at 22:18
• @antkam: Consider a steady-state process with i.i.d. steps uniformly drawn from $(0,1)$, and at some point choose an arbitrary threshold. The probability for a given segment to contain the threshold is proportional to the length of the segment, so the expected length of the segment containing the threshold is $\int_0^12l\cdot l\mathrm dl=\frac23$. – joriki Dec 27 '19 at 23:32

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.

• My numeric simulations are consistent with your calculations. I would say that for "large" $c$, the distribution of the last uniform random variable (i.e. conditioned on the sum of the previous ones being less than $c$) is triangular with density $$f(x) = 2x \mathbb 1(0 < x < 1).$$ I think using some kind of large-sample approximation would get you the conditional density in this case. – heropup Dec 27 '19 at 23:26
• @heropup - clearly you had some kind of triangle in mind, to get to $2/3$. for large $c$ some kind of "ergodicity" must apply and all points become equally likely, in a sense, but i cant quite translate that into a triangle. anyway, very good intuitive guess! but the "averaging" argument in (2) above (if you buy the argument) means the global max must occur within $(0,1)$ and the limit behavior must fluctuate and cannot be monotonic. this is all very hand-wavy, but that's my gut feel – antkam Dec 27 '19 at 23:30
• Your solution seems correct to me (for $c\le1$). For $1\le c\le2$, we have $$f(c)=\int_{c-1}^1\left(-\frac12\mathrm e^x+x+1\right)\mathrm dx+\int_1^cf(x)\mathrm dx\;;$$ differentiating yields $f'(c)=\frac12\mathrm e^{c-1}-c+f(c)$, and the solution for the initial condition $f(1)=-\frac12\mathrm e+2$ is $f(c)=\frac12\mathrm e^{x-1}(x-1)-\frac12\mathrm e^x+x+1$. Here's a plot. This section also has a local maximum, at $\hat c\approx1.4770$ with $f(\hat c)\approx0.67139$, already quite a bit closer to $\frac23\approx0.66667$ than $\ln2\approx0.69315$. – joriki Dec 28 '19 at 0:07
• @joriki - thanks a LOT for both comments. the $2/3$ limit via steady state is what i had a hazy vision of, but i couldn't find the right argument. and doing the new integral, and in particular showing that it is "piecewise" chopped into intervals delimited by the integers, makes a ton of sense. one can probably recurse this and find the formula for every integer interval, but it might be boring work now. – antkam Dec 28 '19 at 1:23
• @felipa - now that joriki has shown the way, you do the boring work! ;) actually it might not be so boring... if we may extrapolate from two data points (ha!), the next $f(c), c \in [2,3]$ might have a $e^{x-2}$ thingy in it, and then the next has $e^{x-3}$ thingy in it, etc. it might all turn out rather neat! so i definitely won't deprive you of the pleasure of discovery. :) (plus: i'm very very bad at integration... notice that in my original answer, i only had to differentiate!) – antkam Dec 28 '19 at 15:55

antkam's approach is correct and elegant. We can also derive the same result with a bit less calculus by approximating the continuous uniform distribution by a discrete uniform distribution.

So we have an $$n$$-sided die that we roll repeatedly, summing the results, and we want to know the threshold $$k$$ that maximizes the final result (where reaching $$k$$ itself is enough to stop).

We can prove by induction that the expected final result for threshold $$k$$ is $$n+k-\frac n2\left(1+\frac1n\right)^k$$. For $$k=1$$ this is $$n+1-\frac n2\left(1+\frac1n\right)=\frac{n+1}2$$, which is correct. Assuming the result for $$k-1$$, we obtain the expected final result for $$k$$ as

$$\begin{eqnarray*} &&\frac1n\left((n-k+1)\frac{n+k}2+\sum_{j=1}^{k-1}\left(n+j-\frac n2\left(1+\frac1n\right)^j\right)\right) \\ &=& \frac1n\left((n-k+1)\frac{n+k}2+(k-1)n+\frac{k(k-1)}2-\frac n2\left(\frac{1-\left(1+\frac1n\right)^k}{1-\left(1+\frac1n\right)}-1\right)\right) \\ &=& n+k-\frac n2\left(1+\frac 1n\right)^k\;. \end{eqnarray*}$$

Setting the derivative with respect to $$k$$ to zero yields

$$1-\frac n2\ln\left(1+\frac 1n\right)\left(1+\frac 1n\right)^k=0\;,$$

so the optimal threshold in the discrete case is an integer near

$$-\frac{\ln\frac n2+\ln\ln\left(1+\frac 1n\right)}{\ln\left(1+\frac 1n\right)}\;.$$

For instance, for $$n=6$$, this is

$$\frac{\ln3+\ln\ln\frac76}{\ln\frac76}\approx5.003\;,$$

so the optimal threshold is $$k=5$$ with an expected final result of

$$6+5-\frac62\left(1+\frac16\right)^5=\frac{11705}{2592}\approx4.516\;.$$

For $$n\to\infty$$, we have $$\ln\left(1+\frac1n\right)\sim\frac1n$$ and thus

$$-\frac{\ln\frac n2+\ln\ln\left(1+\frac 1n\right)}{\ln\frac 1n}\sim-\frac{\ln\frac n2+\ln\frac 1n}{\frac 1n}=n\cdot\ln2\;,$$

in agreement with antkam's result.

• I really like the discrete version of the problem you have introduced. – felipa Dec 29 '19 at 12:17