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
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2011952756 / rank | |||
Normal rank |
Latest revision as of 11:20, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree |
scientific article |
Statements
A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree (English)
0 references
19 November 2007
0 references
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.
0 references
random tree
0 references
root
0 references
delete edges
0 references
distribution of the nember of deletion
0 references
recursive formula
0 references
coupling
0 references
limiting distribution
0 references
stable law
0 references