Séminaire de statistique, Université Laval, 2 février 2012

le 30 janvier 2012 à 11:01
Jean-Francois Plante

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 T_n be a uniformly random rooted tree on labels 1,\ldots, n. Removing an edge from T_n separates T_n 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) C_n. In 2003, Panholzer showed that C_n/n^{1/2} 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.