随机树的极值性质。
Extremal properties of random trees.
作者信息
Ben-Naim E, Krapivsky P L, Majumdar S N
机构信息
Theoretical Division and Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA.
出版信息
Phys Rev E Stat Nonlin Soft Matter Phys. 2001 Sep;64(3 Pt 2):035101. doi: 10.1103/PhysRevE.64.035101. Epub 2001 Aug 6.
We investigate extremal statistical properties such as the maximal and the minimal heights of randomly generated binary trees. By analyzing the master evolution equations we show that the cumulative distribution of extremal heights approaches a traveling wave form. The wave front in the minimal case is governed by the small-extremal-height tail of the distribution, and conversely, the front in the maximal case is governed by the large-extremal-height tail of the distribution. We determine several statistical characteristics of the extremal height distribution analytically. In particular, the expected minimal and maximal heights grow logarithmically with the tree size, N, h(min) approximately v(min) ln N, and h(max) approximately v(max) ln N, with v(min)=0.373365ellipsis and v(max)=4.31107ellipsis, respectively. Corrections to this asymptotic behavior are of order O(ln ln N).
我们研究了随机生成的二叉树的极值统计特性，例如最大高度和最小高度。通过分析主演化方程，我们表明极值高度的累积分布趋近于行波形式。在最小高度的情况下，波前由分布的小极值高度尾部决定，相反，在最大高度的情况下，波前由分布的大极值高度尾部决定。我们通过解析确定了极值高度分布的几个统计特征。特别地，预期的最小高度和最大高度随树的大小(N)呈对数增长，(h(min)\approx v(min)\ln N)，(h(max)\approx v(max)\ln N)，其中(v(min)=0.373365\cdots)，(v(max)=4.31107\cdots)。对这种渐近行为的修正为(O(\ln\ln N))阶。
Zotero 插件