Summing Uniform random variables to reach a target sum

The problem of finding the expected number of standard Uniform variables to get a sum greater than 1 is quite famous. In this post, we deal with the same problem but for a given target $t$.

This problem is not too difficult. Knowing that the sum of uniform random variables follows the Irwin-Hall distribution and the CDF of this distribution has a closed form solves the problem easily.

For example, if we let $N$ be the random variable denoting the number of draws needed to get the sum exceed $t$ for the first time, then

$\displaystyle \mathbb{P}(N>n)=\mathbb{P}(U_1+U_2+\cdots+U_n \leq t)=\frac{1}{n!}\sum_{k=0}^{\lfloor t \rfloor}(-1)^k\binom{n}{k}(t-k)^n$

Then $\mathbb{P}(N=n)=\mathbb{P}(N>n-1)-\mathbb{P}(N>n)$

But we can get this more directly using the idea in Excercise 6.65 (more importantly, its solution) of Concrete Mathematics.

For standard uniform random variables $U_1,U_2,\cdots,U_n$, let $X_1=\{U_1\}$, $X_2=\{U_1+U_2\}$ and so on, where $\{x\}$ denotes the fractional part of $x$.

It can be easily seen that $X_k$'s are all independently distributed uniform random variables. More importantly, the number of descents in the sequence of $X_k$'s is $\lfloor U_1+U_2+\cdots+U_n\rfloor$.

Therefore, for integer $t$, the sum of $n$ uniform random variables exceeding $t$ for the first time corresponds to the sequence of $X_1,X_2,\cdots,X_n$ that has exactly $t$ descents and end with a descent.

The probability of such a sequence is related to the permutation of numbers $1,2,\cdots,n$ that has exactly $t$ and end with the descent. We have already seen in this blog regarding this exact problem. Using that result, we finally have,

$\displaystyle\mathbb{P}(N=n)=\frac{(n-t)A(n-1,t-1)}{n!}$

Though we have solved this for integer $t$, with a giant leap in faith guided by some experimentation, we can also see that this works any real $t$.

With this, we get,

$\mathbb{E}(\text{No. of Uniform variables needed to get a sum greater than }\pi)\approx 6.949504$

$\mathbb{E}(\text{No. of Uniform variables needed to get a sum greater than }e)\approx 6.104002$

Hope you enjoyed this. See ya soon.

Until then, Yours Aye

Me