Cutting down trees with a Markov chainsaw

Abstract : We provide simplified proofs for the asymptotic distribution of the number of cuts required to cut down a Galton--Watson tree with critical, finite-variance offspring distribution, conditioned to have total progeny n. Our proof is based on a coupling which yields a precise, non-asymptotic distributional result for the case of uniformly random rooted labeled trees (or, equivalently, Poisson Galton--Watson trees conditioned on their size). Our approach also provides a new, random reversible transformation between Brownian excursion and Brownian bridge.
Type de document :
Article dans une revue
Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2014, 24 (6), pp.2297-2339. 〈10.1214/13-AAP978〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00773364
Contributeur : Nicolas Broutin <>
Soumis le : dimanche 13 janvier 2013 - 16:04:19
Dernière modification le : vendredi 25 mai 2018 - 12:02:03

Lien texte intégral

Identifiants

Collections

Citation

Louigi Addario-Berry, Nicolas Broutin, Cecilia Holmgren. Cutting down trees with a Markov chainsaw. Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2014, 24 (6), pp.2297-2339. 〈10.1214/13-AAP978〉. 〈hal-00773364〉

Partager

Métriques

Consultations de la notice

211