Isolating the most recent entry in a random recursive tree by random cuts (Q1885072)

A tree \(T\) with \(n\) nodes labelled \(1,2,\dots,n\) is a recursive tree (with node 1 as the root) if for each \(k\) between 2 and \(n\) the labels of the nodes in the path from node 1 to node \(k\) form an increasing sequence. If an edge is removed from one of the \((n-1)!\) recursive trees \(T\) with \(n\) nodes, then \(T\) falls into two subtrees one of which contains node \(n\). If we continue to remove edges from the successively smaller subtrees that contain node \(n\) we eventually isolate node \(n\). Let \(\mu(n)\) and \(\sigma^2(n)\) denote the mean and variance of the number of randomly chosen edges removed from a random recursive tree with \(n\) nodes before isolating node \(n\). The authors show that \(\mu(n)\sim n/2\log n\) and that \(\sigma^2(n)= O(\mu^2(n))\). The analogous problem in which the object is to isolate the root node was considered by \textit{A. Meir} and \textit{J. W. Moon} [Math. Biosc. 21, 173--181 (1974; Zbl 0288.05102)].