\documentstyle[twoside,lot,12pt]{article}

\evensidemargin 11mm
\oddsidemargin 11mm
\marginparwidth 0pt
\marginparsep 0pt
 
\topmargin -1in
\headheight 0.7cm
\headsep 1.8cm
\footheight 0.7cm
\footskip 2cm
\textheight 22cm
\textwidth 14cm
 
\marginparpush 0pt
 
\startpage{1}
\pubnr{[B33i]}
\semnr{33^e}
\parindent0mm
\topmargin-1.5cm

\newcommand{\qed}{\hfill \rule{0.7ex}{1.5ex}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\makeatletter
\def\@theoremfont{\it}
\def\slanttheorems{\def\@theoremfont{\sl}}
\def\@begintheorem#1#2{\@theoremfont\trivlist \global\setbox0=\hbox{\bf
#1}\global\setbox1=\hbox{\bf #2}\item[\hskip \labelsep{\bf #1\ #2.}]}
\def\@opargbegintheorem#1#2#3{\@theoremfont\trivlist
      \item[\hskip \labelsep{\bf #1\ #2.\ (#3)}]}
\makeatother

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}{Definition}[section]

\newenvironment{case}{\left\{\begin{array}{ll}}{\end{array}\right.}
\newenvironment{proof}{\begin{trivlist} \item[\hskip \labelsep{\bf
Proof.}]\setlength{\parindent}{0pt}}{\qed\end{trivlist}}

\newcommand{\nat}{\rm I\!N}                               
\newcommand{\binom}[2]{{#1 \atopwithdelims() #2}}
%\newcommand{\qed}{\rule{2mm}{2mm}}                 
\newcommand{\Res}{\mathop{\rm Res}\nolimits}
\newcommand{\Exp}{\mbox{\rm E}}
\newcommand{\Var}{\mbox{\rm Var}}
\newcommand{\Cov}{\mbox{\rm Cov}}
\newcommand{\dfrac}[2]{\frac{\displaystyle #1}{\displaystyle #2}}
\newcommand{\Prob}{\mbox{\rm Prob}}
\newcommand{\bcomm}{\mbox{$[\![$}}
\newcommand{\ecomm}{\mbox{$]\!]$}}

\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\renewcommand{\S}{{\cal S}}
\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{\theenumi)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\titlepagestyle{empty}
\thispagestyle{headings}

\title[Skip Lists - Some Recent Results]{Skip Lists - Some Results on a
                Recent Data Structure%
\thanks{
This research was supported by the program Acciones Integradas
Hispano-Austr\'{\i}acas (Austrian-Spanish Scientific
Exchange Program).}}
\author[P.~Kirschenhofer]{Peter Kirschenhofer\\
                         Department of Algebra and Discrete Mathematics\\
                         Technical University of Vienna
\thanks{
Wiedner Hauptstr. 8--10, A-1040 Vienna, Austria.
e-mail: {\tt kirsch@rsmb.tuwien.ac.at}}}
%
\date{}

\maketitle



\begin{abstract}
The skip list is a list-based data structure introduced some years ago
by Pugh \cite{Pu90}. In \cite{KMP} an optimized version of the
skip list search algorithm has been investigated and an asymptotic
result on the variance of the total unsuccessful search cost has been 
derived. Here we give the precise asymptotics for the difference of
the variance of this parameter and the variance of the total successful
search cost.

\end{abstract}

\section{Introduction}

The {\sl skip list\/} is a list-based type of data structure that was 
introduced 
by Pugh (\cite{Pu90}). In the following we only give a very short description
of this structure. We refer to \cite{cookbook}, \cite{PPM-BIT},
\cite{PapaPhD}, \cite{Dev92},
\cite{KP-skip} and \cite{KMP} for detailed descriptions and various analyses
 on this 
subject. 

A set of $n$ elements is stored in a collection of sorted linear linked lists in
the following manner: all elements are stored in increasing order in a
linked list called {\sl level\/} 1 and, recursively, each element which
is included in the linked list {\sl level\/} $i$ is included with
independent probability $q$ ($0 < q < 1$) in the linked list {\sl
level\/} $i+1$. 
 The number of linked lists an element $x$
belongs to is called the {\sl level\/} of the element. For each element 
in the skip list, we need a node to store
its key and as many pointers as its level indicates. The successor of
$x$ at the list level $i$ is given by the $i$-th pointer of $x$, also called
$i$-th {\sl forward\/} pointer of $x$.
A {\sl header\/} refers to the first element in each of
the linked lists and it also holds the {\sl height\/} of the skip
list, which is the maximum level of all elements.

In~\cite{KP-skip} 
the asymptotic
analysis of the {\sl total (successful) search cost\/} or 
{\sl path length\/}, i.e. the sum of the successful
search costs to find all the elements in the data structure, was performed for
the instance of the simplest form of the search algorithm.

The paper \cite{KMP} is devoted to the analysis of the total search cost
of an {\sl optimized version\/} of the search algorithm proposed in
\cite{cookbook}, that  reduces
the number of expensive key comparisons by
guaranteeing that the search key will be compared at most once with the
key of any element in the skip list. To this aim, the variable
{\tt alreadyChecked} is introduced. At the beginning this variable is
set to ``NIL''. In the following loop we follow forward
pointers as long
as the elements pointed to are different from {\tt alreadyChecked} and
the keys of those elements are smaller than the search key. As soon as this
horizontal traversal ends, {\tt alreadyChecked} is set to the element
pointed to at this moment and the search continues one level below
(see Figure~\ref{fig:optimized-search}).

\begin{figure}
\begin{verbatim}
 x:= header(S); l:= height(S);
 alreadyChecked:= NIL;
 while l > 0 do
   while (x^.forward [l] <> alreadyChecked) do
     while(x^.forward[l]^.key < search_key) do
             x:= x^.forward[l]
     endwhile 
   endwhile;
   alreadyChecked:= x^.forward[l];
   l:= l - 1
 endwhile 
\end{verbatim}
\caption[Optimized search]{Optimized skip list search algorithm (see~\cite{cookbook})}
\label{fig:optimized-search}
\end{figure}

In \cite{KMP} an explicit example for a search path in a skip list is
depicted together with a comparison of the number of key-to-key comparisons
and pointer inspections in both the original and the optimized instance
 of the search algorithm.

It should be noted that we may also describe a skip list of size $n$ as an 
$n$-tuple 
$(a_1,\dots, a_n)$, where $a_i$ denotes the level of the $i$-th
element. We adopt the 
 probabilistic model for {\sl random skip lists\/}  of being
the outcome of $n$ independent identically
distributed random variables. In particular, each $a_i\in \nat$ 
is the outcome of a {\sl geometric\/} random variable $X_i$
of parameter $p$, i.e. $\Prob\{X_i=k\}=pq^{k-1}$, where $q=1-p$.  
(Note that in some earlier papers the roles of $p$ and $q$ are interchanged.)

Interestingly enough the search cost parameter, i.e. the number of
key-to-key comparisons, can be expressed in terms of
{\sl order statistics\/}: The number $C_{n,i}$ of 
key comparisons when
searching for element $i$ 
equals the number $l_{n,i}$ of {\sl strict left-to-right maxima\/} 
of the sequence
$(a_i,\dots,a_n)$ plus the number $r_i$
of {\sl weak right-to-left maxima\/} of
$(a_1,\dots,a_{i-1})$. 

Observe that for a fixed element $i$ the two parameters are
independent random variables, but that this is no longer true for the
{\sl total successful search cost\/} 
$\widetilde C_n$, which is given by the sum 
$\sum_{i=1}^nC_{n,i}$. 
This dependency is the reason that the variance of $\widetilde C_n$
cannot be gained by simply adding the variances
of the two parameters $\sum_i l_{n,i}$ and $\sum_ir_i,$
which where already computed in~\cite{KP-skip}. 

The number $r_{n+1}$ of weak
right-to-left maxima
of $(a_1,\dots,a_{n})$ is never counted in 
$\widetilde C_n=\sum_{i=1}^nC_{n,i}$, which
causes some kind of asymmetry of this parameter.
 Therefore
in \cite{KMP} instead of $\widetilde C_n$  
the {\sl total unsuccessful search
cost\/}  $C_n$ was studied:
\begin{equation}
C_n = \sum_{1\le i\le n+1} C_{n,i}.
\end{equation}
This parameter fulfills nice recurrence relations, and its
expectation and variance were analyzed asymptotically in the cited
paper. 
The variance of $C_n$ is of order
$n^2$, and it was shown that the difference of the variances
fulfills
\begin{equation}
\Var (C_n) - \Var(\widetilde C_n) = O(n^{17/9+\varepsilon}), 
\quad\mbox{any}\quad 
\varepsilon >0,
\end{equation}

so that $\Var (\widetilde C_n)$ is of order $n^2$, too. It was conjectured,
that the difference of the variances is  of order $n\log ^2n$.
In this paper we will prove that in fact the order of the difference is
$n\log n$. We will give a precise asymptotic result, which also allows
to describe the asymptotics of the {\sl covariance\/}  of the two random variables
$C_n$ and $r_{n+1}$.

From the technical point of view we will make use of probability generating
functions, use a substitution that allows to express the desired coefficients
explicitly in terms of alternating sums and apply a technique due to
S.O.Rice to get the final asymptotics (compare the very recent article
\cite{FlSe} on the latter subject.)
 
\section[Generating Functions \ldots]{ 
Generating Functions and First Order Moments}

We start with 
the following combinatorial decomposition of a skip list of height $m$
(compare \cite{KP-skip,KMP}): 
 We split up the whole skip list
 according to the first appearance of an element
of height $m$ into a skip list $\sigma$ of height $<m$, 
the partitioning element of height $m$ and
the remaining  skip list
$\tau$ of height $\le m$. 
Observing that each successful or unsuccessful search starts with
a comparison of the search key with the key of the partitioning 
element we easily find
\begin{eqnarray} 
C(\sigma m\tau) & = & C(\sigma) + C(\tau)+ |S| +1,\nonumber \\
\widetilde C(\sigma m\tau) & = & C(\sigma) + \widetilde C(\tau)+ |S| .
\label{eq:recurrence-cost}
\end{eqnarray}

We denote by $P^\ast(z,y)$ resp $\widetilde P^\ast(z,y)$
the bivariate generating functions where
the coefficient of $z^ny^k$ is the probability that a random skip
list of size $n$ has height fulfilling condition $\ast$ and the
 total unsuccessful resp. successful search cost is equal to $k$. 
Then Eqs.~(\ref{eq:recurrence-cost})
translate to the system of functional equations

\begin{eqnarray} 
P^{=m}(z,y) & = & pq^{m-1}zy^2P^{<m}(zy,y)P^{\le m}(zy,y), 
 \nonumber\\
\widetilde P^{=m}(z,y) & = 
& pq^{m-1}zyP^{<m}(zy,y)\widetilde P^{\le m}(zy,y), 
\quad m\ge1, \nonumber\\
P^{=0}(z,y) & = & \widetilde P^{=0}(z,y) = 1.
\label{eq:recurrence-P}
\end{eqnarray}

It is convenient to use the bgf's 
$R^*(z,y):=zP^*(z,y), \widetilde R^*(z,y):=z\widetilde P^*(z,y)$
instead. In order to get the expectations we have to derive w.r.t. $y$
and set $y=1$. We introduce the notations $S^*(z)=R_y^*(z,1)$ resp. 
$\widetilde S^*(z)=\widetilde R_y^*(z,1)$ for the generating functions 
of these partial derivatives as well as
the abbreviations
$$Q:=q^{-1},\ L:=\log Q,\ \bcomm m\ecomm:= 1-z(1-q^{m})$$
and get 
\begin{eqnarray}
&\phantom{x}\hspace*{-.8cm}S^{=m}(z) &= pq^{m-1}\left[\(\frac{z}{\bcomm m-1\ecomm^2}
+S^{<m}(z)\)\frac{z}{\bcomm m\ecomm}+
\(\frac{z}{\bcomm m\ecomm^2}+S^{\le m}(z)\)\frac{z}{\bcomm m-1\ecomm}\right],
\nonumber\\
&\phantom{x}\hspace*{-.8cm}\widetilde S^{=m}(z) &=  pq^{m-1}\left[\(\frac{z}{\bcomm m-1\ecomm^2}
+S^{<m}(z)\)\frac{z}{\bcomm m\ecomm}\right.\nonumber\\
&&\phantom{x}\hspace*{-.8cm}+\left.
\(\frac{z}{\bcomm m\ecomm^2}-\frac{z}{\bcomm m\ecomm}
+\widetilde S^{\le m}(z)\)\frac{z}{\bcomm m-1\ecomm}\right]
\label{eq:Delta}
\end{eqnarray}

Since we know $S^{\le m}(z)$ from \cite{KMP} we focus our attention on
the difference
\begin{equation}
\Delta^*(z)=S^*(z)-\widetilde S^*(z).
\end{equation}
Observing $\Delta^{=m}(z)=\Delta^{\le m}(z)-\Delta^{<m}(z)$, we get from
(\ref{eq:Delta}) a first
order linear recurrence relation for the sequence $(\Delta^{\le m}(z))_{m\ge 0},$
which has the solution

\begin{equation}
\Delta^{\le m }(z)=
\frac{p}{q}\frac{z^2}{\bcomm m\ecomm}\sum_{i=1}^m\frac{q^i}{\bcomm i\ecomm}
\label{eq:D<=m}
\end{equation}
For $m\to\infty$, this yields
\begin{equation}
\Delta(z)=
\frac{p}{q}\frac{z^2}{1-z}\sum_{i\ge1}\frac{q^i}{\bcomm i\ecomm}.
\end{equation}

Although we know already the asymptotics of the coefficients of
$\Delta(z)$ from \cite{Pr93}, where, amongst other results, the expectation 
and the variance of
the random variable $r_{n+1}=C_n-\widetilde C_n$ were derived, 
we want to sketch here again
the method used in \cite{KP-skip,KMP},
since it may be well  used for the asymptotic evaluation of the much more complicated
expressions for the differences of the second moments, too.
We start from the substitution
$$
z=\frac{w}{w-1},
$$
which in terms of formal residue composition (compare e.g. \cite{GJ}) reads
$$
[z^n]f(z)=(-1)^n[w^n](1-w)^{n-1}f\bigl(w/(w-1)\bigr).
$$
In our instances the above substitution leads to 
{\sl harmonic sums\/}
$$
G(w)=\sum_i a_i g(b_iw),
$$
so that
$$
[w^n]G(w)=\sum_i a_ib_i^n \cdot [w^n]g(w),
$$
which can be computed explicitly in all our cases.
Proceeding in this manner we find
\begin{eqnarray}
\frac {q}{p}[z^n]\Delta(z)
&=&[z^n]\frac{z^2}{(1-z)}\sum_{i\ge1}\frac{q^i}{\bcomm i\ecomm}
\ \ =\ \ (-1)^n[w^n]w(1-w)^{n-1}\sum_{i\ge1}\frac{wq^i}{1-wq^i}\nonumber \\
&=&(-1)^n\sum_{k=1}^{n-1} \binom{n-1}{k}(-1)^{n-1-k}
[w^{k-1}]\sum_{i\ge1}\frac{wq^i}{1-wq^i}\nonumber\\
&=&-\sum_{k=1}^{n-1}\binom{n-1}{k}(-1)^k\sum_{i\ge1}q^{(k-1)i}
[w^{k-1}]\frac{w}{1-w}\nonumber \\
&=&-\sum_{k=1}^{n-1}\binom{n-1}{k}(-1)^k\frac{1}{Q^{k}-1}.
\label{Deltaexpl}
\end{eqnarray}

There are several techniques to evaluate the alternating sum. 
One of them starts from the observation that according to
Mittag Leff\-ler's Theorem the meromorphic function $\frac {1}{Q^z-1}$
has a 
partial fraction decomposition in the complex plane. This decomposition
is surprisingly simple and follows  from the well-known result 
(compare e.g.~\cite{Henrici} eqn.(7.10)-10)
\begin{equation}
\frac {2\pi}{\mbox{e}^{2\pi z} -1} = -\pi +\frac {1}{z}+
\sum_{n=1}^{\infty}\left(\frac1{z-i n}+\frac1{z+i n}\right).
\label{ML}
\end{equation}
 Inserting the last result
in eqn.(\ref{ML}) we arrive at alternating sums that may be computed
explicitly using the formula (compare e.g. \cite{GKP}~eqn.(5.41))
\begin {equation}
\sum_{k=0}^n\binom{n}{k}(-1)^k\frac1{x+k}=\frac{n!}{x(x+1)\dots(x+n)}. 
\end{equation}
In this manner we find with the abbreviation $\chi_j=2j\pi i/L $
\begin{equation}
\Exp (C_n) - \Exp (\widetilde C_n) = [z^{n+1}]\Delta(z) =
(Q-1)\left( \frac{H_n}L -\frac 12 
-\frac 1L \sum_{j\ne 0}\frac{\Gamma(-\chi_j)\Gamma(n+1)}{\Gamma(n+1-\chi_j)}\right).
\end{equation}
The third term can be rewritten using Euler's classical formula
\begin{equation}
\frac 1{\Gamma (z)}= z\mbox{e}^{\gamma z}
  \prod_{k\ge 1}\left[(1-\frac zk)\mbox{e}^{z/k}\right]
\end{equation}
in the form
\begin{equation}
\frac 1L \sum_{j\ne 0}\frac{\Gamma(-\chi_j)\Gamma(n+1)}{\Gamma(n+1-\chi_j)}
=\frac 1L \sum_{j\ne 0}\Gamma(-\chi_j)
  \mbox{e}^{\frac{2j\pi i(H_n-\gamma)}L}
  \prod_{k\ge n+1}\left[(1-\frac {2j\pi i}{Lk})
  \mbox{e}^{\frac{2j\pi i}{Lk}}\right].
\end{equation}
From this last expression we easily see that for $n\rightarrow \infty$
the third term converges towards a periodic function in $\log _Qn,$ so that
we have the asymptotic result (compare \cite{Pr93})
\begin{equation}
\Exp (C_n) - \Exp (\widetilde C_n) = \Exp (r_{n+1})=
(Q-1)\left(\log _Qn +\frac {\gamma}L -\frac 12 + \delta (\log _Q n)\right),
\end{equation}
where $\delta (x)=-\frac 1L\sum_{j\ne 0}\Gamma(-\chi_j)
  \mbox{e}^{2j\pi ix}$
is a continuous periodic function of period 1 and mean 0
with very small amplitude for reasonable values of $Q$.

If the alternating sums in consideration involve more complicated terms
and we are mainly interested in asymptotic results it is convenient to
follow an approach attributed to S.O.Rice. The excellent survey
\cite{FlSe} explains this methodology in detail. The basic idea is to
express the alternating sum as a complex contour integral:

\begin{equation}
\sum_{k=a}^n\binom{n}{k}(-1)^kf(k)=-\frac1{2\pi i}\int_{\cal C} B(n+1,-z)f(z)\, dz,
\end{equation}
where $B(x,y)=\dfrac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$ is the 
Beta function, ${\cal C}$ is a positively oriented closed curve 
surrounding the
points
$a,a+1,\dots, n$ and $f(z)$ is an analytic continuation of the discrete 
sequence $f(k)$ 
to the complex plane, with no poles within the region surrounded by
 ${\cal C}$.  

If $f(z)$ decreases sufficiently fast towards $\pm i\infty$, 
the  asymptotic evaluation of this expression can be achieved 
by extending the contour of the integral
to the left and collecting the  residues at the newly encountered 
poles.
The residue
computations can often be performed automatically using a Computer
algebra system like {\sc MAPLE}.



\section{Second Order Moments}
\label{sec:variance}

In this section, we will establish the asymptotic behavior of the difference
of the second
factorial moments of $C_n$ resp. $\widetilde C_n$, thereby getting
the desired asymptotics for the difference of the variances resp. the
covariance of $C_n$ and $r_{n+1}$. 

The generating functions
for the second factorial moments are obtained by deriving $P^\ast(z,y)$ resp.
$\widetilde P^\ast(z,y)$
twice w.r.t. $y$ and setting $y=1$. Again we use 
$R$ resp. $\widetilde R$ instead of $P$ resp. $\widetilde P.$
Denoting the generating functions of the second partial derivatives by
 $T^\ast(z):= R^\ast_{yy}(z,1)$ resp. 
$\widetilde T^\ast(z):= \widetilde R^\ast_{yy}(z,1)$ 
we find, starting from eqs.(\ref{eq:recurrence-P}), for the difference 
%\begin{equation}
$\Phi ^*(z) = T^*(z)-\widetilde T^*(z)$
%\end{equation}
the relation
\begin{eqnarray}
\Phi^{=m}(z)& =
&\frac{pq^{m-1}z}{\bcomm m-1\ecomm}
\left(\Phi^{\le m}(z)+2z\Delta_z^{\le m}(z)+2\widetilde S^{\le m}(z) +
\frac{2z}{\bcomm m\ecomm ^2}-\frac{2z}{\bcomm m\ecomm}\right)\nonumber\\
&+&2pq^{m-1}\left(\frac z{\bcomm m-1\ecomm ^2} + S^{\le m-1}\right)
\left(\frac z{\bcomm m\ecomm} +\Delta^{\le m}(z)\right).
\end{eqnarray}

Inserting the functions $\Delta, S, \widetilde S$ explicitly, 
solving the first order linear recurrence for $\Delta^{\le m}(z)$ 
and performing the limit $m\rightarrow \infty$ we get the solution
\begin{eqnarray}
&&\phantom{x}\hspace*{-.8cm}\Phi(z)= \frac{2z^2}{1-z}\frac pq
\left\{-S_1+(1+pz)(S_2+S_3)\right\}\nonumber\\
&&\phantom{x}\hspace*{-.8cm}+\frac{2z^3}{1-z}\frac {p^2}{q^2} 
\left\{-qS_4-S_5+(1+pz)S_6-S_7+(2+q)(S_8+S_{10})+S_9+pzS_{10}\right\}\nonumber\\
&&\phantom{x}\hspace*{-.8cm}+\frac{2z^4}{1-z}\frac {p^3}{q^3} 
\left\{-S_{11}+(1+q)S_{12}\right\}
\end{eqnarray} 
with the sums

\begin{eqnarray}
&&\phantom{x}\hspace*{-.8cm}\displaystyle \S_{1}(z) =  \sum_{i\ge1}
\dfrac{q^{i}}{\bcomm i\ecomm},\
\displaystyle \S_{2}(z) =  \sum_{i\ge1}
\dfrac{q^{i}}{\bcomm i\ecomm^2},\
\displaystyle \S_{3}(z) = \sum_{i\ge1}
\dfrac{q^{i}}{\bcomm i\ecomm\bcomm i-1\ecomm},\
\displaystyle \S_{4}(z) =  \sum_{i\ge1}
\dfrac{q^{2i}}{\bcomm i\ecomm^3},\nonumber\\
&&\phantom{x}\hspace*{-.8cm}\displaystyle \S_{5}(z) = \sum_{i\ge1}
\dfrac{q^{2i}}{\bcomm i\ecomm\bcomm i-1\ecomm^2},\
\displaystyle \S_{6}(z) = \sum_{i\ge1}
\dfrac{q^{2i}}{\bcomm i\ecomm^2\bcomm i-1\ecomm},\
\displaystyle \S_{7}(z) =  \sum_{1\le j \le i}
\dfrac{q^{i+j}}{\bcomm i\ecomm\bcomm j\ecomm},\nonumber\\
&&\phantom{x}\hspace*{-.8cm}\displaystyle \S_{8}(z) =  \sum_{1\le j \le i}
\dfrac{q^{i+j}}{\bcomm i\ecomm^2\bcomm j\ecomm},\
\displaystyle \S_{9}(z) =  \sum_{1\le j \le i}
\dfrac{q^{i+j}}{\bcomm i\ecomm\bcomm j\ecomm^2},\
\displaystyle \S_{10}(z) =  \sum_{1\le j <i}
\dfrac{q^{i+j}}{\bcomm i\ecomm\bcomm i-1\ecomm\bcomm j\ecomm},\nonumber\\
&&\phantom{x}\hspace*{-.8cm}\displaystyle \S_{11}(z) = \sum_{1\le j\le i}
\dfrac{q^{2i+j}}{\bcomm i\ecomm\bcomm i-1\ecomm^2\bcomm j\ecomm},\
\displaystyle \S_{12}(z) =  \sum_{1\le j \le i\atop 1\le h<i}
\dfrac{q^{i+j+h}}
{\bcomm i\ecomm\bcomm i-1\ecomm\bcomm j\ecomm\bcomm h\ecomm}.
\end{eqnarray}

Proceeding as in Section 2 we gain the following explicit expression
for the coefficients of $\Phi (z)$ in terms of alternating sums:
\begin{eqnarray}
&&\phantom{x}\hspace*{-.8cm}
 [z^n]\Phi (z)=-2(Q-1)^2\sum_{k=2}^n\binom nk\frac{(-1)^k}{Q^{k-1}-1}
\left\{-(1+q)+(k-1)(1-\frac q{Q-1})\right. \ \ \ \ \nonumber\\
&&\phantom{x}\hspace*{-.8cm}
\left.+2\binom{k-1}2+q\sum_{m=1}^{k-2}\frac m{Q^m-1}
+2(1+q)\sum_{m=1}^{k-2}\frac 1{Q^m-1} +(k-1)\sum_{m=1}^{k-2}\frac 1{Q^m-1}
\right\}
\nonumber\\
&&\phantom{x}\hspace*{-.8cm}
+2q(Q-1)^2\sum_{k=2}^{n-1}\binom {n-1}k\frac{(-1)^kk}{Q^{k-1}-1}+2(n-1)+\nonumber\\
&&\phantom{x}\hspace*{-.8cm}
-
2(Q-1)^2\sum_{k=1}^{n-1}\binom {n-1}k\frac{(-1)^k}{Q^{k}-1}
\left\{-\frac 1{Q-1}+k-1+\sum_{m=1}^{k-1}\frac 1{Q^m-1}\right\} .
\end{eqnarray}
Applying Rice's method described in Section 2 allows to obtain the asymptotics
of the coefficients now as
\begin{eqnarray}
&&\phantom{x}\hspace*{-.8cm}[z^n]\Phi(z)=2(Q-1)(Q-q)n\log_Q^2n\nonumber\\
&&+ 2(Q-1)^2n\log_Qn\left(-1+\frac{2(\gamma -1)(1+q)}L+\delta_1(\log_Q n)\right)+O(n),
\end{eqnarray}
where $\delta_1(x)=\frac{1+q}L
\sum_{j\ne 0}(2+\chi_j)\Gamma (-1-\chi_j)\mbox{e}^{2j\pi ix}$. 
From this asymptotic formula we can derive in straightforward manner 
the desired result:
\begin{theorem}
{}
The difference of the variances of the total unsuccessful and the total
successful search cost of the optimized skip list search algorithm fulfills
{\begin{eqnarray*}
\Var (C_n)-\Var (\widetilde C_n)&=& 2\Cov (C_n,C_n-\widetilde C_n) +O(\log n)\\
&=&
-\frac{2(Q-1)(Q-q)}Ln\log_Qn\ +\ O(n).
\end{eqnarray*}}
\end{theorem}

\bibliographystyle{plain}

\begin{thebibliography}{12}


\bibitem{Dev92}
L.~Devroye.
\newblock A limit theory for random skip lists.
\newblock {\em The Annals of Applied Probability}, 2(3):597--609, 1992.

\bibitem{FlSe}
Ph. Flajolet and R.~Sedgewick.
\newblock Mellin transforms and asymptotics: Finite differences and {R}ice's
  integrals.
\newblock {\em Theoretical Computer Science}, 144:101--124, 1995.

\bibitem{GJ}
I.~Goulden and D.~Jackson.
\newblock {\em Combinatorial Enumeration}.
\newblock J.~Wiley, 1983.

\bibitem{GKP}
R.L.~Graham, D.E.~Knuth and O.~Patashnik.
\newblock {\em Concrete Mathematics}.
\newblock Addison Wesley, 1994.

\bibitem{Henrici}
P.~Henrici.
\newblock {\em Applied and Computational Complex Analysis},
\newblock Vol.1.
\newblock J.~Wiley, 1988.


\bibitem{KMP}
P.~Kirschenhofer, C.~Martinez and H.~Prodinger.
\newblock Analysis of an optimized search algorithm for skip lists.
\newblock {\em Theoretical Computer Science}, 144:199-220, 1995.

\bibitem{KP-skip}
P.~Kirschenhofer and H.~Prodinger.
\newblock The path length of random skip lists.
\newblock {\em Acta Informatica}, 31:775-792, 1994.

\bibitem{PPM-BIT}
T.~Papadakis, J.~I. Munro, and P.~V. Poblete.
\newblock Average search and update costs in skip lists.
\newblock {\em BIT}, 32:316--332, 1992.

\bibitem{PapaPhD}
Th. Papadakis.
\newblock {\em Skip Lists and Probabilistic Analysis of Algorithms}.
\newblock PhD thesis, University of Waterloo, 1993.
\newblock Available as Technical Report CS-93-28.

\bibitem{Pr93}
H.~Prodinger.
\newblock Combinatorics of geometrically distributed random variables:
  Left-to-right maxima.
\newblock {\em Discrete Mathematics}.
\newblock To appear.
 
\bibitem{cookbook}
W.~Pugh.
\newblock A skip list cookbook.
\newblock Technical Report CS-TR-2286.1, Institute for Advanced Computer
  Studies, Department of Computer Science, University of Maryland, College
  Park, MD, June 1990.
\newblock Also published as UMIACS-TR-89-72.1.

\bibitem{Pu90}
W.~Pugh.
\newblock Skip lists: a probabilistic alternative to balanced trees.
\newblock {\em Comm. ACM}, 33(6):668--676, 1990.

\end{thebibliography}

\end{document} 
