probability theory Probability theory or probability calculus is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expre ...

, a random recursive tree is a

rooted tree In graph theory, a tree is an undirected graph in which any two vertices are connected by path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by path, or equi ...

chosen uniformly at random from the

recursive tree In graph theory, a recursive tree (i.e., unordered tree) is a labeled, rooted tree. A size- recursive tree's vertices are labeled by distinct positive integers , where the labels are strictly increasing starting at the root labeled 1. Recursive ...

s with a given number of vertices.

Definition and generation

In a recursive tree with

n

vertices, the vertices are labeled by the numbers from

1

n

, and the labels must decrease along any path to the root of the tree. These trees are unordered, in the sense that there is no distinguished ordering of the children of each vertex. In a random recursive tree, all such trees are equally likely. Alternatively, a random recursive tree can be generated by starting from a single vertex, the root of the tree, labeled

1

, and then for each successive label from

2

n

choosing a random vertex with a smaller label to be its parent. If each of the choices is uniform and independent of the other choices, the resulting tree will be a random recursive tree.

Properties

With high probability, the longest path from the root to the leaf of an

n

-vertex random recursive tree has length

e\log n

. The maximum number of children of any vertex, i.e., degree, in the tree is, with high probability,

(1\pm o(1))\log_2 n

. The expected distance of the

k

th vertex from the root is the

k

harmonic number In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers: H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac. Starting from , the sequence of harmonic numbers begins: 1, \frac, \frac, \frac, \frac, \dot ...

, from which it follows by

linearity of expectation In probability theory, the expected value (also called expectation, expectancy, expectation operator, mathematical expectation, mean, expectation value, or first moment) is a generalization of the weighted average. Informally, the expected va ...

that the sum of all root-to-vertex path lengths is, with high probability,

(1\pm o(1))n\log n

. The expected number of leaves of the tree is

n/2

with

variance In probability theory and statistics, variance is the expected value of the squared deviation from the mean of a random variable. The standard deviation (SD) is obtained as the square root of the variance. Variance is a measure of dispersion ...

n/12

, so with high probability the number of leaves is

(1\pm o(1))n/2

Applications

lists several applications of random recursive trees in modeling phenomena including disease spreading,

pyramid scheme A pyramid scheme is a business model which, rather than earning money (or providing Return on investment, returns on investments) by sale of legitimate product (business), products to an end consumer, mainly earns money by recruiting new members ...

s, the evolution of languages, and the growth of computer networks.

References

{{reflist, refs= {{citation , last1 = Dobrow , first1 = Robert P. , last2 = Fill , first2 = James Allen , doi = 10.1017/S0963548399003855 , issue = 4 , journal = Combinatorics, Probability and Computing , mr = 1723646 , pages = 317–333 , title = Total path length for random recursive trees , volume = 8 , year = 1999, s2cid = 40574756 {{citation , last1 = Goh , first1 = William , last2 = Schmutz , first2 = Eric , doi = 10.1016/S0377-0427(01)00460-5 , issue = 1 , journal = Journal of Computational and Applied Mathematics , mr = 1910519 , pages = 61–82 , title = Limit distribution for the maximum degree of a random recursive tree , volume = 142 , year = 2002, doi-access = free , bibcode = 2002JCoAM.142...61G {{citation , last = Pittel , first = Boris , doi = 10.1002/rsa.3240050207 , issue = 2 , journal = Random Structures & Algorithms , mr = 1262983 , pages = 337–347 , title = Note on the heights of random recursive trees and random {{mvar, m-ary search trees , volume = 5 , year = 1994 {{citation , last = Zhang , first = Yazhe , doi = 10.1214/14-BJPS252 , issue = 4 , journal = Brazilian Journal of Probability and Statistics , mr = 3397399 , pages = 897–908 , title = On the number of leaves in a random recursive tree , volume = 29 , year = 2015, doi-access = free , url = https://projecteuclid.org/journals/brazilian-journal-of-probability-and-statistics/volume-29/issue-4/On-the-number-of-leaves-in-a-random-recursive-tree/10.1214/14-BJPS252.pdf Trees (graph theory) Random graphs