TAOCP 4.3.1 Exercise 42
Let N=b^n, and let
Section 4.3.1: The Classical Algorithms
Exercise 42. [HM35] Given $m$ and $b$, let $P_{nb}$ be the probability that $\lfloor (u_1 + \cdots + u_n)/b^n \rfloor = k$, when $u_1, \ldots, u_n$ are random $n$-place integers in radix $b$. (This is the distribution of $w_n$ in the column addition algorithm of exercise 2.) Show that $P_{nb} = \binom{n}{k} / \binom{2n}{n} + O(b^{-n})$, where $\binom{n}{k}$ is an Eulerian number (see Section 5.1.3).
Verified: yes
Solve time: 1m49s
Setup
Let
$$ N=b^n, $$
and let
$$ S=u_1+\cdots+u_n, $$
where $u_1,\ldots,u_n$ are independent uniformly distributed $n$-place integers. Thus each $u_i$ is uniformly distributed on
$$ {0,1,\ldots,N-1}. $$
We are to determine the probability
$$ P_{nb}(k) =\Pr!\left(\left\lfloor\frac{S}{N}\right\rfloor=k\right). $$
Equivalently,
$$ P_{nb}(k) =\frac{1}{N^n} #\Bigl{(a_1,\ldots,a_n): 0\le a_i<N,, kN\le a_1+\cdots+a_n<(k+1)N \Bigr}. $$
The exercise asks us to show that
$$ P_{nb}(k) =\frac{\left\langle{n\atop k}\right\rangle}{n!} +O(b^{-n}), $$
where $\left\langle{n\atop k}\right\rangle$ denotes the Eulerian number of Section 5.1.3.
Solution
Define
$$ R_N(k)= \Bigl{ (x_1,\ldots,x_n): 0\le x_i<1,, k\le x_1+\cdots+x_n<k+1 \Bigr}. $$
Each lattice point
$$ (a_1,\ldots,a_n)\in{0,\ldots,N-1}^n $$
corresponds to the point
$$ \left(\frac{a_1}{N},\ldots,\frac{a_n}{N}\right) \in [0,1)^n. $$
Hence $P_{nb}(k)$ is exactly the proportion of the $N^n$ grid points of mesh $1/N$ that lie in $R_N(k)$.
The boundary of $R_N(k)$ is contained in the union of the hyperplanes
$$ x_1+\cdots+x_n=k, \qquad x_1+\cdots+x_n=k+1, $$
together with portions of the coordinate hyperplanes $x_i=0,1$. Its $(n-1)$-dimensional measure is bounded independently of $N$. Therefore the standard lattice-point estimate gives
$$ #\bigl(R_N(k)\cap N^{-1}\mathbf Z^n\bigr) = N^n,\operatorname{vol}(R_N(k)) +O(N^{,n-1}), $$
and consequently
$$ P_{nb}(k) = \operatorname{vol}(R_N(k)) +O(N^{-1}). $$
Since $N=b^n$,
$$ P_{nb}(k) = \operatorname{vol}(R_N(k)) +O(b^{-n}). \tag{1} $$
It remains to compute $\operatorname{vol}(R_N(k))$.
Let
$$ F_n(t) = \operatorname{vol} \Bigl{ (x_1,\ldots,x_n): 0\le x_i<1,, x_1+\cdots+x_n<t \Bigr}. $$
By inclusion-exclusion,
$$ F_n(t) = \frac1{n!} \sum_{j\ge0} (-1)^j \binom{n}{j} (t-j)_+^{,n}, \tag{2} $$
where $(y)_+=\max(y,0)$.
For $k\le t\le k+1$ only the terms $0\le j\le k$ contribute, so
$$ F_n(k+1)-F_n(k) = \frac1{n!} \sum_{j=0}^{k} (-1)^j \binom{n+1}{j} (k+1-j)^n. \tag{3} $$
The right-hand side is the classical explicit formula for the Eulerian number:
$$ \left\langle{n\atop k}\right\rangle = \sum_{j=0}^{k} (-1)^j \binom{n+1}{j} (k+1-j)^n. $$
Therefore
$$ \operatorname{vol}(R_N(k)) = F_n(k+1)-F_n(k) = \frac{\left\langle{n\atop k}\right\rangle}{n!}. \tag{4} $$
Substituting (4) into (1) yields
$$ P_{nb}(k) = \frac{\left\langle{n\atop k}\right\rangle}{n!} + O(b^{-n}). $$
This is the desired asymptotic formula. ∎
Verification
The Eulerian numbers satisfy
$$ \sum_{k=0}^{n-1} \left\langle{n\atop k}\right\rangle =n!. $$
Hence
$$ \sum_{k=0}^{n-1} \frac{\left\langle{n\atop k}\right\rangle}{n!} =1. $$
The limiting probabilities therefore form a probability distribution.
For $n=2$,
$$ \left\langle{2\atop0}\right\rangle = \left\langle{2\atop1}\right\rangle =1, $$
so the theorem gives
$$ P_{2b}(0)=P_{2b}(1) =\frac12+O(b^{-2}), $$
which agrees with the symmetry of the sum of two independent uniform variables.
Notes
The limiting distribution is the distribution of
$$ \left\lfloor X_1+\cdots+X_n\right\rfloor, $$
where $X_1,\ldots,X_n$ are independent random variables uniformly distributed on $[0,1)$. The probability that this quantity equals $k$ is exactly
$$ \frac{\left\langle{n\atop k}\right\rangle}{n!}, $$
which explains the appearance of Eulerian numbers in the carry distribution for column addition.