THE PATH LENGTH OF RANDOM SKIP LISTS

Peter Kirschenhofer and Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

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.

1. Introduction and Main Results

The skip list has recently been introduced by Pugh [15] as an alternative data structure to search trees. We give a short description in the next paragraphs and refer the reader to [13] for more detailed information. In [1], [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 path length, i.e. the sum of the costs to find all the elements in the data structure, (“successful search”), compare [4] and [12]. This parameter has not yet been analyzed for the skip list, and we devote this paper to its study.

In a skip list n elements (n ≥ 1) 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}, …, a_{n}). In the sequel we adopt the following model of random skip lists (compare [1], [13]). Each a_{i} ∈ ℕ is the outcome of a random variable G_{i}

Typeset by AMS-TEX

Key words and phrases. Data structures, generating functions, probabilistic analysis.

that is distributed according to the geometric distribution with parameter p, i.e. Prob{G_{i} = k} = pq^{k−1}, where q = 1 − p. The random variables are 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 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.

Following [13] we define the 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 third element at level 1. The search cost may be split up into the sum of a “vertical cost” corresponding to pointer inspections of pointers refering to elements at a position ≥ i (that initiate the continuation of the search one level below, 11 in the example) and a “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 horizontal path length X_{n} = X_{n}(ρ) of a skip list ρ containing n elements as the sum of the horizontal search costs of all elements in ρ. The vertical path length Y_{n} = Y_{n}(ρ) is defined analogously. Finally, the total path length or 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}(ρ) is n times the height of ρ. The horizontal search cost is more intricate. Let us return to our alternative description of the skip lists as n-tuples (a_{1}, …, a_{n}) from above. The height clearly equals the maximum of (a_{1}, …, a_{n}). The horizontal search cost is zero for the first element. Let now i ≥ 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 number of right-to-left maxima in (a_{1}, …, a_{i−1}), i.e. the number of elements a_{j} (1 ≤ j ≤ i − 1) that are larger than or equal to a_{j}, a_{j+1}, …, 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}, …, a_{n}) is the sum of the numbers of right-to-left maxima of the sequences a_{1}, …, a_{i−1} for 2 ≤ i ≤ n.

The number of right-to-left maxima of a_{1}, …, a_{n} is a well understood parameter in the context of random permutations, see [10], [11] and [16]. In the context of the geometric distribution it was analyzed in [14].

With respect to expectations, the horizontal path length is simply the sum of all the horizontal search costs. This is also easy to check, comparing [14, Lemma 2] and our formula (2.7). However, with respect to 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 [7], [8], [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 technical toolkit for the manipulation of generating functions that will frequently occur with the analysis of skip list parameters.

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 expectations. Observe that these estimates can also be computed from the results of [13] on the search cost of specified elements, though the notion of path length is not considered there. (iii) is equivalent to [13, Theorem 4].

Proposition 1. (i) The expected value E(X_{n}) of the horizontal path length in a random skip list containing n elements fulfills for n → ∞

E(X_{n}) = (Q − 1)n( log_{Q} n + \frac{γ − 1}{L} − \frac{1}{2} + \frac{1}{L}δ_{1}(log_{Q} n)) + O(log n)

where γ is Euler’s constant and δ_{1}(x) = ∑_{k≠0} Γ(−1 − \frac{2kπi}{L})e^{2kπix} is a continuous

periodic function of period 1 and mean zero. (Γ is the Gamma-function.)

(ii) The expected value of the vertical path length fulfills for n → ∞

E(Y_{n}) = n log_{Q} n + n(\frac{γ}{L} + \frac{1}{2} − \frac{1}{L}δ_{2}(log_{Q} n)) + O(log n),

where δ_{2}(x) = ∑_{k≠0} Γ(−\frac{2kπi}{L})e^{2kπix}.

(iii) The expected value E(C_{n}) of the total cost fulfills for n → ∞

E(C_{n}) = Qn log_{Q} n + n(\frac{(γ − 1)Q + 1}{L} − \frac{Q}{2} + 1 + \frac{1}{L}δ_{3}(log_{Q} n)) + O(log n)

where δ_{3}(x) = δ_{1}(x) − δ_{2}(x).

Remark. As a consequence of the exponential decrease of the Γ-function along vertical lines (compare (2.37)) we have that the amplitude of the functions δ_{i}(x) here and in the sequel is very small for all reasonable values of q, e.g. 0.1 ≤ q ≤ 0.9.

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.

Theorem 1. The variance Var(X_{n}) of the horizontal path length in a random skip list containing n elements fulfills for n → ∞

\begin{aligned}Var(X_{n}) & = (Q − 1)^{2}n^{2}\{\frac{Q + 1}{2(Q − 1)L} + \frac{1}{L^{2}} − \frac{π^{2}}{6L^{2}} + \frac{8π^{2}}{L^{2}} h(\frac{4π^{2}}{L} ) − α_{1} + δ_{4}(log_{Q} n)\} \\ & + O(n^{1+ε}), ε > 0, \end{aligned}

where h(x) = ∑_{k≥1} \frac{e^{kx}}{(e^{kx} − 1)^{2}} , α_{1} = L ∑_{k≥1} \frac{1}{k(L^{2} + 4k^{2}π^{2}) sinh(2kπ^{2}/L)} and δ_{4}(x) is

again continuous, periodic of period 1 and mean zero.

With regard to the vertical path length, i.e. n times the maximum element, we have from [5] or [17]

Var(Y_{n}) = n^{2}\{\frac{π^{2}}{6L^{2}} + \frac{1}{12} − α_{2} + δ_{5}(log_{Q} n)\} + O(n^{1+ε}),

where α_{2} = \frac{1}{L} ∑_{k≥1} \frac{1}{k sinh(2kπ^{2}/L)}. Finally the following theorem holds.

Theorem 2. (i) The covariance Cov(X_{n}, Y_{n}) of the horizontal and the vertical path lengths in a random skip list containing n elements fulfills for n → ∞

\begin{aligned}Cov(X_{n}, Y_{n}) = (Q − 1)n^{2}\{ & \frac{1}{L^{2}} − \frac{π^{2}}{6L^{2}} + \frac{8π^{2}}{L^{2}} h(\frac{4π^{2}}{L} ) − α_{1} + \frac{1}{L} ∑_{k≥1} \frac{1}{Q^{k} − 1} \\ & − ∑_{k≥1} \frac{k}{(Q^{k} − 1)^{2}} + δ_{6}(log_{Q} n)\} + O(n^{1+ε}), \end{aligned}

with h and α_{1} from Theorem 1.

(ii) The variance Var(C_{n}) of the total cost fulfills for n → ∞

Var(C_{n}) = (Q^{2} − 1)n^{2}\{\frac{1}{2L} + \frac{1}{L^{2}} − \frac{π^{2}}{6L^{2}} + \frac{8π^{2}}{L^{2}} h(\frac{4π^{2}}{L} ) − α_{1}\}

+ 2(Q − 1)n^{2}\{\frac{1}{L} ∑_{k≥1} \frac{1}{Q^{k} − 1} − ∑_{k≥1} \frac{k}{(Q^{k} − 1)^{2}} \}

+ n^{2}\{\frac{π^{2}}{6L^{2}} + \frac{1}{12} − α_{2} + δ_{7}(log_{Q} n)\} + O(n^{1+ε}).

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}) ∼ n^{2}(K + δ_{7}(log_{Q} n)) takes its minimum value for q = 0.31 …, which differs a little from q = \frac{1}{e} = 0.36 …, where the main term of the expectation takes its minimum. Nevertheless we can conclude that for values of q close to \frac{1}{e}, 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.

\begin{matrix}q & K \\ 0.1 & 10.57 … \\ 0.2 & 3.16 … \\ 0.3 & 2.15 … \\ 0.31 … & 2.13 … \\ 0.4 & 2.44 … \\ 0.5 & 3.66 … \\ 0.6 & 6.41 … \\ 0.7 & 12.96 … \\ 0.8 & 33.03 … \\ 0.9 & 149.35 … \end{matrix}

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.

2. The horizontal path length

We start from the interpretation of a skip list ρ of size n + 1 as a finite sequence (a_{1}, …, a_{n+1}), n ≥ 0, a_{i} ∈ {1, 2, 3, … }. The horizontal path length X_{n+1}(ρ) is the sum b(ρ′) of all numbers of right-to-left maxima in the subsequences (a_{1}, …, a_{i}), 1 ≤ i ≤ n, of ρ′ = (a_{1}, …, 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 ρ′. Then we can write ρ′ in a unique way as

ρ = σmτ, where σ ∈ {1, …, m − 1}^{∗}, τ ∈ {1, …, m}^{∗}  (2.1)

(fixing the leftmost occurence of the maximum m). From this decomposition it follows that

b(ρ′) = b(σmτ) = b(σ) + b(τ) + |τ| + 1, b(ε) = 0,  (2.2)

since the contribution of the leftmost maximum is 1 plus the number of the succeding elements. The reader might observe that relation (2.2), in the context of permutations ρ′ (and thus binary search trees), describes the right-sided path length. However the probabilistic models are quite different. (Compare e.g. [10], [16].)

We introduce the bivariate generating functions P^{=m}(z, y), where the coefficient of z^{n}y^{j} is the probability that a skip list ρ with n+1 elements has maximum element (of the prefix ρ′) m and horizontal path length j (of ρ). P^{≤m}(z, y) and P^{<m}(z, y) are defined analogously. Then relation (2.2) translates into the functional equation

P^{=m}(z, y) = pq^{m−1}zyP^{<m}(z, y)P^{≤m}(zy, y), P^{=0}(z, y) = 1.  (2.3)

Although no simple closed formula for the solution of (2.3) is available, it allows to extract sufficient information on the moments of the path length.

If we set F^{∗}(z) = \frac{∂P^{∗}}{∂y} (z, 1), where ∗ stands for = m, ≤ m or < m, the generating function F (z) = ∑_{n≥0} E(X_{n+1})z^{n} of the expectations is obtained as

F (z) = lim_{m→∞} F^{≤m}(z).

The derivative of (2.3) w.r.t. y at y = 1 involves the terms

P^{≤m}(z, 1) = \frac{1}{1 − z(1 − q^{m})} =: \frac{1}{[[m]]} and \frac{∂}{∂z} P^{≤m}(z, 1) = \frac{1 − q^{m}}{[[m]]^{2}}

and reads

\frac{F^{≤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^{≤m}(z)}{[[m − 1]]} + \frac{F^{<m}(z)}{[[m]]}.

Performing some algebra it translates into

F^{≤m}(z)[[m]]^{2} = F^{<m}(z)[[m − 1]]^{2} + \frac{pq^{m−1}z}{[[m]]} ,

which can be solved by iteration, observing that F^{≤0}(z) = 0:

F^{≤m}(z) = \frac{p}{q} \frac{z}{[[m]]^{2}} ∑_{i=1}^{m} \frac{q^{i}}{[[i]]}.  (2.4)

Now we let m tend to infinity and obtain

F (z) = \frac{p}{q} \frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]}.  (2.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{∂^{2}P^{∗}}{∂y^{2}} (z, 1). The second derivative of (2.3) w.r.t. y at y = 1 involves additionally the quantities

\frac{∂^{2}P^{≤m}}{∂z^{2}} (z, 1) = \frac{2(1 − q^{m})^{2}}{[[m]]^{3}} ,

and

K^{≤m}(z) := \frac{d}{dz} F^{≤m}(z) = \frac{p}{q} · (\frac{1}{[[m]]^{2}} ∑_{j=1}^{m} \frac{q^{j}}{[[j]]^{2}} + \frac{2z(1 − q^{m})}{[[m]]^{3}} ∑_{j=1}^{m} \frac{q^{j}}{[[j]]}).

In this way we find

\frac{H^{≤m}(z) − H^{<m}(z)}{pq^{m−1}z} = \frac{2z (1 − q^{m})}{[[m − 1]][[m]]^{3}} + \frac{2z}{[[m − 1]]}K^{≤m}(z) + \frac{1}{[[m − 1]]}H^{≤m}(z)

+ \frac{1}{[[m]]}H^{<m}(z) + \frac{2}{[[m − 1]]}F^{≤m}(z) + \frac{2}{[[m]]}F^{<m}(z)

+ \frac{2z(1 − q^{m})}{[[m]]^{2}}F^{<m}(z) + 2F^{≤m}(z)F^{<m}(z).

Again we get a first order difference equation

H^{≤m}(z)[[m]]^{2} = H^{<m}(z)[[m − 1]]^{2} + 2pq^{m−1}z · \{\frac{z (1 − q^{m})}{[[m]]^{2}} + z[[m]]K^{≤m}(z)

+ [[m]]F^{≤m}(z) + \frac{[[m − 1]]}{[[m]]}F^{<m}(z)

+ [[m]][[m − 1]]F^{≤m}(z)F^{<m}(z)}.

This equation can be solved for H^{≤m}(z) by iteration; performing the limit for m → ∞ we finally achieve the generating function H(z):

\begin{aligned}H(z) & = 2\frac{p}{q} \frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]^{2}} \\ & − 2\frac{p}{q} \frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]} \\ & − 2 (\frac{p}{q})^{2} \frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j≤i} \frac{q^{i+j}}{[[i]][[j]]} \\ & + 4 (\frac{p}{q})^{2} \frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j≤i} \frac{q^{i+j}}{[[i]]^{2}[[j]]} \\ & + 2 (\frac{p}{q})^{2} \frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j≤i} \frac{q^{i+j}}{[[i]][[j]]^{2}} \\ & + 2 (\frac{p}{q})^{2} \frac{z^{2}}{(1 − z)^{2}} ∑_{1≤j<i} \frac{q^{i+j}}{[[i]][[i − 1]][[j]]} \\ & + 2 (\frac{p}{q})^{3} \frac{z^{3}}{(1 − z)^{2}} ∑_{i≥1} ∑_{1≤j≤i} ∑_{1≤h<i} \frac{q^{i+j+h}}{[[i]][[i − 1]][[j]][[h]]}. \end{aligned}  (2.6)

Now we turn to the evaluation of the expectations 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

E(X_{n}) = [z^{n−1}]F (z) = \frac{p}{q} ∑_{i≥1} [−Q^{i} + n + Q^{i} (1 − q^{i})^{n}]  (2.7)

where Q = q^{−1}, or, by expanding the binomial and interchanging the summations,

E(X_{n}) = \frac{p}{q} ∑_{k=2}^{n} \binom{n}{k}(−1)^{k} \frac{1}{Q^{k−1} − 1}.  (2.8)

In order to get the asymptotic equivalent for E(X_{n}) we might apply a Mellin transform approach (cf. [4]) to (2.7). Alternatively, the expression (2.8) can be rewritten as a complex contour integral (Rice’s method), namely

E(X_{n}) = \frac{p}{q} · \frac{1}{2πi} ∫_{C} B(n + 1, −z)\frac{1}{Q^{z−1} − 1}dz,  (2.9)

where B(x, y) = \frac{Γ(x)Γ(y)}{Γ(x + y)} is the Beta function and the contour C encircles the poles

z = 2, 3, …, n. Now the asymptotics are obtained by extending the contour C “to the left” and collecting the additional residues. (Compare [3] for technical details of this procedure.)

In the integral (2.9) we have additional poles with real part larger than zero at z = χ_{k}, χ_{k} = \frac{2kπi}{log Q}, k ∈ ℤ. The computation of the residues is standard and can be performed e.g. by Maple. It yields for the double pole z = 1

Res_{z=1}B(n + 1, −z)\frac{1}{Q^{z−1} − 1} = \frac{n}{L}(H_{n−1} − 1 − \frac{L}{2}),

with L = log Q and H_{n} the n-th Harmonic number, and thus the asymptotic contribution to E(X_{n})

\frac{p}{q} \frac{n}{L}( log n + γ − 1 − \frac{L}{2}) + O(log n).

Similarily the simple poles z = 1 + χ_{k}, k ≠ 0, contribute

\frac{p}{q} \frac{1}{L} ∑_{k≠0} Γ(−1 − χ_{k})n^{1+χ_{k}}(1 + O(\frac{1}{n})).  (2.11)

Collecting all contributions we have Proposition 1 (i).

In the sequel we concentrate on our main goal, namely the computation of the variance Var(X_{n}). We have

Var(X_{n}) = [z^{n−1}]H(z) + E(X_{n}) − E(X_{n})^{2},  (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 [2] Flajolet and Richmond made extensive use of the relation

A(z) = ∑_{n≥0} a_{n}z^{n} ⟷ \frac{1}{1 − w} A(\frac{w}{1 − w} ) = ∑_{n≥0} ( ∑_{k=0}^{n} \binom{n}{k}a_{k})w^{n}.  (2.12)

Of course this relation can be inverted to read

A(z) = ∑_{n≥0} ( ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}f(k))z^{n} ⟷ \frac{1}{1 − w} A(\frac{w}{w − 1}) = ∑_{n≥0} f(n)w^{n}. (2.13)

The alternating sum can now be rewritten by Rice’s method (compare above), and in this way we find Lemma 1. Let A(z) be a formal power series and

f_{n} = [w^{n}]\frac{1}{1 − w} A(\frac{w}{w − 1}),  n ≥ 0  (2.14)

with f_{0} = f_{1} = ⋯ = f_{s−1} = 0. Then

[z^{n}]A(z) = \frac{1}{2πi} ∫_{C(s,...,n)} B(n + 1, −z)f(z)dz,  (2.15)

where C(s, …, n) encircles the poles z = s, s + 1, …, n, B is the Beta function and f(z) is analytic inside C with f(n) = f_{n} for all n ≥ s.

The following generalization will be useful. Lemma 2. With the assumptions of Lemma 1 we have

[z^{n}]\frac{1}{(1 − z)^{r}} A(z) = \frac{(−1)^{r}}{2πi} ∫_{C(s+r,...,n+r)} B(n + r + 1, −z)f(z − r)dz.  (2.16)

Proof. With z = \frac{w}{w − 1} we have (1 − z)^{−r} = (−1)^{r} \frac{w^{r}}{z^{r}}, so that

[z^{n}](1 − z)^{−r}A(z) = (−1)^{r}[z^{n+r}]w^{r}A(z).

The result follows now from Lemma 1. □

In order to compute the coefficients f_{n} in (2.14) for the formal series A(z) occuring in our problem we will frequently apply Lemma 3. Let C and D be formal power series. Then

[w^{n}] ∑_{i≥0} C(wq^{i}) = \frac{1}{1 − q^{n}} [w^{n}]C(w),  n ≥ 0,  (2.17)
[w^{n}] ∑_{i≥1} C(wq^{i}) = \frac{1}{Q^{n} − 1}[w^{n}]C(w),  n ≥ 1,  (2.18)
[w^{n}] ∑_{i≥1} iC(wq^{i}) = \frac{Q^{n}}{(Q^{n} − 1)^{2}} [w^{n}]C(w),  n ≥ 1,  (2.19)
[w^{n}] ∑_{1≤j≤i} C(wq^{i})D(wq^{j}) = \frac{1}{Q^{n} − 1} ∑_{m=1}^{n} \frac{1}{1 − q^{m}} [w^{m}]C(w) · [w^{n−m}]D(w), (2.20)

and

[w^{n}] ∑_{1≤j<i} C(wq^{i})D(wq^{j}) = \frac{1}{Q^{n} − 1} ∑_{m=1}^{n} \frac{1}{Q^{m} − 1}[w^{m}]C(w) · [w^{n−m}]D(w), (2.21)

Proof. Immediate. □

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 (2.6).

Let us start with the relatively simple first one, namely

A_{1}(z) = \frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]^{2}} =: \frac{1}{(1 − z)^{2}} Ā_{1}(z).  (2.22)

With the substitution z = \frac{w}{w − 1} we have

\frac{1}{[[i]]} = \frac{1 − w}{1 − wq^{i}}  (2.23)

and therefore

\frac{1}{1 − w} Ā_{1}(\frac{w}{w − 1}) = −w ∑_{i≥1} \frac{q^{i}}{(1 − wq^{i})^{2}} .

From Lemma 3 (2.18) we find

[w^{n}] ∑_{i≥1} \frac{wq^{i}}{(1 − wq^{i})^{2}} = \frac{1}{Q^{n} − 1}[w^{n}]\frac{w}{(1 − w)^{2}} = \frac{n}{Q^{n} − 1}.

Therefore, by Lemma 2,

[z^{n−1}]A_{1}(z) = \frac{−1}{2πi} ∫_{C(3,...,n+1)} B(n + 2, −z)\frac{z − 2}{Q^{z−2} − 1}dz.  (2.24)

The most complicated term in H(z) is

A_{7}(z) = \frac{z^{3}}{(1 − z)^{2}} ∑_{i≥1} ∑_{1≤j≤i} ∑_{1≤h<i} \frac{q^{i+j+h}}{[[i]][[i − 1]][[j]][[h]]} =: \frac{1}{(1 − z)^{2}} Ā_{7}(z).  (2.25)

Here we have

\frac{1}{1 − w} Ā_{7}(\frac{w}{w − 1}) = − ∑_{i≥1} \frac{wq^{i}}{(1 − wq^{i})(1 − wq^{i−1})}S^{≤i}(w)S^{≤i−1}(w),  (2.26)

where

S^{≤i}(w) = ∑_{1≤j≤i} \frac{wq^{j}}{1 − wq^{j}} .

Now, a partial fraction decomposition gives

\frac{wq^{i}}{(1 − wq^{i})(1 − wq^{i−1})} = \frac{1}{Q − 1}(\frac{wq^{i−1}}{1 − wq^{i−1}} − \frac{wq^{i}}{1 − wq^{i}} ),

so that the whole expression (2.26) telescopes to

\frac{−1}{Q − 1}(\frac{w}{1 − q} S^{≤1}(w)S^{≤0}(w) + ∑_{i≥1} \frac{wq^{i}}{1 − wq^{i}} (\frac{wq^{i}}{1 − wq^{i}} + \frac{wq^{i+1}}{1 − wq^{i+1}} )S^{≤i}(w)).

Since S^{≤0}(w) = 0 we get with Lemma 3 (2.20)

\begin{aligned}[w^{n}]\frac{1}{1 − w} Ā_{7}(\frac{w}{w − 1}) & = −\frac{1}{Q − 1} \frac{1}{Q^{n} − 1} ∑_{m=2}^{n−1} \frac{1}{1 − q^{m}} × \\ & × [w^{m}] ((\frac{w}{1 − w} )^{2} + \frac{w^{2}q}{(1 − w)(1 − wq)}) · 1. \end{aligned}  (2.27)

A short calculation shows that

[w^{m}] ((\frac{w}{1 − w} )^{2} + \frac{w^{2}q}{(1 − w)(1 − wq)}) = m − 1 + \frac{1}{Q − 1}(1 − Q^{1−m}),

so that finally (2.27) is equal to

−\frac{1}{Q − 1} \frac{1}{Q^{n} − 1} (\binom{n − 1}{2} + \frac{n − 2}{Q − 1} + ∑_{m=2}^{n−1} \frac{m − 2}{Q^{m} − 1}) .  (2.28)

It is not difficult to find an analytic continuation, if we observe that

∑_{m=2}^{n−1} \frac{m − 2}{Q^{m} − 1} = ∑_{m≥2} \frac{m − 2}{Q^{m} − 1} − ∑_{m≥0} \frac{n + m − 2}{Q^{n+m} − 1}.

Altogether Lemma 2 yields

\begin{aligned}[z^{n−1}]A_{7}(z) & = \frac{−1}{2πi} \frac{1}{Q − 1} ∫_{C(4,...,n+1)} B(n + 2, −z)\frac{1}{Q^{z−2} − 1}× \\ & × (\binom{z − 3}{2} + \frac{z − 4}{Q − 1} + ∑_{m≥2} \frac{m − 2}{Q^{m} − 1} − ∑_{m≥0} \frac{z + m − 4}{Q^{z+m−2} − 1})dz. \end{aligned} (2.29)

Observe that C(4, …, n + 1) may be replaced by C(3, …, n + 1) since z = 3 is a removable singularity of the integrand.

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

Lemma 4.

\begin{aligned}[z^{n−1}]H(z) & = 2(Q − 1)^{2} · \frac{1}{2πi}\{ ∫_{C(2,...,n)} B(n + 1, −z)\frac{1}{Q^{z−1} − 1}× \\ & × (z − 2 − \frac{1}{Q − 1} + α − ∑_{m≥0} \frac{1}{Q^{z+m−1} − 1})dz \\ & + ∫_{C(3,...,n+1)} B(n + 2, −z)\frac{1}{Q^{z−2} − 1}× \\ & × ((z − 3)(z − 1) − \frac{z − 2}{Q − 1} + zα − z ∑_{m≥0} \frac{1}{Q^{z+m−2} − 1})dz\} \end{aligned} (2.30)

with α = ∑_{m≥1} \frac{1}{Q^{m} − 1}.

In order to get the asymptotic behaviour of [z^{n−1}]H(z) for n → ∞ we extend the contour of integration to a large rectangle and shift the left side to the line Re z = 1 + ε, ε > 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+ε}) (compare [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+χ_{k}, k ∈ ℤ\{0} (simple). The computation of the residues can be performed by hand, or, more preferably, e.g. by Maple, and we find for the residue at z = 2

\begin{aligned}2(Q − 1)^{2}\binom{n + 1}{2}\{ & \frac{H_{n−1}^{2}}{L^{2}} + \frac{H_{n−1}^{(2)}}{L^{2}} − \frac{H_{n−1}}{L} (1 + \frac{2}{L}) \\ & + \frac{1}{3} + \frac{2}{L^{2}} − 2(α + β) + \frac{1}{2L} + \frac{1}{(Q − 1)L}\}, \end{aligned}  (2.31)

where L = log Q, H_{n} resp. H_{n}^{(2)} are the Harmonic numbers of first resp. second

order, and β = ∑_{m≥1} \frac{1}{(Q^{m} − 1)^{2}} .

The asymptotic equivalent of (2.31) is

2(Q − 1)^{2}\{\frac{n^{2} log_{Q}^{2} n}{2} + n^{2} log_{Q} n(\frac{γ}{L} − \frac{1}{2} − \frac{1}{L})

+ n^{2}(\frac{1}{6} + \frac{1}{L^{2}} − α − β − \frac{γ}{2L} − \frac{γ}{L^{2}} + \frac{γ^{2}}{2L^{2}} + \frac{π^{2}}{12L^{2}} + \frac{1}{4L} + \frac{1}{2(Q − 1)L})

+ O(n log^{2} n)}

(2.32)

The first order poles at z = 2 + χ_{k}, k ∈ ℤ \ {0}, give a contribution of the form

n^{2}δ_{8}(log_{Q} n) + O(n),  (2.33)

where δ_{8}(x) is a continuous periodic function of period 1 and mean zero. The Fourier coefficients of δ_{8}(x) can be obtained explicitly from the residues at the above mentioned poles. They can be used to show that the amplitude of δ_{8}(x) is very small (because of the exponential decrease of the Γ-function along vertical lines). Since from the practical point of view δ_{8}(x) has almost no influence on the variance, we omit these calculations here.

Combining (2.32), (2.33) and Proposition 1 we get the asymptotic equivalent of Var(X_{n}) according to (2.11). The reader should take notice of the fact that the term of order n^{2} in E(X_{n})^{2} contains the square δ_{1}^{2}(log_{Q} n) of the fluctuating term δ_{1}(log_{Q} n), where δ_{1}(x) has mean zero. Therefore we have

\begin{aligned}Var(X_{n}) & = (Q − 1)^{2}n^{2}\{\frac{1}{L^{2}} + \frac{1}{12} − \frac{1}{2L} + \frac{π^{2}}{6L^{2}} − 2(α + β) + \frac{1}{(Q − 1)L} − \frac{1}{L^{2}} [δ_{1}^{2}]_{0}\} \\ & + n^{2}δ_{4}(log_{Q} n) + O(n^{1+ε}), ε > 0, \end{aligned}

(2.34) where [δ_{1}^{2}]_{0} is the mean of δ_{1}^{2}(x), and δ_{4}(x) is a small periodic function of period 1 and mean zero.

The quantity α + β = ∑_{k≥1} \frac{Q^{k}}{(Q^{k} − 1)^{2}} can be rewritten as

α + β = h(L) = \frac{π^{2}}{6L^{2}} − \frac{1}{2L} + \frac{1}{24} − \frac{4π^{2}}{L^{2}} h(\frac{4π^{2}}{L} ),  (2.35)

where

h(x) = ∑_{k≥1} \frac{e^{kx}}{(e^{kx} − 1)^{2}} .  (2.36)

Equation (2.35) follows from the functional equation for the Dedekind η-function and is proved e.g. in [6]. The alternative representation for α + β given by (2.35) is extremely useful for numerical purposes, since the term \frac{4π^{2}}{L^{2}} h(\frac{4π^{2}}{L}) is very small for “reasonable” values of q resp. Q = q^{−1}.

The term [δ_{1}^{2}]_{0} can be computed explicitly from the Fourier expansion in Proposition 1. Since (compare e.g. [18])

|Γ(iy)| = \frac{π}{y sinh πy} ,  (2.37)

we find

\frac{1}{L^{2}} [δ_{1}^{2}]_{0} = α_{1}  (2.38)

with α_{1} defined in the theorem. Therefore the proof of Theorem 1 is complete.

3. The total cost

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 [5] resp. [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 E(C_{n}) = E(X_{n}) + E(Y_{n}) fulfills the asymptotic relation from Proposition 1 (ii).

In order to compute Var(C_{n}) = Var(X_{n} + Y_{n}) we use

Var(C_{n}) = Var(X_{n}) + Var(Y_{n}) + 2Cov(X_{n}, Y_{n}),  (3.1)

where the covariance Cov(X_{n}, Y_{n}) = E(X_{n}Y_{n}) − E(X_{n})E(Y_{n}) will be studied in the sequel.

We start with the term E(X_{n}Y_{n}). The generating function of \frac{1}{n + 1}E(X_{n+1}Y_{n+1}) is

∑_{m≥1} F^{=m}(z)(mProb(G ≤ m) + ∑_{k>m} kProb(G = k))  (3.2)

where G stands for the random variable producing the last elment of the skip list (a_{1}, …). (Observe that the random variables in question were assumed to be i.i.d.) From (4.2) we get immediately the expression

∑_{m≥1} F^{=m}(z)(m + \frac{q^{m}}{1 − q} ) = ∑_{m≥0} (F (z) − (1 − q^{m})F^{≤m}(z)).  (3.3)

Now from (2.4) and (2.5)

\begin{matrix}∑_{m≥0} (F (z) − (1 − q^{m})F^{≤m}(z)) \\ = (Q − 1)z( ∑_{m≥0} (\frac{1}{(1 − z)^{2}} − \frac{1 − q^{m}}{[[m]]^{2}} ) ∑_{i=1}^{m} \frac{q^{i}}{[[i]]} + ∑_{m≥0} \frac{1}{(1 − z)^{2}} ∑_{i>m} \frac{q^{i}}{[[i]]}), \end{matrix}

which can be rewritten as

= (Q − 1)z(\frac{1}{1 − z} ∑_{1≤i≤j} \frac{q^{i+j}}{[[i]][[j]]^{2}} + \frac{z}{(1 − z)^{2}} ∑_{1≤i≤j} \frac{q^{i+j}}{[[i]][[j]]} + \frac{1}{(1 − z)^{2}} ∑_{i≥1} \frac{iq^{i}}{[[i]]} ). (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 (2.19) for the third sum. We find

E(X_{n}Y_{n}) = (Q − 1)n · \{\frac{1}{2πi} ∫_{C(2,...,n)} B(n + 1, −z)\frac{1}{Q^{z−1} − 1}×

× (3 − z − α + ∑_{m≥0} \frac{1}{Q^{m+z} − 1} + \frac{2}{Q^{z−1} − 1})dz

+ \frac{1}{2πi} ∫_{C(2,...,n+1)} B(n + 2, −z)\frac{1}{Q^{z−1} − 1}×

× ( − \binom{z − 1}{2} − ∑_{m≥1} \frac{m}{Q^{m} − 1} + ∑_{m≥0} \frac{m + z − 1}{Q^{m+z−1} − 1})dz\}.

(3.5)

The computation of the residues at z = 1 (third order pole) resp. z = 1 + χ_{k}, k ∈ ℤ \ {0} (simple poles) gives the main asymptotic terms, from which we obtain

\begin{aligned}Cov(X_{n}, Y_{n}) = (Q − 1)n^{2}\{ & \frac{1}{L^{2}} + \frac{1}{12} − \frac{1}{L} + \frac{π^{2}}{6L^{2}} + \frac{α}{L} − ∑_{k≥1} \frac{k}{(Q^{k} − 1)^{2}} − 2(α + β) \\ & + \frac{1}{L^{2}} [δ_{1}δ_{2}]_{0} + δ_{6}(log_{Q} n)\} + O(n^{1+ε}), \end{aligned}

(3.6) with δ_{6}(x) of mean zero. Now

\begin{aligned}[δ_{1}δ_{2}]_{0} & = ∑_{k≠0} Γ(χ_{k})Γ(−1 − χ_{k}) \\ & = ∑_{k≠0}(−1 + χ_{k})Γ(−1 + χ_{k})Γ(−1 − χ_{k}) \\ & = −[δ_{1}^{2}]_{0} + 2Re ∑_{k>0} χ_{k}|Γ(−1 − χ_{k})|^{2} \\ & = −[δ_{1}^{2}]_{0}, \end{aligned}  (3.7)

so that \frac{1}{L^{2}} [δ_{1}δ_{2}]_{0} is the negative value from (2.38). Inserting the last result in (3.6) we find Theorem 2 (i). The variance Var(C_{n}) of the total cost is now computed by (3.1), and this completes the proof of Theorem 2 (ii).

4. Alternative Representations for the Constants

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 α + β we stay with the original representation

α + β = ∑_{k≥1} \frac{Q^{k}}{(Q^{k} − 1)^{2}} .

With regard to [δ_{1}^{2}]_{0} the following transformation can be performed.

From the Fourier expansion of δ_{1}(x) in Proposition 1 we have

[δ_{1}^{2}]_{0} = ∑_{k≠0} Γ(−1 + χ_{k})Γ(−1 − χ_{k}),  χ_{k} = \frac{2kπi}{L}.  (4.1)

Let us consider the function

g(z) = L\frac{Γ(−1 + z)Γ(−1 − z)}{e^{Lz} − 1}.  (4.2)

Then [δ_{1}^{2}]_{0} is the sum of residues of g(z) at the poles z = χ_{k}, k ∈ ℤ \ {0}. Furthermore

Res_{z=0}g(z) = −\frac{L^{2}}{12} − \frac{π^{2}}{6} − 1.  (4.3)

Combining these observations we can easily conclude that (0 < ε < 1)

\frac{1}{2πi} ∫_{ε−i∞}^{ε+i∞}g(z)dz − \frac{1}{2πi} ∫_{−ε−i∞}^{−ε+i∞}g(z)dz = [δ_{1}^{2}]_{0} − \frac{L^{2}}{12} − \frac{π^{2}}{6} − 1  (4.4)

since the Γ-function decreases exponentially towards ±i∞. Because of

\frac{1}{e^{−Lz} − 1} = −1 − \frac{1}{e^{Lz} − 1}

we have

\frac{1}{2πi} ∫_{−ε−i∞}^{−ε+i∞}g(z)dz = \frac{1}{2πi} ∫_{ε−i∞}^{ε+i∞}g(z)dz + \frac{L}{2πi} ∫_{ε−i∞}^{ε+i∞}Γ(−1 + z)Γ(−1 − z)dz. (4.4)

Altogether

[δ_{1}^{2}]_{0} = \frac{L^{2}}{12} + \frac{π^{2}}{6} + 1 + \frac{2}{2πi} ∫_{ε−i∞}^{ε+i∞}g(z)dz + \frac{L}{2πi} ∫_{ε−i∞}^{ε+i∞}Γ(−1 + z)Γ(−1 − z)dz. (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 ∈ ℕ, k ≥ 2 (simple poles) we finally obtain

\begin{aligned}[δ_{1}^{2}]_{0} & = \frac{L^{2}}{12} + \frac{π^{2}}{6} + 1 − \frac{QL^{2}}{(Q − 1)^{2}} − \frac{3}{2} \frac{QL}{Q − 1} \\ & + 2L − 2L log 2 − 2L ∑_{k≥2} \frac{(−1)^{k}}{(k + 1)k(k − 1)(Q^{k} − 1)} \end{aligned}  (4.6)

Inserting (4.6) in expression (2.34) gives for the variance of the horizontal path length the following alternative formula.

Corollary 1.

Var(X_{n}) = (Q − 1)^{2}n^{2}\{\frac{1}{L}(2 log 2 − 1 + \frac{5}{2} \frac{1}{Q − 1} + 2 ∑_{k≥2} \frac{(−1)^{k}}{(k + 1)k(k − 1)(Q^{k} − 1)})

+ \frac{Q}{(Q − 1)^{2}} − 2 ∑_{k≥1} \frac{Q^{k}}{(Q^{k} − 1)^{2}} + δ_{4}(log_{Q} n)\} + O(n^{1+ε}), ε > 0.

In a similar manner we obtain

Corollary 2.

(i)  Var(Y_{n}) = n^{2}(\frac{log 2}{L} + \frac{2}{L} ∑_{k≥1} \frac{(−1)^{k−1}}{k(Q^{k} − 1)} + δ_{5}(log_{Q} n)) + O(n^{1+ε}),

(ii) Cov(X_{n}, Y_{n}) = (Q − 1)n^{2}\{\frac{1}{L}(2 log 2 − \frac{3}{2} + \frac{3}{2} \frac{1}{Q − 1} + ∑_{k≥1} \frac{1}{Q^{k} − 1}

+ 2 ∑_{k≥2} \frac{(−1)^{k}}{(k + 1)k(k − 1)(Q^{k} − 1)})

+ \frac{Q}{(Q − 1)^{2}} − ∑_{k≥1} \frac{(k + 1)Q^{k}}{(Q^{k} − 1)^{2}} + δ_{6}(log_{Q} n))\} + O(n^{1+ε}).

Again, Var(C_{n}) is easily computed from the terms above using (3.1).

5. Variations

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 ρ′ in a unique way as

ρ′ = σmτ, where σ ∈ {1, …, m}^{∗}, τ ∈ {1, …, m − 1}^{∗};

then

b(ρ) = b(σmτ) = b(σ) + b(τ) + |τ| + 1, b(ε) = 0.

Hence

P^{=m}(z, y) = pq^{m−1}zyP^{≤m}(z, y)P^{<m}(zy, y), P^{=0}(z, y) = 1,

and

\frac{F^{≤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^{≤m}(z)}{[[m − 1]]} + \frac{F^{<m}(z)}{[[m]]}

or

F^{≤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}} ∑_{i≥0} \frac{q^{i}}{[[i]]}.

So the expection 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 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.)

Next, we discuss the case where “maximum” is replaced by “minimum”. Let’s start with the first variant (equality counts).

P^{=m}(z, y) = pq^{m−1}zyP^{>m}(z, y)P^{≥m}(zy, y), P^{=0}(z, y) = 1,

This time F (z) = F^{≥1}(z) is the generating function of interest. With

[[[m]]] := \frac{1}{1 − zq^{m}}

we get

F^{≥m}(z)[[[m − 1]]]^{2} = F^{>m}(z)[[[m]]]^{2} + \frac{pq^{m−1}z}{[[[m − 1]]]} = ∑_{j≥m} \frac{pq^{j−1}z}{[[[j − 1]]]},

and therefore

F (z) = p\frac{z}{(1 − z)^{2}} ∑_{j≥0} \frac{q^{j}}{[[[j]]]}.

To get the coefficient of z^{n−1} is now very simple. Apart from exponentially small terms, the expectation is

E_{n} ∼ p\binom{n}{2} + pnα − pα_{4},

with the constants

α = ∑_{k≥1} \frac{1}{Q^{k} − 1}  and  α_{4} = ∑_{k≥1} \frac{k}{Q^{k} − 1} = α + β.

The other variant (equality does not count) leads to

P^{=m}(z, y) = pq^{m−1}zyP^{>m}(zy, y)P^{≥m}(z, y)P^{>m}(zy, y), P^{=0}(z, y) = 1,

and

F (z) = \frac{p}{q} \frac{z}{(1 − z)^{2}} ∑_{j≥1} \frac{q^{j}}{[[[j]]]},

so that

E_{n} ∼ \frac{p}{q}nα − \frac{p}{q}α_{4}.

Acknowledgment. Many computations in this paper have been performed resp. checked by the computer algebra system Maple.

References

1. L.Devroye, A limit theory for random skip lists, Annals of Applied Probability 2 (1992), 597–609.

2. P.Flajolet and L.B.Richmond, Generalized Digital Trees and Their Difference-Differential Equations, Random Structures and Algorithms 3 (1992), 305–320.

3. P.Flajolet and R.Sedgewick, Digital Search Trees Revisited, SIAM J. Comput. 15 (1986), 748–767.

4. P.Flajolet and J.Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A “Algorithms and Complexity”, North-Holland, 1990, pp. 431–524.

5. P.Kirschenhofer and H.Prodinger, A Result in Order Statistics Related to Probabilistic Counting, Computing 51 (1993), 15-27.

6. P.Kirschenhofer, H.Prodinger und J.Schoißengeier, Zur Auswertung gewisser numerischer Reihen mit Hilfe modularer Funktionen, Zahlentheoretische Analysis II, E. Hlawka, Ed., Lecture Notes in Mathematics 1262 (1987), 108–110.

7. P.Kirschenhofer, H.Prodinger and W.Szpankowski, On the Variance of the External Pathlength in a Symmetric Digital Trie, Discrete Applied Mathematics 25 (1989), 129–143.

8. P.Kirschenhofer, H.Prodinger and W.Szpankowski, On the balance property of Patricia tries: External Pathlength View, Theoretical Computer Science 68 (1989), 1–17.

9. P.Kirschenhofer, H.Prodinger and W.Szpankowski, Digital Search Trees again Revisited: The Internal Path Length Perspective, submitted (1990).

10. P.Kirschenhofer, H.Prodinger and R.F.Tichy, A Contribution to the Analysis of in situ Permutation, Glasnik Mathematicki 22(42) (1987), 269–278.

11. D.E.Knuth, The Art of Computer Programming Vol.1, Addison-Wesley, Reading, MA, 1968.

12. D.E.Knuth, The Art of Computer Programming Vol.3, Addison-Wesley, Reading, MA, 1973.

13. T.Papadakis, I.Munro and P.Poblete, Average search and update costs in skip lists, BIT 32 (1992), 316–332.

14. H.Prodinger, Combinatorics of geometrically distributed random variables: Left-to-right maxima, submitted (1992).

15. W.Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM 33 (1990), 668–676.

16. R.Sedgewick, Mathematical analysis of combinatorial algorithms, Probability Theory and Computer Science (G.Louchard and G.Latouche, eds.), Academic Press, 1983, pp. 125–205.

17. W.Szpankowski and V.Rego, Yet another Application of a Binomial Recurrence: Order Statistics, Computing 43 (1990), 401–410.

18. E.T. Whittaker and G.N. Watson, A Course in Modern Analysis, Cambridge University Press, 1927.

TU Vienna Wiedner Hauptstrasse 8–10 A-1040 Vienna Austria

E-mail address: kirsch@email.tuwien.ac.at, proding@email.tuwien.ac.at