A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree (Q2461009): Difference between revisions

In order to isolate the root of a random tree with \(n\) vertices, one deletes an edge at random and repeats the procedure as long as the root is not isolated. The distribution of the number \(X(n)\) of steps in this procedure satisfies a recursive formula, from which the asymptotic distribution of \(X(n)\), with proper normalization, is determined. In the past, analytic methods were used to determine the cited limiting law. The authors of the present paper use a coupling argument, relating \(X(n)\) to a problem of random walks. The limiting law is a stable distribution, for which the characteristic function is explicitly given.