ANALYSIS of ALGORITHMS, Bulletin Board

# Quickselect and the distance to the identity permutation. (III)


Greetings.

I have computed the DE for the second factorial moment of the expected
distance from the identity permutation. I was not able to solve it
with MAXIMA (the URL is http://www.ma.utexas.edu/maxima.html),
although I tried for quite some time.

I am sending what I have.

Best regards,

Marko Riedel

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

\documentclass{article}

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

\begin{document}

\newcommand{\half}{\frac1{2}}
\newcommand{\thrd}{\frac1{3}}
\newcommand{\qurt}{\frac1{4}}
\newcommand{\ffth}{\frac1{5}}
\newcommand{\sxth}{\frac1{6}}
\newcommand{\octa}{\frac1{8}}
\newcommand{\dode}{\frac1{12}}

\newcommand{\EVAL}[2]{\left. #1 \right|_{#2}}

\newcommand{\PAR} [1]{\left(#1\right)}

\newcommand{\DZ} {\frac{\partial}{\partial z}}
\newcommand{\DV} {\frac{\partial}{\partial v}}
\newcommand{\DVV}{\frac{\partial}{\partial v^2}}

\title{Quickselect and the distance to the identity permutation}

\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 distance to the identity permutation of a permutation after
one of its elements has been selected with quickselect, where $1, 2,\ldots n$ are the elements being permuted and the distance is
given by

$\sum_{m=1}^n \PAR{ m - p_m }^p,$

$p>1$ and $p$ even.

Let $r_n(v)$ be the exponential generating function of the distance to
the identity permutation of a random permutation of size $n$. We have
$r_n(1) = 1$ and

$r_n'(1) = \frac{2}{n} \sum_{k=1}^{n - 1} k^p \: (n - k) \MAND r_n''(1) = \frac{2}{n} \sum_{k=1}^{n - 1} k^p \: (k^p - 1) \: (n - k) .$

Recall that
\begin{eqnarray*}
\sum_{k = 1}^n k^2 & = &
\thrd n^3 + \half n^2 + \sxth n                       \\
\sum_{k = 1}^n k^3 & = &
\qurt n^4 + \half n^3 + \qurt n^2                     \\
\sum_{k = 1}^n k^4 & = &
\ffth n^5 + \half n^4 + \thrd n^3 - \frac1{30} n      \\
\sum_{k = 1}^n k^5 & = &
\sxth n^6 + \half n^5 + \frac{5}{12} n^4 - \dode n^2.
\end{eqnarray*}

This yields
\begin{eqnarray*}
r_n'(1) & = &
\frac{2}{n} \: n \:
\PAR { \thrd (n-1)^3 + \half (n-1)^2 + \sxth (n-1)   } \\
& - &
\frac{2}{n} \:
\PAR { \qurt (n-1)^4 + \half (n-1)^3 + \qurt (n-1)^2 }
\end{eqnarray*}
for $k=2$ and
\begin{eqnarray*}
r_{n,4}'(1) & = &
\frac{2}{n} \: n \:
\PAR { \ffth (n-1)^5 + \half (n-1)^4
+ \thrd (n-1)^3 - \frac1{30} (n-1) } \\
& - &
\frac{2}{n} \:
\PAR { \sxth (n-1)^6 + \half (n-1)^5
+ \frac{5}{12} (n-1)^4 - \dode (n-1)^2}
\end{eqnarray*}
for $k=4.$

Hence
\begin{eqnarray*}
r_n'(1)
& = & \sxth      \: n \PAR { n^2 - 1 }
\MAND \\
r_{n, 4}'(1)
& = & \frac1{30} \: n \PAR { n^2 - 1 } \PAR{ 2 n^2 - 3 }.
\end{eqnarray*}

Compute $r_n''(1)$ for $k=2$, as follows:
\begin{eqnarray*}
r_n''(1) & = &
\frac{2}{n} \sum_{k=1}^{n - 1}
\PAR{ n k^4 - k^5 - n k^2 + k^3 } \\ & = &
r_{n, 4}'(1) - r_n'(1) =
\frac1{15} (n - 2) (n - 1) n (n + 1) (n + 2).
\end{eqnarray*}

Let $q_{n, j}(v)$ 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}(v) = 1/1 = 1$ and $n=2$ and $q_{2, 1}(v) = q_{2, 2}(v) = 2/2 = 1.$ We let $r_0(v) = q_{0, j}(v) = 1.$ Let $p$ denote
the pivot, where $1 \le p \le n$. The recurrence for $q_{n, j}(v)$ is
as follows.
\begin{eqnarray*}
q_{n, j}(v)  & = &
\frac1{n}
\sum_{p=1}^{j-1} r_{p-1}(v) q_{n-p, j-p}(v) \\
& + & \frac1{n} r_{j-1}(v) r_{n-j}(v)    \\
& + & \frac1{n} \sum_{p=j+1}^n q_{p-1, j}(v) r_{n-p}(v).
\end{eqnarray*}

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

\newpage

\section{Trivariate generating function}

Let
$R(z, v) = \sum_{n \ge 1} r_n(v) z^n$
and
$F(z, u, v) = \sum q_{n,j}(v) u^j z^n.$
Recall that $r_n(1) = 1, r_n'(1) = \sxth n \PAR { n^2 - 1 }, r_n''(1) = \frac1{15} n (n^2 - 1) (n^ - 4)$ and
$q_{n, l}(1) = 1$ and hence
\begin{eqnarray*}
F(z, u, 1) & = & \sum_{n \ge 1} \sum_{j=1}^n u^j z^n =
\sum_{n \ge 1} z^n
\PAR{ -1 + \frac{1 - u^{n+1}}{1 - u}} \\
& = & - \frac{z}{1 - z}
+ \frac{1}{1 - u} \frac{z}{1 - z}
- \frac{u}{1 - u} \frac{z u}{1 - z u} \\
& = &   \frac{z u}{(1 - z)(1 - z u)},
\end{eqnarray*}
$R(z, 1) = \frac1{1 - z},$
$\PAR{ \DV R(z, v) }(z, 1) = \sxth z^3 \PAR{ \frac1{1-z} }''' + \half z^2 \PAR{ \frac1{1-z} }'' = \frac{z^2}{(1 - z)^4},$
and
$\PAR{ \DVV R(z, v) }(z, 1) = \frac1{15} \: z^3 \: \PAR{\frac1{1-z} }^{(5)} = \frac{ 8 z^3 }{(1 - z)^6}.$

We have
\begin{eqnarray*}
n q_{n, j}(v) u^j z^{n-1}  & = &
u \sum_{p=1}^{j-1} r_{p-1}(v) u^{p-1} z^{p-1}
q_{n-p, j-p}(v) u^{j-p} z^{n-p}  \\
& + & u r_{j-1}(v) u^{j-1} z^{j-1} r_{n-j}(v) z^{n-j}  \\
& + &
\sum_{p=j+1}^n q_{p-1, j}(v) u^j z^{p-1} r_{n-p}(v) z^{n-p}
\end{eqnarray*}
and hence
$\DZ F(z,u,v) = u R(zu,v) F(z,u,v) + u R(zu,v) R(z,v) + R(z,v) F(z,u,v).$
Differentiate with respect to $v$ to obtain
\begin{eqnarray*}
\DV \DZ F(z,u,v) & = &
u \DV R(zu,v) F(z,u,v) + u R(zu,v) \DV F(z,u,v) \\ & + &
u \DV R(zu,v) R(z,v) + u R(zu,v) \DV R(z,v) \\ & + &
\DV R(z,v) F(z,u,v) + R(z,v) \DV F(z,u,v).
\end{eqnarray*}
Let
$G(z, u) = \EVAL{ \PAR{ \DV F(z,u,v) }}{v=1} \MAND G_1(z, u) = \EVAL{ \PAR{ \DVV F(z,u,v) }}{v=1}$
and set $v=1$ so that
\begin{eqnarray*}
\DZ G(z, u) & = &
u  \frac{z^2 u^2}{(1 - z u)^4}
\frac{z u}{(1 - z)(1 - z u)}
+ u \frac1{1 - z u} G(z, u) \\ & + &
u \frac{z^2 u^2}{(1 - z u)^4}
\frac1{1 - z}
+ u \frac1{1 - z u} \frac{z^2}{(1 - z)^4} \\ & + &
\frac{z^2}{(1 - z)^4} \frac{z u}{(1 - z)(1 - z u)}
+ \frac1{1 - z} G(z, u).
\end{eqnarray*}
or
\begin{eqnarray*}
& & \DZ G(z, u) =
\frac{1 + u - 2 z u}{(1 - z) (1 - z u)} G(z, u) \\
& & + \: u z^2
\frac{      u^4 z^4
+    u^2 z^4
-  4 u^3 z^3
-  4 u^2 z^3
+ 12 u^2 z^2
-  4 u^2 z
-  4 u   z
+    u^2
+  1
}
{(1 - z)^5 (1 - z u)^5}
\end{eqnarray*}
Solve this to obtain
$G(z,u) = - \thrd \: u z^3 \: \frac { u^3 z^3 + u^2 z^3 - 6 u^2 z^2 + 3 u^2 z + 3 u z - u^2 - 1} {(1 - z)^4 (1 - z u)^4}.$

\section{Second factorial moment}

\begin{eqnarray*}
\DVV \DZ F(z,u,v) & = &
u \DVV R(zu,v)      F(z,u,v) +
2 u \DV  R(zu,v) \DV  F(z,u,v) \\ & + &
u      R(zu,v) \DVV F(z,u,v) \\ & + &
u \DVV R(zu,v)      R(z,v)   +
2 u \DV  R(zu,v) \DV  R(z,v)   \\ & + &
u      R(zu,v) \DVV R(z,v)   \\ & + &
\DVV R(z,v)       F(z,u,v) +
2   \DV  R(z,v)  \DV  F(z,u,v) \\ & + &
R(z,v)  \DVV F(z,u,v).
\end{eqnarray*}
and hence

\begin{eqnarray*}
\DZ G_1(z,u) & = &
u \frac{ 8 z^3 u^3 }{(1 - z u)^6} \frac{z u}{(1 - z)(1 - z u)} +
2 u \frac{z^2 u^2}{(1 - z u)^4} G(z, u) \\ & + &
u \frac1{1 - z u} G_1(z, u) \\ & + &
u \frac{ 8 z^3 u^3 }{(1 - z u)^6} \frac1{1 - z}  +
2 u \frac{z^2 u^2}{(1 - z u)^4} \frac{z^2}{(1 - z)^4}  \\ & + &
u \frac1{1 - z u} \frac{ 8 z^3 }{(1 - z)^6}  \\ & + &
\frac{ 8 z^3 }{(1 - z)^6}  \frac{z u}{(1 - z)(1 - z u)} +
2   \frac{z^2}{(1 - z)^4}  G(z, u) \\ & + &
\frac1{1 - z} G_1(z, u).
\end{eqnarray*}

References. Basic generating functions.

\end{document}



Date Prev | Date Next | Date Index | Thread Index