%Acta Informatica

\input amstex
\documentstyle{amsppt}


%\input graphic
%The picture of a skiplist is not reproduced in this version


\define\rfuenf{6}
\define\rsechs{10}
\define\rzehn{5}
\font\sc=cmcsc10
\hfuzz=10pt
\define\[{[\! [}
\define\]{]\! ]}
\define\lk{[\! [}
\define\rk{]\! ]}
\define\llk{[\! [\![}
\define\rrk{]\! ]\!]}
\document
\NoRunningHeads
\TagsOnRight
\topmatter
\title
The path length of random skip lists
\endtitle

\author Peter Kirschenhofer and Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address TU Vienna
\newline Wiedner Hauptstrasse 8--10
\newline A-1040 Vienna
\newline Austria
\endaddress 
\abstract 
The skip list is a recently introduced data structure that may be seen
as an alternative to (digital) tries. In the present paper we analyze
the path length of random skip lists asymptotically, i.e. we study
the cumulated successful search costs. In particular we derive a precise
asymptotic result on the variance, being of order $n^2$ (which is in
contrast to tries under the symmetric Bernoulli model, where it is only
of order $n$). We also intend to present some sort of technical toolkit
for the skilful manipulation and asymptotic evaluation of generating
functions that appear in this context.
\endabstract
\keywords Data structures, generating functions, probabilistic analysis
\endkeywords
\email kirsch\@email.tuwien.ac.at, proding\@email.tuwien.ac.at
\endemail

\endtopmatter

\head 1. Introduction and Main Results\endhead

The {\it skip list\/} has recently been introduced  by {\sc Pugh} \cite{15}
as an alternative data structure
to search trees. 
We give a short description in the next paragraphs and refer the reader
to \cite{13} for more detailed information.
In \cite{1}, \cite{13} 
some interesting analytic aspects are obtained
about the average case performance of random skip lists, especially on the
search costs.
Analyzing search trees, probably the most important parameter is the
{\it path length\/}, i.e. {\it the sum of the  costs to
find all the elements in the data structure}, (``successful search''),
 compare \cite{4} and
\cite{12}. This parameter has not yet been analyzed for the
skip list, and  we devote this paper to
its study. 

%We will refrain from repeating implementational details,
%refer for this to the literature (\cite{1}, \cite{13}, \cite{14}),
%and give only an essential description. 

In a skip list $n$ elements ($n\ge1$) are stored in a set of sorted linear
linked lists according to the following rule: all elements are
stored in sorted order in a  linked list named ``level 1'', and each
element stored in the linked list ``level $i$'' is included with
(independent) probability $q$ ($0<q<1$) in the linked list ``level $i+1$''.
A header refers to the first element in each linked list and also
contains the total number of linked lists, i.e. the ``height'' of the
data structure. The number of linked lists which an element belongs to
is constant as long as the element exists in the skip list. Therefore it
suffices to store each element only once, together with an array of
horizontal pointers that refer to the respective consecutive elements of the
linked lists the element belongs to.

If we denote by $a_i$ the number of linear linked lists 
that contain the $i$-th element,
it follows that a skip list of size $n$ can also be described by
the corresponding
 $n$-tuple
$(a_1,\dots,a_n)$.
In the sequel we adopt the following model of {\it random skip lists}
(compare \cite{1}, \cite{13}).
Each $a_i\in \Bbb N$ is the {\it outcome}
of a random variable $G_i$ that is distributed according to the 
{\it geometric distribution} with parameter $p$, i.e. Prob$\{G_i=k\}=
pq^{k-1}$, where $q=1-p$. The random variables are {\it independent}.

The reader is warned that in the earlier papers the roles of $p$ and $q$
are interchanged. Nevertheless, we find it easier to stay with the
present notation that is classical in the context of the geometric
distribution.

The {\it search} for the $i$-th element  starts at the header of the top level 
linked list. This list is followed until the 
index of the next element in the list is
greater  or equal to $i$ (or the reference is null). In this instance the
search continues one level below. The search terminates at level 1 with
an equality test as the last comparison. 

In the figure below we depict the search path for the 4-th element 
in a random skip list of size 4.

%$$
%\includegraphic{skip2}
%$$
%

Following \cite{13} we define
the {\it search cost} for the $i$-th element as the number of pointer expections
excluding the last one for the equality test
(i.e. 13 in the example above). 
Each instance of a pointer inspection is marked by a dot in the figure.
Observe that the last pointer expection comes up with the {\it third
element\/} at level 1. The search cost may be
split up into the sum of a ``{\it vertical cost\/}'' corresponding to
pointer inspections of pointers refering to elements at a position
$\ge i$
(that initiate the continuation of the search one level below,
11 in the example) and a
``{\it horizontal cost\/}'' corresponding to the remaining pointer
inspections, i.e. the number of horizontal steps on the path from the 
header
to the $i$-th element (2 in the example).
We define the {\it horizontal path length} $X_n=X_n(\rho)$
of a skip list $\rho$ containing $n$ elements as the sum of the horizontal
search costs of all elements in $\rho$. The 
{\it vertical path length} $Y_n=Y_n(\rho)$ is defined analogously.
Finally, the total path length or {\it total cost} $C_n$ is $X_n+Y_n$.
$X_n$, $Y_n$ and $C_n$ are random variables under the above defined
probability model for random skip lists.

It is an easy observation that the vertical search cost for each element
equals the height of the skip list, so that $Y_n(\rho)$ is $n$ times
the height of $\rho$. The horizontal search cost is more intricate. Let us
return to our alternative description of the skip lists as
$n$-tuples $(a_1,\dots,a_n)$ from above. The height clearly equals the 
{\it maximum} of $(a_1,\dots,a_n)$. The horizontal search cost is
zero for the first element. Let now $i\ge 2$. If we follow the path from the header
to the $i-1$-th element  in reverse order we find that for 
the $i$-th element  the horizontal
cost is the {\it number of right-to-left maxima\/} in $(a_1,\dots,a_{i-1})$,
i.e. the number of elements $a_j$ ($1\le j\le i-1$) that are larger than
or equal to $a_j,a_{j+1},\dots,a_{i-1}$. (Observe that the convention to
call $a_{i-1}$ itself a right-to-left maximum ensures that the horizontal
step connecting the path with the header is counted, too.) We may
conclude that the horizontal path length of 
$(a_1,\dots,a_n)$ is the sum of the numbers
of  right-to-left maxima of the sequences
$a_1,\dots,a_{i-1}$ for $2\le i\le n$.


\comment
The {\it cost\/} to find the $i$-th data is the sum of 
the {\it horizontal cost\/}
and the {\it vertical cost\/}. The latter is easier to understand; it is
the {\it maximum} of the $(a_1,\dots,a_n)$, so it is the same for each
element.
The horizontal cost of the $i$-th element is the number of
{\it left-to-right maxima\/} of the sequence $a_i,\dots,a_n$,
where we say that $b_j$ is a left-to-right maximum in $b_1,\dots,b_n$
if it is larger or
equal than $b_1,\dots,b_j$.

Therefore we say that the {\it horizontal path length} is the sum
of the number of left-to-right maxima of the sequences $a_i,\dots,a_n$,
where $i=1,\dots,n$. The {\it vertical path length} is simply
$n$ times the maximum (or ``height'').
 Both notions of path length are random variables
that we will denote by $X_n$ resp. $Y_n$ in the sequel.
\endcomment


The number of right-to-left maxima 
of $a_1,\dots,a_n$ is a well understood parameter
in the context of {\it random permutations\/}, see \cite{\rsechs}, \cite{11}
and \cite{16}. In the context of the geometric distribution it was
analyzed in \cite{14}. 

With respect to {\it expectations}, the horizontal path length is simply
the sum of all the horizontal
search costs. This is also easy to check, comparing
\cite{14, Lemma 2} and our formula \thetag{2.7}.
However, with respect to {\it variances} the parameters are different,
and the path length has proved to be more interesting. (For tries,
Patricia tries and digital search trees, these analyses are quite
challenging and are to be found in \cite{7}, \cite{8}, \cite{9}.)
The results about the variance of the horizontal path length $X_n$ and
of the 
total cost $C_n$ are thus considered to be our
main findings in the present paper. We also intend to present some
sort of {\it technical toolkit\/}
 for the manipulation of generating functions
that will frequently occur with the  analysis of skip list parameters.
\medskip

In the following we summarize our main results. Here and in the whole
paper, we will use the handy abbreviations $Q=q^{-1}$ and $L=\log Q$.

For the sake of completeness we start with a formulation of the
asymptotics of the {\it expectations}.
Observe that these estimates can also be computed from the results
of \cite{13} on the search cost of specified elements, though the notion
of path length is not considered there.
(iii) is equivalent to \cite{13, Theorem 4}.


\proclaim{Proposition 1} {\rm (i)} The expected value {\rm E}$(X_n)$
of the horizontal path length in a random skip list containing $n$ 
elements fulfills for $n\to\infty$
$$
\text{{\rm E}}(X_n)=(Q-1)n\Big(\log_Qn+\frac{\gamma-1}{L}-\frac12+\frac 1L
\delta_1(\log_Qn)\Big)+O(\log n)
$$
where $\gamma$ is Euler's constant and
$
\delta_1(x)=\sum\limits_{k\ne0}\Gamma(-1-\frac{2k\pi i}{L})e^{2k\pi ix}
$
is a continuous periodic function of period 1
and mean zero. {\rm (}$\Gamma$ is the Gamma-function.{\rm )}
\medskip


{\rm (ii)} The expected value of the vertical path length  
fulfills for $n\to\infty$
$$
\text{{\rm E}}(Y_n)=n\log_Qn+n\Big(\frac{\gamma}{L}+\frac 12-
\frac 1L\delta_2(\log_Qn
)\Big)+O(\log n),
$$
where ${\delta_2(x)=
\sum\limits_{k\ne0}\Gamma(-\frac{2k\pi i}{L})e^{2k\pi i x}}$.



\medskip



{\rm (iii)} The expected value {\rm E}$(C_n)$ of the total cost fulfills
for $n\to\infty$
$$
\text{{\rm E}}(C_n)=Qn\log_Qn+n\Big(\frac{(\gamma-1)Q+1}{L}-\frac{Q}{2}+1+
\frac 1L
\delta_3(\log_Qn)\Big)+O(\log n)
$$
where \
$\displaystyle{
\delta_3(x)=\delta_1(x)-\delta_2(x)}$.

\endproclaim

{\sc Remark.}
As a consequence of the exponential decrease of the $\Gamma$-function
along vertical lines (compare \thetag{2.37}) we have that
the amplitude of the functions $\delta_i(x)$ here and
in the sequel is very small for all reasonable values of $q$, e.g.
$0.1\le q\le 0.9$.\medskip

The asymptotic equivalents for the
second moments of the path lengths are given in the sequel, and the two
corresponding theorems are the main results of this paper.

\proclaim{Theorem 1} The variance {\rm Var}$(X_n)$ of the horizontal
path length in a random skip list containing $n$ elements fulfills
for $n\to\infty$
$$
\aligned
\text{{\rm Var}}(X_n)&=(Q-1)^2n^2\Bigg\{
\frac{Q+1}{2(Q-1)L}
+\frac{1}{L^2}-\frac{\pi^2}{6L^2}
+\frac{8\pi^2}{L^2}h\Big(\frac{4\pi^2}{L}\Big)-\alpha_1+
\delta_4(\log_Qn)\Bigg\}\\
& +O\big(n^{1+\varepsilon}\big),\qquad \varepsilon>0,
\endaligned
$$
where $\displaystyle{
h(x)=\sum_{k\ge1}\frac{e^{kx}}{\big(e^{kx}-1\big)^2}
}$,\ 
$\displaystyle{
\alpha_1=L\sum_{k\ge1}\frac{1}{k(L^2+4k^2\pi^2)\sinh (2k\pi^2/L)}}$
and
\comment
$$
\aligned
\text{{\rm Var}}(X_n)&=(Q-1)^2n^2\Bigg\{\frac 1L\bigg(2\log 2 -1+\frac 52\frac{1}{Q-1}+
2\sum_{k\ge2}\frac{(-1)^k}{(k+1)k(k-1)(Q^k-1)}\bigg)\\
&+\frac{Q}{(Q-1)^2}-2\sum_{k\ge1}\frac{Q^k}{(Q^k-1)^2}
+\delta_4(\log_Qn)\Bigg\}+O\big(n^{1+\varepsilon}\big),\qquad \varepsilon>0,
\endaligned
$$
\endcomment
 $\delta_4(x)$ is again  continuous, periodic of period 1 and mean zero.
\endproclaim

With regard to the vertical path length, i.e. $n$ times the maximum
element, we have from \cite{\rzehn} or \cite{17}
$$
\text{Var}(Y_n)=n^2\bigg\{
\frac{\pi^2}{6L^2}+\frac{1}{12}-\alpha_2+\delta_5(\log_Qn)\bigg\}
+O(n^{1+\varepsilon}),
$$
where
$\displaystyle{
\alpha_2=\frac1L\sum_{k\ge1}\frac{1}{k\sinh(2k\pi^2/L)}
}$.
\comment
$$
\text{Var}(Y_n)=n^2\Big(\frac{\log2}{L}+\frac 2L\sum_{k\ge1}\frac{(-1)^{k-1}}
{k\big(Q^k-1\big)}
+\delta_5(\log_Qn
)\Big)+O(n^{1+\varepsilon}).
$$
\endcomment
Finally the following theorem holds.

\proclaim{Theorem 2} {\rm (i)} The covariance {\rm Cov}$(X_n,Y_n)$
 of the horizontal and the vertical
path lengths in a random skip list containing $n$ elements fulfills
for $n\to\infty$
$$
\aligned
\text{{\rm Cov}}(X_n,Y_n)=(Q-1)n^2\Bigg\{ &\frac{1}{L^2}
-\frac{\pi^2}{6L^2}
+\frac{8\pi^2}{L^2}h\Big(\frac{4\pi^2}{L}\Big)-\alpha_1
+\frac1L\sum_{k\ge1}\frac{1}{Q^k-1}\\ &
-\sum_{k\ge1}\frac{k}{\big(Q^k-1\big)^2}
+\delta_6(\log_Qn)
\Bigg\}
+O(n^{1+\varepsilon}),
\endaligned
$$
with $h$ and $\alpha_1$ from Theorem 1.
\comment
$$
\aligned
\text{{\rm Cov}}(X_n,Y_n)=(Q-1)n^2\Bigg\{ &
\frac 1L\bigg(2\log2-\frac32+\frac32\frac{1}{Q-1}+
\sum_{k\ge1}\frac{1}{Q^k-1}\\
&+2\sum_{k\ge2}\frac{(-1)^k}{(k+1)k(k-1)(Q^k-1)}
\bigg)\\
&+\frac{Q}{(Q-1)^2}-\sum_{k\ge 1}\frac{(k+1)Q^k}{\big(Q^k-1\big)^2}\Bigg\}
+O(n^{1+\varepsilon}).
\endaligned
$$
\endcomment

{\rm (ii)} The variance {\rm Var}$(C_n)$
 of the total cost fulfills for $n\to\infty$
$$\aligned
\text{{\rm Var}}(C_n)&=
\big(Q^2-1\big)n^2\bigg\{\frac{1}{2L}+\frac{1}{L^2}
-\frac{\pi^2}{6L^2}
+\frac{8\pi^2}{L^2}h\Big(\frac{4\pi^2}{L}\Big)-\alpha_1\bigg\}\\
&+2(Q-1)n^2\bigg\{
\frac 1L\sum_{k\ge1} \frac{1}{Q^k-1}-\sum_{k\ge1}\frac{k}{\big(Q^k-1\big)^2}
\bigg\}\\
&+n^2\bigg\{\frac{\pi^2}{6L^2}
+\frac{1}{12}-\alpha_2+\delta_7(\log_Qn)\bigg\}
+O(n^{1+\varepsilon}).
\endaligned
$$

\comment
$$
\aligned
\text{{\rm Var}}(C_n)=n^2\Bigg\{ & (Q-1)^2\bigg(\frac{1}{L}\Big(2\log2-1+2
\sum_{k\ge2}\frac{(-1)^k}{(k+1)k(k-1)(Q^k-1)}
\Big)\\ & \qquad\qquad -2\sum_{k\ge 1}\frac{Q^k}{\big(Q^k-1\big)^2}
\bigg)\\
&+(Q-1)\bigg(\frac{1}{L}\Big(4\log2-\frac12+2
\sum_{k\ge1}\frac{1}{Q^k-1}\\ &
+4\sum_{k\ge2}\frac{(-1)^k}{(k+1)k(k-1)(Q^k-1)}
\Big) -2
\sum_{k\ge 1}\frac{(k+1)Q^k}{\big(Q^k-1\big)^2}
\bigg)\\
&+\frac1L\Big(\log2+3+2
\sum_{k\ge1}\frac{(-1)^{k-1}}{k(Q^k-1)}
\Big)+Q+2\\
&+\frac{2}{Q-1}+\delta_7(\log_Qn)\Bigg\}+O(n^{1+\varepsilon}).
\endaligned
$$
\endcomment
\endproclaim

Theorems 1 and 2 show that the variances of the  path lengths are of order
$n^2$, whereas the variances of the corresponding parameter for regular
symmetric tries (under the Bernoulli model or the Poisson model) are of 
order $n$.  This means that random skip list parameters are not as closely
concentrated around their expectations as the corresponding parameters
for tries.

It is interesting to investigate the leading term of the variance of the
total cost (Theorem 2 (ii)) for different values of $q$ (resp. $Q=q^{-1}$)
numerically. It  turns out that the constant $K$ in Var$(C_n)\sim
n^2(K+\delta_7(\log_Qn))$ takes its minimum value for $q=0.31\dots$, which
differs a little from $q=\frac1e=0.36\dots$, where the main
 term of the expectation
takes its minimum. 
Nevertheless we can conclude that for values of $q$ close to $\frac1e$,
the variance is close to its minimum, too.
Below we give a small table of $q=Q^{-1}$ and the
corresponding values of the constant $K$.

%\input kratt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\catcode`\@=11
\newif\iftab@\tab@false
\newif\ifvtab@\vtab@false
\def\tab{\bgroup\tab@true\vtab@false\vst@bfalse\Strich@false%
   \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}
   \edef\l@{\the\leftskip}\ialign\bgroup\hskip\l@##\hfil&&##\hfil\cr}
\def\endtab{\cr\egroup\egroup}
\def\vtab{\vtop\bgroup\vst@bfalse\vtab@true\tab@true\Strich@false%
   \bgroup\def\\{\cr}\ialign\bgroup&##\hfil\cr}
\def\endvtab{\cr\egroup\egroup\egroup}
\def\stab{\D@cke0.5pt\null 
 \bgroup\tab@true\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@
 \edef\l@{\the\leftskip}\ialign
 \bgroup\hskip\l@##\hfil&&##\hfil\crcr}
\def\endstab{\crcr\egroup
 \egroup}
\newif\ifvst@b\vst@bfalse
\def\vstab{\D@cke0.5pt\null
 \vtop\bgroup\tab@true\vtab@false\vst@btrue\Strich@true\bgroup\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\bgroup}
\def\endvstab{\crcr\egroup\egroup
 \egroup\tab@false\Strich@false}

\newdimen\htstrut@
\htstrut@8.5\p@
\newdimen\htStrut@
\htStrut@12\p@
\newdimen\dpstrut@
\dpstrut@3.5\p@
\newdimen\dpStrut@
\dpStrut@3.5\p@
\def\openup{\afterassignment\@penup\dimen@=}
\def\@penup{\advance\lineskip\dimen@
  \advance\baselineskip\dimen@
  \advance\lineskiplimit\dimen@
  \divide\dimen@ by2
  \advance\htstrut@\dimen@
  \advance\htStrut@\dimen@
  \advance\dpstrut@\dimen@
  \advance\dpStrut@\dimen@}
\def\Let@@{\relax\iffalse{\fi%
    \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}%
    \iffalse}\fi}
\def\matrix{\null\,\vcenter\bgroup
 \tab@false\vtab@false\vst@bfalse\Strich@false\Let@@\vspace@
 \normalbaselines\openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr
 \Mathstrut@\crcr\noalign{\kern-\baselineskip}}
\def\endmatrix{\crcr\Mathstrut@\crcr\noalign{\kern-\baselineskip}\egroup
 \egroup\,}
\def\smatrix{\D@cke0.5pt\null\,
 \vcenter\bgroup\tab@false\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr}
\def\endsmatrix{\crcr\egroup
 \egroup\,\Strich@false}
\newdimen\D@cke
\def\Dicke#1{\global\D@cke#1}
\newtoks\tabs@\tabs@{&}
\newif\ifStrich@\Strich@false
\newif\iff@rst

\def\Stricherr@{\iftab@\ifvtab@\errmessage{\noexpand\s not allowed
     here. Use \noexpand\vstab!}%
  \else\errmessage{\noexpand\s not allowed here. Use \noexpand\stab!}%
  \fi\else\errmessage{\noexpand\s not allowed
     here. Use \noexpand\smatrix!}\fi}
\def\format{\ifvst@b\else\crcr\fi\egroup\iffalse{\fi\ifnum`}=0 \fi\format@}
\def\format@#1\\{\def\preamble@{#1}%
 \def\Str@chfehlt##1{\ifx##1\s\Stricherr@\fi\ifx##1\\\let\Next\relax%
   \else\let\Next\Str@chfehlt\fi\Next}%
 \def\c{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\r{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi}%
 \def\l{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\s{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@%
          \fi\the\tabs@\ }%
 \def\sa{\ifStrich@\vrule width\D@cke\the\hashtoks@%
            \the\tabs@\ %
            \fi}%
 \def\se{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@\fi}%
 \def\cd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \def\rd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$}%
 \def\ld{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \ifStrich@\else\Str@chfehlt#1\\\fi%
 \setbox\z@\hbox{\xdef\Preamble@{\preamble@}}\ifnum`{=0 \fi\iffalse}\fi
 \ialign\bgroup\span\Preamble@\crcr}
\newif\ifhline@\hline@false
\newif\ifhline@@\hline@@false
\def\hlinefor#1{\multispan@{\strip@#1 }\leaders\hrule height\D@cke\hfill%
    \global\hline@true\ignorespaces}
\catcode`\@=13
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$$
\smatrix \format \sa \l\s\r\se\\
\hlinefor{5}\\
& \ \ q\ &&    K\ \ \ \ \ &\\
\hlinefor{5}\\
&0.1&&10.57\dots&\\
&0.2& &3.16\dots&\\
&0.3&& 2.15\dots&\\
&\bold{0.31\dots}&& \bold{2.13\dots}&\\
&0.4&& 2.44\dots&\\
&0.5&& 3.66\dots&\\
&0.6&& 6.41\dots&\\
&0.7&&12.96\dots&\\
&0.8&&33.03\dots&\\
&0.9&&149.35\dots&\\
\hlinefor{5}\\
\endsmatrix
$$

The proof of the theorems is given in the next two sections. Section 2
contains the considerations on the horizontal path length. It starts with
a set-up of the appropriate generating functions, presents a transformation
that allows to express the coefficients as complex contour integrals in a
very efficient manner, and finally reveals the asymptotic equivalents of
the expectation and the second moment as the sums of residues at certain
poles. 
Section
3 contains the technical details concerning the second moment of the
total cost. 
In Section 4 we present an alternative representation for the constants
in the leading terms of Theorems 1 and 2 which is better suited
for numerical evaluations if $q$ is close to 0. For this purpose a
series transformation result has to be proved that is of its own
interest. 
In the final Section 5 we add some results on parameters
that can be
analyzed using the same toolkit as prepared for the analysis of the
path length.







\head
2. The horizontal path length \endhead

We start from the interpretation of a skip list $\rho$ of size $n+1$
as a finite sequence ($a_1,\dots,a_{n+1}$), $n\ge0$,  
 $a_i\in\{1,2,3,\dots\}$.
The horizontal path length $X_{n+1}(\rho)$ is the sum $b(\rho')$ of
all numbers of right-to-left maxima in the subsequences $(a_1,\dots,a_i)$,
$1\le i\le n$, of $\rho'=(a_1,\dots,a_{n})$.
In order to obtain an expression for the 
corresponding probability generating
function  it is convenient to start from the 
following combinatorial decomposition:
        
Let $m$ be the maximal element occuring in $\rho'$. Then we can write
$\rho'$ in a unique way as
$$
\rho=\sigma m\tau,\quad\text{where}\quad 
\sigma\in\{1,\dots,m-1\}^*,\  \tau\in\{1,\dots,m\}^*
\tag{2.1}
$$
(fixing the leftmost occurence of the maximum $m$). From this decomposition
it follows that
$$
b(\rho')=b(\sigma m\tau)=b(\sigma)+b(\tau)+|\tau|+1,\quad b(\varepsilon)
=0, \tag{2.2}
$$
since the contribution of the leftmost maximum 
is 1 plus the number of the succeding elements. The reader
might observe that relation \thetag{2.2}, in the context of
{\it permutations} $\rho'$ (and thus binary search trees), describes the
{\it right-sided} path length. However the probabilistic models are
quite different. (Compare e.g. \cite{\rsechs}, \cite{16}.)

We introduce the bivariate generating functions $P^{=m}(z,y)$, where
the coefficient of $z^ny^j$ is the probability that a skip list 
$\rho$ with
$n+1$ elements has maximum element (of the prefix $\rho'$)
$m$ and horizontal path length $j$ (of $\rho$).
$P^{\le m}(z,y)$ and $P^{<m}(z,y)$ are defined analogously. Then relation
\thetag{2.2} translates into the functional equation
$$
P^{=m}(z,y)=pq^{m-1}zyP^{<m}(z,y)P^{\le m}(zy,y),
\quad P^{=0}(z,y)=1.
\tag {2.3}
$$
Although no simple closed formula for the solution of \thetag{2.3}
is available, it allows to extract sufficient information on the moments
of the path length. 

If we set $F^*(z)=\frac{\partial P^*}{\partial y}(z,1)$, where $*$ stands
for $=m$, $\le m$ or $<m$, the generating function $F(z)=\sum_{n\ge0}
\text{E}(X_{n+1})z^n$ of the
{\it expectations} is obtained as
$$
F(z)=\lim_{m\to\infty}F^{\le m}(z).
$$
The derivative of \thetag{2.3} w.r.t. $y$ at $y=1$ involves the terms
$$
P^{\le m}(z,1)=\frac{1}{1-z(1-q^m)}=:\frac{1}{\[m\]}
\quad\text{and}\quad
\frac{\partial }{\partial z}P^{\le m}(z,1)=\frac{1-q^m}{\[m\]^2}
$$
and reads
$$
\frac{F^{\le m}(z)-F^{<m}(z)}{pq^{m-1}z}=
\frac{1}{\[m\]\[m-1\]}+\frac{z(1-q^m)}{\[m\]^2\[m-1\]}
+\frac{F^{\le m}(z)}{\[m-1\]}+
\frac{F^{<m}(z)}{\[m\]}.
$$
Performing some algebra it translates into
$$
F^{\le m}(z)
\[m\]^2=
F^{<m}(z)
\[m-1\]^2+
\frac{pq^{m-1}z}{\[m\]},
$$
which  can be solved by {\it iteration}, 
observing that $F^{\le0}(z)=0$:
$$
F^{\le m}(z)=\frac pq \frac z{\[m\]^2}\sum_{i=1}^m\frac{q^{i}}{\[i\]}.
\tag2.4
$$
Now we let $m$ tend to infinity and obtain
$$
F(z)=\frac pq\frac 
z{(1-z)^2}\sum_{i\ge1}\frac{q^i}{\[i\]}.\tag2.5
$$
The generating function $H(z)$ of the second factorial moments can be
obtained in the same way, although the computations are much more involved.
We use the notations $H^*(z)=\frac{\partial ^2P^*}{\partial y^2}(z,1)$.
The second derivative of \thetag{2.3} w.r.t. $y$ at $y=1$ involves 
additionally the 
quantities
$$
\frac{\partial^2P^{\le m}}{\partial z^2}(z,1)=\frac{2\big(1-q^m\big)^2}{\[m\]^3},
$$
and
$$
K^{\le m}(z):=
\frac{d}{dz}F^{\le m}(z)=
\frac{p}{q}
\cdot\bigg(\frac{1}{\[m\]^2}\sum_{j=1}^m\frac{q^j}{\[j\]^2}+
\frac{2z(1-q^m)}{\[m\]^3}\sum_{j=1}^m\frac{q^j}{\[j\]}
\bigg).
$$
In this way we find
$$\aligned
\frac{H^{\le m}(z)-H^{< m}(z)}{pq^{m-1}z}&=\frac{2z\left(1-q^m\right)}{{\[}m-1{\]}{\[}m{\]}^3}+
\frac{2z}{{\[}m-1{\]}}K^{\le m}(z)+\frac{1}{{\[}m-1{\]}}H^{\le m}(z)\\
&+\frac{1}{{\[}m{\]}}H^{< m}(z)
+\frac{2}{{\[}m-1{\]}}F^{\le m}(z)
+\frac{2}{{\[}m{\]}}F^{< m}(z)\\
&+\frac{2z(1-q^m)}{{\[}m{\]}^2}F^{< m}(z)+2F^{\le m}(z)F^{< m}(z).
\endaligned
$$
Again we get a first order difference equation
$$\aligned
H^{\le m}(z)
{\[}m{\]}^2=
H^{<m}(z)
{\[}m-1{\]}^2+2pq^{m-1}z&\cdot
\bigg\{\frac{z\left(1-q^m\right)}{{\[}m{\]}^2}
+z{\[}m{\]}K^{\le m}(z)\\
&+{{\[}m{\]}}F^{\le m}(z)
+\frac{{\[}m-1{\]}}{{\[}m{\]}}F^{< m}(z)\\
&+{\[}m{\]}{\[}m-1{\]}F^{\le m}(z)F^{< m}(z)\bigg\}.
\endaligned
$$
This equation can be solved for $H^{\le m}(z)$ by iteration;
performing the limit for $m\to\infty$ we finally achieve the generating
function $H(z)$:
$$
\aligned
{H(z)}
&={2\frac pq}\frac z{(1-z)^2}\sum_{i\ge1}\frac{q^{i}}{{\lk}i{\rk}^2}\\
&-{2\frac pq}\frac z{(1-z)^2}\sum_{i\ge1}\frac{q^{i}}{{\lk}i{\rk}}\\
&-{2\left(\frac pq\right)^2}\frac{z^2}{(1-z)^2}\sum_{1\le j\le i}\frac{q^{i+j}}{{\lk}i{\rk}{\lk}j{\rk}}\\
&+4\left({\frac pq}\right)^2\frac{z^2}{(1-z)^2}\sum_{1\le j\le i}
\frac{q^{i+j}}{{\lk}i{\rk}^2{\lk}j{\rk}}\\
&+{2\left(\frac pq\right)^2}\frac{z^2}{(1-z)^2}\sum_{1\le j\le i}\frac{q^{i+j}
}{{\lk}i{\rk}{\lk}j{\rk}^2}\\
&+{2\left(\frac pq\right)^2} \frac{z^2}{(1-z)^2}\sum_{1\le j<i}\frac{q^{i+j}}{{\lk}i{\rk}{\lk}i-1{\rk}{\lk}j{\rk}}\\
&+2\left(\frac {p}q\right)^3\frac{z^3}{(1-z)^2}
\sum_{i\ge1}\sum_{1\le j\le i}\sum_{1\le h<i}
\frac{q^{i+j+h}}{{\lk}i{\rk}{\lk}i-1{\rk}{\lk}j{\rk}{\lk}h{\rk}}.
\endaligned \tag 2.6
$$

Now we turn to the {\it evaluation of the expectations} $\text{E}(X_{n})$. 
Since the
generating function $F(z)$ is not too complicated, we find, e.g. by
partial fraction decomposition and extracting the coefficients, that
$$
\text{E}(X_{n})=[z^{n-1}]F(z)=\frac pq\sum_{i\ge1}\left[
-Q^i+n+ Q^i\left(1-q^i\right)^{n}
\right]\tag2.7
$$
where $Q=q^{-1}$, 
or, by expanding the binomial and interchanging the summations,
$$
\text{E}(X_{n})
=\frac pq
\sum_{k=2}^{n}\binom{n}k(-1)^k\frac{1}{Q^{k-1}-1}. \tag 2.8
$$

In order to get the asymptotic equivalent for $\text{E}(X_{n})$ we might 
apply a Mellin transform approach (cf.~\cite{4}) to \thetag{2.7}.
Alternatively, the expression \thetag{2.8} can be rewritten as a
complex contour integral (Rice's method), namely
$$
\text{E}(X_{n})=\frac pq\cdot
\frac{1}{2\pi i}
\int_\Cal C B(n+1,-z)\frac{1}{Q^{z-1}-1}dz,\tag 2.9
$$
where $\displaystyle{B(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}}$
is the {\it Beta function} and the contour $\Cal C$ encircles the poles
$z=2,3,\dots,n$. Now the asymptotics are obtained by extending the
contour $\Cal C$ ``to the left'' and collecting the additional residues.
(Compare \cite{3} for technical details of this procedure.)

In the integral \thetag{2.9} we have additional poles with real part
larger than zero at $z=\chi_k$, $\chi_k=\frac{2k\pi i}{\log Q}$,
$k\in\Bbb Z$. The computation of the residues is standard and can be performed
e.g. by {\sc Maple}. It yields for the double pole $z=1$
$$
\text{Res}_{z=1}B(n+1,-z)\frac{1}{Q^{z-1}-1}=
\frac{n}{L}\Big(H_{n-1}-1-\frac L2\Big),
$$
with $L=\log Q$ and $H_n$ the $n$-th Harmonic number, and thus the
asymptotic contribution to $\text{E}(X_{n})$
$$
\frac pq\, \frac{n}{L}\Big(\log n+\gamma-1-\frac L2\Big)+O(\log n).
$$
Similarily the simple poles $z=1+\chi_k$, $k\ne 0$, contribute
$$
\frac pq\, \frac{1}{L}\sum_{k\ne 0}
\Gamma(-1-\chi_k)n^{1+\chi_k}\Big(1+O\big(\frac 1n\big)\Big).
\tag 2.11
$$
Collecting all contributions we have Proposition 1 (i).\bigskip

In the sequel we concentrate on our main goal, namely the computation
of the {\it variance} $\text{Var}(X_n)$. We have
$$
\text{Var}(X_{n})=[z^{n-1}]H(z)+\text{E}(X_{n})-\text{E}(X_{n})^2,\tag 2.11
$$
so that we need a well suited expression for  the coefficients of $H(z)$.

For this purpose it is extremely useful to start with the following
technical observations.
In \cite{2} Flajolet and Richmond made extensive use of the relation
$$
A(z)=\sum_{n\ge 0}a_nz^n\longleftrightarrow
\frac{1}{1-w}A\Big(\frac{w}{1-w}\Big)=
\sum_{n\ge0}\bigg(
\sum_{k=0}^n\binom nk a_k\bigg) w^n.
\tag 2.12
$$
Of course this relation can be inverted to read
$$
A(z)=\sum_{n\ge0}\bigg(
\sum_{k=0}^n\binom nk (-1)^kf(k)\bigg) z^n\longleftrightarrow
\frac{1}{1-w}A\Big(\frac{w}{w-1}\Big)=\sum_{n\ge 0}f(n)w^n.
\tag 2.13
$$
The alternating sum can now be rewritten by Rice's method (compare above),
and in this way we find






\proclaim{Lemma 1} Let $A(z)$ be a formal power series and
$$
f_n=[w^n]\frac{1}{1-w}A\Big(\frac{w}{w-1}\Big),\qquad n\ge 0\tag2.14
$$
with $f_0=f_1=\dots=f_{s-1}=0$. Then
$$
[z^n]A(z)=\frac{1}{2\pi i}\int\limits_{\Cal C(s,\dots,n)}
B(n+1,-z)f(z)dz,\tag2.15
$$
where $\Cal C(s,\dots,n)$ encircles the poles $z=s,s+1,\dots,n$,
$B$ is the Beta function and 
$f(z)$ is  analytic inside $\Cal C$ with $f(n)=f_n$ for all $n\ge s$.
\endproclaim
%\demo{Proof} We have
%$$\align
%[z^n]A(z)&=[z^n]\frac{-1}{z-1}\sum_{k\ge s}f(k)\frac{z^k}{(z-1)^k}\\
%&=\sum_{k\ge s}f(k)(-1)^k[z^{n-k}](z-1)^{-k-1}\\
%&=\sum_{k\ge s}\binom nk(-1)^kf(k),
%\endalign
%$$
%which can be rewritten as the contour integral as discussed above.
%\enddemo

The following generalization will be useful.

\proclaim{Lemma 2} With the assumptions of  Lemma 1 we have
$$
[z^n]\frac{1}{\big(1-z\big)^r}
A(z)=\frac{(-1)^r}{2\pi i}\int\limits_{\Cal C(s+r,\dots,n+r)}
B(n+r+1,-z)f(z-r)dz.\tag2.16
$$
\endproclaim
\demo{Proof} With $z=\dfrac w{w-1}$ we have $(1-z)^{-r}=(-1)^r\dfrac{w^r}{z^r}$,
so that 
$$
[z^n](1-z)^{-r}A(z)=(-1)^r[z^{n+r}]w^rA(z).
$$
The result follows now from Lemma 1.\qed
\enddemo

In order to compute the coefficients $f_n$ in \thetag{2.14} for
the formal series $A(z)$ occuring in our problem we will frequently
apply

\proclaim{Lemma 3} Let $C$ and $D$ be formal power series. Then
$$
[w^n]\sum_{i\ge 0}C(wq^i)=\frac{1}{1-q^n}[w^n]C(w),\qquad n\ge 0 ,\tag 2.17
$$
$$
[w^n]\sum_{i\ge 1}C(wq^i)=\frac{1}{Q^n-1}[w^n]C(w),\qquad n\ge 1, \tag 2.18
$$
$$
[w^n]\sum_{i\ge 1}iC(wq^i)=\frac{Q^n}{\big(Q^n-1\big)^2}[w^n]C(w),
\qquad n\ge 1, \tag 2.19
$$
$$
[w^n]\sum_{1\le j\le i}C(wq^i)D(wq^j)=\frac{1}{Q^n-1}\sum_{m=1}^n
\frac{1}{1-q^m}[w^m]C(w)\cdot [w^{n-m}]D(w), \tag 2.20
$$
and
$$
[w^n]\sum_{1\le j<i}C(wq^i)D(wq^j)=\frac{1}{Q^n-1}\sum_{m=1}^n
\frac{1}{Q^m-1}[w^m]C(w)\cdot [w^{n-m}]D(w), \tag 2.21
$$

\endproclaim
\demo{Proof} Immediate. \qed\enddemo


Now we are ready to  express $[z^{n-1}]H(z)$ as a complex contour integral.
We confine ourselves here to show how the method works for two of the
seven terms in \thetag{2.6}.

Let us start with the relatively simple first one, namely
$$
A_1(z)=\frac{z}{(1-z)^2}\sum_{i\ge 1}\frac{q^i}{\[i\]^2}=:
\frac{1}{(1-z)^2}\bar A_1(z).
\tag2.22
$$
With the substitution $z=\dfrac w{w-1}$ we have
$$
\frac{1}{\[i\]}=\frac{1-w}{1-wq^i}\tag 2.23
$$
and therefore
$$
\frac{1}{1-w}\bar A_1\Big(\frac{w}{w-1}\Big)=-w\sum_{i\ge1}
\frac{q^i}{\big(1-wq^i\big)^2}.
$$
From Lemma 3 \thetag{2.18} we find
$$
[w^n]\sum_{i\ge1}
\frac{wq^i}{\big(1-wq^i\big)^2}=\frac{1}{Q^n-1}[w^n]
\frac{w}{\big(1-w\big)^2}=\frac{n}{Q^n-1}.
$$
Therefore, by Lemma 2,
$$
[z^{n-1}] A_1(z)=
\frac{-1}{2\pi i}\int\limits_{\Cal C(3,\dots,n+1)}
B(n+2,-z)\frac{z-2}{Q^{z-2}-1}dz.\tag 2.24
$$

The most complicated term in $H(z)$ is
$$
A_7(z)=
\frac{z^3}{(1-z)^2}
\sum_{i\ge1}\sum_{1\le j\le i}\sum_{1\le h<i}
\frac{q^{i+j+h}}{{\lk}i{\rk}{\lk}i-1{\rk}{\lk}j{\rk}{\lk}h{\rk}}
=:
\frac{1}{(1-z)^2}\bar A_7(z).
\tag2.25
$$
Here we have
$$
\frac{1}{1-w}\bar A_7\Big(\frac{w}{w-1}\Big)=-\sum_{i\ge1}
\frac{wq^i}{\big(1-wq^i\big)\big(1-wq^{i-1}\big)}S^{\le i}(w)
S^{\le {i-1}}(w),\tag 2.26
$$
where
$$
S^{\le i}(w)=\sum_{1\le j\le i }\frac{wq^j}{1-wq^j}.
$$
Now, a partial fraction decomposition gives
$$
\frac{wq^i}{\big(1-wq^i\big)\big(1-wq^{i-1}\big)}=
\frac{1}{Q-1}\bigg(
\frac{wq^{i-1}}{1-wq^{i-1}}-\frac{wq^{i}}{1-wq^{i}}\bigg),
$$
so that the whole expression \thetag{2.26} telescopes to 
$$
\frac{-1}{Q-1}\Bigg(\frac{w}{1-q}S^{\le 1}(w)
S^{\le {0}}(w)+
\sum_{i\ge 1}\frac{wq^i}{1-wq^i}
\bigg(
\frac{wq^{i}}{1-wq^{i}}+\frac{wq^{i+1}}{1-wq^{i+1}}\bigg)
S^{\le {i}}(w)\Bigg).
$$
Since $S^{\le {0}}(w)=0$ we get with Lemma 3 \thetag{2.20}
$$
\aligned
[w^n]\frac{1}{1-w}\bar A_7\Big(\frac{w}{w-1}\Big)
&=-\frac{1}{Q-1}\frac{1}{Q^n-1}\sum_{m=2}^{n-1}
\frac{1}{1-q^m}\times\\ & \times[w^m]\left(\Big(\frac{w}{1-w}\Big)^2+
\frac{w^2q}{(1-w)(1-wq)}\right)\cdot1.
\endaligned
\tag 2.27
$$
A short calculation shows that
$$
[w^m]\left(\Big(\frac{w}{1-w}\Big)^2+
\frac{w^2q}{(1-w)(1-wq)}\right)=m-1+\frac{1}{Q-1}\big(1-Q^{1-m}\big),
$$
so that finally \thetag{2.27} is equal to
$$
-\frac{1}{Q-1}\frac{1}{Q^n-1}
\left(
\binom{n-1}2+\frac{n-2}{Q-1}+\sum_{m=2}^{n-1}\frac{m-2}{Q^m-1}
\right).
\tag 2.28
$$
It is not difficult to find an analytic continuation, if we observe that
$$
\sum_{m=2}^{n-1}\frac{m-2}{Q^m-1}=
\sum_{m\ge 2}\frac{m-2}{Q^m-1}-\sum_{m\ge 0}\frac{n+m-2}{Q^{n+m}-1}.
$$
Altogether Lemma 2 yields
$$
\aligned
[z^{n-1}]A_7(z)&=
\frac{-1}{2\pi i}\frac{1}{Q-1}\int\limits_{\Cal C(4,\dots,n+1)}
B(n+2,-z)\frac{1}{Q^{z-2}-1}\times\\ & \times
\Bigg(\binom{z-3}2+\frac{z-4}{Q-1}+
\sum_{m\ge 2}\frac{m-2}{Q^m-1}-\sum_{m\ge 0}\frac{z+m-4}{Q^{z+m-2}-1}
\Bigg) dz.
\endaligned
\tag 2.29
$$
Observe that $\Cal C(4,\dots,n+1)$ may be replaced by $\Cal C(3,\dots,n+1)$
since $z=3$ is a removable singularity of the integrand.

The remaining sums $A_i(z)$ in expression \thetag{2.6} for $H(z)$
can be treated in a similar way. Collecting all contributions we find

\proclaim{Lemma 4}
$$
\aligned
[z^{n-1}]H(z)&=2(Q-1)^2\cdot\frac{1}{2\pi i}\Bigg\{
\int\limits_{\Cal C(2,\dots,n)}
B(n+1,-z)\frac{1}{Q^{z-1}-1}\times\\ & \times\bigg( z-2-
\frac{1}{Q-1}+\alpha-\sum_{m\ge0}\frac{1}{Q^{z+m-1}-1}\bigg)dz\\
&+
\int\limits_{\Cal C(3,\dots,n+1)}
B(n+2,-z)\frac{1}{Q^{z-2}-1}\times\\ & \times\bigg( (z-3)(z-1)-
\frac{z-2}{Q-1}+z\alpha-z\sum_{m\ge0}\frac{1}{Q^{z+m-2}-1}\bigg)dz\Bigg\}
\endaligned
\tag 2.30
$$
with $\displaystyle{\alpha=\sum_{m\ge1}\frac{1}{Q^m-1}}$.
\endproclaim

In order to get the asymptotic behaviour of $[z^{n-1}]H(z)$ 
for $n\to\infty$
we extend the contour of integration to a large rectangle and shift the left
side to the line $\text{Re}\  z=1+\varepsilon$, $\varepsilon>0$.
Then $[z^{n-1}]H(z)$ equals the sum of residues at the additional poles 
included in the contour with an error term of order $ O(n^{1+\varepsilon})$
(compare \cite{3} for technical details of the estimate of the error term).
In our instance the additional poles originate from the second integral,
and they are located at $z=2$ (triple) resp. $z=2+\chi_k$, $k\in \Bbb Z
\setminus\{0\}$ (simple). The computation of the residues can be performed
by hand, or, more preferably, e.g. by {\sc Maple}, and we find for the residue
at $z=2$
$$\aligned
2(Q-1)^2\binom{n+1}2\Bigg\{&
\frac{H_{n-1}^2}{L^2}+\frac{H_{n-1}^{(2)}}{L^2}-
\frac{H_{n-1}}{L}\big(1+\frac 2L\big)
\\ & +\frac 13+\frac{2}{L^2}-2(\alpha+\beta)+\frac{1}{2L}+\frac{1}{(Q-1)L}
\Bigg\},
\endaligned \tag 2.31
$$
where $L=\log Q$, $H_n$ resp. $H_n^{(2)}$ are the Harmonic numbers of
first resp. second order, 
and
$\displaystyle{\beta=\sum_{m\ge 1}\frac{1}{\big(Q^m-1\big)^2}}$.

The asymptotic equivalent of \thetag{2.31} is
$$
\aligned
&2(Q-1)^2\Bigg\{\frac{n^2\log_Q^2n}{2}+n^2\log_Qn\Big(\frac{\gamma}{L}
-\frac12-\frac1L\Big)\\
&+n^2\Big(\frac 16+\frac{1}{L^2}
-\alpha-\beta-\frac{\gamma}{2L}-\frac{\gamma}{L^2}+\frac{\gamma^2}
{2L^2}+\frac{\pi^2}{12L^2}+\frac{1}{4L}+\frac{1}{2(Q-1)L}\Big)\\
&+O\big(n\log^2n\big)\Bigg\}
\endaligned
\tag 2.32
$$
The first order poles at $z=2+\chi_k$, $k\in \Bbb Z\setminus\{0\}$, give
a contribution of the form
$$
n^2\delta_8(\log_Qn)+O(n),\tag 2.33
$$
where $\delta_8(x)$ is a continuous periodic function of period 1 and mean 
zero. The Fourier coefficients of $\delta_8(x)$ can be obtained 
explicitly from the
residues at the above mentioned poles. They can be used to show that the
amplitude of $\delta_8(x)$ is very small (because of the exponential
decrease of the $\Gamma$-function along vertical lines). Since from
the practical point of view $\delta_8(x)$ has almost no influence on
the variance, we omit these calculations here.

Combining \thetag{2.32}, \thetag{2.33} and Proposition 1 we get the
asymptotic equivalent of $\text{Var}(X_n)$
according to \thetag{2.11}. The reader should take notice of the
fact that the term of order $n^2$ in $\text{E}(X_n)^2$ contains the square
$\delta_1^2(\log_Qn)$ of the fluctuating term $\delta_1(\log_Qn)$,
where $\delta_1(x)$ has mean zero. Therefore we have
$$
\aligned
\text{Var}(X_{n})&= (Q-1)^2n^2\bigg\{\frac{1}{L^2}+\frac{1}{12}-\frac{1}{2L}+
\frac{\pi^2}{6L^2}-2(\alpha+\beta)+\frac{1}{(Q-1)L}-\frac{1}{L^2}
\big[\delta_1^2\big]_0\bigg\}\\
&+n^2\delta_4(\log_Qn)+O\big(n^{1+\varepsilon}\big),\qquad \varepsilon>0,
\endaligned\tag 2.34
$$
where $\big[\delta_1^2\big]_0$ is the mean of $\delta_1^2(x)$, and
$\delta_4(x)$ is a small periodic function of period 1 and mean {\it zero}.

The quantity $\displaystyle{\alpha+\beta=\sum_{k\ge1}\frac{Q^k}{
\big(Q^k-1\big)^2}}$ can be rewritten as
$$
\alpha+\beta=h(L)=\frac{\pi^2}{6L^2}-\frac{1}{2L}+\frac{1}{24}-
\frac{4\pi^2}{L^2}h\Big(\frac{4\pi^2}{L}\Big),\tag2.35
$$
where
$$
h(x)=\sum_{k\ge1}\frac{e^{kx}}{\big(e^{kx}-1\big)^2}.\tag2.36
$$
Equation \thetag{2.35} follows from the functional equation for the
Dedekind $\eta$-function and is proved e.g. in \cite{\rfuenf}. The alternative
representation for $\alpha+\beta$ given by \thetag{2.35}
is extremely useful for numerical purposes, since the term
$\frac{4\pi^2}{L^2}h(\frac{4\pi^2}{L})$ is very small for
``reasonable'' values of $q$ resp. $Q=q^{-1}$.
 
The term $\big[\delta_1^2\big]_0$ 
can be computed explicitly from the Fourier expansion
in Proposition 1. 
Since (compare e.g. \cite{18})
$$
|\Gamma(iy)|=\frac{\pi}{y\sinh \pi y},\tag 2.37
$$
we find
$$
\frac{1}{L^2}\big[\delta_1^2\big]_0=\alpha_1\tag 2.38
$$
with $\alpha_1$ defined in the theorem. Therefore the proof of Theorem 1
is complete.

\head 3. The total cost \endhead

As already mentioned in the Introduction, the total cost $C_n$
is the sum of the horizontal path length $X_n$ and the vertical path
length $Y_n$, where $Y_n$ is $n$ times the height of the skiplist.
The variance of the latter parameter was already studied in \cite{\rzehn}
resp. \cite{17} and we have
the asymptotic equivalents for E$(Y_n)$ resp. Var$(Y_n)$ as presented
in the Introduction.
It is an easy consequence that $\text{E}(C_n)=\text{E}(X_n)+\text{E}(Y_n)$
fulfills the asymptotic relation from Proposition 1 (ii).\medskip

 In order to
compute $\text{Var}(C_n)=\text{Var}(X_n+Y_n)$ we use
$$
\text{Var}(C_n)=\text{Var}(X_n)+\text{Var}(Y_n)+2\text{Cov}(X_n,Y_n),
\tag3.1
$$
where the {\it covariance} $\text{Cov}(X_n,Y_n)= \text{E}(X_nY_n)
-\text{E}(X_n)\text{E}(Y_n)$ will be studied in the sequel.
\medskip

We start with the term $ \text{E}(X_nY_n)$. The generating function
of $\dfrac 1{n+1} \text{E}(X_{n+1}Y_{n+1})$ is
$$
\sum_{m\ge1}F^{=m}(z)\bigg(m\text{Prob}(G\le m)+
\sum_{k>m}k\text{Prob}(G=k)\bigg)\tag3.2
$$
where $G$ stands for the random variable producing the last elment of
the skip list $(a_1,\dots)$. (Observe that the random variables in 
question were assumed to be i.i.d.) From \thetag{4.2} we get immediately
the expression


$$
\sum_{m\ge 1}F^{=m}(z)\bigg(m+\frac{q^m}{1-q}\bigg)
=\sum_{m\ge 0}\Big(F(z)-\big(1-q^m\big)F^{\le m}(z)\Big).
\tag 3.3
$$
Now from \thetag{2.4} and \thetag{2.5}
$$
\aligned
&\sum_{m\ge 0}\Big(F(z)-\big(1-q^m\big)F^{\le m}(z)\Big)\\
&=(Q-1)z\Bigg(
\sum_{m\ge 0}\bigg(\frac{1}{(1-z)^2}-\frac{1-q^m}{\[m\]^2}\bigg)
\sum_{i=1}^m\frac{q^i}{\[i\]}+\sum_{m\ge 0}\frac{1}{(1-z)^2}
\sum_{i>m }\frac{q^i}{\[i\]}\Bigg),
\endaligned
$$
which can be rewritten as
$$
=(Q-1)z\Bigg(
\frac{1}{1-z}\sum_{1\le i\le j}\frac{q^{i+j}}{\[i\]\[j\]^2}+
\frac{z}{(1-z)^2}\sum_{1\le i\le j}\frac{q^{i+j}}{\[i\]\[j\]}
+\frac{1}{(1-z)^2}\sum_{i\ge1}\frac{iq^{i}}{\[i\]}\Bigg).
\tag 3.4
$$
The evaluation of the coefficients may now be performed by the same
 technique
as in Section 2. Observe that we use Lemma 3 \thetag{2.19} for the third
sum. We find
$$
\aligned
 \text{E}(X_nY_n)=(Q-1)n&\cdot \Bigg\{
\frac{1}{2\pi i}\int\limits
_{\Cal C(2,\dots,n)}B(n+1,-z)\frac{1}{Q^{z-1}-1}\times\\
&\times\bigg(
3-z-\alpha+\sum_{m\ge 0}\frac{1}{Q^{m+z}-1}+\frac{2}{Q^{z-1}-1}
\bigg)dz
 \\
&+\frac{1}{2\pi i}\int\limits
_{\Cal C(2,\dots,n+1)}B(n+2,-z)\frac{1}{Q^{z-1}-1}\times\\
&\times \bigg(-\binom{z-1}2-\sum_{m\ge 1}\frac{m}{Q^m-1}+
\sum_{m\ge 0}\frac{m+z-1}{Q^{m+z-1}-1}\bigg)dz
\Bigg\}
.
\endaligned
\tag 3.5
$$
The computation of the residues at $z=1$ (third order pole) resp.
$z=1+\chi_k$, $k\in\Bbb Z\setminus\{0\}$ (simple poles) gives  the
main asymptotic terms, from which we obtain
$$
\aligned
\text{Cov}(X_n,Y_n)=(Q-1)n^2\bigg\{
&\frac{1}{L^2}+\frac{1}{12}-\frac 1L+\frac{\pi^2}{6L^2}
+\frac{\alpha}{L}
-\sum_{k\ge1}\frac{k}{\big(Q^k-1\big)^2}-2(\alpha+\beta)\\
&+\frac{1}{L^2}
\big[\delta_1\delta_2\big]_0+\delta_6(\log_Qn)\bigg\}+O(n^{1+\varepsilon
}),
\endaligned
\tag 3.6
$$
with 
$\delta_6(x)$ of mean zero. Now
$$
\aligned
\big[\delta_1\delta_2\big]_0&=\sum_{k\ne0}\Gamma(\chi_k)
\Gamma(-1-\chi_k)\\
&=\sum_{k\ne0}(-1+\chi_k)\Gamma(-1+\chi_k)
\Gamma(-1-\chi_k)\\
&=-\big[\delta_1^2\big]_0+2\text{Re}\sum_{k>0}\chi_k
\big|\Gamma(-1-\chi_k)\big|^2\\
&=-\big[\delta_1^2\big]_0,
\endaligned
\tag 3.7
$$
so that $\frac{1}{L^2}\big[\delta_1\delta_2\big]_0$ is the negative value from
\thetag{2.38}. Inserting the last result in \thetag{3.6} we find 
Theorem 2 (i). The variance Var$(C_n)$
of the total cost is now computed by \thetag{3.1}, and this completes
the proof of Theorem 2 (ii).





















\head 4. 
Alternative Representations for the Constants
\endhead


For values of $q$ that are very close to 0, i.e. $Q$ very large, the
representations of the constants in the theorems are not
well-suited for numerical evaluation. Therefore we present the following
alternative expressions. Concerning $\alpha+\beta$ we stay with the
original representation
$$
\alpha+\beta=\sum_{k\ge1}\frac{Q^k}{\big(Q^k-1\big)^2}.
$$
With regard to $\big[\delta_1^2\big]_0$ the following transformation
can be performed.



From the Fourier expansion of $\delta_1(x)$ in Proposition 1 we have
$$
\big[\delta_1^2\big]_0=\sum_{k\ne0}\Gamma(-1+\chi_k)
\Gamma(-1-\chi_k),\qquad \chi_k=\frac{2k\pi i}{L}.
\tag 4.1
$$
Let us consider the function 
$$
g(z)=L\frac{\Gamma(-1+z)
\Gamma(-1-z)}{e^{Lz}-1}.
\tag 4.2
$$
Then $\big[\delta_1^2\big]_0$ is the sum of residues of $g(z)$ at the
poles $z=\chi_k$, $k\in\Bbb Z\setminus\{0\}$. Furthermore
$$
\text{Res}_{z=0}g(z)=-\frac{L^2}{12}-\frac{\pi^2}{6}-1.\tag4.3
$$
Combining these observations we can easily conclude that ($0<\varepsilon
<1$)
$$
\frac{1}{2\pi i}\int\limits_{\varepsilon-i\infty}^{\varepsilon+i\infty}
g(z)dz-
\frac{1}{2\pi i}\int\limits_{-\varepsilon-i\infty}^{-\varepsilon+i\infty}
g(z)dz=\big[\delta_1^2\big]_0-\frac{L^2}{12}-\frac{\pi^2}{6}-1\tag4.4
$$
since the $\Gamma$-function decreases exponentially towards $\pm i\infty$.
Because of
$$
\frac{1}{e^{-Lz}-1}=-1-\frac{1}{e^{Lz}-1}
$$
we have
$$
\frac{1}{2\pi i}\int\limits_{-\varepsilon-i\infty}^{-\varepsilon+i\infty}
g(z)dz=
\frac{1}{2\pi i}\int\limits_{\varepsilon-i\infty}^{\varepsilon+i\infty}
g(z)dz
+\frac{L}{2\pi i}\int\limits_{\varepsilon-i\infty}^{\varepsilon+i\infty}
\Gamma(-1+z)\Gamma(-1-z)
dz.
\tag 4.4
$$
Altogether
$$
\big[\delta_1^2\big]_0=\frac{L^2}{12}+\frac{\pi^2}{6}+1+
\frac{2}{2\pi i}\int\limits_{\varepsilon-i\infty}^{\varepsilon+i\infty}
g(z)dz
+
\frac{L}{2\pi i}\int\limits_{\varepsilon-i\infty}^{\varepsilon+i\infty}
\Gamma(-1+z)\Gamma(-1-z)
dz.
\tag 4.5
$$
It is easily verified that both remaining integrals coincide with the negative
sum of the corresponding residues at the poles with real part greater than
0. Collecting the residues at $z=1$ (double pole) and $z=k\in\Bbb N$,
$k\ge 2$ (simple poles) we finally obtain
$$
\aligned
\big[\delta_1^2\big]_0&=\frac{L^2}{12}+\frac{\pi^2}{6}+1-
\frac{QL^2}{(Q-1)^2}-\frac 32\frac{QL}{Q-1}\\ &+2L-2L\log 2
-2L\sum_{k\ge2}\frac{(-1)^k}{(k+1)k(k-1)(Q^k-1)}
\endaligned\tag 4.6
$$
Inserting \thetag{4.6} in expression \thetag{2.34} 
gives for the
variance of the horizontal path length the 
following alternative formula.
\proclaim{Corollary 1}
$$
\aligned
\text{{\rm Var}}(X_n)&=(Q-1)^2n^2\Bigg\{\frac 1L\bigg(2\log 2 -1+\frac 52\frac{1}{Q-1}+
2\sum_{k\ge2}\frac{(-1)^k}{(k+1)k(k-1)(Q^k-1)}\bigg)\\
&+\frac{Q}{(Q-1)^2}-2\sum_{k\ge1}\frac{Q^k}{(Q^k-1)^2}
+\delta_4(\log_Qn)\Bigg\}+O\big(n^{1+\varepsilon}\big),\qquad \varepsilon>0.
\endaligned
$$
\endproclaim

In a similar manner we obtain

\TagsOnLeft

\proclaim{Corollary 2}

%\noindent {\rm (i)}
$$
\text{{\rm Var}}(Y_n)=n^2\bigg(\frac{\log2}{L}+\frac 2L\sum_{k\ge1}\frac{(-1)^{k-1}}
{k\big(Q^k-1\big)}
+\delta_5(\log_Qn
)\bigg)+O(n^{1+\varepsilon}),\tag \text{{\rm i}}
$$

%\noindent {\rm (ii)}
$$
\align
\text{{\rm Cov}}(X_n,Y_n)&=(Q-1)n^2\Bigg\{ 
\frac 1L\bigg(2\log2-\frac32+\frac32\frac{1}{Q-1}+
\sum_{k\ge1}\frac{1}{Q^k-1}\tag \text{{\rm ii}}\\
&+2\sum_{k\ge2}\frac{(-1)^k}{(k+1)k(k-1)(Q^k-1)}
\bigg)\\
&+\frac{Q}{(Q-1)^2}-\sum_{k\ge 1}\frac{(k+1)Q^k}{\big(Q^k-1\big)^2}
+\delta_6(\log_Qn)\Big)
\Bigg\}
+O(n^{1+\varepsilon}).
\endalign 
$$
\endproclaim

\TagsOnRight

Again, Var$(C_n)$ is easily computed from the terms above using
\thetag{3.1}.



\head 5. Variations \endhead

Here we first discuss the analogous notion of the path length where
only strictly greater elements count as  right-to-left maxima.
This is quite natural from a combinatorial point of view. However,
since there is no relevance with respect to a computer science  problem,
we confine ourselves to a sketch and, to ease the presentation, use
the analogous notations without explicitly stating them.


We write
$\rho'$ in a unique way as
$$
\rho'=\sigma m\tau,\quad\text{where}\quad 
\sigma\in\{1,\dots,m\}^*,\  \tau\in\{1,\dots,m-1\}^*;
$$
then
$$
b(\rho)=b(\sigma m\tau)=b(\sigma)+b(\tau)+|\tau|+1,\quad b(\varepsilon)
=0.
$$
Hence
$$
P^{=m}(z,y)=pq^{m-1}zyP^{\le m}(z,y)P^{<m}(zy,y),
\quad P^{=0}(z,y)=1,
$$
and 
$$
\frac{F^{\le m}(z)-F^{<m}(z)}{pq^{m-1}z}=
\frac{1}{\[m\]\[m-1\]}+\frac{z(1-q^{m-1})}{\[m\]\[m-1\]^2}
+\frac{F^{\le m}(z)}{\[m-1\]}+
\frac{F^{<m}(z)}{\[m\]}
$$
or
$$
F^{\le m}(z)
\[m\]^2=
F^{<m}(z)
\[m-1\]^2+
\frac{pq^{m-1}z}{\[m-1\]}.
$$
Again we solve it by iteration and let $m$ tend to infinity;
$$
F(z)=p\frac 
z{(1-z)^2}\sum_{i\ge0}\frac{q^i}{\[i\]}.
$$
So the expection $\text{E}(X_n)$ is closely related to the old one; since there
is the extra summand for $i=0$, it is $p(n-1)$ plus $q$ {\it times the
expectation from before}. (The reader should remember that E$(X_n)$
stands for the right-to-left maxima in a sequence of length $n-1$.)
\bigskip

Next, we discuss the case where ``maximum'' is replaced by ``minimum''.
Let's start with the first variant (equality {\it counts}).
$$
P^{=m}(z,y)=pq^{m-1}zyP^{>m}(z,y)P^{\ge m}(zy,y),
\quad P^{=0}(z,y)=1,
$$
This time $F(z)=F^{\ge1}(z)$ is the generating function of interest.
With
$$
\llk m\rrk:=\frac{1}{1-zq^m}
$$
we get
$$
F^{\ge m}(z)\llk m-1\rrk^2=F^{> m}(z)\llk m\rrk^2+\frac{pq^{m-1}z}
{\llk m-1\rrk}
=\sum_{j\ge m}\frac{pq^{j-1}z}{\llk j-1\rrk },
$$
and therefore
$$
F(z)=p\frac{z}{(1-z)^2}\sum_{j\ge 0}\frac{q^{j}}{\llk j\rrk}.
$$

To get the coefficient of $z^{n-1}$ is now very simple. Apart from
exponentially small terms, the expectation  is
$$
E_n\sim p\binom{n}2+pn\alpha -p\alpha_{4},
$$
with the constants
$$
\alpha=\sum_{k\ge 1}\frac{1}{Q^k-1}\qquad\text{and}\qquad
\alpha_{4}=\sum_{k\ge 1}\frac{k}{Q^k-1}=\alpha+\beta.
$$


The other variant (equality does {\it not} count) leads to
$$
P^{=m}(z,y)=pq^{m-1}zyP^{>m}(zy,y)P^{\ge m}(z,y)P^{>m}(zy,y),
\quad P^{=0}(z,y)=1,
$$
and
$$
F(z)=\frac pq \frac{z}{(1-z)^2}\sum_{j\ge 1}\frac{q^{j}}{\llk j\rrk},
$$
so that
$$
E_n \sim \frac pqn\alpha -\frac pq\alpha_{4}.
$$
\bigskip

{\bf Acknowledgment.} Many computations in this paper have been performed
resp. checked by the computer algebra system {\sc Maple}.




\Refs\ref \no 1 \by L.Devroye\paper
A limit theory for random skip lists\jour Annals of Applied Probability 
\vol 2 \yr 1992 \pages 597--609
\endref

\ref \no 2 \by  P.Flajolet and L.B.Richmond
\paper Generalized Digital Trees and Their Difference-Differential Equations
\jour Random Structures and Algorithms
\yr 1992 \pages 305--320        \vol 3      
\endref

\ref \no 3 \by P.Flajolet and R.Sedgewick\paper Digital Search
Trees Revisited \jour SIAM J. Comput. \vol 15 \yr 1986 \pages 748--767
\endref

\ref \no 4 \by P.Flajolet and J.Vitter 
\paper Average-Case Analysis of     Algorithms and Data Structures \yr 
1990 \pages 431--524     \inbook Handbook of Theoretical     
Computer Science Vol. A ``Algorithms and     Complexity''
\publ North-Holland      \endref

\ref \no  5\paper A Result in Order Statistics Related to Probabilistic
Counting\jour Computing \vol 51 \pages 15-27 
\by P.Kirschenhofer and H.Prodinger\yr 1993
\endref

\ref \no 6    
\paper Zur Auswertung gewisser  numerischer Reihen mit Hilfe 
modularer Funk\-tio\-nen      
\jour  Zahlentheoretische 
Analysis II, E. Hlawka, Ed., Lecture Notes in 
Mathematics      
\vol 1262 \yr 1987\pages 108--110 
\by P.Kirschenhofer, H.Prodinger und J.Schoi\ss engeier
\endref



\ref \no 7    \paper On the Variance of the External Pathlength 
in a Symmetric Digital Trie 
\jour Discrete Applied Mathematics \yr 1989 \pages 129--143\vol 25
\by P.Kirschenhofer, {H.Prodinger}  and W.Szpankowski 
\endref

\ref \no 8
\paper On the balance property of Patricia tries: External Pathlength View
\jour  Theoretical      Computer Science\vol 68\yr 1989\pages1--17
\by P.Kirschenhofer, {H.Prodinger}  and W.Szpankowski
\endref

\ref \no 9 
\paper Digital Search Trees again Revisited: The Internal Path
Length Perspective \jour submitted \by P.Kirschenhofer, {H.Prodinger}  and
W.Szpankowski \yr 1990 
\endref



\ref\no 10
  \paper A Contribution to the Analysis of in situ Permutation
\jour Glasnik Mathematicki \vol 22(42)\yr 1987 
\pages 269--278\by P.Kirschenhofer, H.Prodinger 
and R.F.Tichy\endref

\ref \no 11 \by D.E.Knuth \book The Art of Computer Programming Vol.1
\publ Addison-Wesley \yr 1968 \publaddr Reading, MA \endref

\ref \no 12 
\by D.E.Knuth 
\book The Art of Computer Programming Vol.3\publ
Addison-Wesley \yr 1973 \publaddr Reading, MA \endref

\ref \no 13  \by T.Papadakis, I.Munro and P.Poblete 
\paper Average search and update costs in skip lists\jour BIT \yr 1992 
\vol 32 \pages 316--332\endref

\ref \no 14  \by H.Prodinger\paper
Combinatorics of 
geometrically distributed random variables: Left-to-right maxima
\jour submitted \yr 1992 \endref

\ref \no 15 \by W.Pugh \paper Skip lists: a probabilistic 
alternative to balanced trees\jour Communications of the ACM \yr 1990 
\vol 33 \pages 668--676\endref

\ref \no16 \by R.Sedgewick \paper 
Mathematical analysis of 
combinatorial algorithms \pages 125--205 \inbook Probability Theory and 
Computer Science\eds G.Louchard and G.Latouche \yr 1983 \publ 
Academic Press\endref

\ref 
\no 17\by W.Szpankowski and V.Rego \jour Computing\vol 43
\pages 401--410 \yr 1990 \paper Yet another Application of a
Binomial Recurrence: Order 
Statistics\endref

\ref\no 18\by E.T. Whittaker and G.N. Watson\book A Course in Modern
Analysis\publ Cambridge University Press\yr 1927\endref

\endRefs



\enddocument
