Some width function asymptotics for weighted trees
Some width function asymptotics for weighted trees
复制标题
加权树的一些宽度函数渐近
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Qing Zhang
中科院分区：
文献类型：
--
作者：
M. Ossiander;E. Waymire;Qing Zhang
考虑一个总共有n个顶点的带根标签树图τ n。宽度函数将顶点数作为到根φ的距离的函数进行计数。本文计算了两类树图（随机树和确定树）的宽度函数的大n渐近性质，这两类树图分别是：（i）以全子代为条件的Galton-Watson随机树τ n和（ii）一类确定自相似树，其中包含一个“期望”Galton-Watson树（在某种意义上是精确的）.主要成果包括：（i）将Aldous关于Brownian游程的“搜索深度”近似定理推广到加权Galton-Watson树的情形;（ii）推广Troutman和Karlinger关于期望宽度函数的渐近性态的结果并给出涨落律的概率推导;和（iii）宽度函数渐近的一类确定性自相似树的兴趣在研究河网数据。
Consider a rooted labelled tree graph τ n having a total of n vertices. The width function counts the number of vertices as a function of the dis-tance to the root φ . 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 τ 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 gen-eralizes 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.