Sub-Gaussian tail bounds for the width and height of conditioned Galton--Watson trees
Sub-Gaussian tail bounds for the width and height of conditioned Galton--Watson trees
复制标题
条件高尔顿-沃森树的宽度和高度的亚高斯尾界
DOI：
10.1214/12-aop758
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Janson
中科院分区：
文献类型：
--
作者：
L. Addario;L. Devroye;S. Janson
我们研究了一个Galton- Watson树的高度和宽度，其子代分布B满足E(B)= 1,0 < Var(B) <∞，条件是恰好有n个节点。在此条件下，我们导出了宽度（任何级别中节点的最大数量）和高度（包含节点的最大级别）的亚高斯尾界；直到指数中的常数因子，边界都是最优的。在相同的条件下，对于1 <= k <= n，我们还导出了k级节点数的本质最优上尾界。
We study the height and width of a Galton--Watson tree with offspring distribution B satisfying E(B)=1, 0 < Var(B) < infinity, conditioned on having exactly n nodes. Under this conditioning, we derive sub-Gaussian tail bounds for both the width (largest number of nodes in any level) and height (greatest level containing a node); the bounds are optimal up to constant factors in the exponent. Under the same conditioning, we also derive essentially optimal upper tail bounds for the number of nodes at level k, for 1 <= k <= n.