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$$

In your rearrangement,

p0?p1+2p1?2p2?3p2+3p3

should be

p0?p1+2p1?2p2+3p2-3p3

Thanks for the interesting article!

Timur, thanks! Fixed.