TAOCP 5.1.1 Exercise 26
Let \(\pi = a_1 a_2 \ldots a_n\) be a uniformly random permutation of \(\{1,2,\ldots,n\}\).
Exercise 26. [M25] What is the statistical correlation coefficient between the number of inversions and the index of a random permutation? (See Eq. 3.3.2–(24).)
Verified: yes
Solve time: 17m07s
Solution
Let (\pi = a_1 a_2 \ldots a_n) be a uniformly random permutation of ({1,2,\ldots,n}).
Define the number of inversions and the index as
[ \operatorname{inv}(\pi) = \sum_{1\le i<j\le n} X_{i,j}, \qquad X_{i,j} = \mathbf{1}{[a_i > a_j]}, ] [ \operatorname{ind}(\pi) = \sum{k=1}^{n-1} k, Y_k, \qquad Y_k = \mathbf{1}{[a_k > a{k+1}]}. ]
From the text (Eqs. (12) and (13)) we have
[ \mathbb{E}[\operatorname{inv}] = \mathbb{E}[\operatorname{ind}] = \frac{n(n-1)}{4}, \qquad \operatorname{Var}(\operatorname{inv}) = \operatorname{Var}(\operatorname{ind}) = \frac{n(2n+5)(n-1)}{72}. ]
The correlation coefficient is
[ \rho = \frac{\operatorname{Cov}(\operatorname{inv},\operatorname{ind})} {\sqrt{\operatorname{Var}(\operatorname{inv})\operatorname{Var}(\operatorname{ind})}} = \frac{\operatorname{Cov}(\operatorname{inv},\operatorname{ind})} {\operatorname{Var}(\operatorname{inv})}, ]
so we only need (\operatorname{Cov}(\operatorname{inv},\operatorname{ind})).
By linearity of covariance,
[ \operatorname{Cov}(\operatorname{inv},\operatorname{ind}) = \sum_{1\le i<j\le n} \sum_{k=1}^{n-1} k; \operatorname{Cov}(X_{i,j}, Y_k). ]
For fixed (i<j) and (k) we examine the overlap of the two index sets ({i,j}) and ({k,k+1}).
-
Four distinct indices (({i,j}\cap{k,k+1}=\varnothing)).
The relative order of the four values at these positions is uniform over the (4!) permutations. The events (X_{i,j}=1) and (Y_k=1) are independent, each having probability (1/2); hence their covariance is (0). -
Exactly one common index.
There are four subcases:Subcase Conditions Inequalities Probability Covariance 2a (i=k,; j\ge k+2) (a_k>a_j,; a_k>a_{k+1}) (1/3) (+1/12) 2b (j=k+1,; i\le k-1) (a_i>a_{k+1},; a_k>a_{k+1}) (1/3) (+1/12) 2c (i=k+1,; j\ge k+2) (a_{k+1}>a_j,; a_k>a_{k+1}) (1/6) (-1/12) 2d (j=k,; i\le k-1) (a_i>a_k,; a_k>a_{k+1}) (1/6) (-1/12) For a given (k), the number of choices for the free index is (n-k-1) in cases 2a and 2c, and (k-1) in cases 2b and 2d. Summing over (k) gives
[ \sum_{k=1}^{n-1} k\bigl[(n-k-1)(1/12) + (k-1)(1/12)
- (n-k-1)(-1/12) + (k-1)(-1/12)\bigr] = 0. ]
-
Two common indices (({i,j}={k,k+1})).
This happens only for (i=k,; j=k+1). Then (X_{i,j}=Y_k), so (\operatorname{Cov}(X_{i,j},Y_k) = \operatorname{Var}(Y_k) = \frac14).
Thus the only non‑zero contributions come from the pairs ((i,j)=(k,k+1)):
[ \operatorname{Cov}(\operatorname{inv},\operatorname{ind}) = \sum_{k=1}^{n-1} k\cdot\frac14 = \frac{1}{4}\cdot\frac{n(n-1)}{2} = \frac{n(n-1)}{8}. ]
Finally,
[ \rho = \frac{n(n-1)/8}{n(2n+5)(n-1)/72} = \frac{72}{8(2n+5)} = \frac{9}{2n+5}. ]
\boxed{\dfrac{9}{2n+5}}
∎