TAOCP 5.1.3 Exercise 7
Let $X_n$ denote the number of descents in a random permutation of ${1,2,\dots,n}$.
Exercise 7. [HM40] [HM40] Is the probability distribution of runs, given by (14), asymptotically normal? (See exercise 1.2.10-13.)
Verified: yes
Solve time: 1m57s
Setup
Let $X_n$ denote the number of descents in a random permutation of ${1,2,\dots,n}$. Then $X_n$ takes values $k=0,1,\dots,n-1$ with probability
$\mathbb{P}(X_n=k)=\frac{\left\langle \begin{matrix} n \ k \end{matrix} \right\rangle}{n!}.$
The generating polynomial
$g_n(z)=\sum_{k=0}^{n-1} \left\langle \begin{matrix} n \ k \end{matrix} \right\rangle z^k$
is the probability generating function up to normalization:
$\mathbb{E}(z^{X_n})=\frac{g_n(z)}{n!}.$
Exercise 5.1.3.7 asks whether the distribution of $X_n$ is asymptotically normal after centering and scaling.
The mean and variance are given in Section 5.1.3 by symmetry and differentiation of $g_n$:
$\mathbb{E}(X_n)=\frac{n-1}{2}, \qquad \mathrm{Var}(X_n)=\frac{n+1}{12}.$
Solution
Write $X_n$ as a sum of indicator variables
$X_n=\sum_{i=1}^{n-1} I_i,$
where $I_i=1$ if $a_i>a_{i+1}$ and $I_i=0$ otherwise.
Each $I_i$ depends only on the relative order of $(a_i,a_{i+1})$. For any collection of indices $i_1,\dots,i_r$, the joint moment
$\mathbb{E}(I_{i_1}\cdots I_{i_r})$
depends only on the relative order structure of the positions involved. If the indices split into two sets separated by a gap of at least $2$, the corresponding groups of indicators are independent, since disjoint blocks of entries in a random permutation are independent after relabeling ranks. Therefore dependencies occur only when indices are within distance $1$, so the family $(I_i)$ has a dependency graph in which each vertex $i$ is adjacent only to $i-1$ and $i+1$.
Fix an integer $r\ge 3$. The $r$th joint cumulant of $X_n$ is a sum of joint cumulants of products $I_{i_1},\dots,I_{i_r}$. A nonzero contribution requires the indices $i_1,\dots,i_r$ to form a connected set in the dependency graph, hence the set ${i_1,\dots,i_r}$ must lie inside an interval of length at most $r-1$. The number of such index choices is $O(n)$, since the left endpoint of the interval can be chosen in at most $n$ ways and the remaining indices lie in a bounded window.
Each bounded configuration contributes a quantity depending only on $r$, since the joint distribution of a fixed pattern of comparisons among finitely many consecutive elements is independent of $n$ once $n$ is large enough. Therefore the $r$th cumulant $\kappa_r(X_n)$ satisfies
$\kappa_r(X_n)=O(n).$
For $r=1$ and $r=2$, this reproduces $\kappa_1(X_n)=\mathbb{E}(X_n)$ and $\kappa_2(X_n)=\mathrm{Var}(X_n)$, both of order $n$ with leading term $\frac{n}{2}$ and $\frac{n}{12}$ respectively.
Define the standardized variable
$Z_n=\frac{X_n-\mathbb{E}(X_n)}{\sqrt{\mathrm{Var}(X_n)}}.$
The $r$th cumulant of $Z_n$ satisfies
$\kappa_r(Z_n)=\frac{\kappa_r(X_n)}{\mathrm{Var}(X_n)^{r/2}}.$
Since $\kappa_r(X_n)=O(n)$ and $\mathrm{Var}(X_n)\sim \frac{n}{12}$, it follows that
$\kappa_r(Z_n)=O!\left(n^{1-r/2}\right).$
For every fixed $r\ge 3$, the exponent $1-r/2$ is negative, hence
$\lim_{n\to\infty}\kappa_r(Z_n)=0.$
All cumulants of order at least $3$ vanish in the limit, while the first two cumulants of $Z_n$ are $0$ and $1$. The cumulant generating function of $Z_n$ therefore converges pointwise in a neighborhood of $0$ to $t^2/2$, which is the cumulant generating function of the standard normal law. Hence $Z_n$ converges in distribution to $\mathcal{N}(0,1)$.
This completes the proof. ∎
Verification
The key structural claim is that the dependency graph of the indicators $I_i$ has maximum degree $2$. This follows directly from the definition $I_i=1[a_i>a_{i+1}]$, since $I_i$ and $I_j$ involve disjoint sets of permutation entries whenever $|i-j|\ge 2$, and such disjoint sets become independent under uniform random permutation after conditioning on relative ranks.
The bound $\kappa_r(X_n)=O(n)$ uses that a nonzero joint cumulant requires connectedness in this graph. Any connected selection of $r$ indices lies in an interval of length at most $r-1$, which yields $O(n)$ placements.
The variance scaling $\mathrm{Var}(X_n)\sim n/12$ matches the known value $\frac{n+1}{12}$ from Section 5.1.3, ensuring the normalization is of order $n^{1/2}$ and therefore sufficient to force $\kappa_r(Z_n)\to 0$ for $r\ge 3$.
Notes
The argument is a special case of a general central limit theorem for sums of locally dependent random variables. In modern terms, $(I_i)$ form a dependency graph of bounded degree, so the standardized sum satisfies a central limit theorem by cumulant control or Stein’s method. The Eulerian numbers therefore lie in the same universality class as other permutation statistics with bounded interaction range.