Generating Uniform Spanning Trees from conditioned Bienaymé-Galton-Watson trees

Universitat Polit`ecnica de Catalunya Facultat de Matem`atiques i Estad´ıstica Degree in Mathematics Bachelor’s Degree Thesis Generating Uniform Spanning Trees from conditioned Bienaym´e-Galton-Watson trees Albert Vives Supervised by Oriol Serra January 2025 I would like to express my heartfelt gratitude to my supervisor, Oriol Serra. Thank you so much for guiding me through these past months and for giving me the incredible opportunity to explore the fascinating world of random trees under your guidance. I must also express my heartfelt gratitude to my parents, especially my mother. Thank you for instilling in me an admirable sense of discipline in my studies. Thank you for teaching me to fight until the very end, and for showing me that nothing is ever truly lost. I love you, Mom. And thank you, Dad, for being so incredibly proud of me. I am deeply grateful to my friend Laurita. Thank you for lifting me up every time I needed it throughout these years. I would gladly go through this degree a thousand times if it meant doing it by your side. I must also extend my sincere gratitude to all the professors who have guided me at this wonderful faculty. Thank you for the knowledge you’ve shared and for your patience with my countless late-night emails filled with questions. I couldn’t have asked for a better place to learn. I must mention my beloved therapist. Thank you for teaching me so much about emotional management. Thank you for helping me respect and understand myself. I owe you a great deal. Lastly, I want to express gratitude to myself for persevering through challenges, embracing failure as a lesson, and refusing to settle for the first ”no.” My discipline and determination have been unwavering, but above all, it is my resilience that has allowed me to rise time and time again, ultimately bringing me to where I stand today. Abstract This thesis explores the problem of generating uniform spanning trees (USTs), which are essential structures in combinatorics and probability with applications in network theory and physics. Using conditioned Bienaym´e–Galton–Watson (BGW) processes, it proposes a novel methodology to generate USTs uniformly. Through rigorous proofs, it shows that conditioning these stochastic models on the number of vertices produces uniformly distributed spanning trees. In addition to exploring structural properties such as height, width, and leaf distribution, the thesis provides sharp lower bounds for the height and width of the trees, supported by rigorous proofs. These findings not only enrich the theoretical and practical understanding of USTs but also bridge stochastic processes with combinatorial applications, offering new insights and tools for spanning tree generation. Keywords Random Trees, Bienaym´e-Galton-Watson trees 1 Contents 1 Introduction 3 2 A Misleading Method for Generating Uniform Spanning Trees 4 3 Wilson’s algorithm 6 4 Bienaym´e-Galton-Watson trees 11 4.1 Obtaining some uniform spanning trees from BGW trees . . . . . . . . . . . . . . . . . . 13 5 Studying some parameters of random trees 16 5.1 SomePreliminaries ...................................... 16 5.2 Thewidth ........................................... 22 5.3 Theheight........................................... 25 5.3.1 A modified Bienaym´e-Galton-Watson tree . . . . . . . . . . . . . . . . . . . . . . 26 5.4 Thenumberofleaves..................................... 30 6 Binary search trees 31 6.1 Height of a Random Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 7 Conclusions 39 A An example of a Breadth-First Search (BFS) 41 B An example of a Lexicographic Depth-First Search (DFS) 43 2 1. Introduction The generation of uniform spanning trees (USTs) has become an essential problem in the field of combinatorics and probabilistic processes, given their widespread applications in network analysis, random structures, and statistical physics. A spanning tree of a graph is defined as a connected subgraph that includes all vertices with no cycles. When spanning trees are sampled uniformly at random, each spanning tree of the graph has an equal probability of being chosen. This uniformity condition presents significant mathematical challenges in defining an appropriate random model susceptible of being analyzed, driving the search for effective approaches to solve the problem. This thesis explores novel approaches to generating uniform spanning trees using conditioned Bienaym´eGalton-Watson (BGW) processes. These processes, originally conceived to model the growth of populations, are here adapted to generate spanning trees under uniform distributions. The intrinsic randomness of BGW processes provides a natural framework to study spanning trees, bridging classical combinatorics with stochastic processes. In this thesis, we also provide explicit and clear references to the commonly accepted notion in the literature that this method is a robust approach for generating uniform spanning trees. The project begins with an exploration of different approaches to generating uniform spanning trees, starting with an intuitive, yet fundamentally flawed, method that highlights the challenges of achieving uniformity in probability distributions, in section 2. This sets the stage for a review of existing robust methods, focusing on Wilson’s algorithm, in section 3, widely recognized for its efficiency and its theoretical foundation in loop-erased random walks. Its analysis not only highlights its strengths but also establishes a benchmark for comparisons with the novel techniques proposed in this study. A central focus of this thesis is the adaptation of BGW processes for the generation of spanning trees. Detailed mathematical formulations and rigorous proofs show in section 4 that conditioning these processes on having a fixed number of vertices yields uniform spanning trees. Classical distributions such as Poisson, Geometric, and Bernoulli branching are investigated to illustrate the versatility and correctness of this framework. In addition to the theoretical aspects, this work delves deeply into the typical structural characteristics of random trees using the proposed model. The typical height and width are analyzed in section 5 as primary metrics for understanding the complexity and variability of these trees, complemented by the analysis of the number of leaves of Cayley trees. The results are classical in the area and they are usually obtained by the use of generating functions, see e.g. Drmota [7]. The approach presented here uses conditioned BGW trees and follow the relatively recent contribution by Addario-Berry, Devroye and Janson [1]. In fact, the results obtained there apply to a wider class of trees other than uniform spanning trees and moreover establish tight upper bounds on the deviation of the height and width of random trees from which the classical results on these parameters can be derived. Results concerning these parameters provide insights into the asymptotic behavior of the structures, supported by rigorous probabilistic bounds and illustrative examples that underscore their practical relevance. The conclusions derived from these analyses contribute to a broader understanding of uniform spanning trees and their generation through probabilistic techniques. Finally, in section 6, we focus on the particular case of the height of binary search trees, using different methods from those introduced earlier in this work. Additionally, we observe that branching processes play a role in the proof, but in a manner distinct from their previous applications. 3 Random Trees 2. A Misleading Method for Generating Uniform Spanning Trees Our aim is to develop an algorithm that generates random trees such that the probability of obtaining any specific tree with nvertices is 1/nn−2. In other words, our goal is to ensure a uniform probability distribution over all spanning trees of the complete graph Kn. At first glance, a seemingly natural approach to achieve this might be the following: Let V={v1, ... , vn}be a set of nvertices. We randomly choose a vertex from Vwith probability 1/n, let’s call it u1, and consider the new set of vertices U={u1}. Next, we choose another vertex with uniform probability, call it u2, and connect it to u1. We add u2to U, so that U={u1,u2}. We iterate the same process to select a vertex u3, and connect it to one vertex from Uchosen randomly. That is, in the i-th iteration, we select a vertex from V\Uuniformly and connect it to one of the i−1 already connected vertices, chosen at random. Proposition 2.1. The previously defined algorithm generates a tree. Proof. We will prove this by induction on the number of iterations. -Base case: For i= 1, we have a single vertex, which trivially forms a tree. -Inductive hypothesis: Assume that after iiterations, the set of vertices {u1, ... , ui}generates a tree. -Inductive step: We need to show that after i+ 1 iterations, the set of vertices {u1, ... , ui+1}also forms a tree. Consider the tree formed by the vertices {u1, ... , ui}, which, by the inductive hypothesis, is a tree. In the (i+ 1)-th iteration, we add the vertex ui+1, connecting it to exactly one of the vertices {u1, ... , ui}. This adds ui+1 as a degree-1 vertex to the graph, so no cycles can be created by this connection. If a cycle were to form, it would either already exist among {u1, ... , ui}, which contradicts the inductive hypothesis, since the structure is a tree. Despite what intuition might suggest, the probability of obtaining any given tree is not uniform. This can be easily seen with a counterexample. We will calculate the probability of obtaining the star with four vertices centered at vertex u1using the previously described algorithm. The algorithm proceeds as follows: 1. We randomly select a vertex to be u1, the first vertex in the set. Any vertex can be the center of the star, so we can assume that u1is the central vertex. We choose it with probability equals to 1/4. 4 2. In the second step, we choose another vertex u2randomly from the remaining three vertices and connect it to u1. This is the first step towards forming the star tree. Since the choice of the vertex makes no difference to the star tree, as u2,u3,u4will have degree 1, this probability equals 1. 3. In the third step, we choose the next vertex u3and connect it to one of the already connected vertices (u1or u2). For the star structure to be maintained, u3must be connected to u1(the central vertex). The probability of this happening is 1 2, as there are two vertices connected (u1and u2), and we need u3to be connected to u1. 4. In the fourth step, we choose the last vertex u4and connect it to one of the connected vertices (u1,u2,u3). Again, for the star structure to hold, u4must be connected to u1. The probability of this happening is 1 3, as there are three connected vertices (u1,u2,u3), and we need u4to be connected to u1. Thus, the total probability of obtaining the star tree is: P(Star centered at u1) = 1 4×1 2×1 3=1 24. Therefore, the probability of generating a star tree with 4 vertices is 1 24, which is different from 1 16. Then, we conclude that not all trees have the same probability to occur. u1 u2 u3 u4 Figure 1: Star tree with 4 vertices centered at u1 5 Random Trees Different probability distributions of Zlead to different BGW trees. It is so intuitive that the specie explodes if the expected number of children per individual is greater than 1, and bound to extinct if it is less than one. Then, this parameter is important to be studied. m=E[Z] = E[Z1] = ∞ X k=0 kpk=f′(1) The second equality holds because, in the first generation, there is only one individual with the reproduction probability distribution Z. Now, let’s consider the following: fn(s) = E[sZn] (def.) We aim to relate the function fnwith the function f. Let X(i) denote the number of descendants generated by individual iin generation n−1. By the definition of the BGW process, the random variables X(i) and X(j) are independent and identically distributed, each following the probability distribution Z. Thus, we have: fn(s) = E[sZn] = EhE[sZn|Zn−1]i=EhEhsX(1)+···+X(Zn−1)ii =E  Zn−1 Y j=1 E[sX(j)] =E  Zn−1 Y j=1 f(s) =E[f(s)Zn−1] = fn−1(f(s)). By induction: fn(s) = f(n)(s) where f(n)denotes the n-th composition of fwith itself. We will show how E[Z] affects the probability of extinction in a population. Let αn=P(Zn= 0) be the extinction probability of generation nand denote by α=P(∪n≥1{Zn= 0}) = limn→∞ αnthe probability of extinction at some time n. Then, we have: αn=P(Zn= 0) = fn(0) = f(fn−1(0)) = f(αn−1). If we consider n→ ∞, then α=f(α). Therefore, the extinction probability is a fixed point of the function f. Recall that f(0) = p0<1 and f(1) = 1. Therefore αis the first fixed point in the interval [0, 1]. With this, and knowing that E[Z] = f′(1) and f′′(s) = E(Z(Z−1)sZ−2)>0, so the function fis convex in [0, 1], it is clear that we can distinguish the extinction probability based on the following cases: •If E[Z]<1, the first fixed point is reached at s= 1. Thus, the population is certain to become extinct. This case is called subcritical. 12 •If E[Z]>1, the first fixed point must occur before s= 1, which means that the probability of the species’ survival is non-zero. This case is called supercritical. •If E[Z] = 1, we call this case critical. We must consider the value of p0: –If p0>0, we have a situation analogous to the first case. –If p0= 0, it is clear that f(1) = f′(1) ⇒P(Z= 2) = P(Z= 3) = ··· = 0 ⇒P(Z= 1) = 1. 4.1 Obtaining some uniform spanning trees from BGW trees Depending on the probability distribution governing the reproduction of individuals, one may obtain different types of trees. Specifically, we aim to prove that if we condition a Bienaym´e-Galton-Watson tree to have nvertices, and fix certain known distributions, we obtain various types of uniform random trees. The first description of random trees from conditioning a BGW process by its total progeny can be traced back to Kolchin [14] and Aldous [4]. In this chapter, we also provide explicit proofs for various foundational concepts that are often taken for granted in the literature. Many of these proofs, while implicitly assumed, are not always provided explicitly, as they are considered standard results within the field. Here, we aim to present these derivations clearly and rigorously. Lemma 4.1. Let X be a BGW(Z) process. Let Tndenote the class of trees with n vertices which can be generated by the process and let T ∈Tnbe a tree in the class. If the probability that T is generated by the process depends only on the number of vertices n, then P(X=T||X|=n) = 1 |Tn|. Proof. Let’s denote P(T=T) by f(n), where nis the number of vertices of T. Then, the probability of generating a tree with nvertices is: P(|X|=n) = |Tn|f(n) since the last probability is the sum of the probabilities of obtaining each of the trees with nvertices. Now, when conditioned on having nvertices, all possible trees are equally likely to occur: P(X=T| |X|=n) = P(X=T}∩{|X|=n}) P(|X|=n)=f(n) |Tn|f(n)=1 |Tn| We now aim to prove that, by selecting an appropriate reproduction probability distribution, it is possible to generate several well-known types of trees. 13 Random Trees Remark 4.2.If Xis a discrete random variable taking values in nonnegative integers, it is said to have a Poisson distribution with parameter λ > 0 if it has the following probability distribution: P(X=k) = λke−λ k!,k= 0, 1, 2, ... The class of labeled trees with nnodes is also called the class of Cayley trees, due to the Cayley formula enumerating them, its number being nn−2. Theorem 4.3. Conditioning a Poisson(1) Bienaym´e-Galton-Watson tree on having n vertices results in all Cayley trees with n vertices being generated uniformly. Proof. Every rooted Cayley tree can be generated from a Poisson(1) BGW process by a labeling of its vertices. Let Tbe a specific Cayley tree with nvertices. To prove that each tree can be obtained uniformly, we first need to order all sibling sets in Tby increasing vertex labels. Let χ1, ... , χnrepresent the number of children of each node, listed in preorder traversal. The first requirement for generating T is ensuring the correct number of descendants for each vertex. Since these random variables are pairwise independent, the probability of obtaining a specific number of children for all vertices is the product of their individual probabilities. The second requirement is assigning the correct labeling, as we are considering labeled trees. With nvertices, there are n! possible ways to label them. Moreover, the children of the i-th vertex can be permuted in χi! distinct ways for each i= 1, ... , n, resulting in the same tree. Thus, the final calculation can be expressed clearly as follows: P(T=T) = n Y i=1 1 χi!·e−1!·Qn i=1 χi! n!=e−n1 n! Since the last probability depends only on the number of vertices, and it is known that there exist nn−2 labeled trees, by lemma 4.1 the theorem is proved. The class Bnof Full Binary Trees of nvertices is the family of unlabelled rooted plane trees where every node has two or zero children. Being plane means that trees have distinguished left and right subtrees. The trees depicted in Figure 4 are considered to be distinct. Figure 4: Two distinct binary trees A full binary tree with nnodes has an odd number nof vertices and m= (n+ 1)/2 leaves. Its number is the Catalan number Cm−1. Theorem 4.4. Conditioning a 2Be(1/2) Bienaym´e-Galton-Watson tree on having n vertices results in all Binary trees with n vertices being generated uniformly. 14 Proof. It is clear that one can obtain every binary tree from a 2Be(1/2) BGW tree and vice versa. Let T be a particular Binary tree with nvertices. It is known that in a Binary tree there are (n−1)/2 internal nodes, and (n+ 1)/2 leafs. To apply lemma 4.1, we need to calculate P(T=T). Let χ∼2Be(1/2). P(T=T) = P(χ= 0)n+1 2P(χ= 2)n−1 2=1 2n Since the last probability depends just on the number of vertices, by lemma 4.1 we have proved the theorem. The class Pnof ordered plane trees with nvertices is the family of rooted unlabelled trees where the children of every node are ordered from left to right in the plane. Theorem 4.5. Conditioning a Geom(1/2) Bienaym´e-Galton-Watson tree on having n vertices results in all ordered plane trees with n vertices being generated uniformly. Proof. It can be observed that every ordered plane tree can be obtained from a Geom(1/2) BGW tree, and conversely, every Geom(1/2) BGW tree corresponds to an ordered plane tree. Let Tbe a specific ordered plane tree with nvertices. To generate such a tree, it is necessary to account for both internal nodes and leaves. The probability of an internal node having exactly kchildren is (1/2)k(1/2), where the first factor represents the probability of successfully having kchildren, and the second factor accounts for the probability of no additional children. For a leaf, the requirement is simply to have no children, which occurs with probability 1/2. Consequently, the probability of achieving the correct number of children for each vertex is independent of whether the vertex is an internal node or a leaf. This probability is given by (1/2)χi+1, where χidenotes the number of children of vertex i. Thus, the following conclusion naturally arises: P(T=T) = n Y i=1 1 2χi+1 =1 2Pn i=1 χi+1 =1 2n−1+n =1 22n−1 Furthermore, it is usually known that the number of ordered plane trees with nvertices is Cn−1, where Cnis the n-th catalan number. Hence, by lemma 4.1, the theorem has been proved. Figure 5: A random tree with 7 vertices, generated using a geometric (1/2) distribution 15 Random Trees 5. Studying some parameters of random trees This chapter is focused on the study of key parameters of random trees: height, width, and the number of leaves. All results presented in this section are derived from the study L. Addario-Berry, L. Devroye, and S. Janson did in [1]. The approach in [1] applies not only to random Cayley trees, but to any family of trees arising from a BGW(χ) tree as long χhas expectation 1 and finite variance (critical BGW trees). Furthermore, explicit proofs are provided for certain concepts that are often assumed without further justification in the literature. The exploration of these parameters offers a deeper understanding of random trees, contributing new insights into established results in this field. 5.1 Some Preliminaries Before starting with the proofs, we need some preliminaries. Remark 5.1.The Breadth-First Search (BFS) on a BGW tree is an algorithm used to explore the tree level by level, starting from the root. BFS explores the tree by visiting all nodes at one level before moving to the next, ensuring that nodes are processed in increasing distance from the root. Hence, this search keeps a queue Qwith Qinodes at the i−th step, with Q0= 1. During the exploration of a vertex, its offspring are added to the back of the queue. Then, one can easily obtain the following recursion: Qi=Qi−1−1 + χi where χiis an independent and identically distributed copy of the reproduction distribution χ. Hence, by this recursion, Qj= 1 + ˜ Sj, where ˜ Sj:= Pj i=1(χi−1) = Sj−j. The tree is completely explored when Qj= 0. In this case, ˜ Sn=−1 To aid the reader’s understanding, we provide a concrete example of a BFS performed on a specific tree in Appendix A. This illustration serves to offer a clearer perspective on the principles and methods discussed throughout the chapter. We now present three key lemmas that are not proved in [1] but are necessary for studying the expected width of a random tree. Lemma 5.2. (Raney’s Lemma) Let a1,a2, ... , anbe a sequence of integers such that n X i=1 ai=−1. Then there exists a unique index s such that the cyclic partial sums Sk= k−1 X j=0 a(s+j) mod nfor k = 1, 2, ... , n, satisfy: 16 1. Sk>0for 1≤k<n, 2. Sn=−1. Proof. Define the prefix sums of the sequence as Tk= k X i=1 ai, for k= 0, 1, ... , n, where T0= 0. From the assumption Pn i=1 ai=−1, it follows that Tn=−1. Let m= min0≤k≤nTk, and let sbe the smallest index such that Ts=m. By construction, Tk≥Ts for all k, and Tsis the first occurrence of the minimum value. We now define the cyclic partial sums Skstarting from sas: Sk=T(s+k) mod n−Ts, for k= 1, 2, ... , n. 1. For 1 ≤k<n, since Tsis the minimum value of the prefix sums and sis the first occurrence of this minimum, we have T(s+k) mod n>Ts. Thus, Sk=T(s+k) mod n−Ts>0, for 1 ≤k<n. 2. For k=n, since Pn i=1 ai=−1, we have: Sn=T(s+n) mod n−Ts=Ts+ n X i=1 ai−Ts=−1. Lemma 5.3. Suppose that the individuals in a BGW process reproduce according to a random variable χ, with E[χ]=1and Var(χ)<∞. Then, there is a constant c10 ∈Rsuch that, for all n sufficiently large, P˜ Sn=−1≥c10n−1/2. Proof. Let’s remind ˜ Snis defined as: ˜ Sn= n X i=1 (χi−1) where χiare independent and identically distributed (i.i.d.) random variables with mean µ= 1 and variance σ2<∞. Let Xi=χi−1. These random variables Xiare i.i.d. with mean: E[Xi] = E[χi−1] = µ−1, and variance: Var(Xi) = Var(χi) = σ2. 17 Random Trees Thus, ˜ Sn=Pn i=1 Xi. To apply the Central Limit Theorem (CLT), we normalize ˜ Snas: Zn=˜ Sn−n(µ−1) √nσ2, which, by the central limit theorem, converges in distribution to a standard normal: Zn d −→ N(0, 1), as n→ ∞. Rewriting ˜ Snin terms of Zn, we get: ˜ Sn=n(µ−1) + √nσ2Zn. We are interested in the probability: P(˜ Sn=−1). From the above, the event ˜ Sn=−1 implies: −1 = n(µ−1) + √nσ2Zn. Solving for Zn, we get: Zn=−1−n(µ−1) √nσ2. Then, the following equality is clear: P(˜ Sn=−1) = PZn=−1−n(µ−1) √nσ2. Since Zn d −→ N(0, 1) for large n, by the Local Central Limit Theorem the probability can be approximated by the density of the normal distribution at that point. The density of a standard normal at z is: fN(0,1)(z) = 1 √2πe−z2/2. Thus, the probability P(˜ Sn=−1) is proportional to the normal density evaluated at z=−1−n(µ−1) √nσ2: P(˜ Sn=−1) ∝1 √2πnσ2exp −(−1−n(µ−1))2 2nσ2!. When the mean of the reproduction distribution is µ= 1, the linear term n(µ−1) vanishes, and: Zn=−1 √nσ2. 18 The probability becomes: P(˜ Sn=−1) ∝1 √nexp −1 2nσ2 Hence, it is clear that there is an absolute constant csuch that for every sufficiently large nwe have P(˜ Sn=−1) ≥cn−1/2. Lemma 5.4. Suppose that χiare i.i.d., non-negative and integer-valued random variables, with E[χi]=1 and Var[χi]<∞, and let Sn=Pn i=1 χi. Then, for all n ≥1and m ≥0, P(Sn=n−m)≤C7 √ne−c7m2/n, where C7>0and c7>0are real constants. Proof. Since χiare i.i.d. random variables with mean E[χi] = 1 and variance Var[χi] = σ2<∞, by central limit theorem, the sum Sn=Pn i=1 χisatisfies Sn−n √nσ2 d −→ N(0, 1), as n→ ∞. Rewriting Sn=n−mand defining Znas follows, we get Zn=Sn−n √nσ2=−m √nσ2. Under the normal approximation, the probability P(Sn=n−m) can be approximated using the normal density fN(0,1)(z): P(Sn=n−m)≈1 √2πnσ2exp −Z2 n 2, Substituting Zn, we find P(Sn=n−m)≈1 √2πnσ2exp   −−m √nσ22 2  . Simplifying the exponent, P(Sn=n−m)≈1 √2πnσ2exp −m2 2nσ2. Now, define C7=1 √2πσ2and c7=1 2σ2. The probability bound becomes what we seek: 19 Random Trees P(Sn=n−m)≤C7 √ne−c7m2/n. where C7>0 and c7>0 depend on the variance σ2of χi. This completes the proof. Lemma 5.5. Let χbe a discrete random variable taking values in nonnegative integers. Suppose that E(χ)=1and 0<Var(χ)<∞. Let Tbe a BGW(χ) tree. Then, P(|T | =n)≥n−3/2. Proof. We observe that the event |T | =nis equivalent to χ1+χ2+···+χn=n−1 and χ1+χ2+···+χi>0 for all 1 ≤i<n. The first event is ˜ Sn=−1. Let Undenote the second one. By Lemma 5.2, under the condition that ˜ Sn=−1, there is a single ordering of the variables χ1, ... , χn such that all initial partial sums are positive. Thus, P(Un|˜ Sn=−1) = 1 n. It follows that P(|T| =n) = P({˜ Sn=−1}∩Un) = P(˜ Sn=−1)P(Un|˜ Sn=−1) = 1 nP(˜ Sn=−1) ≥c10n−3/2, where the last inequality follows from Lemma 5.3. We will also use the following Chernoff type inequality. Lemma 5.6. Let X1,X2, ... , Xnbe independent random variables such that Xi−E[Xi]≤b for every i, where b ∈R. Let V := Pn i=1 Var(Xi). Then, P n X i=1 (Xi−EXi)≥t!≤exp −t2 2V+2bt 3!. Proof. Let Sn:= Pn i=1(Xi−E[Xi]). Using Markov’s inequality, we have: P(Sn≥t) = P(eλSn≥eλt)≤E[eλSn] eλt, where λ > 0 is a parameter to be chosen later. Since X1,X2, ... , Xnare independent, the following is clear: E[eλSn] = n Y i=1 Eheλ(Xi−E[Xi])i. Let Yi:= Xi−E[Xi], and we suppose that Yi≤b. For any random variable Yisuch that Yi≤b, we can bound E[eλYi] using the Taylor expansion of eλYi. Specifically: E[eλYi]≤1 + λE[Yi] + λ2E[Y2 i] 2+λ3E[Y3 i] 6+··· . 20 Since E[Yi] = 0, and E[Y2 i] = Var(Xi), the leading contributions are: E[eλYi]≤exp λ2Var(Xi) 2+λ3b2 6. E[eλSn]≤ n Y i=1 exp λ2Var(Xi) 2+λ3b2 6. Since Pn i=1 Var(Xi) = V, this simplifies to: E[eλSn]≤exp λ2V 2+λ3b2n 6. Substituting this into Markov’s inequality gives: P(Sn≥t)≤exp λ2V 2+λ3b2n 6−λt. We now choose λ > 0 to minimize the exponent: λ2V 2+λ3b2n 6−λt. Ignoring the cubic term temporarily, we first minimize: λ2V 2−λt. Taking the derivative with respect to λand setting it to zero: d dλλ2V 2−λt=λV−t= 0 =⇒λ=t V. However, the cubic term λ3b2n 6becomes significant when λis large. To control this, we modify λto balance all terms: λ=t V+2bt 3 . This choice ensures that the quadratic and cubic terms remain balanced while maximizing the negative linear term −λt. Substituting λ=t V+2bt 3 into the exponent, the proof is done: P(Sn≥t)≤exp −t2 2V+2bt 3!. 21 Random Trees It is clear that, if the height of the tree is h, either there exists a jsuch that Qd j=h, or there exists a k such that Qr k=h. Let p1=P(χ= 1) and let q1= 1−p1. Let v∈Tnsuch that h(v) = h. Let j(resp. k) be the index of vin lexicographic (resp. reverse-lexicographic) order. Let Xbe the number of nodes which have more than one child in P. Each ancestor of vwith more than one child contributes to at least one unit to Qd jor to Qr k. We distinguish two cases, either max(Qd j,Qr k)≥q1 3hor max(Qd j,Qr k)<q1 3h. In the second case, by the above remark, the number of ancestors of vwith exactly one child is at least (1−2q1/3)h= (p1+q1/3)h. Now, it is not useful to think about the queues because when the algorithm processes a node which has just 1 child, the size of the queue does not increase, so it is not a well representation for the height of the tree. Let Sbe the set of trees Twith |T|=nand containing a node vsuch that h(v) = hand has (p1+q1/3)h(v) ancestors in Pwith exactly one child. Then, let δ:= {Tn∈S}=ST∈S{Tn=T}. Then, we can apply these two cases described to the calculus of the following probability. The first two terms correspond to the first case, while the remaining term corresponds to the second case: P(H(Tn)≥h)≤Pmax jQd j≥q1 3h+Pmax kQr k≥q1 3h+P(δ) = 2Pmax iQi≥q1 3h+P(δ)≤C11e−c11h2/n+P(δ) where the last inequality has been seen in the proof of theorem 5.8. Then, we only need to bound P(δ). To achieve it, we will use 2: P(T ∈ S) = X T∈S P(T=T) = X T∈S P(ˆ T(h)=Twith γTas spine) =P [ T∈S{ˆ T(h)=Twith γTas spine}!≤P h−1 X i=0 1ˆχi=1 ≥(p1+q1/3)h!. where the last inequality is due to the fact that the event of the left-hand side is included in the right-hand side event. Since 1ˆχi=1 are Bernoulli(p1), by Lemma 5.6, and taking t=q1h/3, V=p1q1h,b=q1, we have the following bound: P h−1 X i=0 1ˆχi=1 ≥(p1+q1/3)h!≤exp −(q1h/3)2 2p1q1h+ 2q2 1h/9 = exp −h 18p1/q1+ 2. Furthermore, the following equality is clear: P(T ∈ S) = P(δ)·P(|T | =n) 28 By Lemma 5.5, P(|T| =n)≥n−3/2and we can stablish an upper bound for P(δ). P(δ) = P(T ∈ S) P(|T| =n)≤C12n3/2exp −h 18p1/q1+ 2≤C12n3/2exp h 18p1/q1+ 2 h √n ≤C13e−c12h2/n for all h≥√n. Taking everything into account, what we have is the following bound for the height of a BGW tree: P(H(Tn)≥h)≤C11e−c11h2/n+C13e−c12h2/n Now, taking C2:= max{C11,C13},c2:= min{c11,c12} P(H(Tn)≥h)≤C2e−c2h2/n Having proved that, we left the following result without proof due to its analogy with theorem 5.9. Theorem 5.16. Let χbe a discrete random variable taking values in nonnegative integers. Suppose that E[χ]=1and 0<Varχ < ∞. Then, E[H(Tn)] = O(√n) for all n ≥1. Figure 6: We illustrate all possible ordered plane trees with 5 vertices. One can verify that the average values for height and width approximate √5. 29 Random Trees 5.4 The number of leaves This subsection is based on Goldsmith [9]. We will study the expected number of leaves in a random Cayley tree with nvertices, focusing on the distribution of the number of leaves and its expected value as a function of the tree’s parameters. Remark 5.17.A sequence of random variables Xnconverges in probability to X, denoted as Xn P −→ X, if for every ϵ > 0, lim n→∞ P(|Xn−X|> ϵ) = 0. Remark 5.18.Chebyshev’s Inequality: Let Xbe a random variable with finite mean µ=E[X] and variance Var(X). Then, for any ϵ > 0, P(|X−µ| ≥ ϵ)≤Var(X) ϵ2. Theorem 5.19. Let Nnbe the number of leaves in the random Cayley tree Tn. Then, Nn n P −→ e−1 Proof. Let 1ibe the following indicator function: 1i=(1, if iis a leaf 0, if iis not a leaf It is clear that Nn=Pn i=1 1i. To prove this convergence in probability, we will use Remark 5.18. Hence, we need to calculate E[1i] = P(1i= 1) To get the probability in question, we first need to determine how many trees on the set [n] have ias a leaf. Each such tree can be viewed as a tree on [n−1] labeled vertices, with an additional edge connecting one of the other vertices to i. Since the number of trees on (n−1) labeled vertices is (n−1)n−3, and we can add the edge mentioned to each vertex, it follows that the number of trees with ias a leaf is (n−1)n−2. Therefore, the probability that iis a leaf is given by: P(iis a leaf) = (n−1)n−2 nn−2=1−1 nn−2 →e−1 where we have taken the limit as napproaches infinity. It is clear that 1i, 1jare not independent if i=j, but one can show that they are asymptotically independent: P(iis a leaf and jis a leaf) = (n−2)2(n−2)n−4 nn−2=1−2 nn−2 →e−2 30 where we have used the same argument as before. In particular, it is not difficult to calculate their covariance: cov(1i, 1j) = 1−2 nn−2 −1−1 n2(n−2) →0 We also have: Var(1i) = 1−1 nn−2 −1−1 n2(n−2) = 1−1 nn−2 1−1−1 nn−2!→e−11−e−1 Hence, the following is clear: Var Nn n=1 n2 n X i=1 Var(1i) + 2 n2X i<j Cov(1i, 1j) =1 nVar(11) + n−1 nCov(11, 12)→0 So that, we already have all we need to apply Chebyshev’s inequality and finish the proof: P Nn n−e−1 > ϵ≤Var (Nn/n) ϵ2→0 6. Binary search trees Our goal in this chapter is to ensure clarity and accessibility in the analytic study of the height of a binary search tree, utilizing BGW trees as a key component in the main proof. To achieve this, we closely follow Luc Devroye’s proof from [17], supplementing it with detailed demonstrations of concepts often left implicit in related works. Definition 6.1. A binary search tree for distinct real numbers x1, ... , xnis a binary tree in which x1is the root, whose left subtree is a binary search tree for {x2, ... , xn} ∩ (−∞,x1) and whose right subtree is a binary search tree for {x2, ... , xn}∩(x1,∞). Remark 6.2.A binary search tree depends on the order in which its vertices are presented. Remark 6.3.If the left subtree has kpoints, then in the total ordering of the vertices, the rank of the root is k+ 1. By this definition, we have a clear way to add a new vertex. If we want to grow the tree with a vertex xn+1, we can compare xn+1 with the current root and choose left or right subtree as appropriate. The insertion time is equal to the depth of xn+1, which is the distance between the root and the inserted node. 31 Random Trees One can easily obtain a uniform binary search tree. We can take a permutation of {1, ... , n}with each permutation equally probable. For each permutation, we will get a different binary search tree. All of them will be equally likely to occur because their structure depends only on the permutation assigned, and we take every permutation uniformly. 4 2 1 3 5 Figure 7: Binary search tree with 5 vertices. 6.1 Height of a Random Binary Search Tree Before delving into the proof offered by Luc Devroye in [17], we will provide explicit demonstrations of the essential preliminaries required for the proof. These foundational results, often taken as given in the literature, are crucial for a complete and rigorous understanding of the argument. Theorem 6.4. The average depth of a node in a randomly constructed binary search tree is O(log n). Proof. The sum of the depths of all the nodes is called the internal path length. Let’s denote it by D(n). Since for each insertion of a vertex, the tree has inodes in its left side, and n−i−1 in its right side, and both trees have its root one level down, we have the following recurrence: D(n) = D(i) + D(n−i−1) + n−1 Hence, the average internal path node can be described as follows: 1 n n X i=0 (D(i) + D(n−i−1) + (n−1)) = (n−1) + 2 n n−1 X i=0 D(i) Let’s use this to prove that D(n) = O(n·log(n)). Then, if it holds, it is clear that the average depth o a node in a random BST is O(log n). We will prove it by induction on n. We need to find some constant Csuch that D(n)≤C·n·log(n) •If n= 1, D(1) = 0. Since C·0 = 0 for each constant C, the result holds. •Assume D(m)≤C·m·log(m) for all m<n. Let’s find the right Cfor D(n). (n−1) + 2 n n−1 X i=0 D(i)HI ≤(n−1) + 2 n n−1 X i=0 C·i·log(i)≤(n−1) + 2 nZn 1 C·x·log(x)dx = 32 2 nCn2 2log(n)−1 2 ln(2) Zn 1 x dx+ (n−1) = C·n·log(n)−C(n2−1) 2n·ln(2) + (n−1) ≤C·n·log(n) where we have considered C>2·ln(2) and nsufficiently large. Before starting with the study of the height of a binary search tree, we need to make some remarks: Lemma 6.5. Let U1,U2, ... , Ukbe k independent random variables, each uniformly distributed on (0, 1). Define X as the product of these variables: X=U1·U2·... ·Uk. Then X is a random variable that follows a Gamma distribution with shape parameter k and scale parameter 1, denoted X ∼Gamma(k, 1). Proof. To prove this, we will proceed by examining the logarithm of the product X. Define Y=−ln(X). Then, Y=−ln(U1·U2·... ·Uk) = −(ln(U1) + ln(U2) + ... + ln(Uk)) . Since Ui∼Uniform(0, 1), we know that each −ln(Ui) follows an exponential distribution with rate parameter 1. Then, −ln(Ui)∼Exponential(1). Because Yis the sum of kindependent exponential random variables with rate 1, Yitself has a Gamma distribution with shape parameter kand scale parameter 1, denoted: Y∼Gamma(k, 1). Since Y=−ln(X), we can express Xas: X=e−Y. Therefore, Xfollows a Gamma distribution with parameters k(shape) and 1 (scale), as required. Lemma 6.6. Let Gk∼Gamma(k, 1) denote a gamma-distributed random variable with shape parameter k and scale parameter 1. The following inequality holds: 1≤P(Gk≤y) yke−y k!≤1 1−y k+1 . 33 Random Trees Proof. The probability distribution function of Gkis given by: P(Gk≤y) = Zy 0 xk−1e−x (k−1)! dx. For y>0, it is clear that f(y) = yk−1e−y (k−1)! >0, then: P(Gk≤y)≥0. Thus, it follows that: P(Gk≤y) yke−y k!≥0, which trivially implies, for k>> 0: 1≤P(Gk≤y) yke−y k! . Now we need to prove P(Gk≤y)≤1 1−y k+1 . To find an upper bound, we rewrite P(Gk≤y) as follows: Using integration by parts ktimes and properties of the gamma function, we can express: P(Gk≤y) = 1 −e−y k−1 X j=0 yj j!. Thus, we can easily obtain the following: P(Gk≤y) yke−y k! =k!(1 −e−yPk−1 j=0 yj j!) yke−y. For y<k+ 1, we can use the series expansion of e−yand obtain the following inequality: 1−e−y k−1 X j=0 yj j!≤yke−y k!(k+ 1 −y), Then, we trivially have: P(Gk≤y) yke−y k!≤1 1−y k+1 . Once all the preliminaries have been established, we have the necessary tools to undertake the proof offered in [17] of the height of a binary search tree with nvertices in full detail. This comprehensive approach ensures a thorough understanding of each step in the argument. 34 Theorem 6.7. Let Hnbe the height in a random binary search tree on n nodes. Then, Hn log(n) P −→ γ= 4.331107 ... where P −→ means convergence in probability. Proof. To start with it, we need to introduce a new representation of a binary search tree. Let Tbe a random BST. Augment the tree Tassociating with each node the size of the subtree rooted at that node. Let T′be this last tree. The rank of the root element of Tis equally likely to be 1, ..., n. Hence, the number of nodes Nin the left subtree of the root of Tis uniformly distributed on {0, 1, ... , n−1}. What is more, if Uis a random variable uniformly distributed on [0, 1], we can read N=⌊nU⌋. Then, the number of nodes in the right subtree of the root of T, which is n−1−N, is distributed as ⌊n(1 −U)⌋. This is an embedding argument. All subsequent splits can be represented similarly by introducing independent uniform [0, 1] random variables. Furthermore, given an infinite binary tree, and a node whose assigned value is Vand whose copy of Uis U′, the value of the two children are distributed by ⌊VU′⌋and ⌊V(U′−1)⌋. It is not difficult to obtain a more general form for the distribution of the value of a vertex at distance kfrom the root of T′: ⌊... ⌊⌊nU1⌋U2⌋... Uk⌋ , where U1, ..., Ukare independent copies of U. With this representation, we can start to talk about height Hn. The structure of the proof is as follows: first, we will prove that γlog(n) serves as an upper asymptotic bound for Hn. Subsequently, we will show that γlog(n) is also a lower asymptotic bound for Hn. Together, these results establish the equality. We start with the upper bound. To know if the height of a random BST is at least k, it is sufficient to go to the k-th level and see if there exists some node with any subtree rooted at it. At most, we can have 2knodes at that level. Hence, this condition can be described as follows: Hn≥k⇐⇒ max 1≤i≤2kVi≥1 It is clear that Vi’s are dependent, just consider the values Viand Vjfor nodes near one another. We will analyze the probability of having a random tree whose height is, at least, k. P(Hn≥k) = P( 2k [ i=1 [Vi≥1]) ≤2k·P(V1≥1), 35 Random Trees where the inequality holds by Bonferroni’s inequality and the symmetry of the variables Vi. This can be further bounded as follows: 2k·P(V1≥1) ≤2k·P n k Y i=1 Ui≥1!, where we use the independence and identical distribution of the variables U1, ... , Uk. Now, applying lemma 6.5, we have: 2k·P n k Y i=1 Ui≥1!= 2k·Pne−Gk≥1= 2k·P(Gk≤log(n)) . The point now is to find the smallest ksuch that the upper bound tends to zero. It is clear that, if we take k= log(n), the upper bound is O(2k). This is due to, for k= log(n), P(Glog(n)≤log(n)) ≈1−e−log(n) log(n)−1 X j=0 (log(n))j j!⇒P(Glog(n)≤log(n)) ≈1, if n>> 0. Then, what we search is some kmuch larger than log(n) to cancel the effect of that 2k. Let’s try k≈c·log(n) for some c>1. Hence, by lemma 6.6, we have the following: 1≤P(Gk≤y) yke−y k!≤1 1−y k+1 where the lower bound is valid for all y>0, and upper bound just for 0 <y<k+ 1. In particular, P(Gk≤log(n)) ≤log(n)k nk!×1 1−log(n) k+1 which is valid for log(n)<k+1. Hence, taking k=⌈c·log(n)⌉, and using Stirling’s inequality (k!≥(k e)k), we have the following: P(Hn≥k)≤(2 log(n))k nk!×1 + o(1) 1−1 c≤n−12elog(n) kk ×1 + o(1) 1−1 c ≤1 e2e cclog(n) ×1 + o(1) 1−1 c→0 where the last expression tends to 0 if 1 e2e cc<1. For c=γ= 4.31107... we obtain the equality. So that, we conclude the following: ∀c> γ, lim n→∞ P(Hn> γ log(n)) = 0 36 as we wanted to prove. At this point, we have proved that γlog(n) serves as an upper asymptotic bound for the height of a random binary search tree. Let’s show it is also a lower asymptotic bound. Pick ϵ > 0. We will prove the following: lim n→∞ P(Hn≥(γ−ϵ) log(n)) = 1 To prove it, we will use branching processes. Firstly, we need to track down nodes with large values in the augmented tree. Let’s define V=nU1U2... Ukfor a node at distance kfrom the root, where the Ui’s are defined as before and describe the splits on the path to the root. We aim to construct a surviving BGW process. Clearly, the root of Tbecomes the zeroth generation of the BGW process. Let’s consider all descendants in Twhich are Llevels away, and identify these nodes as BGW children if the product of uniform splitting random variables encountered in the path from the root to the possible child is greater that dL, for a given constant d. It is clear that the number of BGW children per node is bounded between 0 and 2L. If Twere infinite, it is obvious that we can find a node at any distance from the root. Moreover, the corresponding BGW process would survive with probability 1 −q>0, where qis the extinction probability, if the expected number of BGW children per node were greater than one. Let’s see that we can get it for a large Land right constants: Let Ijbe an indicator variable for the j-th node, where: Ij=(1 if the node is a BGW child 0 if the node is not a BGW child E  N X j=1 Ij = 2L·PU1... UL>dL= 2L·P(GL<L·log(1/d)) ≥(2Ld ·log(1/d))L L!∼(2ed ·log(1/d))L √2πL>1 if 2ed ·log(1/d)>1. Choosing d=e−1/c, where cis a constant close to γ, we get it. It can be proved numerically. Furthermore, we have used Stirling’s approximation for large L, and lemmas 6.5, 6.6. In conclusion, with probability 1 −q>0, there exists a vertex at distance kL from the root with value V≥ndkL =ne−kL/c. Taking truncations into account, it is clear that, at most, one unit can be lost at worst in every truncation. Hence, we have the following lower bound: P(Hn≥kL)≥1−q if ne−kL/c−kL ≥1. Taking kL =c′·log(n)−θL, for c′arbitrarily close to cand θ∈[0, 1) depending on n, the last condition is verified for large n: ne−kl/c−kL ≥n1−c′/c−c′·log(n)>1 Since c,c′have been taken arbitrarily close to γ, we have the following ∀ϵ > 0: 37 Random Trees •Move to node 5. •Queue: [3, 5]. 4. Processing Node 5: •Current node: 5. •Children of node 5: None (leaf node). •Backtrack to node 4. •Queue: [3]. 5. Backtrack: •All children of node 4 have been visited. •Backtrack to node 2. •All children of node 2 have been visited. •Backtrack to node 1. •Queue: [3]. 6. Backtrack to Node 1 and Move to Node 3: •Current node: 1. •Move to the next child: Node 3. •Current node: 3. •Children of node 3: None (leaf node). •Queue: []. The lexicographic DFS traversal order of the tree is: [1, 2, 4, 5, 3] 44