Random recursive tree

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Random recursive trees are rooted trees with n labeled vertices chosen uniformly from all such trees. The labels 1 to n must decrease along any path to the root, and the children of each node have no fixed order. Every valid tree is equally likely.

Construction: Start with the root labeled 1. For each new label i from 2 to n, attach i to a randomly chosen existing vertex with a smaller label (uniformly among the i−1 current vertices).

Key properties (as n grows large and with high probability):
- The longest path from the root to a leaf (the height) is about e times log n.
- The maximum number of children a node can have (the maximum degree) is about log base 2 of n.
- The distance from the root to the i-th added vertex has expected value about the i-th harmonic number H_i, and the total sum of all root-to-vertex distances is about n log n.
- The expected number of leaves is about n/2, with variance about n/12, so the number of leaves is typically around n/2.

Applications: These trees are used to model phenomena such as disease spread, pyramid schemes, language evolution, and the growth of computer networks.