5
$\begingroup$

Let $\pi$ be a permutation of $\{1,2,...,n\}$. A pair of elements ($\pi_i$,$\pi_j$) is called an inversion if $i$ $>$ $j$ and $\pi_i$ $<$ $\pi_j$. The total number of inversions in $\pi$ is denoted by $\mathrm{Inv}(\pi$). My question is: How can one estimate the inverse moment of $\mathrm{Inv}(\pi$), $E\left(\frac{1}{\mathrm{Inv}(\pi)}\right)$? (I don't know if there is an issue with the fact that $Inv$($\pi$) can evaluate to 0. In case it does, assume that we want to estimate the inverse moment of $\mathrm{Inv}^{\prime}(\pi) = \mathrm{Inv}(\pi) + 1$)

All that I know is that the expected number of inversions in a random permutation $\pi$, $E(\mathrm{Inv}(\pi)$), of size $n$ is $\frac{n^2 - n}{4}$. Then, Jensen’s inequality yields $E$($\frac{1}{Inv(\pi)}$) $\geq$ $\frac{1}{E(\mathrm{Inv}(\pi))}$, but I need a better (asymptotic) approximation for $E$($\frac{1}{\mathrm{Inv}(\pi)}$).

$\endgroup$
3
  • $\begingroup$ For Inv' you are asking about $\int_0^1 (1+x)(1+x+x^2)\cdots (1+x+\cdots+x^{n-1})dx $, though I don't see how to estimate this integral. $\endgroup$ May 8, 2014 at 21:32
  • $\begingroup$ One approach may be to use the fact that the components of the inversion table sum to the number of inversions, and the components are independent random variables, with the kth component having uniform distribution on {0,1,2,...,k-1}. Note this is assuming your permutations are selected uniformly (which you havent said). $\endgroup$
    – PeterR
    May 9, 2014 at 13:11
  • $\begingroup$ You might also consider E(1/Inv(pi)) where you draw pi from nonidentical permutations. If you look at those generated by a few neighboring transpositions (12),(23),(34),... you will find a small number of permutations with small number of inversions, and the expected value will not just be less than 1/n but tend to something over n^2, where I would not be surprised if the something were n^{1/2}. Gerhard "Dividing By Zero: Not Good" Paseman, 2014.05.09 $\endgroup$ May 9, 2014 at 19:32

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.