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

[Marko Riedel <mriedel@neuearbeit.de>]

Greetings.

I forgot the conclusion in my rush to finish the induction proof. I am
not sending the whole file, just the part that should be added.

I figure the variance should consist of terms from the following
product:

/     \       /       \
| m^3 |       | H_m^2 |
| m^2 |   x   |  H_m  |
|  m  |       |   1   |
|  1  |       |       |
\     /       \       /

and be symmetric. It might be possible to compute the coefficients by
starting with the coefficient of j^3 and (n-j+1)^3 and working one's
way down to the lower-order terms. I'm sure the variance can be proved 
by induction, too, but it would be nice if it could be derived from
the super generating function. Few readers if any are going to check
the details of the computation that would be needed to prove the
variance, I believe.

Regards,

Marko Riedel

I did read some Karl May in my early teens (his books weren't
published in East Germany until the late eighties, and obtaining one
required a bibliophile's expertise in knowing what bookstores to
check), but I never inquired into his biography. I don't read as much
as I used to.

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


{\bf Claim.} The expected number of inversions after a single
quickselect is 
\[ \frac{q_n'(1)}{n} = 
   \dode n^2 - \half n - \frac{19}{12} + 
   \PAR{ 1 + \frac{1}{n} } H_n. \]
{\bf Proof.}
We have
\begin{eqnarray*}
q_n'(1) & = & \sum_{j=1}^n q_{n, j}'(1) \\
& = & 
\sum_{j=1}^n  
\PAR{\octa (n+1-j)(n-4-j) + \octa j(j-5)+
     \half H_{n+1-j} + \half H_j} \\
& = & 
\qurt \sum_{j=1}^n j(j-5) + \sum_{j=1}^n H_j \\
& = & 
\qurt \PAR{ \thrd n^3 - 2 n^2 - \frac{7}{3} n } +
(n+1) H_n - n \\
& = & \dode n^3 - \half n^2 - \frac{19}{12} n
+ (n+1) H_n
\end{eqnarray*}
and this is the claim.