## 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
Full Text: