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

["Helmut" <helmut@cam.wits.ac.za>]

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



Oh, for the induction you don't need Maple, you just have to know
how to sum polynomials and harmonic numbers. I guess you do.

But for the variance: you should get a functional-differential
equation that I might work out for you eventually that probably
cannot be solved explicitly. However, moments can be extracted, 
and the diff eqs ("DEs") can be solved. Then one has to read off
the coefficients and simplify, partially by hand.
Without Maple, I would not start this project. 
Are you not affiliated with an academic institution?

Too bad....

Neue Arbeit sounds good, but must first be written.

Regards, H.P.



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