A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. (English) Zbl 1187.05068

Drmota, Michael; Iksanov, Alex; Moehle, Martin; Roesler, Uwe

Random Struct. Algorithms 34, No. 3, 319-336 (2009).

Summary: Let \(X_n\) be the number of cuts needed to isolate the root in a random recursive tree with \(n\) vertices. We provide a weak convergence result for \(X_n\). The basic observation for its proof is that the probability distributions of \(\{X_n:n=2,3,\dots\}\) are recursively defined by \(X_n\overset {d}= X_{n-D_n}+1\), \(n=2,3,\dots\), \(X_1=0\), where \(D_n\) is a discrete random variable with \(\mathbb P\{D_n=k\}= \frac{1}{k(k+1)} \frac{n}{n-1}\), \(k=1,2,\dots,n-1\), which is independent of \((X_2,\dots,X_n)\). This distributional recursion was studied previously in the sense of weak convergence.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C05	Trees

Keywords:

recursive tree; stable limiting law; singularity analysis

References:

[1]	Drmota, Asymptotic results about the total branch length of the Bolthausen-Sznitman coalescent, Stoch Proc Appl 117 pp 1404– (2007) · Zbl 1129.60069
[2]	Fill, Destruction of very simple trees, Algorithmica 46 pp 345– (2006) · Zbl 1106.68081
[3]	Gnedin, The Bernoulli sieve, Bernoulli 10 pp 79– (2004) · Zbl 1044.60005
[4]	Iksanov, A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree, Electron Commun Probabil 12 pp 28– (2007) · Zbl 1133.60012 · doi:10.1214/ECP.v12-1253
[5]	Janson, Random records and cuttings in complete binary trees, In Mathematics and Computer Science III pp 241– (2004) · Zbl 1063.60018
[6]	Janson, Random cutting and records in deterministic and random trees, Random Struct Alg 29 pp 139– (2006) · Zbl 1120.05083
[7]	Meir, Cutting down recursive trees, Math Biosci 21 pp 173– (1974) · Zbl 0288.05102
[8]	Neininger, On the contraction method with degenerate limit equation, Ann Probab 32 pp 2838– (2004) · Zbl 1060.60005
[9]	Panholzer, Non-crossing trees revisited: cutting down and spanning subtrees pp 265– (2003) · Zbl 1073.60503
[10]	Panholzer, Destruction of recursive trees, In Mathematics and Computer Science III pp 267– (2004) · Zbl 1060.05022 · doi:10.1007/978-3-0348-7915-6_29
[11]	Panholzer, Cutting down very simple trees, Quaest Math 29 pp 211– (2006) · Zbl 1120.05020 · doi:10.2989/16073600609486160
[12]	Rösler, On the analysis of stochastic divide and conquer algorithms, Algorithmica 29 pp 238– (2001) · Zbl 0967.68168