# Normal Limiting Distribution of the Size of Binary Interval Trees

Authors: Jie Liu; Yang Yang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The limiting distribution of the size of binary interval tree is investigated. Our illustration is based on the contraction method, and it is quite different from the case in one-sided binary interval tree. First, we build a distributional recursive equation of the size. Then, we draw the expectation, the variance, and some high order moments. Finally, it is shown that the size (with suitable standardization) approaches  the standard normal random variable in the Zolotarev metric space.


---

## Body

## 1. Introduction

Random trees are usually generated based on combinatorics and occur also in the context of algorithms from computer science. There are many kinds of random trees with different structures, such as recursive trees, search trees, binary trees, and interval trees. The asymptotic probability behavior of random variables in random trees has attracted more scholars’ attention and has become a popular research area. Drmota [1] introduced some labelled and unlabelled random trees in his book. Devroye and Janson [2] studied the protected nodes in several random trees. Feng and Hu [3] researched the phase changes of scale-free trees. The limiting law for the height, size, and subtree of binary search trees was also considered (see [4–6]). There were also some researchers investigating the Zagreb index and nodes of random recursive trees (see [7–9]).Binary interval tree is a random structure that underlies the process of random division of a line interval and parking problems. It has recently been a popular subject. Sibuya and Itoh [10] showed that the number of internal and external nodes in different levels of binary internal tree is asymptotically normal, from which the asymptotic normality of the size of the tree could not be achieved directly. Prodinger [11] looked into various parameters of the incomplete trie, a one-sided version of a random tree with a digital flavor. Fill et al. [12] followed with a study of the nonexistence of limit distribution for the height of the incomplete trie. Itoh and Mahmoud [13] considered five incomplete one-sided variants of binary interval trees and proved that their sizes all approach some normal random variables. Janson [14] drew the same result for a larger scale of one-sided interval trees by the renewal theory, and one kind of fragmentation trees was discussed by Janson and Neininger [15]. Javanian et al. [16] investigated the paths in m-ary interval trees. Su et al. [17] studied the complete binary interval trees and got the Law of Large Numbers. In addition, Pan et al. [18] considered the construction algorithm about binary interval trees.The binary interval tree is a tree associated with repeated divisions of a line interval of lengthx. The process of divisions is as follows. If x
<
1, there is no division in effect; the associated interval tree consists only of one terminal node. Supposing that x
≥
1, we begin with the interval (
0
,
x
). Divide the interval (
0
,
x
) into two subintervals by choosing U
x, a point uniformly distributed over the interval (
0
,
x
). Then, we get two intervals, (
0
,
U
x
) and (
U
x
,
x
). Each of the two subintervals is further divided at a uniform point of its length, and two smaller subintervals are got as before. If the length of the subinterval is less than 1, we stop the division. Repeat this process until the length of every interval (or subinterval) is less than 1.We takex
=
4, for instance. Figures 1(a) and 1(b) show how the above random division process of interval generates a binary interval tree.Figure 1
(a) The division process. (b) The binary interval tree.
(a)
(b)If some different conditions are added and those intervals satisfying the conditions are not allowed to be divided (see [13, 14]), then we can get different incomplete interval trees. In particular, if we only divide one subinterval of every interval, then the interval tree we get is the so-called one-sided interval tree (see [13]).It is obvious that interval tree could embody many properties of random division, so it can elicit lots of valuable subjects related to probability. For example, forx
>
0, the height of the interval tree is the greatest level of all subintervals after the divisions, denoted by H
x; the total number of nodes of an interval tree is the total number of intervals that were got from the random division process, and so on. Let S
x be the size of the interval trees, that is, the total number of nodes of the binary interval trees. Our intention is to investigate the random variable S
x, the size of binary interval trees.In this paper, the central limit theorem of the size of binary interval trees is investigated. In view of the difficulty to calculate the moment generating function ofS
x, the method we used is completely different from that in the case of one-sided interval trees. In Section 2, we build a distributional recursive equation of S
x and give the expectation, the variance, and some high order moments of S
x. In Section 3, via the contraction method, the limit law of S
x is shown to approach the unique solution of a fixed-point distributional equation in the Zolotarev metric space. Finally, we demonstrate that S
x, with suitable standardization, converges to a normal limiting random variable, as x
→
∞.


## 2. The Moments ofS
x

Compared with the one-sided interval trees, the properties of binary interval trees are much more complex. There are a lot of difficulties when it comes to obtaining the moment generating function ofS
x. Therefore, the method used in the case of one-sided interval trees (see [13]) is no longer applicable. Here, we build a distributional recursive equation of S
x. We can calculate the expectation and the variance of S
x. Furthermore, we find that the order of the fourth central moment of S
x is O
(
x
2
) as x goes to infinity.From the definition of binary interval tree, it is easy to see thatS
1
=
3 and S
x
=
1, for x
<
1. For our purpose to investigate the case of x
≥
1, let U
x denote the point chosen uniformly from interval (
0
,
x
); hence, U
x
~
U
(
0
,
x
). For any fixed real number 0
<
u
<
x, if U
x
=
u, we denote S
u
(
1
) to be the size of the left subtree associated with the interval (
0
,
u
). Correspondingly, S
x
-
u
(
2
) denotes the size of the right subtree associated with the interval (
u
,
x
). According to the rule of division, we can see that S
u
(
1
) and S
x
-
u
(
2
) are mutually independent. Thus, we have (1)
S
x
U
=
u
=
d
1
+
S
u
1
+
S
x
-
u
2
,
∀
0
<
u
<
x
. This formula implies that if U
x
=
u is given, S
x has the same distribution as 1
+
S
u
(
1
)
+
S
x
-
u
(
2
). Obviously, we can rewrite the above formula as(2)
S
x
=
d
1
+
S
U
x
1
+
S
x
-
U
x
2
.Define (3)
m
1
x
≔
E
S
x
;
m
2
x
≔
E
S
x
2
. It is easy to see that (4)
m
1
1
=
E
S
1
=
3
;
m
2
1
=
9
;
m
1
x
=
m
2
x
=
1
,
0
<
x
<
1
.From the distributional recursive equation (2) and the above boundary conditions, Su et al. [17] calculated the expectation E
S
x and the variance Var
⁡
S
x, for any x
≥
0.Lemma 1.
LetS
x be the size of a binary interval tree. Then(5)
E
S
x
=
m
1
x
=
4
x
-
1
,
x
≥
1
.Lemma 2.
LetS
x be the size of a binary interval tree. Then(6)
Var
⁡
S
x
=
32
x
ln
⁡
x
-
16
x
2
+
8
x
+
8
,
1
≤
x
≤
2
,
32
ln
⁡
2
-
20
x
,
x
≥
2
.In order to prove that the asymptotic distribution ofS
x is normal, we also need the order of E
(
S
x
-
E
S
x
)
4 as x
→
∞. The following proposition shows the fourth central moment of S
x.Proposition 3.
LetS
x be the size of a binary interval tree. Then (7)
E
S
x
-
E
S
x
4
=
O
x
2
,
x
⟶
∞
.Proof.
See the appendix.


## 3. The CLT forS
x

In this section, we will prove the asymptotic normality ofS
x as x
→
∞. The main method is the contraction method and some metrics are needed especially the Zolotarev metrics (see [19]).First we introduce the Zolotarev metrics. Denote the distribution of the random variableX by L
(
X
). Let D be the set of the distributions of all real random variables, and define (8)
D
∗
=
F
:
F
∈
D
,
∫
R
x
d
F
x
=
0
,
∫
R
x
2
d
F
x
=
1
,
∫
R
x
3
d
F
x
<
∞
.It can be verified that random variableZ with L
(
Z
)
=
N
(
0
,
σ
2
) satisfies the following formula. For any u
∈
[
0,1
], (9)
Z
=
d
Z
u
+
Z
¯
1
-
u
, and more generally, we have the following lemma.Lemma 4.
IfZ and Z
¯ are standard normal random variables, U is uniformly distributed over interval [
0,1
], and (
U
,
Z
,
Z
¯
) are mutually independent and then one has(10)
Z
=
d
Z
U
+
Z
¯
1
-
U
.Proof.
In fact, for anyu
∈
[
0,1
], we have (11)
E
exp
⁡
i
t
u
Z
+
1
-
u
Z
¯
=
E
exp
⁡
i
t
u
Z
+
1
-
u
Z
¯
=
E
e
i
t
u
Z
E
e
i
t
1
-
u
Z
¯
=
exp
⁡
-
u
t
2
2
exp
⁡
-
1
-
u
t
2
2
=
exp
⁡
-
t
2
2
. Therefore, (12)
E
exp
⁡
i
t
U
Z
+
1
-
U
Z
¯
=
∫
0
1
E
exp
⁡
i
t
u
Z
+
1
-
u
Z
¯
d
u
=
∫
0
1
exp
⁡
-
t
2
2
d
u
=
exp
⁡
-
t
2
2
. But, we can find that, in the set D
∗, there is only one distribution, the standard normal N
(
0,1
), satisfying (10).Suppose thatm is a nonnegative integer. Denote F
(
m
) by the set of all real functions that are m times continuous and differentiable, defined on the real line. Let (13)
F
α
m
≔
f
:
f
∈
F
m
,
f
m
x
-
f
m
y
≤
x
-
y
α
, where 0
<
α
≤
1 is a fixed real number. Let s
=
m
+
α and(14)
ζ
s
X
,
Y
≔
ζ
s
L
X
,
L
Y
=
sup
⁡
E
f
X
-
E
f
Y
:
f
∈
F
α
m
,and then ζ
s is the Zolotarev metrics with order s on the set D. According to the properties of the Zolotarev metric, we know(15)
ζ
s
X
,
Y
<
∞
⟺
E
X
s
+
E
Y
s
<
∞
,
E
X
k
=
E
Y
k
,
k
=
1
,
…
,
m
. Therefore, we can choose ζ
3 as the metric we need on the subset D
∗ (see [20, 21]); that is, m
=
2,  α
=
1. This is due to the fact that, for any L
(
X
)
∈
D
∗ and L
(
Y
)
∉
D
∗, we have ζ
3
(
X
,
Y
)
=
∞, but if L
(
X
)
,
L
(
Y
)
∈
D
∗, then ζ
3
(
X
,
Y
)
<
∞.The metricζ
s
(
X
,
Y
) has several properties as follows (see [20]):(1)
For any constantc
>
0,(16)
ζ
s
c
X
,
c
Y
=
c
s
ζ
s
X
,
Y
;
(2)
if random variablesY and (
X
1
,
X
2
) are mutually independent, then(17)
ζ
s
X
1
+
Y
,
X
2
+
Y
≤
ζ
s
X
1
,
X
2
;
(3)
for random variablesX and {
X
n
,
n
=
1,2
,
3
,
…
},(18)
ζ
s
X
n
,
X
⟶
0
⟹
X
n
→
d
X
.Now, we begin to prove the main result in this paper.Theorem 5.
LetS
x be the size of a binary interval tree. Then, as x
→
∞, (19)
S
x
-
E
S
x
Var
⁡
S
x
⟶
d
N
0,1
.Proof.
Denote(20)
S
x
∗
≔
S
x
-
4
x
-
1
32
ln
⁡
2
-
20
x
,
x
>
0
,
h
x
≔
32
x
ln
⁡
x
-
16
x
2
+
8
x
+
8
32
ln
⁡
2
-
20
x
,
x
>
0
. Then from Lemmas 1 and 2, we know that(21)
S
x
∗
=
S
x
-
E
S
x
Var
⁡
S
x
,
x
≥
2
,
S
x
-
E
S
x
Var
⁡
S
x
·
h
x
,
1
≤
x
<
2
,
2
-
4
x
32
ln
⁡
2
-
20
x
,
0
<
x
<
1
.So, we have L
(
S
x
∗
)
∈
D
∗ for x
≥
2 and L
(
S
x
∗
)
∉
D
∗ for 0
<
x
<
2.
According to the correlative inequality in [21], for any L
(
X
)
∈
D
∗
,
L
(
Y
)
∈
D
∗, (22)
ζ
3
X
,
Y
≤
Γ
2
Γ
4
∫
R
t
3
d
P
X
<
t
-
P
Y
<
t
, where Γ is the gamma function. Assume that the distribution of random variable Z is N
(
0,1
). It follows from Proposition 3 that(23)
sup
x
≥
4
⁡
E
S
x
∗
4
<
∞
. Therefore, there exists a constant C
>
0 such that(24)
sup
x
≥
4
⁡
ζ
3
S
x
∗
,
Z
≤
C
sup
x
≥
4
⁡
E
S
x
∗
3
+
E
Z
3
<
∞
.Denote(25)
a
x
≔
ζ
3
L
S
x
∗
,
Φ
=
ζ
3
S
x
∗
,
Z
,where Φ is standard normal distribution and Z is standard normal random variable; then we can see that(26)
0
≤
b
≔
limsup
x
→
∞
⁡
a
x
<
∞
.Now, we just need to prove that b
=
0; then the theorem follows.
Suppose thatx
≥
4; by (A.1) and (21), we have (27)
S
x
∗
U
x
=
t
=
S
x
-
4
x
-
1
32
ln
⁡
2
-
20
x
U
x
=
t
=
d
S
t
1
-
E
S
t
1
32
ln
⁡
2
-
20
x
+
S
x
-
t
2
-
E
S
x
-
t
2
32
ln
⁡
2
-
20
x
,
2
≤
t
≤
x
-
2
,
S
t
1
-
E
S
t
1
32
ln
⁡
2
-
20
x
+
S
x
-
t
2
-
E
S
x
-
t
2
32
ln
⁡
2
-
20
x
,
1
≤
t
<
2
,
S
t
1
-
E
S
t
1
32
ln
⁡
2
-
20
x
+
S
x
-
t
2
-
E
S
x
-
t
2
32
ln
⁡
2
-
20
x
,
x
-
2
<
t
≤
x
-
1
,
S
x
-
t
2
-
E
S
x
-
t
2
-
4
t
-
2
32
ln
⁡
2
-
20
x
,
0
<
t
<
1
S
t
1
-
E
S
t
1
-
4
x
-
t
-
2
32
ln
⁡
2
-
20
x
,
x
-
1
<
t
<
x
=
d
S
t
∗
t
x
+
S
~
x
-
t
∗
x
-
t
x
,
2
≤
t
≤
x
-
2
;
S
t
∗
h
t
t
x
+
S
~
x
-
t
∗
x
-
t
x
,
1
≤
t
<
2
,
S
t
∗
t
x
+
S
~
x
-
t
∗
h
x
-
t
x
-
t
x
,
x
-
2
<
t
≤
x
-
1
,
S
~
x
-
t
∗
x
-
t
x
-
4
t
-
2
32
ln
⁡
2
-
20
x
,
0
<
t
<
1
;
S
t
∗
t
x
-
4
x
-
t
-
2
32
ln
⁡
2
-
20
x
,
x
-
1
<
t
<
x
, where U
x
=
t is the first point chosen from interval (
0
,
x
) and {
S
~
x
∗
,
x
>
0
} is an independent copy of {
S
x
∗
,
x
>
0
}.
If we denoteU
≔
U
x
/
x, then U
~
U
(
0,1
) and we can rewrite the above formula as(28)
S
x
∗
U
=
u
=
S
x
-
4
x
-
1
32
ln
⁡
2
-
20
x
U
=
u
(29)
=
d
S
u
x
∗
u
+
S
~
1
-
u
x
∗
1
-
u
,
2
x
≤
u
≤
1
-
2
x
;
S
u
x
∗
h
u
x
u
+
S
~
1
-
u
x
∗
1
-
u
,
1
x
≤
u
<
2
x
,
S
u
x
∗
u
+
S
~
1
-
u
x
∗
h
1
-
u
x
1
-
u
,
1
-
2
x
<
u
≤
1
-
1
x
,
S
~
1
-
u
x
∗
1
-
u
-
4
u
x
-
2
32
ln
⁡
2
-
20
x
,
0
<
u
<
1
x
;
S
u
x
∗
u
-
4
1
-
u
x
-
2
32
ln
⁡
2
-
20
x
,
1
-
1
x
<
u
<
1
.
According to the definition ofD
∗ and ζ
3, it could be found that S
x
∗
∣
U
x
=
t
∈
D
∗ for 2
<
t
<
x
-
2 and S
x
∗
∈
D
∗. If we define S
x
′
≔
S
x
∗
∣
U
x
<
2
o
r
U
x
>
x
-
2, then we can also see that S
x
′
∈
D
∗. Furthermore, E
(
(
S
x
′
)
4
)
≤
C
1 for some positive constant C
1 by conditioning on U
x and using the similar calculation in the appendix. Hence,(30)
ζ
3
S
x
′
,
Z
≤
β
, for some positive constant β.
As we had pointed out before, the standard normal distribution is the only distribution satisfying (10) in the set D
∗. From (25), (14), and Lemma 4, for x
>
4, we have (31)
a
x
=
ζ
3
S
x
∗
,
Z
≤
ζ
3
S
x
′
,
Z
·
4
x
+
∫
2
/
x
1
-
2
/
x
ζ
3
S
x
∗
∣
U
=
u
,
Z
d
u
≤
4
β
x
+
∫
2
/
x
1
-
2
/
x
ζ
3
S
x
u
∗
u
+
S
¯
x
1
-
u
∗
1
-
u
,
Z
u
+
Z
¯
1
-
u
d
u
By
15
and
29
≤
4
β
x
+
∫
2
/
x
1
-
2
/
x
ζ
3
S
x
u
∗
u
+
S
¯
x
1
-
u
∗
1
-
u
,
Z
u
+
S
¯
x
1
-
u
∗
1
-
u
d
u
+
∫
2
/
x
1
-
2
/
x
ζ
3
Z
u
+
S
¯
x
1
-
u
∗
1
-
u
,
Z
u
+
Z
¯
1
-
u
d
u
≤
4
β
x
+
∫
2
/
x
1
-
2
/
x
ζ
3
S
x
u
∗
u
,
Z
u
d
u
+
∫
2
/
x
1
-
2
/
x
ζ
3
S
¯
x
1
-
u
∗
1
-
u
,
Z
¯
1
-
u
d
u
=
4
β
x
+
2
∫
2
/
x
1
-
2
/
x
ζ
3
S
x
u
∗
u
,
Z
u
d
u
=
4
β
x
+
2
∫
2
/
x
1
-
2
/
x
u
3
/
2
ζ
3
S
x
u
∗
,
Z
d
u
=
4
β
x
+
2
∫
2
/
x
1
-
2
/
x
u
3
/
2
a
x
u
d
u
. Given ε
>
0, let δ
>
0 be small enough such that β
δ
5
/
2
<
ε
/
8. For any fixed δ
>
0, when x is sufficiently large, then (32)
4
β
x
<
ε
10
,
2
x
<
δ
,
sup
δ
≤
u
≤
1
⁡
a
x
u
<
b
+
ε
. Thus, (33)
2
∫
2
/
x
δ
u
3
/
2
a
x
u
d
u
≤
2
β
∫
2
/
x
δ
u
3
/
2
d
u
≤
2
β
∫
0
δ
u
3
/
2
d
u
=
4
β
δ
5
/
2
5
<
ε
10
;
2
∫
δ
1
-
2
/
x
u
3
/
2
a
x
u
d
u
≤
2
b
+
ε
∫
δ
1
-
2
/
x
u
3
/
2
d
u
≤
2
b
+
ε
∫
0
1
u
3
/
2
d
u
<
4
b
+
ε
5
, where β is the constant as before and x is sufficiently large. It implies that (34)
a
x
≤
4
β
x
+
2
∫
2
/
x
δ
u
3
/
2
a
x
u
d
u
+
2
∫
δ
1
-
2
/
x
u
3
/
2
a
x
u
d
u
<
ε
10
+
ε
10
+
4
b
+
ε
5
<
4
b
5
+
ε
, when x is sufficiently large. Therefore, (35)
b
≔
limsup
x
→
∞
⁡
a
x
≤
4
b
5
+
ε
. From this equation and the arbitrariness of ε
>
0, we can conclude b
=
0 and (36)
lim
x
→
∞
⁡
ζ
3
S
x
∗
,
Z
=
lim
x
→
∞
⁡
a
x
=
0 immediately. By (18), the theorem holds.



---

*Source: 756548-2015-10-12.xml*