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)}$).

Improve this question
$\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$
    – Richard Stanley
    Commented 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
    Commented 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$
    – Gerhard Paseman
    Commented May 9, 2014 at 19:32

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .