Uniform recursive trees: branching structure and simple random downward walk (Q819045)

Starting with a single node called the root and labeled 1, a random tree with \(k+1\) labeled nodes is recursively defined from the tree with \(k\) labeled nodes by joining a new node labeled \(k+1\) to a randomly chosen previous node for \(k=1,2,\dots\). The random recursive tree with \(n\) nodes has a uniform probability distribution on \((n-1)!\) different labeled rooted trees. The branches of the tree are the remaining connected components when the root is removed. The probability distribution of the frequencies of branches of different sizes \(1,2,\dots,n-1\) is determined, and its limiting properties are studied for increasing \(n\). The results are used to investigate the length of a random walk from the root.