In probability theory, a random recursive tree is a rooted tree chosen uniformly at random from the recursive trees with a given number of vertices.
Definition and generation.
In a recursive tree with formula_1 vertices, the vertices are labeled by the numbers from formula_2 to formula_1, 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 formula_2, and then for each successive label from formula_5 to formula_1 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 formula_1-vertex random recursive tree has length formula_8.
The maximum number of children of any vertex, i.e., degree, in the tree is, with high probability, formula_9.
The expected distance of the formula_10th vertex from the root is the formula_10th harmonic number, from which it follows by linearity of expectation that the sum of all root-to-vertex path lengths is, with high probability, formula_12.
The expected number of leaves of the tree is formula_13 with variance formula_14, so with high probability the number of leaves is formula_15.
Applications.
 lists several applications of random recursive trees in modeling phenomena including disease spreading, pyramid schemes, the evolution of languages, and the growth of computer networks.
References.
 ;templatestyles src="Reflist/styles.css" / ;