A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree

Alex Iksanov (National Taras Shevchenko University of Kiev)
Martin Möhle (University of Tuebingen)

Abstract


We present a short probabilistic proof of a weak convergence result for the number of cuts needed to isolate the root of a random recursive tree. The proof is based on a coupling related to a certain random walk.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 28-35

Publication Date: February 28, 2007

DOI: 10.1214/ECP.v12-1253

References

  1. E. Bolthausen, A.-S. Sznitman. On Ruelle's probability cascades and an abstract cavity method. Comm. Math. Phys. 197 (1998), 247-276. Math. Review 99k:60244
  2. M. Drmota, A. Iksanov, M. Möhle, and U. Rösler. Asymptotic results about the total branch length of the Bolthausen-Sznitman coalescent. Stoch. Process. Appl. 117 (2007), to appear.
  3. M. Drmota, A. Iksanov, M. Möhle, and U. Rösler. A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. (2006), Preprint, submitted to Random Structures Algorithms
  4. K.B. Erickson. Strong renewal theorems with infinite mean. Trans. Amer. Math. Soc. 151 (1970), 263-291. Math. Review 42 #3873
  5. J.L. Geluk and L. De Haan. Stable probability distributions and their domains of attraction: a direct approach. Probab. Math. Statist. 20 (2000), 169-188. Math. Review 2001g:60031
  6. K. Hinderer and H. Walk. Anwendung von Erneuerungstheoremen und Taubersätzen für eine Verallgemeinerung der Erneuerungsprozesse. Math. Z. 126 (1972), 95-115. Math. Review 45 #9400
  7. S. Janson. Random records and cuttings in complete binary trees. In: Mathematics and Computer Science III (2004), Birkhäuser, Basel, pp. 241-253. Math. Review 2005i:05034
  8. S. Janson. Random cutting and records in deterministic and random trees. Random Structures Algorithm 29 (2006), 139-179. Math. Review in process
  9. A. Meir and J.W. Moon. Cutting down recursive trees. Math. Biosci. 21 (1974), 173-181. Math. Review number not available. Zentralblatt MATH 0288.05102
  10. M. Möhle. Convergence results for compound Poisson distributions and applications to the standard Luria-Delbrück distribution. J. Appl. Probab. 42 (2005), 620-631. Math. Review 2006e:60032
  11. A. Panholzer. Destruction of recursive trees. In: Mathematics and Computer Science III (2004), Birkhäuser, Basel, pp. 267-280. Math. Review 2005e:60026
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.