On the degree distribution of the nodes in increasing trees

Simple families of increasing trees can be constructed from simply generated tree families, if one considers for every tree of size n all its increasing labellings, i.e., labellings of the nodes by distinct integers of the set {1,…,n} in such a way that each sequence of labels along any branch starting at the root is increasing. Three such tree families are of particular interest: recursive trees, plane-oriented recursive trees and binary increasing trees. We study the quantity degree of node j in a random tree of size n and give closed formulae for the probability distribution and all factorial moments for those subclass of tree families, which can be constructed via a tree evolution process. Furthermore limiting distribution results of this parameter are given, which completely characterize the phase change behavior depending on the growth of j compared to n.     

Note on the outdegree of a node in random recursive trees

In this note we find the exact probability distribution ofd _n,i , the outdegree of the nodei in a random recursive tree withn nodes, Fori=i _n increasing as a linear function onn, we show thatd _n ,i _n is asymptotically normal.     

An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm

A random recursive tree on n vertices is either a single isolated vertex (for n=1) or is a vertex v_n connected to a vertex chosen uniformly at random from a random recursive tree on n−1 vertices. Such trees have been studied before [R. Smythe, H. Mahmoud, A survey of recursive trees, Theory of Probability and Mathematical Statistics 51 (1996) 1-29] as models of boolean circuits. More recently, Barabási and Albert [A. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509-512] have used modifications of such models to model for the web and other “power-law” networks.A minimum (cardinality) dominating set in a tree can be found in linear time using the algorithm of Cockayne et al. [E. Cockayne, S. Goodman, S. Hedetniemi, A linear algorithm for the domination number of a tree, Information Processing Letters 4 (1975) 41-44]. We prove that there exists a constant d?0.3745… such that the size of a minimum dominating set in a random recursive tree on n vertices is dn+o(n) with probability approaching one as n tends to infinity. The result is obtained by analysing the algorithm of Cockayne, Goodman and Hedetniemi.     

Level of nodes in increasing trees revisited

Simply generated families of trees are described by the equation T(z) = ϕ(T(z)) for their generating function. If a tree has n nodes, we say that it is increasing if each node has a label ∈ { 1,…,n}, no label occurs twice, and whenever we proceed from the root to a leaf, the labels are increasing. This leads to the concept of simple families of increasing trees. Three such families are especially important: recursive trees, heap ordered trees, and binary increasing trees. They belong to the subclass of very simple families of increasing trees, which can be characterized in 3 different ways. This paper contains results about these families as well as about polynomial families (the function ϕ(u) is just a polynomial). The random variable of interest is the level of the node (labelled) j, in random trees of size n ≥ j. For very simple families, this is independent of n, and the limiting distribution is Gaussian. For polynomial families, we can prove this as well for j,n → ∞ such that n − j is fixed. Additional results are also given. These results follow from the study of certain trivariate generating functions and Hwang's quasi power theorem. They unify and extend earlier results by Devroye, Mahmoud, and others. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

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.     

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.     

Left and Right Length of Paths in Binary Trees or on a Question of Knuth

We consider extended binary trees and study the joint right and left depth of leaf j, where the leaves are labelled from left to right by 0, 1, . . . , n, and the joint right and left external pathlength of binary trees of size n. Under the random tree model, i.e., the Catalan model, we characterize the joint limiting distribution of the suitably scaled left depth and the difference between the right and the left depth of leaf j in a random size-n binary tree when j ~ ρn with 0 < ρ > 1, as well as the joint limiting distribution of the suitably scaled left external pathlength and the difference between the right and the left external pathlength of a random size-n binary tree. This work was supported by the Austrian Science Foundation FWF, grant S9608-N13.     

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.     

Recursive functions on conditional Galton‐Watson trees

A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicitly specified random element U. The value of the root is the key quantity of interest in general. In this study, all node values and function values are in a finite set S. In this note, we describe the limit behavior when the leaf values are drawn independently from a fixed distribution on S, and the tree T_n is a random Galton‐Watson tree of size n.     

Cutting down very simple trees

We study here, by using a recursive approach, the number of random cuts that are necessary to destroy a random tree of size n for simply generated tree families. Crucial for the applicability of such a recursive approach is a "randomness-preservation" property when cutting off a random edge. We can fully characterize the subclass of simply generated tree families, which satisfy this property and show then for for all these tree families that the number of random cuts to destroy a random size-n tree is asymptotically, for n → ∞, Rayleigh distributed.     

Some properties of random walk paths

For random walk on the d-dimensional integer lattice we consider again the problem of deciding when a set is recurrent, that is visited infinitely often with probability one by the random walk in question. Some special cases are considered, among them the following: for d = 2, what sequences (n_j) have the property that with probability one the random walk visits the origin for infinitely many n_j. A related problem, which is however not a special case of the recurrence problem, is to decide for what sequences (n_j) the states visited by the random walk at times n_j are all distinct, with only a finite number of exceptions. This problem is dealt with in the final part of the paper.     

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

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.     

Convergence of Point Processes with Weakly Dependent Points

For each n≥1, let {X _j,n }_1≤j≤n be a sequence of strictly stationary random variables. In this article, we give some asymptotic weak dependence conditions for the convergence in distribution of the point process $N_{n}=\sum_{j=1}^{n}\delta_{X_{j,n}}For each n≥1, let {X _j,n }_1≤j≤n be a sequence of strictly stationary random variables. In this article, we give some asymptotic weak dependence conditions for the convergence in distribution of the point process N_n=?_j=1ⁿd_Xj,nN_{n}=\sum_{j=1}^{n}\delta_{X_{j,n}} to an infinitely divisible point process. From the point process convergence we obtain the convergence in distribution of the partial sum sequence S _n =∑ _j=1 ⁿ X _j,n to an infinitely divisible random variable whose Lévy measure is related to the canonical measure of the limiting point process. As examples, we discuss the case of triangular arrays which possess known (row-wise) dependence structures, like the strong mixing property, the association, or the dependence structure of a stochastic volatility model.     

The Power of Choice in the Construction of Recursive Trees

The power of choice is known to change the character of random structures and produce desirable optimization effects. We discuss generalizations of random recursive trees, grown under the choice to meet optimization criteria. Specifically, we discuss the random k-minimal (k-maximal) label recursive tree, where a set of k candidate parents, instead of one as in the usual recursive tree, is selected and the node with minimal (maximal) label among them is assigned as parent for the next node. These models are proposed as alternatives for D’Souza et al. (Eur Phys J B59:535–543, 2007) minimal and maximal depth models. The advantage of the label models is that they are tractable and at the same time provide approximations and bounds for the depth models. For the depth of nodes in label models we give the average behavior and exact distributions involving Stirling’s numbers and derive Gaussian limit laws.     

A note on the flow time and the number of tardy jobs in stochastic open shops

In this note open shops with two machines are considered. The processing time of job j, j = 1, …, n, on machine 1 (2) is a random variable X_j (Y_j), which is exponentially distributed with rate γ (μ). If the completion time of job j is C_j, a waiting cost is incurred of g(C_j), where g is a function that is increasing concave. The preemptive policy that minimizes the total expected waiting cost E(Σg(C_j)) is determined. Two machine open shops with jobs that have random due dates are considered as well. For the case where the due dates D₁,…,D_n are exchangeable, the preemptive policy that minimizes the expected number of tardy jobs is determined.     

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 Distributions for the Number of Inversions in Labelled Tree Families

We consider the so-called simple families of labelled trees, which contain, e.g., ordered, unordered, binary, and cyclic labelled trees as special instances, and study the global and local behaviour of the number of inversions. In particular, we obtain limiting distribution results for the total number of inversions as well as the number of inversions induced by the node labelled j in a random tree of size n.     

Counting labelled trees with given indegree sequence

For a labelled tree on the vertex set [n]:={1,2,…,n}, define the direction of each edge ij to be i→j if i<j. The indegree sequence of T can be considered as a partition λ?n−1. The enumeration of trees with a given indegree sequence arises in counting secant planes of curves in projective spaces. Recently Ethan Cotterill conjectured a formula for the number of trees on [n] with indegree sequence corresponding to a partition λ. In this paper we give two proofs of Cotterill's conjecture: one is “semi-combinatorial” based on induction, the other is a bijective proof.