Consider a rooted labelled tree graph $\tau_n$ having a total of
n vertices. The width function counts the number of vertices as a
function of the distance to the root $\phi$. In this paper we compute large
n asymptotic behavior of the width functions for two classes of tree
graphs (both random and deterministic) of the following types: (i)
Galton-Watson random trees $\tau_n$ conditioned on total progeny and (ii) a
class of deterministic self-similar trees which include an "expected"
Galton-Watson tree in a sense to be made precise. The main results include: (i)
an extension of Aldous's theorem on "search-depth" approximations by
Brownian excursion to the case of weighted Galton-Watson trees; (ii) a
probabilistic derivation which generalizes previous results by Troutman and
Karlinger on the asymptotic behavior of the expected width function and
provides the fluctuation law; and (iii) width function asymptotics for a class
of deterministic self-similar trees of interest in the study of river network
data.
Publié le : 1997-11-14
Classification:
Branching process,
width function,
Brownian excursion,
local time,
occupation time,
self-similar
tree,
60J80,
60J85,
60J55,
60J70
@article{1043862421,
author = {Ossiander, Mina and Waymire, Ed and Zhang, Qing},
title = {Some width function asymptotics for weighted trees},
journal = {Ann. Appl. Probab.},
volume = {7},
number = {1},
year = {1997},
pages = { 972-995},
language = {en},
url = {http://dml.mathdoc.fr/item/1043862421}
}
Ossiander, Mina; Waymire, Ed; Zhang, Qing. Some width function asymptotics for weighted trees. Ann. Appl. Probab., Tome 7 (1997) no. 1, pp. 972-995. http://gdmltest.u-ga.fr/item/1043862421/