ANALYSIS of ALGORITHMS, Bulletin Board

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


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

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


Date Prev | Date Next | Date Index | Thread Index