A Problem of Counting Expectation of Inversions in a Half-Sorted List.

Question

Has any one got any idea about this problem? I found my formula is too complicated to get a closed form.

Let $P_{2n}$ be the set of all $(2n)!$ permutations of $\{1,2,3,···,2n\}$. For any $\sigma = (a_1,a_2,···,a_{2n})$ in $P_{2n}$, a pair of positions $(i,j)$ such that $i < j$ is called an inversion in $\sigma$ if $a_i > a_j$. For example, in the permutation $(a_1,a_2,a_3,a_4) = (2,4,1,3)$, $(2,4)$ is an inversion as $a_2 = 4 > a_4 = 3$; in fact, in this case there are exactly $3$ inversions $(1, 3)$, $(2, 3)$, $(2, 4)$.

For any $\sigma = (a_1,a_2,···,a_{2n})$ in $P_{2n}$, let $f(\sigma)$ be the permutation obtained from $\sigma$ by sorting the sublist of odd positions. That is, $f(\sigma) =(b_1,b_2,···,b_{2n}) \in P_{2n}$, where $b_{2k} = a_{2k}$ for $1\le k\le n$, and $b_1 < b_3 < b_5 < ··· < b_{2n-1} $ is the sorted list of $a_1,a_3,···,a_{2n−1}$. For example, for $\sigma = (3,8,2,5,6,7,1,4)$, $f(\sigma) = (1,8,2,5,3,7,6,4)$.

For a random $\sigma $ uniformly chosen from $P_{2n}$, let $I_n$ be the random variable corresponding to the number of inversions in the permutation $f(\sigma)$. Determine $E(I_n)$ and $\text{Var}(I_n)$.

Answer 1

The expected number of inversions is the sum of the expected numbers of inversions among odd positions, among even positions and between odd and even positions.

Since the sublist of odd positions is sorted, there are no inversions in it, $I_{n,\text{odd}}=0$. Since the sublist of even positions is unchanged, there is the usual expected number of inversions in it, half an inversion per pair, so this is $I_{n,\text{even}}=n(n-1)/4$.

For the inversions between odd and even positions, consider an even entry and compare it to all odd entries. By symmetry, the rank of the even entry among these $n+1$ entries is uniformly distributed between $1$ and $n+1$. The number of inversions is the absolute value of the difference between this rank and the rank of the even entry in the actual positions of the entries. Thus, for instance the last even entry has equal probabilities of being part of $0,1,\dotsc,n$ inversions, the one before that, $1,0,1,\dotsc,n-1$, and so on, and the first even entry, $n-1,\dotsc,1,0,1$. The sum of the averages of these numbers is

$$ \begin{eqnarray} I_{n,\text{mixed}} &=& \frac1{n+1}\left(\sum_{k=1}^n\frac{k(k+1)}2+\sum_{k=1}^{n-1}\frac{k(k+1)}2\right) \\ &=& \frac16\frac1{n+1}(n(n+1)(n+2)+(n-1)n(n+1)) \\ &=& \frac{n(2n+1)}6\;. \end{eqnarray} $$

Thus the expected total number of inversions is

$$I_n=\frac{n(n-1)}4+\frac{n(2n+1)}6=\frac {n(7n-1)}{12}\;.$$

The variance can be calculated with a similar approach, though this is going to be a bit more messy.