CUTTING DOWN TREES WITH A MARKOV CHAINSAW

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

Subject headings

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Publication and Content Type

ref (subject category)

art (subject category)