Draws from the uniform distribution are taken until the sum exceeds 1. What is the expected value of the final draw?

Question

I was thinking about this question after a related problem: what's the expected number of draws for the sum to exceed 1? For that problem, the answer is known and is a surprising result http://mathworld.wolfram.com/UniformSumDistribution.html

My intuition is the final draw will be larger than the average draw. This is because larger draws are more likely to make the sum exceed 1, skewing the expectation to be above average.

I did a simulation in a spreadsheet with 1 million draws and the estimate I found was the final draw was about 0.655.

I have tried many techniques to try and solve this analytically. But none of my answers are close to 0.655, so either my simulation is wrong or my math is wrong (I'm thinking it's my math).

Anyone able to help how to write out this expectation?

My current method is this: the expectation of the final draw will be the sum from k=2 to infinity of the probability the kth draw makes the sum exceed 1 (this is 1/[k(k-2)!] as explained here) times the expected value of the final draw--which would range from a lower value of 1 - (sum on turn k-1, given this sum is less than 1) to the upper value of 1. It's this term that is giving me trouble.

Or maybe I'm approaching this completely wrong. Any pointers would be great.

Also, I'm planning on using this as a puzzle for my blog. I will definitely credit anyone that helps. Thanks.

Answer 1

The idea in this exercise, as in the one asking about the number of draws needed for the sum to exceed $1$, is to condition on the value of the first draw.

To wit, for every $x$ in $(0,1)$, consider $$ g(x)=\sum_{n\geqslant1}P(S_n\leqslant x). $$ Then $P(S_1\leqslant x)=x$ and $S'_n=S_{n+1}-S_1$ defines a process $(S'_n)_{n\geqslant1}$ independent of $S_1$ and distributed like $(S_n)_{n\geqslant1}$. Conditioning on the value $z$ of $S_1$, one gets $$ g(x)=x+\sum_{n\geqslant1}\int_0^xP(S_n\leqslant x-z)\mathrm dz=x+\int_0^xg(z)\mathrm dz. $$ Thus, $$ g(x)=\mathrm e^x-1. $$ The value of $g(1)$ implies the well known fact that one needs a mean number of $\mathrm e$ draws to exceed $1$.

As regards the present exercise, note that the density $f$ of the draw when the sum first exceeds $1$ is such that, for every $x$ in $(0,1)$, $$ f(x)=\sum_{n\geqslant1}P(S_n\lt1\leqslant S_n+x)=\sum_{n\geqslant1}P(1-x\leqslant S_n\lt1), $$ that is, $$ f(x)=g(1)-g(1-x)=\mathrm e-\mathrm e^{1-x}. $$ Finally, the expected value of the final draw is $$ \int_0^1xf(x)\mathrm dx=2-\tfrac12\mathrm e\approx0.640859. $$

Answer 2

Let $f(x)$ reflect the desired distribution. Then, of course, we want to calculate $$ \int_0^1 x f(x)\,dx. $$

Let us try to find what form $f(x)$ takes; let $S_n$ denote the sum of $n$ uniform draws. Then, we have $$ f(x) = \sum_{n=1}^\infty Pr[1-x<S_n<1] = \sum_{n=1}^\infty f_n(x). $$

Great; we may use the PDF from MathWorld and integrate over $(1-x,1)$. We have $$ f_n(x) = \int_{1-x}^1 \frac{1}{2(n-1)!} \sum_{k=0}^n (-1)^k \binom{n}{k} (s-k)^{n-1} \mathrm{sgn}(s-k)\,ds = \frac{1}{2(n!)} \left[ 1-(1-x)^n + \sum_{k=1}^n \binom{n}{k} (-1)^{k+n} \left[(k-1+x)^n-(k-1)^n\right]\right].$$

In some sense, we are done. Mathematica confirms that $\sum_{n=1}^\infty \int_0^1 x\,f_n(x)\,dx$ gives us the numerical answer we desire. (I switched the order of integration and summation over an infinite series... let's just pretend that is okay.)

If you need to get a closed form answer, you're in luck. Sort of... you can at least compute $\int_0^1 xf_n(x)\,dx$ in terms of beta functions and incomplete beta functions. Not sure if the infinite sum over $n$ will close nicely.

Also, if you want to explore the distribution, here is some Mathematica code I wrote:

With[{samples = Table[
    First[NestWhile[
      With[{x = RandomReal[]}, {x, #1[[2]] + x}] &,
      {0, 0}, #1[[2]] < 1 &]], {100000}]},
 Print[Mean[samples]];
 Histogram[samples]]

[edit] I was mistaken about the beta functions. Let's find it exactly. Clearly, the $x(1-(1-x)^n) / (2*n!)$ poses no problem. We can integrate the stuff inside the binomial term and (skipping some steps), obtain $$ \sum_{n=1}^\infty \int_0^1 x\,f_n(x)\,dx = 1-e/4 + \frac{1}{2}\sum_{n=1}^\infty \frac{(-1)^n}{n!} \sum_{k=1}^n \binom{n}{k} (-1)^k \frac{(n+2)k^{n+1}-k^{n+2}+(k-1)^{n+2}}{(n+1)(n+2)}. $$

Now, at this point, I am stuck. I bet there are some cute binomial identities that will reduce this further. I'll continue thinking about it.

[edit 2] Mathematica strongly suggests that the remaining double sum is also $1-e/4$. In other words, the complete answer is $2-e/2$. Mystifying.

[edit 3; final edit] Ugly, but effective. Let $$ b_n = \sum_{k=1}^n \binom{n}{k} (-1)^k \frac{(n+2)k^{n+1}-k^{n+2}+(k-1)^{n+2}}{(n+1)(n+2)}$$ One can show by induction that $$ b_n = \frac{(-1)^n}{2} \frac{n(n+3)}{(n+2)(n+1)}. $$

At this point, we are actually done; we obtain our expected value as $$ 1-e/4 + \frac{1}{4} \sum_{n=0}^\infty \frac{1}{n!} \cdot \frac{n+4}{(n+3)(n+2)}. $$ Recognize $\frac{n+4}{(n+3)(n+2)} = -\frac{1}{n+3}+\frac{2}{n+2}$ and do power series tricks on $e^x$ to reduce the sum.