×

A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. (English) Zbl 1133.60012

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.

MSC:

60F05 Central limit and other weak theorems
60G50 Sums of independent random variables; random walks
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI EuDML