Depth Properties of scaled attachment random recursive trees

We study depth properties of a general class of random recursive trees where each node i attaches to the random node \begin{align*}\left\lfloor iX_i\right\rfloor\end{align*} and X₀,…,X_n is a sequence of i.i.d. random variables taking values in [0,1). We call such trees scaled attachment random recursive trees (sarrt). We prove that the typical depth D_n, the maximum depth (or height) H_n and the minimum depth M_n of a sarrt are asymptotically given by D_n ～μ^‐1 log n, H_n ～ α_max log n and M_n ～ α_min log n where μ,α_max and α_min are constants depending only on the distribution of X₀ whenever X₀ has a density. In particular, this gives a new elementary proof for the height of uniform random recursive trees H_n ～ elog n that does not use branching random walks.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

Percolation on random recursive trees

We study Bernoulli bond percolation on a random recursive tree of size n with percolation parameter p(n) converging to 1 as n tends to infinity. The sizes of the percolation clusters are naturally stored in a tree structure. We prove convergence in distribution of this tree‐indexed process of cluster sizes to the genealogical tree of a continuous‐state branching process in discrete time. As a corollary we obtain the asymptotic sizes of the largest and next largest percolation clusters, extending thereby a recent work of Bertoin [5]. In a second part, we show that the same limit tree appears in the study of the tree components which emerge from a continuous‐time destruction of a random recursive tree. We comment on the connection to our first result on Bernoulli bond percolation. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 655–680, 2016     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

On the complexity of branch‐and‐bound search for random trees

Let T_n be a b‐ary tree of height n, which has independent, non‐negative, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T_n. Assume that the edge random variable X is nondegenerate, has E {X^θ}<∞ for some θ>2, and satisfies bP{X=c}<1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch‐and‐bound algorithm for this problem and prove that the number of nodes visited is in probability (β+o(1))ⁿ, where β∈(1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for β are derived. We also show that any search algorithm must visit (β+o(1))ⁿ nodes with probability tending to 1, so branch‐and‐bound is asymptotically optimal where first‐order asymptotics are concerned. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 309–327, 1999     

Branching structure of uniform recursive trees

The branching structure of uniform recursive trees is investigated in this paper. Using the method of sums for a sequence of independent random variables, the distribution law of ηn, the number of branches of the uniform recursive tree of size n are given first. It is shown that the strong law of large numbers, the central limit theorem and the law of iterated logarithm for ηn follow easily from this method. Next it is shown that ηn and ξn, the depth of vertex n, have the same distribution, and the distribution law of ζn,m, the number of branches of size m, is also given, whose asymptotic distribution is the Poisson distribution with parameter λ= 1/m. In addition, the joint distribution and the asymptotic joint distribution of the numbers of various branches are given. Finally, it is proved that the size of the biggest branch tends to infinity almost sure as n→∞.     

On martingale tail sums for the path length in random trees

For a martingale (X_n) converging almost surely to a random variable X, the sequence (X_n– X) is called martingale tail sum. Recently, Neininger (Random Structures Algorithms 46 (2015), 346–361) proved a central limit theorem for the martingale tail sum of Régnier's martingale for the path length in random binary search trees. Grübel and Kabluchko (in press) gave an alternative proof also conjecturing a corresponding law of the iterated logarithm. We prove the central limit theorem with convergence of higher moments and the law of the iterated logarithm for a family of trees containing binary search trees, recursive trees and plane‐oriented recursive trees. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 493–508, 2017     

Induced trees in sparse random graphs

The random graphG(n, p) onn vertices with edge probabilityp = c/n contains an induced tree of order _c n where _c > 0 forc > 1. This proves a conjecture of Erdös and Palka.     

Almost sure central limit theorems for random functions

Let {Xn,-∞< n <∞} be a sequence of independent identically distributed random variables with EX1 = 0, EX12 = 1 and let Sn =∑k=1∞Xk, and Tn = Tn(X1,…,Xn) be a random function such that Tn = ASn Rn, where supn E|Rn| <∞and Rn = o(n~(1/2)) a.s., or Rn = O(n1/2-2γ) a.s., 0 <γ< 1/8. In this paper, we prove the almost sure central limit theorem (ASCLT) and the function-typed almost sure central limit theorem (FASCLT) for the random function Tn. As a consequence, it can be shown that ASCLT and FASCLT also hold for U-statistics, Von-Mises statistics, linear processes, moving average processes, error variance estimates in linear models, power sums, product-limit estimators of a continuous distribution, product-limit estimators of a quantile function, etc.     

The structure and distances in Yule recursive trees

Based on uniform recursive trees, we introduce random trees with the factor of time, which are named Yule recursive trees. The structure and the distance between the vertices in Yule recursive trees are investigated in this paper. For arbitrary time t > 0, we first give the probability that a Yule recursive tree Y_t is isomorphic to a given rooted tree γ; and then prove that the asymptotic distribution of ζ_t,m, the number of the branches of size m, is the Poisson distribution with parameter λ = 1/m. Finally, two types of distance between vertices in Yule recursive trees are studied, and some limit theorems for them are established.© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Limits of random trees

Local convergence of bounded degree graphs was introduced by Benjamini and Schramm [2]. This result was extended further by Lyons [4] to bounded average degree graphs. In this paper, we study the convergence of a random tree sequence (T _n ), where the probability of a given tree T is proportional to $\prod_{v_{i}\in V(T)}d(v_{i})!$ . We show that this sequence is convergent and describe the limit object, which is a random infinite rooted tree.     

A study of random Weyl trees

We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H_n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H_n∼(12/π²)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998     

Uniform recursive trees: Branching structure and simple random downward walk

As models for spread of epidemics, family trees, etc., various authors have used a random tree called the uniform recursive tree. Its branching structure and the length of simple random downward walk (SRDW) on it are investigated in this paper. On the uniform recursive tree of size n, we first give the distribution law of ζn,m, the number of m-branches, whose asymptotic distribution is the Poisson distribution with parameter . We also give the joint distribution of the numbers of various branches and their covariance matrix. On Ln, the walk length of SRDW, we first give the exact expression of P(Ln=2). Finally, the asymptotic behavior of Ln is given.     

Tail bounds for the height and width of a random tree with a given degree sequence

Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}$ be a plane tree drawn uniformly at random from among all plane trees with child sequence c . In this note we prove sub‐Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of ${\mathcal T}$. These bounds are optimal up to the constant in the exponent when c satisfies $\sum_{i=1}^n c_i^2=O(n)$; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Recursive reconstruction on periodic trees

A periodic tree T_n consists of full n-level copies of a finite tree T. The tree T_n is labeled by random bits. The root label is chosen randomly, and the probability of two adjacent vertices to have the same label is 1−ϵ. This model simulates noisy propagation of a bit from the root, and has significance both in communication theory and in biology. Our aim is to find an algorithm which decides for every set of values of the boundary bits of T, if the root is more probable to be 0 or 1. We want to use this algorithm recursively to reconstruct the value of the root of T_n with a probability bounded away from ½ for all n. In this paper we find for all T, the values of ϵ for which such a reconstruction is possible. We then compare the ϵ values for recursive and nonrecursive algorithms. Finally, we discuss some problems concerning generalizations of this model. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 81–97, 1998     

On the distribution of binary search trees under the random permutation model

We study the distribution Q on the set B_n of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B_n when successive requests are independent and identically distributed with each record equally likely. We identify the minimum and maximum values of the functional Q and the trees achieving those values and argue that Q is a crude measure of the “shape” of the tree. We study the distribution of Q(T) for two choices of distribution for random trees T; uniform over B_n and Q. In the latter case, we obtain a limiting normal distribution for −ln Q(T). © 1996 John Wiley & Sons, Inc.     

On growing random binary trees

A sequence {T_n}_{n = 1}^∞ of nested binary trees generated by an infinite sequence of i.i.d. random variables is studied. Two absolute constants β₁,β₂ are shown to exist (0.37 < β₁ < 0.50, 3.58 < β₂ < 4.32), such that $\text{lim}\text{h}{}_{\mathrm{n}}\text{ln}\text{n = β}{}_1\text{,}\text{lim}\text{H}{}_{\mathrm{n}}\text{/}\text{ln}\text{n = β}{}_2$ with probability one; here h_n and H_n are respectively the lengths of the shortest and the longest branches of the tree T_n.     

The cores of random hypergraphs with a given degree sequence

We study random r‐uniform n vertex hypergraphs with fixed degree sequence d = (d₁…,d_n), maximum degree Δ = o(n^1/24) and total degree θn, where θ is bounded. We give the size, number of edges and degree sequence of the κ ≥ 2) up to a whp error of O(n^2/3 Δ^4/3 log n). In the case of graphs (r = 2) we give further structural details such as the number of tree components and, for the case of smooth degree sequences, the size of the mantle. We give various examples, such as the cores of r‐uniform hypergraphs with a near Poisson degree sequence, and an improved upper bound for the first linear dependence among the columns in the independent column model of random Boolean matrices. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 25, 2004     

Extremal cover times for random walks on trees

Let C_ν(T) denote the “cover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C_ν(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2n In n) by showing that C_ν(T) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).