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.

  • $\begingroup$ The final sample is the last number you draw, right? Interesting question! $\endgroup$ – Vincent Dec 27 '19 at 22:02
  • 1
    $\begingroup$ @Vincent Yes, it's the sample that pushes the sum of the samples over $c$. $\endgroup$ – felipa Dec 27 '19 at 22:03
  • $\begingroup$ 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)$? $\endgroup$ – antkam Dec 27 '19 at 22:16
  • $\begingroup$ @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)$. $\endgroup$ – felipa Dec 27 '19 at 22:18
  • 1
    $\begingroup$ @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$. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – heropup Dec 27 '19 at 23:26
  • $\begingroup$ @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 $\endgroup$ – antkam Dec 27 '19 at 23:30
  • 1
    $\begingroup$ 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$. $\endgroup$ – joriki Dec 28 '19 at 0:07
  • 1
    $\begingroup$ @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. $\endgroup$ – antkam Dec 28 '19 at 1:23
  • 1
    $\begingroup$ @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!) $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.