Choose a random number between $0$ and $1$ and record its value. Keep doing it until the sum of the numbers exceeds $1$. How many tries do we need?

Question

Choose a random number between $0$ and $1$ and record its value. Do this again and add the second number to the first number. Keep doing this until the sum of the numbers exceeds $1$. What's the expected value of the number of random numbers needed to accomplish this?

Answer 1

Here is a (perhaps) more elementary method. Let $X$ be the amount of numbers you need to add until the sum exceeds $1$. Then (by linearity of expectation):

$$ \mathbb{E}[X] = 1 + \sum_{k \geq 1} \Pr[X > k] $$

Now $X > k$ if the sum of the first $k$ numbers $x_1,\ldots,x_k$ is smaller than $1$. This is exactly equal to the volume of the $k$-dimensional set:

$$ \left\{(x_1,\ldots,x_k) : \sum_{i=1}^k x_i \leq 1, \, x_1,\ldots,x_k \geq 0\right\}$$

This is known as the $k$-dimensional simplex. When $k = 1$, we get a line segment of length $1$. When $k = 2$, we get a right isosceles triangle with sides of length $1$, so the area is $1/2$. When $k=3$, we get a triangular pyramid (tetrahedron) with unit sides, so the volume is $1/6$. In general, the volume is $1/k!$, and so

$$ \mathbb{E}[X] = 1 + \sum_{k \geq 1} \frac{1}{k!} = e. $$

Answer 2

Assuming the numbers come from a uniform distribution over $[0,1]$ and that the trials are independent, here is an outline (this is example 7.4 4h. in Sheldon Ross' A First Course in Probability, sixth edition):

1. Let $X_i$ be the number obtained on the $i$'th trial.

2. For $0\le x\le1$, let $Y(x)$ be the minimum number of trials needed so that the sum of the $X_i$ exceeds $x$. Set $e(x)=\Bbb E [Y(x)]$.

3. Compute $e(x)$ by conditioning on the value of $X_1$: $$\tag{1} e(x)=\int_0^1 \Bbb E [ Y(x) | X_1=y]\, dy. $$

Here, use the fact that $$\tag{2}\Bbb E [ Y(x) | X_1=y] = \cases{1,& $y>x$\cr 1+e(x-y),& $y\le x $}.$$

Substitution of $(2)$ into $(1)$ will give $$\tag{3} e(x)=1+\int_0^x e(u)\,du. $$

4. Solve equation $(3)$ (by differentiating both sides with respect to $x$ first) for $e(x)$.

5. You wish to find $e(1)$.

Answer 3

Here is another method. This is exactly the same technique Yuval has given above but with an added step that goes through computing the pmf first before computing the expectation. Hopefully, this will help you understand the problem from a slightly different angle.

Let us denote by $N$ the number of random variables we need to add for the sum to exceed $1$. We first find the distribution (probability mass function) of $N$. The easiest way to do this is by computing $P(N > n)$ for $n=1,2,3,\dots$. Once we know this, we can compute $P(N = n) = P(N > n-1) - P(N > n)$.

The event that $(N > n)$ in plain English says that the sum of the first $n$ uniform random variables did not exceed $1$. The probability of this event is therefore $P(N > n) = P(U_1 + U_2 + \dots + U_n < 1)$. This can be calculated by a standard multi-dimensional integral to be $\frac{1}{n!}$. If you don't want to use calculus, one can justify this result geometrically but integration is perhaps the most natural approach to evaluate this probability. Therefore, we have $P(N = n) = \frac{1}{(n-1)!} - \frac{1}{n!} = \frac{n-1}{n!}$ for $n=1,2,3\dots$.

Once we know the pmf of N, we calculate

$E(N) = \sum_{n=1}^{\infty} n P(N=n) = \sum_{n=1}^{\infty} \frac{n(n-1)}{n!} = \sum_{n=0}^{\infty} \frac{1}{n!} = e$.

Answer 4

The solutions presented here are short and elegant, but I do not find them very intuitive. Here is a longer solution that I find more intuitive.

Restating the problem

Let us sample values, $x_i$, from a uniform distribution between 0 and 1 until their sum is greater than 1,

$$ x_1 + x_2 + x_3 + \ldots + x_n > 1\;, $$

where the $n$-th value is the first value such that the sequence sums to a number greater than 1. This means that the sum of the sequence up to the $(n-1)$-th term has to be lower or equal to 1,

$$ x_1 + x_2 + x_3 + \ldots + x_{n-1} \leq 1\;. $$

What is the expected value of the sequence length, $n$?

Solution

The expected value of the sequence length, $n$, is, by definition,

$$ \mathbb{E}(n) = \sum_{n=1}^{\infty} n P(n)\;, $$

where $P(n)$ is the probability that the sequence terminates with the $n$-th element. So, by finding $P(n)$, we should be able to calculate $\mathbb{E}(n)$.

To calculate the probability, $P(n)$, let us consider the following facts:

• The sequence of elements up to the $(n-1)$-th elements has to sum up to a value, $x \leq 1$, that is, $\sum_{i=1}^{n-1} x_i = x \leq 1$.
• Adding the $n$-th element to $x$ has to lead to a value higher than 1, that is, $x + x_n > 1$.

As a first step, let us consider a sequence whose first $(n-1)$ values sum to $x$. This happens with probability,

$$ P(x_1 + \ldots + x_{n-1} = x) = \int_0^1 \mathrm{d}x_1 \ldots \int_0^1 \mathrm{d}x_{n-1} \, \delta(x_1 + \ldots + x_{n-1} = x) \; , $$

where $\delta(x)$ is the Dirac delta. Given that the sum of the first $(n-1)$ elements is $x \leq 1$, the probability that summing the $n$-th element results in a value greater than 1 is,

$$ P(x + x_n > 1) = P(x_n > 1 - x) = x $$

Hence, the probability that the first $(n-1)$ elements sum to $x < 1$ and that the $n$-th elements leads to a sum higher than 1 is the product of the two probabilities just derived,

$$ P(x_1 + \ldots + x_{n-1} = x) \, P(x + x_n > 1) \;. $$

Here, $x$ is fixed. To consider all cases, we have to sum over all the values of $x \leq 1$,

$$ P(n) = \int_0^1 \mathrm{d}x \, P(x_1 + \ldots + x_{n-1} = x) \, P(x + x_n > 1) \;. $$

Substituting the expressions of the probabilities, we have,

$$ P(n) = \int_0^1 \mathrm{d}x \, \int_0^1 \mathrm{d}x_1 \ldots \int_0^1 \mathrm{d}x_{n-1} \, \delta(x_1 + \ldots + x_{n-1} = x) \, x \;. $$

We integrate over $x$ to find,

$$ P(n) = \int_0^1 \mathrm{d}x_1 \ldots \int_0^1 \mathrm{d}x_{n-1} \, \theta(1 - x_1 - \ldots - x_{n-1}) \, (x_1 + \ldots + x_{n-1}) \;, $$

where $\theta$ is the Heaviside step function. The equation is symmetric in all the $x_i$'s, meaning that it simplifies to,

$$ P(n) = (n - 1) \int_0^1 \mathrm{d}x_1 \ldots \int_0^1 \mathrm{d}x_{n-1} \, \theta(1 - x_1 - \ldots - x_{n-1}) \, x_{n-1} \;. $$

We can rearrange the equation into,

$$ P(n) = (n - 1) \int_0^1 \mathrm{d}y \, y \left[ \int_0^1 \mathrm{d}x_1 \ldots \int_0^1 \mathrm{d}x_{n-2} \, \theta((1 - y) - x_1 - \ldots - x_{n-2}) \right]\;. $$

The multi-dimensional integral in the square brackets is the volume of the $(n-2)$-dimensional simplex with edge of length $(1-y)$, which is $(1-y)^{n-2} / (n - 2)!$. To understand this, note that the volume of a $k$-dimensional simplex with an edge of unit length is $1/k!$. Shortening the edge in each dimension by a factor of $z$ leads to a reduction of the volume by a factor $z^k$. Hence the volume of a $k$-dimensional simplex with edge of length $z$ is $z^k/k!$. Substituting $k=n-2$ and $z=1-y$, we get the formula stated above. We substitute this formula into the equation of $P(n)$ to obtain,

$$ P(n) = (n - 1) \int_0^1 \mathrm{d}y \, y \left[ \frac{(1-y)^{n-2}}{(n - 2)!} \right]\;. $$

We move the denominator outside of the integral and substitute $y \rightarrow 1 - y$,

$$ P(n) = \frac{n - 1}{(n - 2)!} \int_0^1 \mathrm{d}y \, (1 - y) y^{n-2} = \frac{n - 1}{(n - 2)!} \frac{1}{n(n-1)} = \frac{n - 1}{n!}\;. $$

Finally, we substitute this expression for the probability, $P(n)$, into the equation of the expectation value of $n$ and obtain,

$$ \mathbb{E}(n) = \sum_{n=1}^{\infty} n P(n) = \sum_{n=1}^{\infty} n \frac{n - 1}{n!} = \sum_{n=2}^{\infty} n \frac{n - 1}{n!} = \sum_{n=2}^{\infty} \frac{1}{(n-2)!} = \sum_{n=0}^{\infty} \frac{1}{n!} = e\;, $$

Hence, the expected value of the sequence length, $n$, is $e$.

Answer 5

The derivations involving the multidimensional integral for the probability of finding a sum smaller than 1, can be simplified by restoring permutation symmetry in the integration before evaluating it. The probability that the sum of $n$ uniformly distributed random numbers between 0 and 1 does not exceed 1 is given by:

$$P(n) = \int_{0\leq s_1\leq s_2\leq\cdots \leq s_n\leq 1} ds_1 ds_2\cdots ds_n $$

The integration variables here are the partial sums of the first $n$ random variables, which are therefore ordered as indicated. But because these are dummy variables, we can permute these variables in any way we like. This means that integrating over the variables without imposing the ordering will yield $n!$ times the value of the original integral. We thus have:

$$P_n = \frac{1}{n!} \int_0^1\int_0^1\cdots\int_0^1 ds_1 ds_2\cdots ds_n = \frac{1}{n!}$$

The expectation value then follows e.g. using the derivation given in this answer by Dinesh.

Answer 6

The following is the most intuitive and shortest way of solving this question.

In general, let $f(x)$ = Expected number of random numbers to be drawn such that the sum exceeds $x$. Assume that on drawing the first random number, you get a value $0 \le t \le 1$. Now you've drawn one number, and want to find how many numbers need to be drawn to reach a value greater than $x-t$

$ f(x) = 1 + \int_{0}^{x} f(x - t) \, dt $

Let $t = x-t$, and change limits appropriately

$ f(x) = 1 - \int_{x}^{0} f(t) \, dt $

Differentiating wrt. x, using the Newton Leibniz rule

$ f'(x) = 0 \, -f(0).0 \, + \,f(x).1 $

$f'(x) = f(x)$

$f(x) = e^x$

$f(1) = e$

Answer 7

I have (what I believe is) a nice combinatorial proof (though it turned out way longer to write than I hoped...):

One can show that (for n even)

$$P(U_1+\ldots+U_n \leq 1) = P(X_1 < X_3 < X_5 < \ldots < X_{n-1} < X_{n} < X_{n-2} < X_{n-4} < ... < X_2)$$

and (essentially identically) for n odd

$$P(U_1+\ldots+U_n \leq 1) = P(X_1 < X_3 < X_5 < \ldots < X_{n} < X_{n-1} < X_{n-3} < X_{n-5} < ... < X_2)$$

where $X_1, \ldots, X_n$ are also iid U(0,1).

If, for the moment, we assume that is true; then the RHS is the probability of a single ordering of n identically distributed RVs. Since each of the $n!$ orderings is equally likely, we have that $P(U_1+\ldots+U_n \leq 1) = 1/n!$.

From here we have, for $T$ the stopping time (first time the sum exceeds 1), $E[T] = \sum_{n=0}^{\infty}P(T\geq n) = \sum 1/n! = e$

Now, we just need to prove the equivalence mentioned above. To do that we will give an additional representation of the problem, and show that the LHS and RHS are equivalent to that representation (I will refer to this as the "slicing" representation):

Define 3 sequences:
-$A_1, A_2,\ldots$ a sequence of iid $U(0,1)$ random variables
-$R_0, R_1, \ldots$ with $R_0 = 1$; and for $n\geq 1$, $R_n = A_nR_{n-1}$
-$S_1, S_2,\ldots$ with $S_n \sim bernoulli(R_{n-1})$ independent for each $n$

I posit that $$P(U_1+\ldots+U_n \leq 1) = P(S_1=1,\ldots,S_n =1)$$ and $$P(X_1 < X_3 < X_5 < \ldots < X_{n-1} < X_{n} < X_{n-2} < X_{n-4} < ... < X_2) = P(S_1=1,\ldots,S_n =1)$$

For the first identity, we start with our $\{U_n\}$ process, and use it to define our slicing representation: Set $A_n = U_n$; $R_n = 1-(U_1+\ldots+U_n)$; and $S_n = I(R_n < 1)$. This gives the desired result (conditional on the sum not exceeding 1, we take a uniform slice off of it)

For the second identity, we start with the process in our slicing representation, and use that to define our $\{X_n\}$ process recursively. If n is even, then $$(X_n|S_1=1,\ldots,S_n=1) \sim U(X_{n-1},X_{n-2});$$ $$(X_n|S_1=1,\ldots,S_{n-1}=1, S_n = 0) \sim \textrm{ uniformly on $(0,1) - (X_{n-1},X_{n-2})$}$$ $$(X_n|S_i = 0 \textrm{ for some i < n}) \sim U(0,1)$$

If $n$ is odd, then we do the same as above, but every $(X_{n-1},X_{n-2})$ interval becomes a $(X_{n-2},X_{n-1})$ interval. When $S_1=1,\ldots,S_n=1$ then, by construction, we have (for eg. even n) $X_1 < X_3 < \ldots < X_{n-1} < X_{n} < X_{n-2} < ... < X_2$. Note that, by construction, we also have $|X_{n} - X_{n-1}| = R_n$. This completes the equivalence.

Heuristically one can think of these as follows: When engaging with the Us, we have a block of wood, of width initially $1$, in a channel of width $1$. We randomly try to chop the wood in 2 pieces with a knife; and (if we successfully chop the wood), we remove the left-most piece from the channel. Before each chop, we position the wood so that it lies flush with the right side of the channel. If ever we miss the piece of wood completely (swing our knife entirely to its left in the channel) we stop.

When engaging with the Xs, we have the same wood in the same channel, but now there are 2 differences; 1) we don't reposition the wood after chopping and removing a piece; and 2) we alternate between removing the left and right piece after each "chop". We still stop when we "miss" the wood (ie. chop down and either swing completely to the left or completely to the right of the piece of wood).

In both cases, the amount of "empty" space (where we might miss the wood piece completely) follows the same distribution conditional on not yet having stopped (each chop, we add a uniformly random amount of empty space, up to the current width of the wood regardless of whether we remove from the left or the right, or translate the center of the wood within the channel).

Answer 8

If $\gamma_t(dx)=\frac{x^{t-1}}{\Gamma(t)}1_{(0,\infty)}(x)dx$ and $U_1,\ldots U_n,\ldots$ are iid and uniform on $(0,1)$, then the law of $S_n=U_1+\cdots+U_n$ conditioned by $S_n<u\leq 1$ is $\gamma_n(dx)1_{x<u}(dx).$ If $T_u=\inf \{n; S_n>u\}$ then $\Pr(T_u>n)=\int_0^u\gamma_n(dx)=u^n/n!$ and $$E(T_u)=\sum_{n=0}^{\infty}\Pr(T_u>n)=e^u.$$