A riedel computation. (V) Was re. Quickselect and inversions.

[Marko Riedel <mriedel@neuearbeit.de>]

Greetings.

The induction proof is now complete.

Regards,

Marko Riedel

----------------------------------------------------------------------


\documentclass{article}

\usepackage{latexsym,amsfonts,amssymb,amsmath,amstext,amsthm}

\begin{document}

\newcommand{\half}{\frac{1}{2}}
\newcommand{\thrd}{\frac{1}{3}}
\newcommand{\qurt}{\frac{1}{4}}
\newcommand{\sxth}{\frac{1}{6}}
\newcommand{\octa}{\frac{1}{8}}
\newcommand{\dode}{\frac{1}{12}}

\newcommand{\PAR} [1]{\left(#1\right)}
\newcommand{\MAND}  {\quad \text{and   }  \quad}
\newcommand{\MWHERE}{\quad \text{where }  \quad}

\title{Quickselect and inversions}

\author{Marko Riedel}
\maketitle

\section{Recurrence relation}

Consider the following question. What amount of disorder is left in a
permutation after one of its elements has been selected with
quickselect?

This can be rephrased as follows. Compute the "grand average" for the
expected number of inversions left in a permutation after one of its
elements has been selected with quickselect.

Let $r_n(z)$ be the exponential generating function of the inversions
in a random permutation of size $n$, where $0, 1,\ldots n-1$ are the
elements being permuted. We have

\[ r_n(z) = 
  \frac{1}{n!}
  \prod_{k=0}^{n-1} \sum_{l=0}^k z^l =
  \frac{1}{n!}
  \prod_{k=0}^{n-1} \frac{z^{k+1}-1}{z-1}.\]

Let $q_{n, j}(z)$ be the exponential generating function of the number
of inversions after the element $j$, where $1 \le j \le n$ has been
selected from a random permutation of size $n$. The base cases are:
$n=1$ and $q_{1, 1}(z) = 1/1 = 1$ and $n=2$ and $q_{2, 1}(z) = q_{2,
2}(z) = 2/2 = 1.$ We let $r_0(z) = q_{0, j}(z) = 1.$ Let $p$ denote
the pivot, where $1 \le p \le n$. The recurrence for $q_{n, j}(z)$ is
as follows.
\begin{eqnarray*}
 q_{n, j}(z)  & = &
  \frac{1}{n} 
  \sum_{p=1}^{j-1} r_{p-1}(z) q_{n-p, j-p}(z) \\
   & + & \frac{1}{n} r_{j-1}(z) r_{n-j}(z)    \\
   & + & \frac{1}{n} \sum_{p=j+1}^n q_{p-1, j}(z) r_{n-p}(z).
\end{eqnarray*}

We are interested in the asymptotics of
\[ \frac{q_n'(1)}{n}
   \MWHERE
   q_n(z) = \sum_{j=1}^n q_{n, j}(z).\]

\newpage

{\bf Claim.} We have
\[ q_{n, j}'(1) = 
   \octa (n+1-j)(n-4-j) + \octa j(j-5)+
   \half H_{n+1-j} + \half H_j.\]

{\bf Proof.} Use induction. Indeed $q_{1, 1} = -4 \octa - 4 \octa +
\half H_1 + \half H_1 = -1 + 1 = 0$, $q_{2, 1} = -6 \octa - 4 \octa +
\half H_2 + \half H_1 = 0$ and $q_{2, 2} = -4 \octa - 6 \octa + \half
H_1 + \half H_2 = 0.$

Note that $r_n(1) = 1, r_n'(1) = \qurt n (n-1)$ and $q_{n, l}(1) = 1.$

Compute the recurrence relation for $q_{n, j}'(1).$
We have
\begin{eqnarray*}
 q_{n, j}'(z)  & = &
  \frac{1}{n} 
  \sum_{p=1}^{j-1} r_{p-1}'(z) q_{n-p, j-p}(z)
  + \frac{1}{n} 
  \sum_{p=1}^{j-1} r_{p-1}(z) q_{n-p, j-p}'(z) \\
   & + & \frac{1}{n} r_{j-1}'(z) r_{n-j}(z)
     +   \frac{1}{n} r_{j-1}(z) r_{n-j}'(z)    \\
   & + & \frac{1}{n} \sum_{p=j+1}^n q_{p-1, j}'(z) r_{n-p}(z)
     +  \frac{1}{n} \sum_{p=j+1}^n q_{p-1, j}(z) r_{n-p}'(z)
\end{eqnarray*}
and hence for $1 < j < n$
\begin{eqnarray*}
 q_{n, j}'(1)  & = &
  \frac{1}{n} 
  \sum_{p=1}^{j-1} \qurt (p-1)(p-2)
  + \frac{1}{n} 
  \sum_{p=1}^{j-1} q_{n-p, j-p}'(1)     \\       
   & + & \frac{1}{n} \qurt (j-1)(j-2)
     +   \frac{1}{n} \qurt (n-j)(n-j-1) \\
   & + & \frac{1}{n} \sum_{p=j+1}^n q_{p-1, j}'(1)
     +   \frac{1}{n} \sum_{p=j+1}^n \qurt (n-p)(n-p-1),
\end{eqnarray*}
for $j=1$
\[
 q_{n, 1}'(1) =
         \frac{1}{n} \qurt (n-1)(n-2)
     +   \frac{1}{n} \sum_{p=2}^n q_{p-1, 1}'(1)
     +   \frac{1}{n} \sum_{p=2}^n \qurt (n-p)(n-p-1),
\]
and for $j=n$
\[
 q_{n, n}'(1)  =
    \frac{1}{n} \sum_{p=1}^{n-1} \qurt (p-1)(p-2)
  + \frac{1}{n} \sum_{p=1}^{n-1} q_{n-p, n-p}'(1)
  + \frac{1}{n} \qurt (n-1)(n-2).
\]
Note that
\[ \sum_{p=2}^n (n-p)(n-p-1) =
   \sum_{p=1}^{n-1} (p-1)(p-2) = 
   \thrd n^3 - 2 n^2 + \frac{11}{3} n - 2
\]
and so the above becomes
\[
 q_{n, 1}'(1) =
         \sxth - \qurt n + \dode n^2     
     +   \frac{1}{n} \sum_{p=2}^n q_{p-1, 1}'(1),
\]
for $j=1$,
\[
 q_{n, n}'(1)  =
         \sxth - \qurt n + \dode n^2     
     +   \frac{1}{n} \sum_{p=1}^{n-1} q_{n-p, n-p}'(1)
\]
for $j=n$, and
\begin{eqnarray*}
 q_{n, j}'(1)  & = &
  \frac{1}{4n} 
  \PAR{\thrd j^3 - 2 j^2 
     + \frac{11}{3} j - 2}
  + \frac{1}{n} 
  \sum_{p=1}^{j-1} q_{n-p, j-p}'(1)     \\       
   & + & \frac{1}{4n} (j-1)(j-2)
     +   \frac{1}{4n} (n-j)(n-j-1) 
     +   \frac{1}{n} \sum_{p=j+1}^n q_{p-1, j}'(1) \\
   & + & 
  \frac{1}{4n}
  \PAR{\thrd (n-j+1)^3 - 2 (n-j+1)^2 
     + \frac{11}{3} (n-j+1) - 2}
\end{eqnarray*}
or
\begin{eqnarray*}
 q_{n, j}'(1)  & = &
    \frac{1}{n} \sum_{p=1}^{j-1} q_{n-p, j-p}'(1) 
  + \frac{1}{n} \sum_{p=j+1}^n q_{p-1, j}'(1) \\
  & + & 
  \frac{1}{4n}
  \PAR{\thrd n^3 - j n^2 + j^2 n - \thrd n + j - j^2}
\end{eqnarray*}
for $1 < j < n.$

{\bf Induction step when $j=1$ and $j=n.$} 
We need to show that
\begin{eqnarray*} 
   q_{n, 1}'(1) & = &
   \octa (n+1-1)(n-4-1) -4 \octa +
   \half H_{n+1-1} + \half \\ & = &
   \octa n(n-5) +
   \half H_n
\end{eqnarray*}
and
\[
   q_{n, n}'(1)  = 
   -4 \octa + \octa n(n-5)+
   \half + \half H_n =
   \octa n(n-5) +
   \half H_n.
\]
The cases $j=1$ and $j=n$ are completely symmetric. 
We verify the case $j=1.$
We need to show that
\[ 
  \octa n(n-5) + \half H_n =
  \sxth - \qurt n + \dode n^2 +
  \frac{1}{n} 
  \sum_{p=2}^n 
  \PAR{\octa (p-1)(p-6) + \half H_{p-1} }.\]
Note that
\[
  \sum_{p=2}^n (p-1)(p-6) = 
  \thrd n^3 - 3 n^2 + \frac{8}{3} n
  \MAND
  \sum_{p=1}^{n-1} H_p = n H_n - n
\]
and the claim follows by substitution.

{\bf Induction step when $1 < j < n.$} 
By induction
\begin{eqnarray*}
\sum_{p=1}^{j-1} q_{n-p, j-p}'(1) & = &
\sum_{p=1}^{j-1} 
\PAR{\octa (n+1-j)(n-4-j) + \octa (j-p)(j-p-5)} \\ & + &
\sum_{p=1}^{j-1} 
\PAR{\half H_{n+1-j} + \half H_{j-p}} \\ & = &
\octa (j-1)(n+1-j)(n-4-j) \\ & + &
\octa \PAR{ \thrd j^3 - 3 j^2 + \frac{8}{3} j} \\ & + &
\half (j-1) H_{n+1-j} +
\half (j H_j - j)
\end{eqnarray*}
and
\begin{eqnarray*}
\sum_{p=j+1}^n q_{p-1, j}'(1) & = &
\sum_{p=j+1}^n
\PAR{\octa (p-j)(p-5-j) + \octa j(j-5)} \\ & + &
\sum_{p=j+1}^n
\PAR{\half H_{p-j} + \half H_j} \\ & = &
\octa \PAR{ \thrd (n-j+1)^3 - 3 (n-j+1)^2 
          + \frac{8}{3} (n-j+1)} \\ & + &
\octa (n-j)j(j-5) \\ & + &
\half ((n-j+1) H_{n-j+1} - (n-j+1)) +
\half (n-j) H_j
\end{eqnarray*}
so that
\begin{eqnarray*}
\sum_{p=1}^{j-1} q_{n-p, j-p}'(1) & + &
\sum_{p=j+1}^n q_{p-1, j}'(1)  = 
\half - \qurt j n - \frac{3}{8} n^2 \\ & + & 
        \frac{1}{24} n^3
      - \qurt j   + \dode n + \qurt j^2 \\ & + &
\half (j-1) H_{n+1-j} +
\half (j H_j - j) \\ & + &
\half ((n-j+1) H_{n-j+1} - (n-j+1)) +
\half (n-j) H_j \\ & = &
      - \qurt j n - \frac{3}{8} n^2 +
        \frac{1}{24} n^3
      - \qurt j   - \frac{5}{12} n + \qurt j^2 \\ & + &
\half n H_{n+1-j} + \half n H_j.
\end{eqnarray*}
This implies that
\begin{eqnarray*}
 q_{n, j}'(1)  & = &
- \qurt j - \frac{3}{8} n + \frac{1}{24} n^2
- \qurt \frac{j}{n}   - \frac{5}{12} + \qurt \frac{j^2}{n} \\ & + &
\half H_{n+1-j} + \half H_j
+ \frac{1}{4n}
  \PAR{\thrd n^3 - j n^2 + j^2 n - \thrd n + j - j^2} \\ & = &
\octa n^2 + \qurt j^2 - \half 
- \qurt n j - \frac{3}{8} n - \qurt j
+ \half H_{n+1-j} + \half H_j \\ & = &
\octa (n+1-j)(n-4-j) + \octa j(j-5)+
   \half H_{n+1-j} + \half H_j
\end{eqnarray*}
as claimed.

\newpage

{\bf Trivariate generating function.}
We have
\begin{eqnarray*}
 n q_{n, j}(z) u^n v^j  & = &
   u \sum_{p=1}^{j-1} u^{p-1} v^{p-1} r_{p-1}(z) 
                      u^{n-p} v^{j-p} q_{n-p, j-p}(z)  \\
   & + & u v^j u^{j-1} r_{j-1}(z) u^{n-j} r_{n-j}(z)   \\
   & + & u \sum_{p=j+1}^n u^{p-1} v^j q_{p-1, j}(z) 
                          u^{n-p} r_{n-p}(z).
\end{eqnarray*}



References. Basic generating functions.

\end{document}