Random cutting and records in deterministic and random trees
Author:
- 12 December 2005
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 29 (2) , 139-179
Abstract
We study random cutting down of a rooted tree and show that the number of cuts is equal (in distribution) to the number of records in the tree when edges (or vertices) are assigned random labels.Limit theorems are given for this number, in particular when the tree is a random conditioned Galton–Watson tree. We consider both the distribution when both the tree and the cutting (or labels) are random and the case when we condition on the tree.The proofs are based on Aldous' theory of the continuum random tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006Keywords
This publication has 24 references indexed in Scilit:
- Mixed Poisson approximation of node depth distributions in random binary search treesThe Annals of Applied Probability, 2005
- Building uniformly random subtreesRandom Structures & Algorithms, 2004
- The depth first processes of Galton--Watson trees converge to the same Brownian excursionThe Annals of Probability, 2003
- Noncrossing trees are almost conditioned Galton–Watson treesRandom Structures & Algorithms, 2001
- On the profile of random treesRandom Structures & Algorithms, 1997
- Conceptual Proofs of $L$ Log $L$ Criteria for Mean Behavior of Branching ProcessesThe Annals of Probability, 1995
- The Continuum Random Tree IIIThe Annals of Probability, 1993
- On the Altitude of Nodes in Random TreesCanadian Journal of Mathematics, 1978
- An Invariance Principle for Random Walk Conditioned by a Late Return to ZeroThe Annals of Probability, 1976
- Cutting down random treesJournal of the Australian Mathematical Society, 1970