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

Published in at http://dx.doi.org/10.1214/13-AAP978 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• The cut-tree of large Galton-Watson trees and the Brownian CRT

Cited by in corpus (13)

• A note on Gromov-Hausdorff-Prokhorov distance between (locally) compact measure spaces
• The vertex-cut-tree of Galton-Watson trees converging to a stable tree
• Tree limits and limits of random trees
• Cutting edges at random in large recursive trees
• Multiple isolation of nodes in recursive trees
• K-cut on paths and some trees
• Fragmentation of Random Trees
• On moment sequences and mixed Poisson distributions
• Convex minorant trees associated with Brownian paths and the continuum limit of the minimum spanning tree
• $k$-cut model for the Brownian Continuum Random Tree
• The tree search game for two players
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of n-leaf Galton-Watson trees
• Cutting down $\mathbf{p}$-trees and inhomogeneous continuum random trees