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

[Marko Riedel <mriedel@neuearbeit.de>]

Greetings.

I tried proving your result by induction or by using a trivariate
generating function. I didn't get very far with either, but I am now
convinced that induction is not the way to go (I don't have access to
Maple and couldn't simplify some of the intermediate expressions. Even
if I could have, proving the variance by induction would require a
complicated, long, and mathematically trivial computation.) So I think
the problem is best solved using generating functions. I took the
first step and multiplied the recurrence by u^n v^j and distributed
the factors among the terms on the RHS. Could you give me a hint where
to go from here?  It looks as though the LHS is a derivative of the
super-gf.

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{\octa}{\frac{1}{8}}
\newcommand{\dode}{\frac{1}{12}}

\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}'(z)  & = &
  \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$
\begin{eqnarray*}
 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),
\end{eqnarray*}
and for $j=n$
\begin{eqnarray*}
 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).
\end{eqnarray*}


{\bf Induction step when $j=1.$} 
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*}

\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}