ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH
TREES

arXiv:1707.00165v1 [math.PR] 1 Jul 2017

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

Abstract. Following the model introduced by Aguech, Lasmar and Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133–141], the weighted depth
of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyze weighted depths of nodes with given
labels, the last inserted node, nodes ordered as visited by the depth first search
process, the weighted path length and the weighted Wiener index in a random
binary search tree. We establish three regimes of nodes depending on whether
the second order behaviour of their weighted depths follows from fluctuations
of the keys on the path, the depth of the nodes, or both. Finally, we investigate
a random distribution function on the unit interval arising as scaling limit for
weighted depths of nodes with at most one child.

1. Introduction
The binary search tree is an important data structure in computer science allowing for efficient execution of database operations such as insertion, deletion and
retrieving of data. Given a list of elements x1 , x2 , . . . , xn from a totally ordered set,
it is the unique labelled rooted binary tree with n nodes constructed by successive
insertion of all elements satisfying the following property: for each node in the tree
with label (or key), say y, all keys stored in its left (right) subtree are at most equal
to (strictly larger than) y. For an illustration, see Figure 1.
4

2

1

6

3

5

7

Figure 1. binary search tree constructed from the list 4, 2, 6, 5, 7, 3, 1.
Date: July 4, 2017.
1991 Mathematics Subject Classification. 60F05, 68P05, 68Q25.
Key words and phrases. analysis of algorithm, data structures, binary search trees, central
limit theorems, contraction method, random probability measures.
1

2

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

Properties of binary search trees are typically analyzed under the random permutation model where the data x1 , . . . , xn are generated by a uniformly chosen
permutation of the first n integers. Among the quantities studied in binary search
trees, one finds depths of and distances between nodes related to the performance of
search queries and finger searches in the database, the (total) path length measuring
the cost of constructing the tree as well as the Wiener index. Further, more complex parameters such as the height corresponding to worst case search times, the
saturation level and the profile have been studied thoroughly. We review literature
relevant in the context of our work below.
In this note we complement the wide literature on random binary search trees
by the analysis of depths of nodes, path length and Wiener index in their weighted
versions as introduced by Aguech, Lasmar and Mahmoud [1]. Here, the weighted
depth of a node is the sum of all keys stored on the path to the root. In [1],
results about weighted depths of extremal paths have been obtained. Kuba and
Panholzer [19], [20] studied the problem in random increasing trees covering the
random recursive tree and the random plane-oriented recursive tree. Weighted
depths of nodes and the weighted height were also studied by Broutin and Devroye
[3] in a more general tree model, which relies on assigning weights to the edges
of the tree. Further, the weighted path length in this model was investigated by
Rüschendorf and Schopp [29]. Note that we deviate from the notation introduced in
[1] and [19] using the term weighted depth for what is called weighted path length
there since we also study a weighted version of the (total) path length of binary
search trees.

2. Preliminaries
We introduce some notation. By the size of a finite binary tree, we refer to
its number of nodes. Upon embedding a finite rooted binary tree in the complete
infinite binary tree, a node is called external if its graph distance to the binary
tree is one. Any node on level k ≥ 1 in a rooted binary tree is associated a vector
v1 v2 . . . vk ∈ {0, 1}k where vi = 0 if and only if the path from the root to the node
continues in the left subtree upon reaching level i − 1.
Let n ≥ 1 and 1 ≤ k ≤ n. Under the random permutation model (short:
permutation model ), let Dk (n) be the depth of the node labelled k. By Wk (n)
we denote the sum of all keys on the path from the root to the node labelled k
including the labels of both endpoints. For x = x1 x2 . . . ∈ {0, 1}∞ , let Bn (x) be
the maximal depth among nodes of the form x1 . . . xk , k ≥ 0. We use Xn (Xn ) to
denote the (weighted) depth of the nth inserted node. Finally, we define the height
of the tree by Hn = sup{k ∈ N : Dk (n) > 0}.
Throughout the paper, we denote by L(X) the distribution of a random variable
X. For real-valued X with finite second moment, we write σX for its standard deviation. By N we denote a random variable with the standard normal distribution,

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

3

and by µ the Dickman distribution on [0, ∞) characterized by its Fourier transform,
Z 1 iλx

Z
e −1
eiλx dµ(x) = exp
(1)
dx , λ ∈ R.
x
0
The origins of the Dickman distribution go back to Dickman’s [10] classical result
on large prime divisors. Compare Hildebrandt and Tenenbaum [15] for a survey on
the problem. In the probabilistic analysis of algorithm, µ first arose in Hwang and
Tsai’s [17] study of the complexity of Hoare’s selection algorithm. We refer to this
work for a discussion of more details on the distribution, historical background and
further references.
Finally, we use the Landau notations little–o, big–O, little–ω, big–Ω and big–Θ
as n → ∞.
2.1. Depths and height. We recall the following fundamental property of random
binary search trees going back to Devroye [6]: in probability and with respect to
all moments, we have
Hn
→ c∗ ,
log n

(2)

where c∗ = 4.31 . . . is the larger of the two solutions to the transcendent equation
x
e = ( 2e
x ) . Next, by classical results due to Brown and Shubert [4] and Devroye [7],
for any x ∈ {0, 1}∞ , in distribution,
(3)

Bn (x) − log n
√
→ N,
log n

Xn − 2 log n
√
→ N.
2 log n

(In [7, Theorem O1], the first convergence in the last display is formulated for
x = 0 := 00 . . . The general case follows, since, by symmetry, L(Bn (x)) = L(Bn (0))
for all x. The second convergence was also claimed in a footnote by Mahmoud and
Pittel [23].) Grübel [13] studied the process {Bn (x) : x ∈ {0, 1}∞ }, the so-called
silhouette, thereby obtaining a functional limit theorem for its integrated version.
The asymptotic behaviour of depths of nodes with given labels has been analyzed
by Devroye and Neininger [9]: uniformly in 1 ≤ k ≤ n and as n → ∞,
(4)

E [Dk (n)] = log(k(n − k)) + O(1),

Var(Dk (n)) = log(k(n − k)) + O(1).

Moreover, for any 1 ≤ k ≤ n, which may depend on n, in distribution
(5)

Dk (n) − E [Dk (n)]
→ N.
σDk (n)

Here, one should also compare Grübel and Stefanoski [14] for stronger results in
the context of the corresponding Poisson approximation. For a survey on depths
and distances in binary search trees, we refer to Mahmoud’s book [21]. Finally,
the asymptotic behaviour of the weighted depths of the nodes associated with the
vectors 0 and 1 := 11 . . . denoted by Ln and Rn (L and R stand for left and right)
were studied in [1]. In distribution,
(6)

Ln
→ Y,
n

Rn − nBn (1)
√
→ 0,
n log n

4

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

where Y has the Dickman distribution. The first convergence is closely related to
the limit law in Theorem 3.1 in [17].
2.2. Path length and Wiener index. In a rooted tree, the path length is defined
as the sum over all depths of nodes. Moreover, the Wiener index is obtained by
summing all distances of unordered pairs of vertices. For a random binary search
tree of size n, we denote its path length by Pn and its Wiener index by Wn . Denoting
by γ the Euler-Mascheroni constant, we have
(7)

E [Pn ] = 2n log n + (2γ − 4)n + o(n),

Var(Pn ) =

21 − 2π 2 2
n + o(n2 ),
3

going back to Hoare [16] and Knuth [18]. Further, by [25],
(8) E [Wn ] = 2n2 log n + (2γ − 6)n2 + o(n2 ),

Var(Wn ) =

20 − 2π 2 4
n + o(n4 ).
3

Central limit theorems for the path length go back to Régnier [27] and Rösler
[28], for the Wiener index to Neininger [25]. More precisely, by [25, Theorem 1.1],
there exists a non-trivial random variable Z ∗ on R2 characterized by a stochastic
fixed-point equation, such that, in distribution,


Wn − E[Wn ] Pn − E[Pn ]
,
(9)
→ Z ∗.
n2
n
2.3. The i.i.d. model. We also consider binary search trees of size n where the
data are chosen as the first n values of a sequence of independent random variables U1 , U2 , . . . each having the uniform distribution on [0, 1]. Since the vector
(rank(U1 ), . . . , rank(Un )) constitutes a uniformly chosen permutation, in distribution, both the permutation model and the i.i.d. model lead to the same unlabelled
tree. We use the same notation as in the permutation model for quantities not
involving the labels of nodes, that is, Xn , hn , Hn , Pn , Wn and Bn (x). Further, we
define the weighted path length Pn as the sum of all weighted depths, and the
weighted Wiener index Wn as the sum over all pairs of weighted distances. Here,
the weighted distance between two nodes equals the sum of all labels on the path
connecting them, labels of endpoints included. (Notice that the weighted distance
between a node and itself is equal to its label.) Finally, analogously to Bn (x), we
define Bn (x) as the weighted depth of the node of largest depth on the path x. We
call {Bn (x) : x ∈ {0, 1}∞ }, the weighted silhouette of the tree (at time n).
3. Main results
Our main results are divided into two groups: Theorems 1 and 2 hold in the
permutation model while Theorems 3 and 4 are formulated in the i.i.d. model.
3.1. Results in the permutation model. We start with the expansions of the
first two moments of the weighted depth Wk (n). Uniformly in 1 ≤ k ≤ n, as

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

5

n → ∞,
(10)

E [Wk (n)] = k log(k(n − k + 1)) + n + O(k + log n),

n2
+ O(kn).
2
It turns out that the asymptotic distributional behavior of Wk (n) with respect
to terms of second order is entirely described by that of kDk (n) if and only if
√
k = ω(n/ log n). Accordingly, in the remainder of this paper, we call nodes with
√
√
labels of order ω(n/ log n) large and of order O(n/ log n) small.
√
Theorem 1 (Weighted depths of large nodes). For k = ω(n/ log n),
(11)

(12)

Var(Wk (n)) = k 2 log(k(n − k + 1)) +

E [|Wk (n) − kDk (n)|] = o(σkDk (n) ).

In particular, for 0 < α < 1 and |k/n − α| = o((log n)−1/2 ), in distribution,


Dk (n) − 2 log n Wk (n) − 2αn log n
√
√
,
(13)
→ (N , N ).
2 log n
αn 2 log n
For the last inserted node, in distribution,


Xn
Xn − 2 log n
√
,
(14)
→ (N , ξ) ,
2n log n
2 log n
where N and ξ are independent and ξ is uniformly distributed on [0, 1].
The asymptotic behavior of weighted depths of small nodes is to be compared
with the corresponding results in [19]. Here, another phase transition occurs when
√
k = o(n/ log n).
√
Theorem 2 (Weighted depths of small nodes). Let k = O(n/ log n). Then, in
distribution,


Dk (n) − E [Dk (n)] Wk (n) − kDk (n)
(15)
,
→ (N , Y),
σDk (n)
n
where N and Y are independent and Y has the Dickman distribution. Thus, if
√
k log n/n → β ≥ 0, in distribution,


√
Dk (n) − 2 log n Wk (n) − E [Wk (n)]
√
,
→ (N , Y + 2βN − 1).
n
2 log n
√
In particular, if |k log n/n − β| = o((log n)−1/2 ) with β > 0, then, in distribution,
√


√
Dk (n) − 2 log n Wk (n) − 2βn log n
√
,
→ (N , Y + 2βN ).
n
2 log n
3.2. Results in the i.i.d. model. Any x ∈ {0, 1}∞ corresponds to a unique value
P∞
x ∈ [0, 1] by x = i=0 xi 2−i . This identification becomes one-to-one upon allowing
only those x ∈ {0, 1}∞ which contain infinitely many zeros and x = 1. In the
i.i.d. model, for any x ∈ {0, 1}∞ , k ≥ 1, the node x1 . . . xk eventually appears
in the sequence of binary search trees and we write Ξk (x) for its ultimate label.
The following theorem about the behavior of Bn (x) involves a random continuous
distribution function arising as the almost sure limit of Ξk (x), x ∈ [0, 1], as k →
∞. We believe that this process is of independent interest and state some of its

6

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

properties in Proposition 1 in Section 3.3. The simulations of Ξ15 presented in
Figure 2 illustrate the scaling limit.
Theorem 3 (Weighted silhouette). There exists a random continuous and strictly
increasing bijection Ξ(x), x ∈ [0, 1], such that, almost surely, uniformly on the unit
interval, Ξk (x) → Ξ(x). For any x ∈ [0, 1], in probability,
Bn (x)
→ Ξ(x).
log n
Also, for any m ≥ 1, in probability
Z 1
m
Bn (x)
(17)
− Ξ(x) dx → 0.
log n
0
(16)

Further, in probability,
Bn (x)
→ c∗ = 4.31 . . .
x∈[0,1] log n
sup

(18)

with c∗ as in (2). Finally, for any x ∈ [0, 1], in distribution,


Bn (x) − log n Bn (x)
√
(19)
→ (N , Ξ(x)),
,
log n
log n

1
0

0

1

where N and Ξ(x) are independent.

0

1

0

1

Figure 2. two simulations of Ξ15 , the dotted line being the graph
of the identity function.
The next theorem extends the distributional convergence result in Theorem 1.1
in [25], that is (9), by central limit theorems for the weighted path length and the
weighted Wiener index.
Theorem 4 (Weighted path length and Wiener index). In the i.i.d. model, we
have
E [Pn ] = n log n + (γ − 3/2)n + o(n),

E [Wn ] = n2 log n + (γ − 11/4)n2 + o(n2 ),

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

7

and
Var(Pn ) =

65 − 6π 2 2
n + o(n2 ),
36

Var(Wn ) =

2413 − 240π 2 4
n + o(n4 ).
1440

The leading constants in the expansions of the covariances between Pn , Wn , Pn and
Wn are given in (36)–(38). (The leading constant for Cov(Pn , Wn ) was already
given in [25].) As n → ∞, with convergence in distribution and with respect to the
first two moments in R4 , we have


Wn − E[Wn ] Wn − E[Wn ] Pn − E[Pn ] Pn − E[Pn ]
,
,
,
→ Z,
n2
n2
n
n
where the limiting distribution L(Z) is the unique fixed-point of the map T in (35).
Conclusions. We have seen that there exist three types of nodes showing
significantly different behavior with respect to their weighted depths. By Theorem
√
1, for k = ω(n/ log n), second order fluctuations of weighted depths are due to
√
variations of the depth of nodes. In the second regime, when k = Θ(n/ log n),
variations of weighted depths are determined by two independent contributions, one
√
for the depths and one for the keys on the paths. Finally, when k = o(n/ log n)
only fluctuations of labels on paths influence second order terms of weighted depths.
The third regime can be further subdivided with respect to the first order terms of
Wk (n) and kDk (n): for k = ω(n/ log n), they coincide, for k = Θ(n/ log n), they
are of the same magnitude, whereas, for k = o(n/ log n), they are of different scale.
By Theorem 3, the weighted silhouette behaves considerably different. Here, the
lack of concentration around the mean leads to an interesting random distribution
function on the unit interval as scaling limit.
3.3. Further results and remarks.
Model comparison. We decided to present Theorems 3 and 4 in the i.i.d.
model rather than in the permutation model since this allows for a stronger mode
of convergence in (16), (17) and a clearer presentation of the proof of Theorem 4.
In the i.i.d. model, denoting by W(k) (n) the weighted depth of the node of rank
k among the first n inserted keys, Theorems 1 and 2 remain valid upon replacing
Wk (n) by nW(k) (n). Similarly, Theorems 3 and 4 hold in the permutation model
where weighted depths and the weighted path length are to be scaled down by a
factor n and the weighted Wiener index by a factor n2 . The convergences in (16)
and (17) then only hold in distribution. This can be deduced most easily from the
following coupling of the two models: starting with the binary search tree in the
i.i.d. model, also consider the random binary search tree in the permutation model
relying on the permutation (rank(U1 ), . . . , rank(Un )). Then, for all 1 ≤ k ≤ n,
(20)

W(k) (n) −

rank(Ui )
Wk (n)
≤ Hn max Ui −
.
1≤i≤n
n
n

8

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

It is well-known that the second factor on right hand side grows like n−1/2 , compare,
e.g. Donsker’s theorem for empirical distribution functions or the Dvoretzky-KieferWolfowitz inequality [11]. Combining this, (20) and (2) is sufficient to transfer all
results in Section 3 between the two models.
The depth first search process. In the permutation model, let v1 , . . . , vn+1
be the external nodes as discovered by the depth first search process from left to
right. By Dk∗ (n) and Wk∗ (n), 1 ≤ k ≤ n + 1, we denote depth and weighted depth
of the external node vk . Then, at the end of Section 4.1, we show that, uniformly
in 1 ≤ k ≤ n,




(21) E |Dk (n) − Dk∗ (n)|2 = o(log n), E |Wk (n) − Wk∗ (n)|2 = o(Var(Wk (n))).
Thus, the results in Theorems 1 and 2 also cover the second order analysis of the
sequences Dk∗ (n) and Wk∗ (n).
Weighted distances. In the permutation model, let Dk,` (n) be the graph
distance between the nodes labelled 1 ≤ k ≤ ` ≤ n and Wk,` (n) be the sum of
all labels on the path from k to `, labels at the endpoints included. Asymptotic
normality for the sequence (Dk,` (n)) (after rescaling) under the optimal condition
` − k → ∞ has been obtained in [9]. For uniformly chosen nodes, distributional
convergence results date back to Mahmoud and Neininger [22] and Panholzer and
Prodinger [26]. Analogously to Theorem 1, it is straightforward to prove central
limit theorems jointly for weighted and non-weighted distances. We only state the
√
results. If ` − k = Ω(n) and k = ω(n/ log n), then
E [|Wk,` (n) − kDk (n) − `D` (n)|] = σ`D` (n) .
In particular, for 0 < s < t < 1 and |k/n − s| = o((log n)−1/2 ), |`/n − t| =
o((log n)−1/2 ), we have, in distribution,
!
Dk (n) − 2 log n D` (n) − 2 log n Dk,` (n) − 4 log n Wk,` (n) − 2(s + t)n log n
√
√
√
√
,
,
,
2 log n
2 log n
4 log n
n 2 log n


N1 + N2
√
→ N1 , N2 ,
, sN1 + tN2 .
2
Here, N1 , N2 are independent random variables both with the standard normal
distribution.
The limit process Ξ. The process Ξ in Theorem 3 is a random distribution
function. In particular, it can be regarded as an element in the set of càdlàg
functions D[0, 1] consisting of all f : [0, 1] → R, such that, for all t ∈ [0, 1], f (t) =
lims↓t f (s) and lims↑t f (s) exists. The absolute value of f is defined by sup{|f (t)| :
t ∈ [0, 1]}. Endowed with Skorokhod’s topology J1 , D[0, 1] becomes a Polish space.
We refer to Chapter 3 in Billingsley’s book [2] for detailed information on this
matter.

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

9

Proposition 1 (Properties of Ξ). The process Ξ is unique (in distribution) among
all càdlàg processes with finite absolute second moment satisfying
(22)

L((Ξ(t))t∈[0,1] ) = L( 1[0,1/2) (t)U Ξ(2t) + 1[1/2,1) (t) ((1 − U )Ξ0 (2t − 1) + U ) t∈[0,1] ).
Here, Ξ, Ξ0 , U are independent, U has the uniform distribution on [0, 1] and Ξ0 is
distributed like Ξ. We have
i) E [Ξ(t)] = t for all t ∈ (0, 1);
ii) L((Ξ(t))t∈[0,1] ) = L((1 − Ξ(1 − t))t∈[0,1] );
iii) Ξ(ξ) has the arcsine distribution with density
1
π

p

x(1 − x)

,

x ∈ (0, 1),

where Ξ, ξ are independent and ξ has the uniform distribution on [0, 1];
iv) for t ∈ (0, 1), L(Ξ(t)) has a smooth density ft : (0, 1) → (0, ∞);
v) for t ∈ (0, 1/2), xft0 (x) = −f2t (x), x ∈ (0, 1), ft is strictly monotonically
decreasing and limx↑1 ft (x) = 0;
(i)
(i)
vi) with αt := limx↓0 ft (x), i = 0, 1, t ∈ (0, 1/2) and γ0 = 1/4, γ1 = 5/16,
(i)
(i)
we have αt = (−1)i ∞ for 0 < t ≤ γi , |αt | < ∞ for γi < t < 1/2 and
(i)
|αt | ↑ ∞ as t ↓ γi .
Random recursive trees. A random recursive tree is constructed as follows:
starting with the root labelled one, in the kth step, k ≥ 2, a node labelled k is
inserted in the tree and connected to an already existing node chosen uniformly
at random. Weighted depths in random binary search trees differ substantially
from those in random recursive trees analyzed in [19] where all nodes show an
√
asymptotic behaviour comparable to that of nodes labelled k = o(n/ log n) in
the binary search tree. The difference is highlighted by the weighted path length.
Being of the same order as the path length in binary search trees, it follows from
results in [19] that the weighted path length Qn in a random recursive tree of size
n is of order n2 . The same is valid for its standard deviation. We conjecture that
the sequence (n−2 Qn ) converges in distribution to a non-trivial limit; however, the
recursive approach worked out in the proof of Theorem 4, which also applies to the
analysis of the path length in random recursive trees, seems not to be fruitful in
this context.
Outline. All results are proved in Section 4 starting with the proofs of Theorems 1 and 2 as well as (21) in Section 4.1. Here, most arguments are based on
representations of (weighted) depths as sums of bounded independent random variables which go back to Devroye and Neininger [9]. Theorem 3 and Proposition 1 are
proved in Section 4.2. In this part, the construction of the limiting process relies
on suitable uniform L1 -bounds on the increments of the process Ξk (x)x∈[0,1] , k ≥ 1,
while the properties of the limit laws formulated in Proposition 1 follow from the
distributional fixed-point equation (22). Finally, the proof of Theorem 4 relying on
the contraction method is worked out in Section 4.3.

10

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

4. Proofs
4.1. Weighted depths of labelled nodes. In the permutation model, let Aj,k
be the event that the node labelled k is in the subtree of the node labelled j.
Pn
Pn
Then, Dk (n) = j=1 1Aj,k − 1 and Wk (n) = j=1 j1Aj,k . It is easy to see that
A1,k , . . . , Ak−1,k and Ak+1,k , . . . , An,k are two families of independent events; however, there exist subtle dependencies between the sets. Following the approach in
[9], let Bj,k = Aj,k−1 for j < k and Bj,k = Aj,k+1 for j > k. For convenience,
let Bk,k be an almost sure event. The following lemma summarizes results in [9]
and we refer to this paper for a proof. In this context, note that Devroye [8] gives
distributional representations as sums of independent (or m-independent) indicator
variables for quantities growing linearly in n, such as the number of leaves.
Lemma 1. Let 1 ≤ k ≤ n. Then, the events Bj,k , j = 1, . . . , n, are independent.
For j 6= k, we have
P (Aj,k ) =

1
,
|k − j| + 1

P (Bj,k ) =

1
.
|k − j|

From the lemma, it follows that




n
n
X
X
j1Bj,k \Aj,k  ≤ 2k + log n.
1Bj,k \Aj,k  ≤ 2, and E 
E
j=1

j=1

The ideas in [9] can also be used to analyze second (mixed) moments. Straightforward calculations show the following bounds:


n
X
1Bj,k 1Bi,k \Ai,k  = O(1),
E
i,j=1

and

E

n
X


ij1Bj,k 1Bi,k \Ai,k  = O(k 2 + k(log n)2 ).

i,j=1

Here, both O-terms are uniform in 1 ≤ k ≤ n. Define D̄k (n) =
Pn
W̄k (n) = j=1 j1Bj,k . We make the following observation:

Pn

j=1

1Bj,k − 1 and

O: The asymptotic statements in (10), (11), Theorem 1 and Theorem 2 are
correct if and only if they are correct upon replacing Dk (n) by D̄k (n) and/or
Wk (n) by W̄k (n).
Pn
(i)
(i)
(i)
For i = 1, 2, n ≥ 0 and 1 ≤ k ≤ n, set Hn := j=1 j −i and Hk,n := Hk−1 +
(i)

Hn−k . Using Lemma 1, one easily computes


(1)
E W̄k (n) = k(Hk,n − 1) + n + 1,
(1)

(2)

Var(W̄k (n)) = k 2 (Hk,n − Hk,n − 3) +
(1)

(2)

n2
n
(1)
(1)
+ kn + 2k(Hk−1 − Hn−k ) − + k + 1.
2
2

As Hn = log(n + 1) + O(1) and Hn = O(1), both expansions (10) and (11) follow
from observation O.

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

11

4.1.1. Weighted depths of large nodes. We prove Theorem 1. First, (12) follows
from (4) and
(23)

E [|kDk (n) − Wk (n)|] ≤ k +

n
X

|k − j|P (Aj,k ) ≤ k + n.

j=1

√
For k = ω(n/ log n), combining (4), (5) and (10), in distribution,


Dk (n) − E [Dk (n)] Wk (n) − E [Wk (n)]
,
→ (N , N ).
σDk (n)
σWk (n)
From here, statement (13) follows from (4) and (10).
Considering the last inserted node with value Yn , note that, conditionally on
Yn = k, the correlations between the events Aj,k , j < k and Aj,k , j > k vanish.
More precisely, given Yn = k, the family {1Aj,k , j = 1, . . . , n} is distributed like
a family of independent Bernoulli random variables {Vj,k : j = 1, . . . , n} with
P (Vj,k = 1) = |k − j|−1 for j 6= k and P (Vk,k = 1) = 1. Thus,


n
n
1 X X
E [|Yn (Xn + 1) − Xn |] ≤
E
|k − j|1Aj,k Yn = k 
n
j=1
k=1


n
n
1 X X
|k − j|Vj,k  ≤ n.
E
=
n
j=1
k=1

By (3), we have Xn / log n → 2 in probability. Hence, in order to prove (14), it
suffices to show that, in distribution,


Xn − 2 log n Yn
√
(24)
,
→ (N , ξ) .
n
2 log n
For a sequence (kn ) satisfying sn ≤ kn ≤ tn for 0 < s < t < 1, let us condition
on the event Yn = kn . Then, by the central limit theorem for triangular arrays of
row-wise independent uniformly bounded random variables with diverging variance
applied to Vj,kn , j = 1, . . . , n, in distribution,
Xn − 2 log n
√
→ N.
2 log n
Hence, (24) follows from an application of the theorem of dominated convergence
noting that Yn is uniformly distributed on {1, . . . , n}.
4.1.2. Weighted depths of small nodes. We prove Theorem 2. Let D̄k> (n) =
√
Pn
Pn
>
j=k+1 j1Bj,k . Since k = O(n/ log n), the same
j=k+1 1Bj,k and W̄k (n) =
calculation as in (23) shows that,


E |W̄k (n) − W̄k> (n) − k(D̄k (n) − D̄k> (n))|
k
(25)
≤ → 0, n → ∞.
n
n

12

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

For λ, µ ∈ R, we have
h

i
p
logE exp iλ(D̄k> (n) − log n))/ log n + iµ(W̄k> (n) − k D̄k> (n))/n





n
X
p
j
−
k
λ
√
= −iλ log n + log E exp i
Bj,k 
+µ
n
log
n
j=k+1

 


λ
n
+ µ j−k
−1
exp i √log
X
p
n
n
.
= −iλ log n +
log 1 +
j−k
j=k+1

By a standard Taylor expansion, the last display equals
 

j−k
λ
n
exp i √log
+
µ
−1
X
p
n
n
− iλ log n +
+ o(1)
j−k
j=k+1



λ2
n
√ iλ
exp iµ j−k
1
+
−
X
p
n
2 log n − 1
log n
+ o(1)
= −iλ log n +
j−k
j=k+1


 n−1
X exp iµ j+1 − 1
iλ
λ2
2
n
= −λ /2 + 1 + √
+ o(1)
−
j+1
log n 2 log n j=0
Z 1 iµx
e −1
= −λ2 /2 +
dx + o(1).
x
0
Here, in the last step, we have used that the sum on the right hand side is a Riemann
sum over the unit interval whose mesh size n−1 tends to zero. Thus, using the
notation of the theorem, (1) and Lévy’s continuity theorem, in distribution,
 >

D̄k (n) − log n W̄k> (n) − k D̄k> (n)
√
(26)
,
→ (N , Y).
n
log n
In order to deduce (15) note that, by Lemma 1, D̄k (n)−D̄k> (n) and (D̄k> (n), W̄k> (n))
are independent while


D̄k (n) − D̄k> (n) − E D̄k (n) − D̄k> (n)
→ N,
σD̄k (n)−D̄k> (n)
in distribution if and only if k → ∞ using the central limit theorem for sums of
independent and uniformly bounded random variables. Since


√
D̄k (n) − E D̄k (n)
D̄k> (n) − E [Dk> (n)] log n
√
=
σD̄k (n)
σD̄k (n)
log n


>
D̄k (n) − D̄k (n) − E D̄k (n) − D̄k> (n) σD̄k (n)−D̄k> (n)
+
,
σD̄k (n)−D̄k> (n)
σD̄k (n)
we deduce
!


D̄k (n) − E D̄k (n) W̄k> (n) − k D̄k> (n)
,
→ (N , Y),
σD̄k (n)
n
from (26) upon treating the cases k = O(1) and k = ω(1) separately. From here,
the assertion (15) follows with the help of (25) and observation O.

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

13

4.1.3. Proof of (21). The main observation is that the kth external node visited
by the depth first search process is always contained in the subtree rooted at the
node labelled k. This can be proved by induction exploiting the decomposition of
the tree at the root. Thus, denoting by Hk (n) the height of the subtree rooted at
the node labelled k, we have
Dk (n) ≤ Dk∗ (n) ≤ Dk (n) + Hk (n),
Wk (n) ≤ Wk∗ (n) ≤ Wk (n) + Mk (n)Hk (n).
Here, Mk (n) stands for the largest label in the subtree rooted at the node labelled k.
Let Tk (n) be the size of the subtree rooted at k. Then Tk (n) = 1 + Tk< (n) + Tk> (n)
where Tk< (n) denotes the number of elements in the subtree rooted at k with values
smaller than k. By Lemma 1, for ` ≤ n − k, we have P (Tk> (n) ≥ `) = P (Ak,k+` ) =
1/(` + 1). Using the same arguments for the quantity Tk< (n), we deduce that,
uniformly in 1 ≤ k ≤ n,
E [Tk (n)] = Θ(log n),



E (Tk (n))2 = Θ(n1/2 ),



E (log Tk (n))2 = O(1).

Thus, by an application of (2), for some C1 > 0,






E |Dk (n) − Dk∗ (n)|2 ≤ E (Hk (n))2 ≤ C1 E (log Tk (n))2 = O(1).
By the same arguments, for some C2 > 0, we have






E |Wk (n) − Wk∗ (n)|2 ≤ E (Mk (n)Hk (n))2 ≤ E (k + Tk (n))2 (Hk (n))2


≤ C2 k 2 + 2C1 kE Tk (n)(log Tk (n))2


+ C1 E (Tk (n))2 (log Tk (n))2
= O(k 2 + (log n)2 n1/2 ).
From here, (21) follows from (10).
4.2. The weighted silhouette.
We prove Theorem 3 and Proposition 1.
Proof of Theorem 3. We start with the uniform convergence of (Ξk ). For
all x ∈ [0, 1], |Ξk (x) − Ξk−1 (x)| is distributed like the product of k + 1 independent random variables, each of which having the uniform distribution on [0, 1]. In
particular, by the union bound and Markov’s inequality, for any m ≥ 1,
!
! 
k
k+1
Y
2
k
t−m .
P sup |Ξk (x) − Ξk−1 (x)| ≥ t ≤ 2 P
Ui ≥ t ≤
m+1
x∈[0,1]
i=1
For k ≥ 1, let Dk = {`2−k : ` = 1, . . . , 2k − 1}. By construction, for k ≥ 1, the map
x → Ξk (x) is a right-continuous step function. Further, it is continuous at x if and

14

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

only if x ∈
/ Dk . Next, for 0 < q < 1,
"
# Z
E sup |Ξk (x) − Ξk−1 (x)| =
x∈[0,1]

!

∞

sup |Ξk (x) − Ξk−1 (x)| ≥ t dt

P

x∈[0,1]

0

k
2
≤q +
t−m dt
m+1
qk

k
1
2
k
=q +
q −k(m−1) .
m−1 m+1
k

Z

∞



p
2/3 the latter expression is bounded by 2q k . By
With m = 2 and q =
Markov’s inequality, it follows that supm≥n supx∈[0,1] |Ξm (x) − Ξn (x)| → 0 in
probability as n → ∞. An application of the triangle inequality shows that
supm,p≥n supx∈[0,1] |Ξm (x) − Ξp (x)| → 0 in probability as n → ∞. By monotonicity, this convergence is almost sure. Thus, almost surely, (Ξk ) is uniformly
Cauchy in the space of càdlàg functions endowed with the uniform topology. By
completeness, (Ξk ) converges to a limit denoted by Ξ with càdlàg paths. Moreover,
Ξ is continuous at x ∈
/ D where D = ∪m≥1 Dm since this is true for all Ξk , k ≥ 1.
For x ∈ D, let Φ(x) be the key of the node associated with x1 . . . xk−1 where k ≥ 1
is chosen minimal with x ∈ Dk . Then, limy↑x Ξ(x) = Φ(x) = Ξ(x). Thus, x 7→ Ξ(x)
is continuous. By the construction of the tree, it is clear that Ξ(x) < Ξ(y) for any
x, y ∈ D with x < y. As D is dense in [0, 1], the process Ξ is strictly monotonically
increasing. Obviously, Ξ(0) = 0 and Ξ(1) = 1; hence, Ξ is the distribution function
of a probability measure on [0, 1].
We turn to the convergence of Bn (x). For any fixed x ∈ [0, 1], display (3) implies
that, as n → ∞, in probability, Bn (x)/ log n → 1. Thus, (16) follows from the
convergence Ξk (x) → Ξ(x). The convergence (16) is with respect to all moments
since Bn (x) ≤ Hn and we have convergence of all moments in (2). By the theorem
of dominated convergence, for any m ≥ 1, again using (2), we have
Z 1 
m
Bn (x)
E
− Ξ(x)
dx → 0.
log n
0
This shows (17). To prove (18), note that, for any k ≥ 1, supx∈[0,1] Bn (x) is larger
than the product of the height of the subtree rooted at the node wk := 1 . . . 1 on level
k and Ξk−1 (1). Let ε > 0. Fix k large enough such that P (Ξk−1 (1) < 1 − ε) < ε.
Conditional on its size, the subtree rooted at wk is a random binary search tree.
Since its size grows linearly in n as n → ∞, it follows from (2) that, for all n
sufficiently large, its height exceeds (c∗ − ε) log n with probability at least 1 − ε.
For these values of n, we have supx∈[0,1] Bn (x) ≥ (c∗ − 6ε) log n with probability at
least 1 − 2ε. As ε was chosen arbitrarily, this shows (18).
For the joint convergence of Bn (x) and Bn (x) for fixed x ∈ [0, 1], we abbreviate
√
Bn := Bn (x), Bn := Bn (x), Ξk := Ξk (x), Ξ = Ξ(x) and B̄n = (Bn − log n)/ log n.
Note that Ξ and Bn are not independent which causes the proof to be more technical. Denote by Nk the time when the node associated with x1 . . . xk is inserted
in the binary search tree. For any ε > 0, we can choose k, L ≥ 1 such that, for all

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

15

n sufficiently large,

P (|Ξk − Ξ| ≥ ε) + P (Nk ≥ L) + P


Bn
− Ξ ≥ ε ≤ ε.
log n

Further, there exists δ > 0 such that P (|Ξk − Ξk−1 | ≤ δ) ≤ ε. Then, for r, y ∈ R
with P (Ξ = y) = 0, and n large enough,



Bn
P B̄n ≤ r,
≤ y ≤ 2ε + P B̄n ≤ r, Ξk ≤ y + 2ε, |Ξk − Ξk−1 | ≥ δ, Nk < L .
log n
Let x̄ = xk+1 xk+2 . . ., (V1 , V2 , . . .) be an independent copy of (U1 , U2 , . . .) and
Bin(n, p) :=

n
X

1{Vi ≤p} ,

n ≥ 0, p ∈ [0, 1].

i=1

Given Ξk , |Ξk − Ξk−1 |, Nk , on Nk
<
n, B̄n is distributed like
√
∗
∗
(x̄))
is distributed like (Bn (x̄)) and
log
n
where
(B
B̄Bin(n−N
(x̄)
+
k/
n
k ,|Ξk −Ξk−1 |)
independent from the remaining quantities. We deduce


Bn
≤y
P B̄n ≤ r,
log n


k
∗
≤ 2ε + P √
+ B̄Bin(n−L,δ) (x̄) ≤ r, Ξk ≤ y + 2ε, |Ξk − Ξk−1 | ≥ δ, Nk < L
log n


k
∗
≤ 3ε + P √
+ B̄Bin(n−L,δ) (x̄) ≤ r P (Ξ ≤ y + 2ε)
log n
Using the asymptotic normality of (B̄n∗ (x̄)) (after rescaling) in (3), taking the limit
superior as n → ∞ and then letting ε tend to zero, we obtain


Bn
≤ y ≤ P (N ≤ r) P (Ξ ≤ y) .
lim sup P B̄n ≤ r,
log n
n→∞
The proof of the converse direction establishing (19) is easier. It runs along the
same lines upon using the trivial bounds |Ξk − Ξk−1 | ≤ 1 and Nk ≥ 0.
Proof of Proposition 1. We start with the characterization of the distribution
of the process. For a deterministic sequence of pairwise different numbers u1 , u2 , . . .
on the unit interval, we define ξk (x) analogously to Ξk (x) in the infinite binary
search tree constructed from this sequence. Here, we abbreviate ξk (x) = 0 if the
node x1 . . . xk is not in the tree. Let n−
m , m ≥ 1, be the subsequence defined by the
+
elements un−
<
u
and
u
,
m
≥
1,
be
the subsequence defined by the elements
1
m
m
−
un+
>
u
.
At
least
one
of
these
sequences
is infinite. For m ≥ 1, let ym
= un−
/u1
1
m
m
−
+
+
and ym = (un+
− u1 )/(1 − u1 ). Next, define ξk (ξk , respectively) analogously to
m
−
+
ξk based on the sequence (ym
) ((ym
), respectively). By construction, for k ≥ 1,
−
+
ξk (x) = 1[0,1/2) (x)u1 ξk−1
(2x) + 1[1/2,1] (x)((1 − u1 )ξk−1
(2x − 1) + u1 ).

Applying the construction to the sequence U1 , U2 , . . . yields
+
Ξk (x) = 1[0,1/2) (x)U1 Ξ−
k−1 (2x) + 1[1/2,1] (x)((1 − U1 )Ξk−1 (2x − 1) + U1 ).
+
−
+
Almost surely, the random sequences ym
and ym
are both infinite and (Ξ−
k ), (Ξk )
are independent copies of (Ξk ). Further, both sequences are independent of U1 .

16

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

Hence, letting k → ∞ in the last display, we obtain (22) on an almost sure level.
The characterization of L(Ξ) by (22) follows from a standard contraction argument,
the argument on page 267 in [12] applies to our setting without any modifications.
We move on to the statements i) – vi) on the marginal distributions of the
process. Here, we use notation that was introduced in the proof of Theorem 3.
By continuity, it suffices to show i) for x ∈ D. Let k ≥ 1. By symmetry, for


1 ≤ i ≤ 2k − 1, we have E Φ(i2−k ) = i2−k . Thus, the assertion follows for x ∈ D
since Φ(x) = Ξ(x). The symmetry statement ii) is reminiscent of the fact that the
uniform distribution on [0, 1] is symmetric around 1/2. More precisely, we apply
the reflection argument from [1] which is at the core of the proof of the second
assertion in (6). Let U1∗ = 1 − U1 , U2∗ = 1 − U2 , . . . and define Ξ∗ analogously
to Ξ in the binary search tree process relying on the sequence U1∗ , U2∗ , . . . Then,
Ξ∗ (t) + Ξ(1 − t) = 1 for all t ∈ [0, 1] which proves ii). With Y = Ξ(ξ), (22) yields
L(Y ) = L(U Y + 1A (1 − U )),
where 1A , U, Y are independent and P (A) = 1/2. From [5], it follows that Y
has the arcsine distribution, proving iii). We move on to the statements about
the distribution of Ξ(t). Let t ∈ (0, 1/2). Since Ξ is strictly increasing, we have
Ξ(2t) ∈ (0, 1) almost surely. By (22), L(Ξ(t)) = L(U Ξ(2t)) with conditions as
in (22). Therefore, L(Ξ(t)) admits a density. By symmetry, the same is true for
t ∈ (1/2, 1). For t ∈ (0, 1/2), by conditioning on the value of U , one finds the
density


1[x,1] (Ξ(2t))
(27)
, x ∈ (0, 1].
ft (x) = E
Ξ(2t)
ft (x) is monotonically decreasing and continuous on (0, 1] with f (1) = 0. For
t ∈ (1/2, 1), ft (x) = f1−t (1 − x), x ∈ (0, 1) is a density of L(Ξ(t)) by ii). By (27),
for t ∈ (0, 1/2), x ∈ (0, 1),
Z 1
f2t (y)
dy, or xft0 (x) = −f2t (x).
(28)
ft (x) =
y
x
Upon setting f0 = f1 = 0, the last identity also holds for t = 0 and t = 1/2
since f1/2 = 1[0,1] is a density of L(Ξ(1/2)). Thus, for any t ∈ (0, 1), ft is smooth
on (0, 1). Since the uniform distribution takes values arbitrarily close to one, it
follows that, for all δ > 0, t ∈ (0, 1), we have P (Ξ(t) > 1 − δ) > 0. Hence, for
all t ∈ (0, 1), the density ft is strictly positive on (0, 1). Thus, for t ∈ (0, 1/2),
ft is strictly monotonically decreasing. Summarizing, we have shown iv) and v).
(0)
For t ∈ (0, 1/4], the assertion αt = ∞ in vi) follows immediately from (28) since
(0)
(0)
α2t > 0. Let 1/4 < t < 1/2. Assume α1−2(1−2t) < ∞. Then, f2(1−2t) (1) < ∞.
0
0
(0) is finite. Thus, f2t (y)/y
By (28), it follows that f1−2t
(1) is finite and hence f2t
(0)
is bounded in a neighhourhood of zero and αt < ∞. For t > 3/8, we have
(0)
(0)
1 − 2(1 − 2t) > 1/2, thus, αt < ∞. Iterating this argument leads to αt < ∞
for all 1/3 < t < 1/2. In order to proceed further, note that, for t > 1/4, there
Qk
exists k ∈ N, such that, in probability, Ξ(t) ≥ Z := U1 (U2 + (1 − U2 ) `=1 U2+` ).

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

Z admits a density fZ given by
Z 1
fZ (x) = 1 +
r(y)dy − xr(x),
x

1
r(x) = 2
x

Z

x

P
0

k
Y
`=1

U2+`

x−v
≤
1−v

17

!
dv.

Thus,
Z
x↓0

(0)

It follows that αt

≤ 1+

1

r(y)dy < ∞.

lim fZ (x) = 1 +
0

R1
0

r(x)dx < ∞. Since Ξ is increasing, the function

(0)
αt

(0)

t 7→
is decreasing. Thus, by monotonicity and continuity, it follows αt ↑ ∞
(0)
(0)
as t ↓ 1/4. For t ≤ 1/4, αt = ∞ follows immediately from (28) since α2t < ∞.
(1)
For 1/4 < t < 1/2, the remaining statements about αt are direct corollaries of
(0)
(1)
(0)
the results for αt since αt = α1−2(1−2t) . This finishes the proof of vi).
The curvature. We make a concluding remark about the curvature of ft , t ∈
00
0
(x) − ft0 (x), for 0 < t ≤ 1/4, the function ft is
(0, 1/2). First, since xft (x) = −f2t
00
00
convex. From (28) it is easy to deduce f1/3 (x) = 2(1−x). Since f1/3
= f1/2
= 0, it is
plausible to conjecture that ft is convex for t ≤ 1/3 and concave for 1/3 ≤ t < 1/2.
Concavity at rational points with small denominator such as t = 3/8 or t = 5/12
can be verified by hand using (28).
4.3. Weighted path length and Wiener index. In order to obtain mean and
variance for the weighted path length and the weighted Wiener index, we use the
reflection argument from the proof of Proposition 1 ii). To this end, let Pn∗ and
Wn∗ denote weighted path length and weighted Wiener index in the binary search
tree built from the sequence U1∗ = 1 − U1 , U2∗ = 1 − U2 , . . . Then, Pn + Pn∗ = Pn + n

and Wn + Wn∗ = Wn + n2 providing the claimed expansions for E [Pn ] and E [Wn ]
upon recalling (7) and (8).
For a finite rooted labelled binary tree T , denote by p(T ) its path length, by
p(T ) its weighted path length, by w(T ) its Wiener index and by w(T ) its weighted
Wiener index. Let T1 , T2 be its left and right subtree and x the label of the root.
Then, denoting by |T | the size of T , for |T | ≥ 1,
(29)
p(T ) = p(T1 ) + p(T2 ) + |T | − 1,
(30)
w(T ) = w(T1 ) + w(T2 ) + (|T2 | + 1)p(T1 ) + (|T1 | + 1)p(T2 ) + |T | + 2|T1 ||T2 | − 1.
The first statement is obvious, the argument for the second can be found in [25].
For the weighted quantities, one obtains
(31)
p(T ) = p(T1 ) + p(T2 ) + |T |x,
(32)
w(T ) = w(T1 ) + w(T2 ) + (|T2 | + 1)p(T1 ) + (|T1 | + 1)p(T2 ) + (|T | + |T1 ||T2 |)x.
Again, the first assertion is easy to see and we only justify the second. The terms
w(T1 ) and w(T2 ) account for weighted distances within the subtrees. The sum

18

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

of all weighted distances between nodes in the left subtree and the root equals
p(T1 )+|T1 |x. Replacing T1 by T2 , we obtain the analogous sum in the right subtree.
The sum of all distances between nodes in different subtrees equals |T1 |p(T2 ) +
|T2 |p(T1 ) + |T1 ||T2 |x. Finally, we need to add x for the weighted distance of the
root to itself. Adding up the terms and simplifying leads to (32). For α, β > 0
let αT + β be the tree obtained from T where each label y is replaced by αy + β.
Obviously, p(T ) = p(αT + β) with the analogous identity for the Wiener index. For
the weighted quantities, we have

(33)

p(αT + β) = αp(T ) + (p(T ) + |T |)β,

(34)

w(αT + β) = αw(T ) + (w(T ) + |T |(|T | + 1)/2)β.

Let T be the binary search tree of size n in the i.i.d. model. Then, given In :=
1
U
rank(U1 ), U := U1 , in distribution, the trees U1 T1 and 1−U
T2 − 1−U
are independent
binary search trees of size In −1 and n−In , constructed from independent sequences
of uniformly distributed random variables on [0, 1]. Thus, combining (29)–(34), for
the vector Yn = (Wn , Wn , Pn , Pn )T , we have


U
0
(n + 1 − In )U
0
1
0
n + 1 − In 
d  0
 YIn −1
Yn = 
 0

0
U
0
0
0
0
1


1−U
U
In (1 − U )
In U

0
1
0
In 
0
 Yn−I
+
n


0
0
1−U
U
0
0
0
1


(2n + (n − In )(3In + n − 2))U/2


n − 1 + 2(In − 1)(n − In )
,
+


(2n − In )U
n−1


where (Yn0 ), (Yn ), (In , U ) are independent and (Yn0 ) is distributed like (Yn ). Here,
d

= indicates that left- and righthand side are identically distributed.

We consider the sequence (Zn )n≥0 defined by


Zn :=

Wn − E[Wn ] Wn − E[Wn ] Pn − E[Pn ] Pn − E[Pn ]
,
,
,
n2
n2
n
n

T
,

n ≥ 1,

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

19

and Z0 = 0. Let αn = E [Wn ] , βn = E [Wn ] , γn = E [Pn ] and δn = E [Pn ]. Further,
let




In −1 2
U
0
1 − Inn−1 Inn−1 U
0
n




In −1 2

(n)
0
0
1 − Inn−1 Inn−1  ,
n
A1 = 

In −1


0
0
0
n U
In −1
0
0
0
n





In 2
In 2
In
In
In
1 − n (1 − U )
1− n U
1 − n (1 − U )
1 − Inn U
n
n
2


In
In

(n)
0
0
1 − Inn
n 1 − n
A2 = 


0
0
1 − Inn (1 − U )
1 − Inn U
0
0
0
1 − Inn
(n)

(n)

(n)

(n)

and C (n) = (C1 , C2 , C3 , C4 )T with
(n)

C1

(n)

C2

(n)

C3

(n)

C4

U
1−U
U
(n + 1 − In )
αIn −1 +
αn−In + 2 βn−In + U
γIn −1
2
2
n
n
n
n2
In
In
2n + (n − In )(3In + n − 2)
1
+ (1 − U ) 2 γn−In + U 2 δn−In + U
− 2 αn ,
2
n
n
2n
n

1
In − 1 1
In
1
δIn −1 + 2 δn−In
= 2 βIn −1 + 2 βn−In + 1 −
n
n
n
n
n
n − 1 + 2(n − 1)(n − In )
1
+
− 2 βn ,
n2
n


U
1−U
U
In
1
= γIn −1 +
γn−In + δn−In + 2 −
U − γn ,
n
n
n
n
n
1
1
1
1
= δIn −1 + δn−In + 1 − − δn .
n
n
n n
=

Then, from the recurrence for (Yn ), it follows
d

(n)

(n)

0
Zn = A1 ZIn −1 + A2 Zn−I
+ C (n) ,
n

n ≥ 1,

where (Zn ), (Zn0 ), (In , U ) are independent and (Zn0 ) is distributed like (Zn ). We
prove convergence of Zn in distribution by an application of the contraction method.
To this end, note that In /n → U almost surely by the strong law of large numbers.
Thus, with convergence in L2 and almost surely,
U3
0
2
 0
U
→ A1 := 
 0
0
0
0

(1 − U )3

0
→ A2 := 

0
0


(n)

A1

(n)

A2


U 2 (1 − U )
0
0
U (1 − U ) 
,

U2
0
0
U
U (1 − U )2
(1 − U )2
0
0

U (1 − U )2
0
(1 − U )2
0


U 2 (1 − U )
U (1 − U ) 
,
U (1 − U ) 
1−U




,


20

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

and

U 2 log U + (1 − U 2 ) log (1 − U ) + U (−14U 2 + 9U + 5)/4


2U log U + 2(1 − U ) log(1 − U ) + 6U (1 − U )
.
→ C := 
2
2


U ln U + (1 − U ) ln(1 − U ) + U
2U ln U + 2(1 − U ) ln (1 − U ) + 1


C (n)

For a quadratic matrix A, denote by kAkop its spectral radius. By calculating the
eigenvalues of A1 AT1 and A2 AT2 , one checks that kA1 kop = U and kA2 kop = 1 − U .
Thus,








E kA1 AT1 kop + E kA2 AT2 kop ≤ E kA1 k2op + E kA2 k2op < 1.
Moreover, we have P (In ∈ {1, . . . , `} ∪ {n}) → 0 for all fixed `. Thus, by Theorem
4.1 in [24], in distribution and with convergence of the first two moments, we have
Zn → (W, W, P, P ) where L(W, W, P, P ) is the unique fixed-point of the map:
(35)

T : M42 (0) −→ M42 (0),

T (µ) = L (A1 Z + A2 Z 0 + C) ,

with A1 , A2 , C defined above, where Z, Z 0 , U are independent and L(Z) = L(Z 0 ) =
µ. Here, M42 (0) denotes the set of probability measures on R4 with finite absolute
second moment and zero mean. Variances and covariances can be computed succes 
sively using the fixed-point equation, e.g. in the following order: E P 2 , E [P W ],
 2
 2
 2
E W , E [P P] , E P , E [PW ] , E [P W] , E [W W], E [PW] , E W . Additionally to the variances given in the theorem, one obtains
(36)
(37)
(38)

21 − 2π 2 2
n ,
6
10 − π 2 3
Cov(Pn , Wn ) ∼
n ,
3
10 − π 2 4
Cov(Wn , Wn ) ∼
n ,
3
Cov(Pn , Pn ) ∼

20 − 2π 2 3
n ,
3
10 − π 2 3
Cov(Pn , Wn ) ∼
n ,
3
481 − 48π 2 3
Cov(Pn , Wn ) ∼
n .
288
Cov(Pn , Wn ) ∼

Acknowledgements
The first author is grateful to the King Saud University, Deanship of Scientific
Research, College of Science Research Center. The research of the third author
was supported by a Feodor Lynen Fellowship of the Alexander von HumboldtFoundation.
References
[1] Rafik Aguech, Nabil Lasmar, and Hosam Mahmoud, Extremal weighted path lengths in random binary search trees, Probab. Engrg. Inform. Sci., 21(1), 133–141 (2007)
[2] Patrick Billingsley, Convergence of probability measures, Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons, Inc., New York (1999)
[3] Nicolas Broutin and Luc Devroye, Large deviations for the weighted height of an extended
class of trees, Algorithmica, 46(3-4), 271–297 (2006)
[4] Gerald G. Brown and Bruno O. Shubert, On random binary trees, Math. Oper. Res., 9(1),
43–65 (1984)
[5] Robert Chen, Elsa Lin and Alan Zame, Another arc sine law, Sankhyā Ser. A, 43(3), 371–373
(1981)

ON WEIGHTED DEPTHS IN RANDOM BINARY SEARCH TREES

21

[6] Luc Devroye, A note on the height of binary search trees, J. Assoc. Comput. Mach., 33(3),
489–498 (1986)
[7] Luc Devroye, Applications of the theory of records in the study of random trees, Acta Inform.,
26(1-2), 123–1301 (1988)
[8] Luc Devroye, Limit laws for local counters in random binary search trees, Random Structures
Algorithms, 2(3), 303–315 (1991)
[9] Luc Devroye and Ralph Neininger, Distances and finger search in random binary search trees,
SIAM J. Comput., 33(3), 647–658 (2004)
[10] Karl Dickman, On the frequency of numbers containing prime factors of a certain relative
magnitude, Arkiv för Mathematik, Astronomi och Fysik, 22A(10), 1–14 (1930)
[11] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz, Asymptotic minimax character of the
sample distribution function and of the classical multinomial estimator, Ann. Math. Statist., 27,
642–669 (1956)
[12] Rudolf Grübel and Uwe Rösler, Asymptotic distribution theory for Hoare’s selection algorithm, Adv. in Appl. Probab., 28(1), 252–269 (1996)
[13] Rudolf Grübel, On the silhouette of binary search trees, Ann. Appl. Probab., 19(5), 1781–1802
(2009)
[14] Rudolf Grübel and Nikolče Stefanoski, Mixed Poisson approximation of node depth distributions in random binary search trees, Ann. Appl. Probab., 15(1A), 279–297 (2005)
[15] Adolf Hildebrand and Gérald Tenenbaum, Integers without large prime factors, J. Théor.
Nombres Bordeaux, 5(2), 411–484 (1993)
[16] C. A. R. Hoare, Quicksort, Comput. J., 5, 10–15 (1962)
[17] Hsien-Kuei Hwang and Tsung-Hsi Tsai, Quickselect and the Dickman function, Combin.
Probab. Comput., 11(4), 353–371 (2002)
[18] Donald. E. Knuth, The Art of Computer Programming: Sorting and Searching, volume 3,
Addison-Wesley, Reading, MA (1973)
[19] Markus Kuba and Alois Panholzer, On weighted path lengths and distances in increasing
trees, Probab. Engrg. Inform. Sci., 21(3), 419–433 (2007)
[20] Markus Kuba and Alois Panholzer, On edge-weighted recursive trees and inversions in random
permutations, Discrete Math., 308(4), 529–540 (2008)
[21] Hosam M. Mahmoud, Evolution of random search trees, Wiley-Interscience Series in Discrete
Mathematics and Optimization. John Wiley & Sons, Inc., New York (1992)
[22] Hosam M. Mahmoud and Ralph Neininger, Distribution of distances in random binary search
trees, Ann. Appl. Probab., 13(1), 253–276 (2003)
[23] Hosam M. Mahmoud and Boris Pittel, On the most probable shape of a search tree grown
from a random permutation, SIAM J. Algebraic Discrete Methods, 5(1), 69–81 (1984)
[24] Ralph Neininger, On a multivariate contraction method for random recursive structures with
applications to Quicksort, Random Structures Algorithms, 19(3-4), 498–524 (2001) Analysis of
algorithms (Krynica Morska, 2000).
[25] Ralph Neininger, The Wiener index of random trees, Combin. Probab. Comput., 11 (6),
587–597 (2002)
[26] Alois Panholzer and Helmut Prodinger, Spanning tree size in random binary search trees.
Ann. Appl. Probab., 14(2), 718–733 (2004)
[27] Mireille Régnier, A limiting distribution for quicksort, RAIRO Inform. Théor. Appl., 23(3),
335–343 (1989)
[28] Uwe Rösler, A limit theorem for “Quicksort”, RAIRO Inform. Théor. Appl., 25, 85–100 (1991)
[29] Ludger Rüschendorf and Eva-Maria Schopp, Note on the weighted internal path length of
b-ary trees., Discrete Math. Theor. Comput. Sci., 9(1), 1–6 (2007)

22

RAFIK AGUECH, ANIS AMRI, AND HENNING SULZBACH

Rafik Aguech, Department of Statistic and Operation Research, College of Sciences, King Saud University, P.O. Box 2455, Riyadh 11451, Saudi Arabia
E-mail address: rafik.aguech@ksu.edu.sa
Anis Amri, University of Monastir, Avenue Taher Hadded B.P 56, Monastir 5000,
Tunisia
E-mail address: anis.amri@hotmail.com
Henning Sulzbach, McGill University, 3480 University Street, H3A 0E9 Montreal,
QC, Canada
E-mail address: henning.sulzbach@gmail.com
Current address: School of Mathematics, University of Birmingham, Birmingham B15 2TT,
Great Britain

