## Unexpected expected value

Let’s say that random variables $$x_i$$ are distributed uniformly on segment $$[0;1]$$. How many such variables we have to add to get a sum bigger than 1? Formally, if $$n$$ is a minimum value such that $$\sum_{i=1}^{n}x_i > 1$$, what is the expected value of $$n$$? Surprisingly, it is $$e$$.

Let $$m$$ be a natural number. We denote the probability that we need more than $$m$$ variables so that their sum exceeds 1 as $$p_n$$. Geometrically, this probability is just the volume of an $$n$$-dimensional simplex $$X = \{x | \sum_{i=1}^n x_i < 1\}$$. In particular, $$p_0 = 1$$. This volume can be calculated directly, but there is an elegant probabilistic proof which I’ll demonstrate.

Consider the random variables

$$\begin{eqnarray}y_1 &=& x_1\\ y_2 &=& x_1 + x_2\\ y_3 &=& x_1 + x_2 + x_3\\ \ldots\\ y_m &=& x_1 + x_2 + \ldots + x_m \end{eqnarray}$$

It is obvious that this sequence is increasing and that $$x\in X$$ iff $$y \in Y = \{0 \le y_1 \le y_2 \le \ldots \le y_m \le 1\}$$. The linear operator which takes $$\{x_i\}$$ to $$\{y_i\}$$ has determinant 1, so the volumes of $$X$$ and $$Y$$ are exactly the same.

The volume of $$Y$$ is easily calculated. It is the probability that $$m$$ random values would appear in a sorted order, which is $$\frac{1}{m!}$$. We conclude that $$p_m = \frac{1}{m!}$$.

The probability that the sum of the first $$m$$ variables exceeds 1 is $$q_m = 1 – p_m$$, so the probability that we need exactly $$m$$ variables to exceed 1 is given by $$q_m – q_{m-1} = p_{m-1} – p_m$$. The expected number of variables which we have to add is then

$$E\left[n\right] = \sum_{m=1}^\infty m (p_{m-1} – p_m)$$

We can get an easier equivalent expression if we consider how we can rearrange a partial sum:

$$\begin{eqnarray} \sum_{m=1}^k m(p_{m-1} – p_m) &=& p_0 – p_1 + 2p_1 – 2p_2 + 3p_2 – 3p_3 + \ldots + kp_{k-1} – kp_k\\ &=& p_0 + p_1 + p_2 + \ldots + p_{k-1} – kp_k\\ &=& \left(\sum_{m=0}^{k-1} \frac{1}{m!}\right) – kp_k \end{eqnarray}$$

Since $$kp_k = \frac{k}{k!} \to 0$$, we conclude that

$$E\left[n\right] = \sum_{m=0}^\infty \frac{1}{m!} = e$$