Sum greater than one
Question
Given \( x_{1}, x_{2}, ... \) are iids from a continuous uniform distribution with a range \( [0, 1] \), and define \( S_{n} \) as
\[ S_{n} = \sum_{i = 1}^{n}x_{i} \]
Let \( N \) be the minimal \( n \) such that \( S_{n} > 1 \). What is E[N]?
Solution
Let us start with the probability that the sum \( S_{n} \) is less than or equal to 1.
\( P[S_{1} \le 1] = 1 \)
\( P[S_{2} \le 1] = \int_{0}^{1}\int_{0}^{1-x_{1}}dx_{2}dx_{1} = \int_{0}^{1}(1-x_{1})dx_{1} = [-\frac{(1-x_{1})^2}{2}]_{0}^{1} = \frac{1}{2} \)
For a general \( S_{n} \)
\( P[S_{n} \le 1] = \int_{0}^{1}\int_{0}^{1-x_{1}}\int_{0}^{1-x_{1}-x_{2}}...\int_{0}^{1-x_{1}-...-x_{n-1}}dx_{n}dx_{n-1}...dx_{1} \)
\( = \int_{0}^{1}\int_{0}^{1-x_{1}}...\int_{0}^{1-x_{1}-...-x_{n-2}}(1-x_{1}-...x_{n-1})dx_{n-1}...dx_{1} \)
\( = \int_{0}^{1}\int_{0}^{1-x_{1}}...\int_{0}^{1-x_{1}-...-x_{n-3}}[-\frac{(1-x_{1}-...-x_{n-1})^2}{2}]_{0}^{1-x_{1}-...-x_{n-2}}dx_{n-2}...dx_{1} \)
\( = \int_{0}^{1}\int_{0}^{1-x_{1}}...\int_{0}^{1-x_{1}-...-x_{n-3}}\frac{(1-x_{1}-...-x_{n-2})^2}{2}dx_{n-2}...dx_{1} \)
\( = \int_{0}^{1}\int_{0}^{1-x_{1}}...\int_{0}^{1-x_{1}-...-x_{n-4}}[-\frac{(1-x_{1}-...-x_{n-2})^3}{3!}]_{0}^{1-x_{1}-...-x_{n-3}}dx_{n-3}...dx_{1} \)
\( = \int_{0}^{1}\int_{0}^{1-x_{1}}...\int_{0}^{1-x_{1}-...-x_{n-3}}\frac{(1-x_{1}-...-x_{n-3})^3}{3!}dx_{n-3}...dx_{1} \)
\( ... \)
\( ... \)
\( ... \)
\( = \int_{0}^{1}\frac{(1-x_{1})^{n-1}}{(n-1)!}dx_{1} \)
\( = [-\frac{(1-x_{1})^{n}}{n!}]_{0}^{1} \)
\( = \frac{1}{n!} \)
We now calculate the conditional probability that the sum \( S_{n} \) is greater than 1 given that the sum till then \( S_{n-1} \) is less than or equal to 1. Since the possibilities leading to \( S_{n} \le 1 \) is a subset of \( S_{n-1} \le 1 \), we can calculate our conditional probability as
\[ P[S_{n} > 1 | S_{n-1} \le 1] = \frac{\frac{1}{(n-1)!} - \frac{1}{n!}}{\frac{1}{(n-1)!}} = \frac{n-1}{n} \]
Now we calculate the probability of n being the minimal iid where the sum exceeds 1.
\[ P[S_{n} > 1 \& S_{n-1} \le 1] = P[S_{n-1} < 1]P[S_{n} > 1 | S_{n-1} < 1] = \frac{1}{(n-1)!}*\frac{n-1}{n} = \frac{n-1}{n!} \]
Finally the expectation
\[ E[N] = \sum_{n=2}^{\infty}n*P[S_{n} > 1 \& S_{n-1} \le 1] = \sum_{n=2}^{\infty}n*\frac{n-1}{n!} = \sum_{n=2}^{\infty}\frac{1}{(n-1)!} = \sum_{n=1}^{\infty}\frac{1}{n!} = e \]
quant0
