SOME WIDTH FUNCTION ASYMPTOTICS FOR WEIGHTED TREES
成果类型：
Article
署名作者：
Ossiander, Mina; Waymire, Ed; Zhang, Qing
署名单位：
Oregon State University
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
发表日期：
1997
页码：
972-995
关键词：
摘要：
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 tn 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.