CUTTING DOWN TREES WITH A MARKOV CHAINSAW

• 成果类型: Article
• 署名作者: Addario-Berry, Louigi; Broutin, Nicolas; Holmgren, Cecilia
• 署名单位: McGill University; Stockholm University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/13-AAP978
• 发表日期: 2014
• 页码: 2297-2339
• 关键词: galton-watson; Brownian bridge; record process; random-walk; nodes

摘要

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.