TAOCP 5.1.3 Exercise 25

Section 5.1.3: Runs

Exercise 25. [M25] Let $U_1, \ldots, U_n$ be independent uniform random numbers in $[0,..,1]$. What is the probability that $\lfloor U_1 + \cdots + U_n \rfloor = k$?

Verified: yes
Solve time: 12m27s

Solution

Let $S_n = U_1 + \cdots + U_n$. The probability that $\lfloor S_n \rfloor = k$ is $P(k \le S_n < k+1)$. For $n \ge 1$ and integer $k$, this probability is zero unless $0 \le k \le n-1$, because $0 \le S_n \le n$ and $S_n = n$ only with probability zero.

The sum $S_n$ follows the Irwin-Hall distribution. Its cumulative distribution function is $$F_n(x) = P(S_n \le x) = \frac{1}{n!} \sum_{j=0}^{\lfloor x \rfloor} (-1)^j \binom{n}{j} (x-j)^n, \qquad 0 \le x \le n.$$ (This can be obtained by $n$-fold convolution of the uniform density, or by volume integration using inclusion-exclusion.)

For $0 \le k \le n-1$, $$P(\lfloor S_n \rfloor = k) = F_n(k+1) - F_n(k) = \frac{1}{n!} \left( \sum_{j=0}^{k+1} (-1)^j \binom{n}{j} (k+1-j)^n - \sum_{j=0}^{k} (-1)^j \binom{n}{j} (k-j)^n \right).$$

In the second sum, substitute $i = j+1$; it becomes $$\sum_{i=1}^{k+1} (-1)^{i-1} \binom{n}{i-1} (k+1-i)^n = -\sum_{i=1}^{k+1} (-1)^{i} \binom{n}{i-1} (k+1-i)^n.$$

Adding the two sums gives $$P(\lfloor S_n \rfloor = k) = \frac{1}{n!} \sum_{j=0}^{k+1} (-1)^j \left[ \binom{n}{j} + \binom{n}{j-1} \right] (k+1-j)^n,$$ where we define $\binom{n}{-1} = \binom{n}{k+1} = 0$ for the endpoints. Using Pascal's identity $\binom{n}{j} + \binom{n}{j-1} = \binom{n+1}{j}$, we obtain $$P(\lfloor S_n \rfloor = k) = \frac{1}{n!} \sum_{j=0}^{k+1} (-1)^j \binom{n+1}{j} (k+1-j)^n.$$

The term for $j = k+1$ is $(-1)^{k+1} \binom{n+1}{k+1} 0^n = 0$ (since $n \ge 1$), so the sum equals $$\frac{1}{n!} \sum_{j=0}^{k} (-1)^j \binom{n+1}{j} (k+1-j)^n.$$

By Euler's formula (13) in the text, $$\left\langle {n \atop k} \right\rangle = \sum_{j=0}^{k} (-1)^j \binom{n+1}{j} (k+1-j)^n,$$ which is exactly the Eulerian number. Therefore, $$P(\lfloor U_1 + \cdots + U_n \rfloor = k) = \frac{ \left\langle {n \atop k} \right\rangle }{ n! } \qquad \text{for } 0 \le k \le n-1,$$ and the probability is $0$ for all other $k$.

\boxed{ P(\lfloor U_1 + \cdots + U_n \rfloor = k) = \begin{cases} \dfrac{ \left\langle {n \atop k} \right\rangle }{ n! }, & 0 \le k \le n-1, \[1em] 0, & \text{otherwise.} \end{cases} }

∎