Random recursive trees are a well-studied mathematical model for growing networks. Starting from a single node, each new node attaches itself to one of the existing nodes chosen uniformly at random. These trees serve as simplified models for real-world networks like citation graphs, family trees, or spread of information, and researchers care deeply about understanding how their structure evolves. Two natural ways to measure how "deep inside" a tree a node sits are its rank (shortest distance to any dead-end node, called a leaf) and its layer (how many rounds of leaf-removal are needed before the node itself becomes removable). This paper works out the full probability distributions of both quantities in random recursive trees.
The authors derive exact mathematical formulas, expressed as recursive equations, that describe how many nodes fall into each rank or layer category. They find that rank distributions decay very rapidly, following a factorial pattern, meaning nodes with high ranks become vanishingly rare very quickly. Layer distributions decay more gently, following a geometric pattern, so deeper layers thin out at a steady exponential rate. They also prove a property called self-averaging, which means that as the tree grows large, the fraction of nodes at any fixed rank or layer becomes highly predictable and concentrates tightly around its average value, with very little random fluctuation from one realization of the tree to the next.
A notable feature of this work is that the analytical approach does not rely on node labels or the special status of a root node, which are crutches that many earlier studies depended on. Because rank and layer are defined purely in terms of local tree structure rather than the history of how nodes were added, the framework is more broadly applicable to other types of networks beyond random recursive trees. This generality makes the results potentially useful for analyzing depth-related properties in a wider class of complex networks encountered in practice.