Skip to main content
Formatting improvements.
Source Link
Davide Giraudo
  • 4k
  • 2
  • 30
  • 42

Let $\pi$ be a permutation of {1,2,...,n}$\{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 $Inv$($\pi$$\mathrm{Inv}(\pi$). My question is: How can one estimate the inverse moment of $Inv$($\pi$$\mathrm{Inv}(\pi$), $E$($\frac{1}{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 $Inv^{\prime}$($\pi$) $=$ $Inv$($\pi$) $+$ $1$$\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$($Inv$($\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(Inv(\pi))}$$\frac{1}{E(\mathrm{Inv}(\pi))}$, but I need a better (asymptotic) approximation for $E$($\frac{1}{Inv(\pi)}$$\frac{1}{\mathrm{Inv}(\pi)}$).

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 $Inv$($\pi$). My question is: How can one estimate the inverse moment of $Inv$($\pi$), $E$($\frac{1}{Inv(\pi)}$)? (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 $Inv^{\prime}$($\pi$) $=$ $Inv$($\pi$) $+$ $1$)

All that I know is that the expected number of inversions in a random permutation $\pi$, $E$($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(Inv(\pi))}$, but I need a better (asymptotic) approximation for $E$($\frac{1}{Inv(\pi)}$).

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

Source Link

Inverse moment of the number of inversions of a permutation

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 $Inv$($\pi$). My question is: How can one estimate the inverse moment of $Inv$($\pi$), $E$($\frac{1}{Inv(\pi)}$)? (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 $Inv^{\prime}$($\pi$) $=$ $Inv$($\pi$) $+$ $1$)

All that I know is that the expected number of inversions in a random permutation $\pi$, $E$($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(Inv(\pi))}$, but I need a better (asymptotic) approximation for $E$($\frac{1}{Inv(\pi)}$).