Summing (0,1) uniform random variables up to 1 [duplicate]

Possible Duplicate:
choose a random number between 0 and 1 and record its value. and keep doing it until the sum of the numbers exceeds 1. how many tries?

So I'm reading a book about simulation, and in one of the chapters about random numbers generation I found the following exercise:

For uniform $(0,1)$ random independent variables $U_1, U_2, \dots$ define

$$ N = \min \bigg \{ n : \sum_{i=1}^n U_i > 1 \bigg \} $$

Give an estimate for the value of $E[N]$.

That is: $N$ is equal to the number of random numbers uniformly distributed in $(0,1)$ that must be summed to exceed $1$. What's the expected value of $N$?

I wrote some code and I saw that the expected value of $N$ goes to $e = 2.71\dots$

The book does not ask for a formal proof of this fact, but now I'm curious!

So I would like to ask for

• A (possibily) simple (= undergraduate level) analytic proof of this fact
• An intuitive explanation for this fact

or both.

Solution 1:

Here is a way to compute $\mathbb E(N)$. We begin by complicating things, namely, for every $x$ in $(0,1)$, we consider $m_x=\mathbb E(N_x)$ where $$ N_x=\min\left\{n\,;\,\sum_{k=1}^nU_k\gt x\right\}. $$ Our goal is to compute $m_1$ since $N_1=N$. Assume that $U_1=u$ for some $u$ in $(0,1)$. If $u\gt x$, then $N_x=1$. If $u\lt x$, then $N_x=1+N'$ where $N'$ is distributed like $N_{x-u}$. Hence $$ m_x=1+\int_0^xm_{x-u}\,\mathrm du=1+\int_0^xm_{u}\,\mathrm du. $$ Thus, $x\mapsto m_x$ is differentiable with $m'_x=m_x$. Since $m_0=1$, $m_x=\mathrm e^x$ for every $x\leqslant1$, in particular $\mathbb E(N)=m_1=\mathrm e$.

Solution 2:

In fact it turns out that $P(N = n) = \frac{n-1}{n!}$ for $n \ge 2$. Let $S_n = \sum_{j=1}^n U_j$, and $f_n(s)$ the probability density function for $S_n$. For $0 < x < 1$ we have $f_1(x) = 1$ and $f_{n+1}(x) = \int_0^x f_n(s) \ ds$. By induction, we get $f_n(x) = x^{n-1}/(n-1)!$ for $0 < x < 1$, and thus $P(S_n < 1) = \int_0^1 f_n(s)\ ds = \dfrac{1}{n!}$. Now \begin{align*} P(N=n) &= P(S_{n-1} < 1 \le S_n)\\ &= P(S_{n-1} < 1) - P(S_n \le 1)\\ &= \frac{1}{(n-1)!} - \frac{1}{n!} \\ &= \frac{n-1}{n!} \end{align*}