Cutting down trees with a Markov chainsaw

By Louigi Addario-Berry, Nicolas Broutin, Cecilia Holmgren. 2011

48 citations recorded by the source corpus.

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, nonasymptotic 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.

Subfields: Artificial Intelligence, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/60751d65188fa3a4cb22918acf581825ad37c07f