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     

LIMITING BEHAVIOR OF UNIFORM RECURSIVE TREES

The authors consider the limiting behavior of various branches in a uniform recursive tree with size growing to infinity.The limiting distribution ofζ_(n,m),the number of branches with size m in a uniform recursive tree of order n,converges weakly to a Poisson distribution with parameter 1/m with convergence of all moments.The size of any large branch tends to infinity almost surely.     

High degrees in random recursive trees

For , let T_n be a random recursive tree (RRT) on the vertex set . Let be the degree of vertex v in T_n, that is, the number of children of v in T_n. Devroye and Lu showed that the maximum degree Δ_n of T_n satisfies almost surely; Goh and Schmutz showed distributional convergence of along suitable subsequences. In this work we show how a version of Kingman's coalescent can be used to access much finer properties of the degree distribution in T_n. For any , let . Also, let be a Poisson point process on with rate function . We show that, up to lattice effects, the vectors converge weakly in distribution to . We also prove asymptotic normality of when slowly, and obtain precise asymptotics for when and is not too large. Our results recover and extends the previous distributional convergence results on maximal and near‐maximal degrees in RRT.     

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→∞.     

Profiles of random trees: Plane‐oriented recursive trees

We derive several limit results for the profile of random plane‐oriented recursive trees. These include the limit distribution of the normalized profile, asymptotic bimodality of the variance, asymptotic approximation to the expected width, and the correlation coefficients of two level sizes. Most of our proofs are based on a method of moments. We also discover an unexpected connection between the profile of plane‐oriented recursive trees (with logarithmic height) and that of random binary trees (with height proportional to the square root of tree size). © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Representing probability measures using probabilistic processes

In the Type-2 Theory of Effectivity, one considers representations of topological spaces in which infinite words are used as “names” for the elements they represent. Given such a representation, we show that probabilistic processes on infinite words, under which each successive symbol is determined by a finite probabilistic choice, generate Borel probability measures on the represented space. Conversely, for several well-behaved types of space, every Borel probability measure is represented by a corresponding probabilistic process. Accordingly, we consider probabilistic processes as providing “probabilistic names” for Borel probability measures. We show that integration is computable with respect to the induced representation of measures.     

When probability trees don't work

Tree diagrams arise naturally in courses on probability at high school or university, even at an elementary level. Often they are used to depict outcomes and associated probabilities from a sequence of games. A subtle issue is whether or not the Markov condition holds in the sequence of games. We present two examples that illustrate the importance of this issue. Suggestions as to how these examples may be used in a classroom are offered.     

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     

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     

Note on the heights of random recursive trees and random m-ary search trees

A process of growing a random recursive tree T_n is studied. The sequence {T_n} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of T_n is asymptotic, with probability one, to c log n. In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ)^?1, where γe^1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m-ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union-find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc.     

Generating binary trees with uniform probability

A binary tree is characterized as a sequence of graftings. This sequence is used to construct a Markov chain useful for generating trees with uniform probability. A code for the Markov chain gives a characteristic binary string for the trees. The main result is the calculation of the transition probabilities of the Markov chain. Some applications are pointed out.     

On edge-weighted recursive trees and inversions in random permutations

We introduce random recursive trees, where deterministically weights are attached to the edges according to the labeling of the trees. We will give a bijection between recursive trees and permutations, which relates the arising edge-weights in recursive trees with inversions of the corresponding permutations. Using this bijection we obtain exact and limiting distribution results for the number of permutations of size n, where exactly m elements have j inversions. Furthermore we analyze the distribution of the sum of labels of the elements, which have exactly j inversions, where we can identify Dickman's infinitely divisible distribution as the limit law. Moreover we give a distributional analysis of weighted depths and weighted distances in edge-weighted recursive trees.     

Depth in bucket recursive trees with variable capacities of buckets

We consider bucket recursive trees of sizen consisting of all buckets with variable capacities1,2,...,b and with a specifc stochastic growth rule.This model can be considered as a generalization of random recursive trees like bucket recursive trees introduced by Mahmoud and Smythe where all buckets have the same capacities.In this work,we provide a combinatorial analysis of these trees where the generating function of the total weights satisfes an autonomous frst order diferential equation.We study the depth of the largest label（i.e.,the number of edges from the root node to the node containing label n）and give a closed formula for the probability distribution.Also we prove a limit law for this quantity which is a direct application of quasi power theorem and compute its mean and variance.Our results for b=1 reduce to the previous results for random recursive trees.     

The height of depth‐weighted random recursive trees

In this paper, we introduce a model of depth‐weighted random recursive trees, created by recursively joining a new leaf to an existing vertex . In this model, the probability of choosing depends on its depth in the tree. In particular, we assume that there is a function such that if has depth then its probability of being chosen is proportional to . We consider the expected value of the diameter of this model as determined by , and for various increasing we find expectations that range from polylogarithmic to linear.     

A note on the probabilistic analysis of patricia trees

We consider random PATRICIA trees constructed from n i.i.d. sequences of independent equiprobable bits. We study the height H_n (the maximal distance between the root and a leaf), and the minimal fill-up level F_n (the minimum distance between the root and a leaf). We give probabilistic proofs of .     

Biharmonic extensions on trees without positive potentials

Let T be a tree rooted at e endowed with a nearest-neighbor transition probability that yields a recurrent random walk. We show that there exists a function K biharmonic off e whose Laplacian has potential theoretic importance and, in addition, has the following property: Any function f on T which is biharmonic outside a finite set has a representation, unique up to addition of a harmonic function, of the form f=βK+B+L, where β a constant, B is a biharmonic function on T, and L is a function, subject to certain normalization conditions, whose Laplacian is constant on all sectors sufficiently far from the root. We obtain a characterization of the functions biharmonic outside a finite set whose Laplacian has 0 flux similar to one that holds for a function biharmonic outside a compact set in Rn for n=2,3, and 4 proved by Bajunaid and Anandam. Moreover, we extend the definition of flux and, under certain restrictions on the tree, we characterize the functions biharmonic outside a finite set that have finite flux in this extended sense.     

Justifying the small‐world phenomenon via random recursive trees

We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. The advantage of the technique is three‐fold: it is quite simple and provides short proofs, it is applicable to a broad variety of models including those incorporating preferential attachment, and it provides bounds with small constants. We illustrate this by proving, for the first time, logarithmic upper bounds for the diameters of the following well known models: the forest fire model, the copying model, the PageRank‐based selection model, the Aiello‐Chung‐Lu models, the generalized linear preference model, directed scale‐free graphs, the Cooper‐Frieze model, and random unordered increasing k‐trees. Our results shed light on why the small‐world phenomenon is observed in so many real‐world graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 201–224, 2017