In this paper, we show a strong relation between the
depth first processes associated to Galton--Watson trees with
finite variance, conditioned by the total progeny: the depth first
walk, the depth first queue process, the height process; a
consequence is that these processes (suitably normalized) converge
to the same Brownian excursion. This provides an alternative proof
of Aldous' one of the convergence of the depth first walk to the
Brownian excursion which does not use the existence of a limit
tree. The methods that we introduce allow one to compute some
functionals of trees or discrete excursions; for example, we
compute the limit law of the process of the height of nodes with a
given out-degree, and the process of the height of nodes, root of
a given subtree.
@article{1055425793,
author = {Marckert, Jean-Fran\c cois and Mokkadem, Abdelkader},
title = {The depth first processes of Galton--Watson trees converge to the same Brownian excursion},
journal = {Ann. Probab.},
volume = {31},
number = {1},
year = {2003},
pages = { 1655-1678},
language = {en},
url = {http://dml.mathdoc.fr/item/1055425793}
}
Marckert, Jean-François; Mokkadem, Abdelkader. The depth first processes of Galton--Watson trees converge to the same Brownian excursion. Ann. Probab., Tome 31 (2003) no. 1, pp. 1655-1678. http://gdmltest.u-ga.fr/item/1055425793/