Le jeudi 2 février 2012, à 13 h 30, en la salle 1240 du pavillon Alexandre-Vachon

Cutting down trees with a Markov chainsaw
Louigi Addario-Berry, Université McGill

Let be a uniformly random rooted tree on labels . Removing an edge from separates into two components. Throw away the component not containing the root. Repeat this process until all that is left is the root, and call the number of edge removals (cuts) . In 2003, Panholzer showed that converges in distribution to a Rayleigh random variable; Janson (2005) generalized the result to all critical conditioned Galton-Watson trees with finite variance offspring distribution.

We present a new, coupling-based proof of Janson’s result, based on the Markov Chain Tree Theorem (referred to by Aldous as « perhaps the most frequently rediscovered result in probability »). Our approach also yields a novel transformation from Brownian excursion to Brownian bridge.

Travail fait en collaboration avec Nicolas Broutin et Cecilia Holmgren.