SPANNING TREE SIZE IN RANDOM BINARY SEARCH TREES

ALOIS PANHOLZER^{†} AND HELMUT PRODINGER^{‡}

Abstract. This paper deals with the size of the spanning tree of p randomly chosen nodes in a binary search tree. It is shown via generating functions methods, that for fixed p, the (normalized) spanning tree size converges in law to the Normal distribution. The special case p = 2 reproves the recent result (obtained by the contraction method in [7]), that the distribution of distances in random binary search trees has a Gaussian limit law. In the proof we use the fact that the spanning tree size is closely related to the number of passes in Multiple Quickselect. This parameter, in particular its first two moments were studied earlier in [9]. Here we show also that this normalized parameter has for fixed p order statistics a Gaussian limit law. For p = 1 this gives the well known result that the depth of a randomly selected node in a random binary search tree converges in law to the Normal distribution.

1. Introduction

In the papers [7] and [1] the distances between nodes in random search trees resp. random recursive trees were studied. It was proven in [7] that the (edge) distances Δ_{n} between two randomly selected nodes in random binary search trees of size n are asymptotically normally (Gaussian) distributed, where the so called random permutation model was used as the model of randomness for the trees. This means that every permutation of length n is assumed to be equally likely when generating a binary search tree; furthermore, for selecting nodes, all \binom{n}{2} pairs of nodes are assumed to be equally likely.

In [1] it was shown that the distribution of the distance Δ(i, n) between a fixed node i and the node n in a random recursive tree of size n is (for a fixed ratio ρ := \frac{i}{n} with 0 < ρ < 1) asymptotically normally distributed. A related parameter to the distance between two randomly selected nodes is the Wiener index of a graph, which is defined to be the sum of all distances between pairs of nodes in the considered graph. The Wiener index was studied for certain families of graphs, and although the scaled mean of this parameter must coincide with the mean distance of two randomly selected nodes, it turned out that the Wiener index was asymptotically not normally distributed for random recursive trees and random binary search trees (see [8, 5]).

In this paper we concentrate on random binary search trees and study a natural extension of the distance between two randomly selected nodes, namely the size of the spanning tree of p randomly chosen nodes in the tree. Again, we use the random permutation model for the generation of the binary search trees and also that all \binom{n}{p} possibilities to select p nodes in the tree of size n are equally likely. The random variable Y_{n,p}, which counts the size of the spanning tree of p selected nodes in a random binary search tree of size n, is then a direct extension of Δ_{n}, since the edge distance between two nodes is nothing else than the size of the spanning tree of these two nodes minus one and thus Δ_{n} =^{L} Y_{n,2} − 1, where =^{L} denotes equality in distribution.

In the mathematical analysis of Y_{n,p} we use the fact that it is closely related to the random variable X_{n,p}, which counts the number of passes required in the Multiple Quickselect algorithm to find a random p–order statistic in a data file of length n (see [9] and the references cited therein for a description of this divide and conquer algorithm); the natural probability model for the data is, that their ranks form a random permutation of {1, …, n} and we assume further that all \binom{n}{p} sets of p order statistics \{1 ≤ i_{1} < … < i_{p} ≤ n\} are equally likely. Then by well known relations between binary search trees and Quicksortlike algorithms, X_{n,p} is equal to the number of ascendants of p randomly chosen nodes in a random binary search tree of size n or, equivalently, to the size of the spanning tree, spanned by the root and p randomly chosen nodes (where of course the root could have been chosen as well) in a random binary search tree of size n. See Figure 1 for a comparison of both parameters.

Figure 1. A binary search tree with the two parameters under consideration.

Spanning tree of the nodes 7, 9 and 10 is of size 4.

5 passes of the Multiple Quickselect algorithm to find the ranks 7, 9 and 10.

The parameter X_{n,p} was studied already in [9], where exact formulæ for the expectation and the variance were given. Here we show additionally that X_{n,p} is, for fixed p ≥ 1, asymptotically normally distributed.^{1}

For Y_{n,p} we also derive exact formulæ for the expectation and the variance and show, that Y_{n,p} is, for fixed p ≥ 2, asymptotically normally distributed, where the special case p = 2 reproves that the distances Δ_{n} between two randomly selected nodes in random binary search trees of size n are asymptotically normally distributed. Our approach uses generating functions, singularity analysis and a central limit theorem for combinatorial structures due to Hwang and avoids the difficulties which occur in [7] when showing the asymptotic normality for Δ_{n} using the contraction method which arises due to the degenerate nature of the distributional limit equation for X_{n,1} (that was studied there to obtain the result for Δ_{n}).

2. Passes in Multiple Quickselect and spanning tree size in binary search trees

First we want to translate the close relation between X_{n,p} and Y_{n,p} into an equation for suitable generating functions as described below.

Here we denote with φ_{n,p,m} := ℙ{X_{n,p} = m} the probability that exactly m passes of the Multiple Quickselect algorithm are required, in order to find a random set of p order statistics in a data file of length n, and with F_{n,p,m} := ℙ{Y_{n,p} = m} the probability that the size of the spanning tree of p randomly chosen nodes in a binary search tree of size n is exactly m. Using the recursive structure of the search trees, we obtain for the generating functions ϕ_{p}(z, v) = ∑_{n,m≥0} \binom{n}{p}φ_{n,p,m}z^{n}v^{m} resp. F_{p}(z, v) = ∑_{n,m≥0} \binom{n}{p}F_{n,p,m}z^{n}v^{m} for p ≥ 1 the recurrences

1Philippe Flajolet mentioned that to H. P. in 1998 without working out the details.

\frac{∂}{∂z} ϕ_{p}(z, v) = v ∑_{i=0}^{p} ϕ_{i}(z, v)ϕ_{p−i}(z, v) + v ∑_{i=0}^{p−1} ϕ_{i}(z, v)ϕ_{p−1−i}(z, v)  (1)

and

\frac{∂}{∂z} F_{p}(z, v) = v ∑_{i=1}^{p−1} ϕ_{i}(z, v)ϕ_{p−i}(z, v) + v ∑_{i=0}^{p−1} ϕ_{i}(z, v)ϕ_{p−1−i}(z, v) + 2F_{0}(z, v)F_{p}(z, v), (2)

with the initial functions ϕ_{0}(z, v) = F_{0}(z, v) = \frac{1}{1−z}. The difference in the above recurrences reflects the difference between both parameters coming from the instance where the root is not selected and also the left (i = 0) resp. right (i = p) subtree of the root does not contain a selected node.

Introducing the trivariate generating functions Φ(z, u, v) = ∑_{p≥0} ϕ_{p}(z, v)u^{p} and F (z, u, v) = ∑_{p≥0} F_{p}(z, v)u^{p}, we obtain first from (1) a Riccati differential equation:

\frac{∂}{∂z} Φ(z, u, v) = v(1 + u)Φ^{2}(z, u, v) + \frac{1 − v}{(1 − z)^{2}} ,  (3)

with the initial value Φ(0, u, v) = 1. The solution of this equation is already given in [9]:

Φ(z, u, v) = \frac{Ω + 1 − 2v + (1 − z)^{Ω}(Ω − 1 + 2v)}{(Ω + 1 − 2v(1 + u) + (1 − z)^{Ω}(Ω − 1 + 2v(1 + u)))(1 − z)},  (4)

with

Ω = \sqrt{1 − 4(1 + u)v(1 − v)}.  (5)

For F (z, u, v) we get from (2) the differential equation

\frac{∂}{∂z} F (z, u, v) = v(1 + u)Φ^{2}(z, u, v) − \frac{2v}{1 − z} Φ(z, u, v) + \frac{2}{1 − z} F (z, u, v) + \frac{v − 1}{(1 − z)^{2}}

or

\frac{∂}{∂z} F (z, u, v) = \frac{∂}{∂z} Φ(z, u, v) − \frac{2v}{1 − z} Φ(z, u, v) + \frac{2}{1 − z} F (z, u, v) + \frac{2(v − 1)}{(1 − z)^{2}},

with F (0, u, v) = 1.

This equation has then the solution

F (z, u, v) = \frac{1 + 2z(v − 1)}{(1 − z)^{2}} + \frac{1}{(1 − z)^{2}} ∫_{0}^{z} [\frac{∂}{∂t}Φ(t, u, v) − \frac{2v}{1 − t}Φ(t, u, v)] (1 − t)^{2}dt, (6)

with Φ(z, u, v) given by (4).

3. Expectation and variance of the spanning tree size

From (6) it is easy to obtain exact formulæ for the expectation

E_{n,p} = 𝔼(Y_{n,p}) = \frac{1}{\binom{n}{p}}[z^{n}u^{p}] \frac{∂}{∂v} F (z, u, v)|_{v=1}

and the second factorial moment

M_{n,p}^{(2)} = 𝔼(Y_{n,p}(Y_{n,p} − 1)) = \frac{1}{\binom{n}{p}}[z^{n}u^{p}] \frac{∂^{2}}{∂v^{2}} F (z, u, v)|_{v=1}

(and thus also for the variance V_{n,p}) of Y_{n,p}, the size of the spanning tree of p randomly selected nodes in a random binary search tree of size n.

Differentiating (6) with respect to v and evaluating at v = 1 gives the following equation for E(z, u) := \frac{∂}{∂v} F (z, u, v)|_{v=1}:

E(z, u) = \frac{2z}{(1 − z)^{2}} + \frac{1}{(1 − z)^{2}} ∫_{0}^{z} [\frac{4(1 − t)(1 + u)u^{2}}{(1 − t(1 + u))^{3}} log \frac{1}{1 − t} + \frac{X}{(1 − t(1 + u))^{3}} ] dt, (7)

with X = (−2 + u) + (6 + 3u − 3u^{2} − 4u^{3})t + (1 + u)(2u^{2} − 3u − 6)t^{2} + (2 + u)(1 + u)^{2}t^{3}. This can be simplified to

\begin{aligned}E(z, u) & = \frac{2u(1 + u)}{(1 − z(1 + u))^{2}} log \frac{1}{1 − z} − \frac{2u}{(1 − z)^{2}(1 + u)^{2}} log \frac{1}{1 − z(1 + u)} \\ & + \frac{zu(1 − 2z − 3u + z^{2} + uz − 2u^{2} + 2uz^{2} + 3u^{2}z + u^{2}z^{2})}{(1 − z)^{2}(1 + u)(1 − z(1 + u))^{2}}. \end{aligned}  (8)

To extract coefficients we use here and in the sequel the general formulæ (see e. g. [3])

[z^{n}]\frac{1}{(1 − z)^{m+1}} log \frac{1}{1 − z} = \binom{n + m}{n}(H_{n+m} − H_{m}),
[z^{n}]\frac{1}{(1 − z)^{m+1}} log^{2} \frac{1}{1 − z} = \binom{n + m}{n}((H_{n+m} − H_{m})^{2} − (H_{n+m}^{(2)} − H_{m}^{(2)})),

where H_{n} = ∑_{k=1}^{n} \frac{1}{k} and H_{n}^{(2)} = ∑_{k=1}^{n} \frac{1}{k^{2}} denote the first and second order harmonic numbers.

By lengthy, but routine calculations, we finally get for E_{n,p} = \frac{1}{\binom{n}{p}}[z^{n}u^{p}]E(z, u) an exact

formula, which is given in the next lemma:

Lemma 1. The expectation E_{n,p} = 𝔼(Y_{n,p}) of the size of the spanning tree of p randomly chosen nodes in a random binary search tree of size n is for p ≥ 1 given by

E_{n,p} = \frac{2p(n + 1)^{2}}{(n + 2 − p)(n + 1 − p)}(H_{n} − H_{p}) + \frac{2(2p − 1)(n + 1)}{(n + 2 − p)(n + 1 − p)} + 3 + 2p − \frac{2pn}{n + 1 − p}

+ \frac{2p(n + 1)(−1)^{p}}{\binom{n}{p}} H_{n} + \frac{2p(n + 1)(−1)^{p}}{\binom{n}{p}} ∑_{k=1}^{p−1} \frac{(−1)^{k}}{k} \binom{n}{k},

and asymptotically for fixed p ≥ 2 by

E_{n,p} = 2p log n + 2pγ − 2pH_{p} + 3 − 2p − \frac{2p}{p − 1} + O(\frac{log n}{n}).

For p = 1 the formula simplifies to E_{n,1} = 1 as it should.

We remark that

H_{n} = ∑_{k=1}^{n} \frac{(−1)^{k−1}}{k} \binom{n}{k},

and so one can give the alternative formula

E_{n,p} = \frac{2p(n + 1)^{2}}{(n + 2 − p)(n + 1 − p)}(H_{n} − H_{p}) + \frac{2(2p − 1)(n + 1)}{(n + 2 − p)(n + 1 − p)} + 3 + 2p − \frac{2pn}{n + 1 − p}

+ \frac{2p(n + 1)(−1)^{p}}{\binom{n}{p}} ∑_{k=p}^{n} \frac{(−1)^{k−1}}{k} \binom{n}{k}.

When we differentiate equation (6) twice with respect to v and evaluate at v = 1, we finally obtain the following formula for M_{2}(z, u) := \frac{∂^{2}}{∂v^{2}} F (z, u, v)|_{v=1}:

M_{2}(z, u) = −\frac{8u}{(1 − z)^{2}} ∫_{0}^{z} \frac{1}{1 − t(1 + u)} log \frac{1}{1 − t}dt + \frac{4u(1 + u)^{2}(1 − z + 2u − uz)}{(1 − z(1 + u))^{3}} log^{2} \frac{1}{1 − z}
+ \frac{12u}{(1 − z)^{2}(1 + u)^{2}} log \frac{1}{1 − z(1 + u)} + \frac{4uΨ_{1}}{(1 − z)(1 − z(1 + u))^{3}} log \frac{1}{1 − z}  (9)

+ \frac{2u^{2}zΨ_{2}}{(1 − z)^{2}(1 − z(1 + u))^{3}(1 + u)},

with the abbreviations

Ψ_{1} = −z^{2}u^{2} − 3z^{2} − 5z^{2}u + u^{3}z^{2} + 6z + 9zu + 2u^{2}z − u^{3}z − 3u^{2} − 4u − 3,
Ψ_{2} = −z^{3}u^{3} + 3u^{3}z^{2} − 2u^{3}z − 19u^{2}z + 22z^{2}u^{2} + 6u^{2} − 3z^{3}u^{2} + 14u − 3z^{3}u − 46zu
+ 35z^{2}u + 14 − 29z − z^{3} + 16z^{2}.

Extracting coefficients gives after a somewhat lengthy calculation an exact formula for the

second factorial moment M_{n,p}^{(2)} = \frac{1}{\binom{n}{p}}[z^{n}u^{p}]M_{2}(z, u) and we get via V_{n,p} = M_{n,p}^{(2)} +E_{n,p} −E_{n,p}^{2}

the following result: Lemma 2. The variance V_{n,p} = 𝕍(Y_{n,p}) of the size of the spanning tree of p chosen nodes in a random binary search tree of size n is for p ≥ 2 given by

V_{n,p} = \frac{4(−1)^{p}(n + 1)(2pH_{n} − 2pH_{p} + 2 − 3p^{2})}{p\binom{n}{p}} ∑_{k=1}^{p−1} \frac{(−1)^{k}}{k} \binom{n}{k}

− \frac{8(−1)^{p}(n + 1)}{\binom{n}{p}} ∑_{k=1}^{p−1} \frac{(−1)^{k}}{k^{2}} \binom{n}{k} + \frac{4(−1)^{p}(n + 1)}{\binom{n}{p}}(H_{n}^{2} − H_{n}^{(2)} − 2H_{p}H_{n})

+ \frac{4(−1)^{p}(2 − 3p^{2})(n + 1)}{p\binom{n}{p}}H_{n} − \frac{4Ψ_{3}}{(n + 4 − p)\underline{4}} (H_{n} − H_{p})

+ \frac{4p(n + 2)(n + 1)^{3}(np + 2 + p)}{(n + 4 − p)\underline{4}}((H_{n} − H_{p})^{2} − (H_{n}^{(2)} − H_{p}^{(2)})) + \frac{2Ψ_{4}}{(n + 4 − p)\underline{4}}

+ E_{n,p} − E_{n,p}^{2}, with

Ψ_{3} = −2p^{4} − 6n^{2}p^{3} + 16p^{3} − 2n^{3}p^{3} − 45p^{2}n − 58p^{2} − 4n^{2}p^{2} + 2p^{2}n^{4} + 7n^{3}p^{2} + 56p

+ 78np + 6n^{3}p + 41pn^{2} − n^{4}p − 8 − 20n − 16n^{2} − 4n^{3},

Ψ_{4} = −144 − 6p^{5} − 3n^{4} − 152p^{3}n + 2p^{4}n^{2} + 25p^{4}n − 234n + 78p + 10np − 5n^{4}p − 39n^{2}p^{3}

− 4n^{3}p^{3} + 250p^{2}n + 119n^{2}p^{2} + 2p^{2}n^{4} + 25n^{3}p^{2} −22n^{3}p − 35pn^{2} + 155p^{2} −173p^{3} + 58p^{4} − 153n^{2} − 42n^{3}.

Further we have V_{n,1} = 0 and the following asymptotic expansion for n → ∞ and fixed p ≥ 2:

V_{n,p} = 2p log n − 2p(H_{p} − γ) − 4p^{2}(\frac{π^{2}}{6} − H_{p}^{(2)}) + \frac{2(−2 + 7p − 5p^{2} + 2p^{3})}{(1 − p)^{2}} + O(\frac{log^{2} n}{n}).

Here we used the abbreviation x\underline{m} := x(x − 1) ⋯ (x − m + 1) for the falling factorials. We remark again that an alternative representation of the variance would be possible

using the additional formula

\frac{1}{2}(H_{n}^{2} + H_{n}^{(2)}) = ∑_{k=1}^{n} \frac{(−1)^{k−1}}{k^{2}} \binom{n}{k}.

4. The limiting distribution of the number of passes in Multiple Quickselect

We will show that both random variables X_{n,p} and Y_{n,p} satisfy, for fixed p, a Gaussian limit law. To do this, we will expand the coefficients at u^{p} (for fixed p) of the trivariate generating functions Φ(z, u, v) resp. F (z, u, v) around their dominant singularity z = 1, where the expansion holds uniformly for |v − 1| < τ, for τ > 0. Singularity analysis (see [2]) of generating functions allows then to translate these expansions into an asymptotic expansion of the moment generating function (the Laplace transform) of the considered random variables. Then we can apply the so called Quasi power theorem (see [4]) to establish the weak convergence of the random variables to the normal distribution with certain convergence rates.

In this section we will treat the random variable X_{n,p}. As described above, we are interested in an asymptotic expansion of \frac{1}{\binom{n}{p}}[z^{n}u^{p}]Φ(z, u, v) for n → ∞ and fixed p uniformly

for |v − 1| ≤ τ, where Φ(z, u, v) is given by the exact formula (4).

To expand Φ(z, u, v) we will use some auxiliary expansions of

f(u) = Ω + 1 − 2v + (1 − z)^{Ω}(Ω − 1 + 2v),  (10)
g(u) = Ω + 1 − 2v(1 + u) + (1 − z)^{Ω}(Ω − 1 + 2v(1 + u))  (11)

with Ω given by (5). All O–terms in the expansions given below are uniform for |v − 1| ≤ τ, as required. In the sequel, we will use the notations D_{u} for the differential operator w. r. t. u and N_{u} for the evaluation operator at u = 0.

Since

Ω = (2v − 1) ∑_{k≥0} \binom{\frac{1}{2}}{k}( − \frac{4v(1 − v)}{1 − 4v(1 − v)})^{k}u^{k},

we get

(1 − z)^{Ω} = e^{Ω log(1−z)} = (1 − z)^{2v−1} exp [(2v − 1) log(1 − z) ∑_{k≥1} \binom{\frac{1}{2}}{k}( − \frac{4v(1 − v)}{1 − 4v(1 − v)})^{k}u^{k}],

and thus

N_{u}D_{u}^{p}(1 − z)^{Ω} = O((1 − z)^{2v−1} log^{p}(1 − z)).  (12)

We have

f(0) = g(0) = (1 − z)^{2v−1}2(2v − 1)  (13)

and we get further

N_{u}D_{u}f(u) = −\frac{4v(1 − v)}{2(2v − 1)} + O((1 − z)^{2v−1} log(1 − z)),  (14a)
N_{u}D_{u}g(u) = −\frac{2v^{2}}{2v − 1} + O((1 − z)^{2v−1} log(1 − z)),  (14b)

N_{u}D_{u}^{p}f(u) = (2v − 1)p!\binom{\frac{1}{2}}{p} (−\frac{4v(1 − v)}{1 − 4v(1 − v)})^{p} + O((1 − z)^{2v−1} log^{p}(1 − z)), (14c)
N_{u}D_{u}^{p}g(u) = (2v − 1)p!\binom{\frac{1}{2}}{p} (−\frac{4v(1 − v)}{1 − 4v(1 − v)})^{p} + O((1 − z)^{2v−1} log^{p}(1 − z)), (14d)

for p ≥ 2. Furthermore, we want to expand D_{u}^{p}(g(u))^{−1} (for p ≥ 1) in terms of falling powers of (g(u))^{−1}, which gives

D_{u}^{p}(g(u))^{−1} = (−1)^{p}p!(g(u))^{−p−1}(g′(u))^{p} + \frac{(−1)^{p−1}(p − 1)p!}{2}(g(u))^{−p}(g′(u))^{p−2}g′′(u)
+ O((g(u))^{−p+1})

and hence we obtain the expansion

N_{u}D_{u}^{p}(g(u))^{−1} = (−1)^{p}p!\frac{( − \frac{2v^{2}}{2v−1} + O((1 − z)^{2v−1} log(1 − z)))^{p}}{(1 − z)^{(p+1)(2v−1)}2^{p+1}(2v − 1)^{p+1}} + O(\frac{1}{(1 − z)^{p(2v−1)}} )

= \frac{(−1)^{p}p!( − \frac{2v^{2}}{2v−1})^{p}}{(1 − z)^{(p+1)(2v−1)}2^{p+1}(2v − 1)^{p+1}} + O(\frac{log(1 − z)}{(1 − z)^{p(2v−1)}} ).  (15)

This finally gives

N_{u}D_{u}^{p}Φ(z, u, v) = N_{u}D_{u}^{p} \frac{f(u)}{(1 − z)g(u)}

= \frac{1}{1 − z} f(0)N_{u}D_{u}^{p}(g(u))^{−1} + \frac{1}{1 − z} pf′(0)N_{u}D_{u}^{p−1}(g(u))^{−1} + \frac{1}{1 − z} O(\frac{1}{(1 − z)^{(p−1)(2v−1)}} )

= \frac{(1 − z)^{2v−1}2(2v − 1)(−1)^{p}p!( − \frac{2v^{2}}{2v−1})^{p}}{(1 − z)^{(p+1)(2v−1)+1}2^{p+1}(2v − 1)^{p+1}} + \frac{p( − \frac{4v(1−v)}{2(2v−1)})(−1)^{p−1}(p − 1)!( − \frac{2v^{2}}{2v−1})^{p−1}}{(1 − z)^{p(2v−1)+1}2^{p}(2v − 1)^{p}}

+ O(\frac{log(1 − z)}{(1 − z)^{(p−1)(2v−1)+1}} )

= \frac{p!(\frac{v}{2v−1})^{2p−1}}{(1 − z)^{p(2v−1)+1}} + O(\frac{log(1 − z)}{(1 − z)^{(p−1)(2v−1)+1}} ).  (16)

Singularity analysis leads then directly to

[z^{n}]N_{u}D_{u}^{p}Φ(z, u, v) = p!(\frac{v}{2v − 1})^{2p−1}\frac{n^{p(2v−1)}}{Γ(p(2v − 1) + 1)}(1 + O(\frac{1}{n}))+ O((log n) n^{(p−1)(2v−1)})

= \frac{p!(\frac{v}{2v−1})^{2p−1}n^{p(2v−1)}}{Γ(p(2v − 1) + 1)} (1 + O(\frac{1}{n}))(1 + O(\frac{log n}{n^{2v−1}} ))

= \frac{p!(\frac{v}{2v−1})^{2p−1}n^{p(2v−1)}}{Γ(p(2v − 1) + 1)} (1 + O(\frac{1}{n^{1−ϵ}} )),  (17)

uniformly for ϵ > 0 and |v − 1| ≤ τ := \frac{ϵ}{3} and also to the following expansion, which is valid for fixed p ≥ 1:

\frac{1}{\binom{n}{p}}[z^{n}u^{p}]Φ(z, u, v) = \frac{p!}{n^{p}} [z^{n}u^{p}]Φ(z, u, v)(1 + O(\frac{1}{n}))  (18)

= \frac{1}{n^{p}} [z^{n}]N_{u}D_{u}^{p}Φ(z, u, v)(1 + O(\frac{1}{n}))

= \frac{p!(\frac{v}{2v−1})^{2p−1}n^{p(2v−2)}}{Γ(p(2v − 1) + 1)} (1 + O(\frac{1}{n^{1−ϵ}} ))

= exp [p(2v − 2) log n + log (\frac{p!(\frac{v}{2v−1})^{2p−1}}{Γ(p(2v − 1) + 1)})](1 + O(\frac{1}{n^{1−ϵ}} )).

(19)

We give here the Quasi power theorem as proven in [4], which we want to apply to our problem:

Theorem 3. [H. K. Hwang] Let {Ω_{n}}_{n≥1} be a sequence of integral random variables. Suppose that the moment generating function satisfies the asymptotic expression

M_{n}(s) := 𝔼 (e^{Ω_{n}s}) = ∑_{m≥0} ℙ{Ω_{n} = m}e^{ms} = e^{H_{n}(s)}(1 + O(κ_{n}^{−1})),

the O–term being uniform for |s| ≤ τ, s ∈ ℂ, τ > 0, where

(i) H_{n}(s) = u(s)ϕ(n) + v(s), with u(s) and v(s) analytic for |s| ≤ τ and independent of n; u′′(0) ≠ 0,

(ii) ϕ(n) → ∞, (iii) κ_{n} → ∞.

Under these assumptions, the distribution of Ω_{n} is asymptotically Gaussian:

ℙ\{\frac{Ω_{n} − u′(0)ϕ(n)}{\sqrt{u′′(0)ϕ(n)}} < x\} = Φ(x) + O(\frac{1}{κ_{n}} + \frac{1}{\sqrt{ϕ(n)}}),

uniformly with respect to x, x ∈ ℝ. Here Φ(x) denotes the distribution function of the standard normal distribution N (0, 1).

Moreover, the mean and the variance of Ω_{n} satisfy

𝔼(Ω_{n}) = u′(0)ϕ(n) + v′(0) + O(κ_{n}^{−1}), 𝕍(Ω_{n}) = u′′(0)ϕ(n) + v′′(0) + O(κ_{n}^{−1}).

From (19) we get with the notations in Theorem 3:

u(s) = p(2e^{s} − 2), v(s) = log (\frac{p!(\frac{e^{s}}{2e^{s}−1})^{2p−1}}{Γ(p(2e^{s} − 1) + 1)}), ϕ(n) = log n, κ_{n} = n^{1−ϵ}.

We find

u′(0) = 2p,  u′′(0) = 2p,  (20)

and

v′(0) = −2p + 1 − 2pΨ(p + 1) = −2pH_{p} + 2pγ + 1 − 2p,
v′′(0) = 2(2p − 1) − 2pΨ(p + 1) − 4p^{2}Ψ′(p + 1)  (21)

= 2(2p − 1) − 2pH_{p} + 2pγ − \frac{2}{3}π^{2}p^{2} + 4p^{2}H_{p}^{(2)},

where Ψ(x) denotes the digamma function: Ψ(x) := ( log Γ(x))′.

Hence, with equations (20) and (21), we get from Theorem 3 the following result:

Theorem 4. The distribution of the random variable X_{n,p}, which counts the number of passes in the Multiple Quickselect algorithm that are required to find a random order statistic of p elements in a data file of size n, is for fixed p ≥ 1 asymptotically Gaussian, where the convergence rate is of order O(\frac{1}{\sqrt{log n}}):

ℙ \{\frac{X_{n,p} − 2p log n}{\sqrt{2p log n}}\} = Φ(x) + O(\frac{1}{\sqrt{log n}}),

and the expectation E_{n,p} = 𝔼(X_{n,p}) and the variance V_{n,p} = 𝕍(X_{n,p}) satisfy

E_{n,p} = 2p log n + 1 − 2p − 2pH_{p} + 2pγ + O(\frac{1}{n^{1−ϵ}} ),

V_{n,p} = 2p log n + 4p − 2 − 2pH_{p} + 2pγ + 4p^{2}H_{p}^{(2)} − \frac{2}{3}π^{2}p^{2} + O(\frac{1}{n^{1−ϵ}} ).

The result for E_{n,p} and V_{n,p} already appeared in [9], but unfortunately there was a typo in the formula for V_{n,p}.

For the case p = 1 we have that X_{n,1} counts the number of comparisons encountered by a successful search in a random binary search tree and this is, up to an additive constant, the same as the depth D_{n} of a randomly selected node, D_{n} =^{L} X_{n,1} − 1. The asymptotic normality of the distribution of X_{n,1} is well known (see e. g. [6]), and the convergence rate was recently established in [7].

5. The limiting distribution of the spanning tree size in binary search trees

In this section we will show, that the normalized random variable Y_{n,p}, as defined in Section 4, has for fixed p a Gaussian limiting distribution. Hence we are interested in an asymptotic expansion of \frac{1}{\binom{n}{p}}[z^{n}u^{p}]F (z, u, v) for n → ∞ and fixed p uniformly for |v−1| ≤ τ,

where F (z, u, v) is given by (6).

To do this, we will first study the behaviour near the singularity z = 1 of the expression

Φ̃(z, u, v) = (\frac{∂}{∂z} Φ(z, u, v) − \frac{2v}{1 − z} Φ(z, u, v)) (1 − z)^{2},  (22)

which we can write as

Φ̃(z, u, v) = \frac{f̃(u)}{(g(u))^{2}} ,  (23)

where the function f̃(u) is defined by

f̃(u) = −Ω(Ω − 1 + 2v)(1 − z)^{Ω}g(u) + Ω(Ω − 1 + 2v(1 + u))(1 − z)^{Ω}f(u) + (1 − 2v)f(u)g(u), (24)

and Φ(z, u, v), Ω, f(u) and g(u) are given by equations (4), (5), (10) and (11), respectively. The relevant expansions are now

f̃(0) = −4(2v − 1)^{3}(1 − z)^{4v−2},
f̃′(0) = 8v^{2}(2v − 1)(1 − z)^{2v−1} + O( log(1 − z) (1 − z)^{4v−2}),
f̃′′(0) = \frac{8(v − 1)v^{3}}{2v − 1} + O( log(1 − z) (1 − z)^{2v−1}),

and

N_{u}D_{u}^{p}(g(u))^{−2} = (−1)^{p}(p + 1)!\frac{(g′(0))^{p}}{(g(0))^{p+2}} + O(\frac{1}{(g(0))^{p+1}} ),

which leads for p ≥ 2 eventually to

N_{u}D_{u}^{p}Φ̃(z, u, v) = f̃(0)N_{u}D_{u}^{p}(g(u))^{−2} + pf̃′(0)N_{u}D_{u}^{p−1}(g(u))^{−2}

+ \frac{p(p − 1)}{2}f̃′′(0)N_{u}D_{u}^{p−2}(g(u))^{−2} + O(\frac{1}{(1 − z)^{(p−1)(2v−1)}} )

= \frac{(p − 1)p!v(\frac{v}{2v−1})^{2p−2}}{(1 − z)^{p(2v−1)}} + O(\frac{log(1 − z)}{(1 − z)^{(p−1)(2v−1)}} ).  (25)

This gives then

\frac{1}{\binom{n}{p}}[z^{n}u^{p}]F (z, u, v) = \frac{1}{\binom{n}{p}}[z^{n}u^{p}]\frac{1}{(1 − z)^{2}} ∫_{t=0}^{z} Φ̃(t, u, v)dt

= \frac{1}{n^{p}} [z^{n}]\frac{1}{(1 − z)^{2}} ∫_{t=0}^{z} N_{u}D_{u}^{p}Φ̃(t, u, v)dt (1 + O(\frac{1}{n}))  (26)

= \frac{1}{n^{p}} [z^{n}]\frac{1}{(1 − z)^{2}} ∫_{t=0}^{z} [\frac{(p − 1)p!v(\frac{v}{2v−1})^{2p−2}}{(1 − z)^{p(2v−1)}} + O(\frac{log(1 − z)}{(1 − z)^{(p−1)(2v−1)}} )] dt (1 + O(\frac{1}{n})).

We get via singularity analysis

[z^{n}]\frac{1}{(1 − z)^{2}} ∫_{t=0}^{z} \frac{(p − 1)p!v(\frac{v}{2v−1})^{2p−2}}{(1 − z)^{p(2v−1)}} dt = [z^{n}]\frac{(p − 1)p!v(\frac{v}{2v−1})^{2p−2}}{(p(2v − 1) − 1)(1 − z)^{p(2v−1)+1}}

= \frac{(p − 1)p!v(\frac{v}{2v−1})^{2p−2}n^{p(2v−1)}}{(p(2v − 1) − 1)Γ(p(2v − 1) + 1)}(1 + O(\frac{1}{n}))  (27)

and

[z^{n}]\frac{1}{(1 − z)^{2}} ∫_{t=0}^{z} O(\frac{log(1 − t)}{(1 − t)^{(p−1)(2v−1)}} )dt

= O( ∑_{k=1}^{n}[z^{n−k}]\frac{1}{(1 − z)^{2}} [z^{k}] ∫_{t=0}^{z} \frac{log(1 − t)}{(1 − t)^{(p−1)(2v−1)}} dt)

= O (n max_{1≤k≤n}[z^{n−k}]\frac{1}{(1 − z)^{2}} max_{1≤k≤n}[z^{k}] ∫_{t=0}^{z} \frac{log(1 − t)}{(1 − t)^{(p−1)(2v−1)}} dt)

= O (n^{2}[z^{n}] ∫_{t=0}^{z} \frac{log(1 − t)}{(1 − t)^{(p−1)(2v−1)}} dt) = O ((log n) n^{(p−1)(2v−1)})

= O(n^{p(2v−1)} \frac{1}{n^{1−ϵ}} ),  (28)

uniformly for ϵ > 0 and |v − 1| ≤ τ := \frac{ϵ}{3}.

Thus we obtain by combining the results (26), (27) and (28) for p ≥ 2 the asymptotic expansion

\frac{1}{\binom{n}{p}}[z^{n}u^{p}]F (z, u, v) = \frac{(p − 1)p!v(\frac{v}{2v−1})^{2p−2}n^{p(2v−2)}}{(p(2v − 1) − 1)Γ(p(2v − 1) + 1)}(1 + O(\frac{1}{n^{1−ϵ}} )).  (29)

To apply the Quasi power theorem, we write (29) as

\frac{1}{\binom{n}{p}}[z^{n}u^{p}]F (z, u, v) = exp [p(2v − 2) log n + log (\frac{(p − 1)p!v(\frac{v}{2v−1})^{2p−2}}{(p(2v − 1) − 1)Γ(p(2v − 1) + 1)})]

× (1 + O(\frac{1}{n^{1−ϵ}} )) (30)

and then get, with the notations used in Theorem 3,

u(s) = p(2e^{s} − 2), v(s) = log (\frac{(p − 1)p!e^{s}(\frac{e^{s}}{2e^{s}−1})^{2p−2}}{(p(2e^{s} − 1) − 1)Γ(p(2e^{s} − 1) + 1)}),
ϕ(n) = log n, κ_{n} = n^{1−ϵ}.

We have

u′(0) = 2p, u′′(0) = 2p,  (31)

and

v′(0) = −2pΨ(p + 1) + 3 − 2p − \frac{2p}{p − 1} = −2pH_{p} + 2pγ + 3 − 2p − \frac{2p}{p − 1},

v′′(0) = −2pΨ(p + 1) − 4p^{2}Ψ′(p + 1) + \frac{2(2p^{3} − 5p^{2} + 7p − 2)}{(p − 1)^{2}}  (32)

= −2pH_{p} + 2pγ − \frac{2}{3}π^{2}p^{2} + 4p^{2}H_{p}^{(2)} + \frac{2(2p^{3} − 5p^{2} + 7p − 2)}{(p − 1)^{2}},

which leads now to the following result:

Theorem 5. The distribution of the random variable Y_{n,p}, which counts the size of the spanning tree of p randomly chosen nodes in a binary search tree of size n is for fixed p ≥ 2 asymptotically Gaussian, where the convergence rate is of order O(\frac{1}{\sqrt{log n}}):

ℙ \{\frac{Y_{n,p} − 2p log n}{\sqrt{2p log n}}\} = Φ(x) + O(\frac{1}{\sqrt{log n}}),

and the expectation E_{n,p} = 𝔼(Y_{n,p}) and the variance V_{n,p} = 𝔼(Y_{n,p}) satisfy

E_{n,p} = 2p log n − 2pH_{p} + 2pγ + 3 − 2p − \frac{2p}{p − 1} + O(\frac{1}{n^{1−ϵ}} ),

V_{n,p} = 2p log n − 2pH_{p} + 2pγ − \frac{2}{3}π^{2}p^{2} + 4p^{2}H_{p}^{(2)} + \frac{2(2p^{3} − 5p^{2} + 7p − 2)}{(p − 1)^{2}} + O(\frac{1}{n^{1−ϵ}} ).

Of course, the case p = 1 is trivial, since we have ℙ{Y_{n,1} = 1} = 1 due to the fact that the spanning tree of a single node is the node itself.

The case p = 2 is of particular interest, since Y_{n,2} is as described earlier, up to an additive constant, the distance Δ_{n} between two randomly selected nodes in a binary search tree of size n, viz. Δ_{n} =^{L} Y_{n,2} − 1. This parameter was studied already in [7], where the asymptotic normality of the distribution was shown by means of a refined contraction method.

References

[1] R. Dobrow, On the distribution of distances in recursive trees, Journal of Applied Probability 33, 749–757, 1996.

[2] Ph. Flajolet and A. Odlyzko, Singularity Analysis of Generating Functions, SIAM Journal on Discrete Mathematics 3, 216–240, 1990.

[3] D. Greene and D. Knuth, Mathematics for the Analysis of Algorithms, 2nd Ed., Birkhäuser, Boston, 1982.

[4] H.-K. Hwang, On Convergence Rates in the Central Limit Theorems for Combinatorial Structures, European Journal of Combinatorics 19, 329–343, 1998.

[5] S. Janson, The Wiener index of simply generated random trees, preprint, 2001.

[6] H. Mahmoud, Evolution of Random Search Trees, Wiley, New York, 1992.

[7] H. Mahmoud and R. Neininger, Distribution of Distances in Random Binary Search Trees, The Annals of Applied Probability, accepted for publication, 2002.

[8] R. Neininger, Wiener index of random trees, Combinatorics, Probability & Computing, accepted for publication, 2002.

[9] A. Panholzer and H. Prodinger, A Generating Functions Approach for the Analysis of Grand Averages for Multiple Quickselect, Random Structures and Algorithms 13, 189–209, 1998.

†Institut für Algebra und Computermathematik, Technische Universität Wien, Wiedner Hauptstraße 8–10, A- 1040 Wien, Austria.

   E-mail address: Alois.Panholzer@tuwien.ac.at

‡The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P.O. Wits, 2050 Johannesburg, South Africa.

   E-mail address: helmut@staff.ms.wits.ac.za
   WWW-address: http://www.wits.ac.za/helmut/index.htm