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

Iksanov, Alex; Möhle, Martin

Electron. Commun. Probab. 12, 28-35 (2007).

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.

Reviewer: Janos Galambos (Philadelphia)

MSC:

60F05	Central limit and other weak theorems
60G50	Sums of independent random variables; random walks
05C05	Trees

Keywords:

random tree; root; delete edges; distribution of the nember of deletion; recursive formula; coupling; limiting distribution; stable law