Skip to main content
added 50 characters in body
Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

$\DeclareMathOperator\E{E}$LetI will show the upper bound $\E[X]=O(n^2\log n)$. Let $D(m)$ denote the number of inversions in a random permutations after applying $m$ random comparators.

It is easy to see that if $\pi$ is a permutation with $d$ inversions, and we apply a random comparator $(i,j)$ to $\pi$, then either nothing changes (if $(i,j)$ is not itself an inversion of $\pi$), or the number of inversions strictly decreases (if $(i,j)$ is an inversion, which happens with probability $d\binom n2^{-1}$). Thus, $\E[D(m+1)\mid D(m)=d]\le d-d\binom n2^{-1}$, that is,

$$\E[D(m+1)]\le\left(1-\tbinom n2^{-1}\right)\E[D(m)].$$

It follows that

$$\begin{align*} \Pr[X\ge m+1]&=\Pr[D(m)\ge1]\le\E[D(m)]\\&\le\tbinom n2\left(1-\tbinom n2^{-1}\right)^m\le\exp\left(2\log n-\tfrac{2m}{n^2}\right), \end{align*}$$

which implies

$$\begin{align*} \E[X]&\le n^2\log n+\sum_{s=1}^\infty\Pr[X\ge n^2\log n+s]\\&\le n^2\log n+\sum_{s=0}^\infty e^{-2s/n^2}=n^2\log n+O(n^2). \end{align*}$$

$\DeclareMathOperator\E{E}$Let $D(m)$ denote the number of inversions in a random permutations after applying $m$ random comparators.

It is easy to see that if $\pi$ is a permutation with $d$ inversions, and we apply a random comparator $(i,j)$ to $\pi$, then either nothing changes (if $(i,j)$ is not itself an inversion of $\pi$), or the number of inversions strictly decreases (if $(i,j)$ is an inversion, which happens with probability $d\binom n2^{-1}$). Thus, $\E[D(m+1)\mid D(m)=d]\le d-d\binom n2^{-1}$, that is,

$$\E[D(m+1)]\le\left(1-\tbinom n2^{-1}\right)\E[D(m)].$$

It follows that

$$\begin{align*} \Pr[X\ge m+1]&=\Pr[D(m)\ge1]\le\E[D(m)]\\&\le\tbinom n2\left(1-\tbinom n2^{-1}\right)^m\le\exp\left(2\log n-\tfrac{2m}{n^2}\right), \end{align*}$$

which implies

$$\begin{align*} \E[X]&\le n^2\log n+\sum_{s=1}^\infty\Pr[X\ge n^2\log n+s]\\&\le n^2\log n+\sum_{s=0}^\infty e^{-2s/n^2}=n^2\log n+O(n^2). \end{align*}$$

$\DeclareMathOperator\E{E}$I will show the upper bound $\E[X]=O(n^2\log n)$. Let $D(m)$ denote the number of inversions in a random permutations after applying $m$ random comparators.

It is easy to see that if $\pi$ is a permutation with $d$ inversions, and we apply a random comparator $(i,j)$ to $\pi$, then either nothing changes (if $(i,j)$ is not itself an inversion of $\pi$), or the number of inversions strictly decreases (if $(i,j)$ is an inversion, which happens with probability $d\binom n2^{-1}$). Thus, $\E[D(m+1)\mid D(m)=d]\le d-d\binom n2^{-1}$, that is,

$$\E[D(m+1)]\le\left(1-\tbinom n2^{-1}\right)\E[D(m)].$$

It follows that

$$\begin{align*} \Pr[X\ge m+1]&=\Pr[D(m)\ge1]\le\E[D(m)]\\&\le\tbinom n2\left(1-\tbinom n2^{-1}\right)^m\le\exp\left(2\log n-\tfrac{2m}{n^2}\right), \end{align*}$$

which implies

$$\begin{align*} \E[X]&\le n^2\log n+\sum_{s=1}^\infty\Pr[X\ge n^2\log n+s]\\&\le n^2\log n+\sum_{s=0}^\infty e^{-2s/n^2}=n^2\log n+O(n^2). \end{align*}$$

Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

$\DeclareMathOperator\E{E}$Let $D(m)$ denote the number of inversions in a random permutations after applying $m$ random comparators.

It is easy to see that if $\pi$ is a permutation with $d$ inversions, and we apply a random comparator $(i,j)$ to $\pi$, then either nothing changes (if $(i,j)$ is not itself an inversion of $\pi$), or the number of inversions strictly decreases (if $(i,j)$ is an inversion, which happens with probability $d\binom n2^{-1}$). Thus, $\E[D(m+1)\mid D(m)=d]\le d-d\binom n2^{-1}$, that is,

$$\E[D(m+1)]\le\left(1-\tbinom n2^{-1}\right)\E[D(m)].$$

It follows that

$$\begin{align*} \Pr[X\ge m+1]&=\Pr[D(m)\ge1]\le\E[D(m)]\\&\le\tbinom n2\left(1-\tbinom n2^{-1}\right)^m\le\exp\left(2\log n-\tfrac{2m}{n^2}\right), \end{align*}$$

which implies

$$\begin{align*} \E[X]&\le n^2\log n+\sum_{s=1}^\infty\Pr[X\ge n^2\log n+s]\\&\le n^2\log n+\sum_{s=0}^\infty e^{-2s/n^2}=n^2\log n+O(n^2). \end{align*}$$