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

2 thoughts on “Unexpected expected value”

  1. In your rearrangement,
    should be

    Thanks for the interesting article!

Leave a Reply

Your email address will not be published. Required fields are marked *