A diffusion limit for a class of randomly-growing binary trees

A diffusion limit for a class of randomly-growing binary trees
复制标题

一类随机生长二叉树的扩散极限

DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
P. Shields
P. Shields
中科院分区：
--
文献类型：
--
作者：
D. Aldous;P. Shields

文献摘要

被引文献

相似文献

摘要二叉树是通过一次添加一个结点来生长的，高度i处的可用结点以与c-i，c&gt；1成正比的概率被相加。我们建立了向量X(T)=(xi(T))的“强大数定律”和“中心极限定理”，其中xi(T)是在时间t可用的高度i的结点的比例。我们证明，实际上存在一个确定性过程xi(T)使得 $$sum{|xi_i(T)-xi(T)|}{ext{收敛到0 a}}{ext{.s}}{ext{.，}}$$ 这样，如果c2 $$Frc{1}{2}$$ ， $$Z_i^n(T)=2^{n/2}{X_{n+1}(TC^n)-x_{n+1}(TC^n)}，$$ 且锌(T)=(Zin(T))，则锌(T)弱收敛于高斯扩散Z(T)。在无偏抛硬币的情况下，利用J·Ziv的结果建立了一个熵估计过程的渐近正态分布，并得到了树的最大高度的增长结果。
SummaryBinary trees are grown by adding one node at a time, an available node at height i being added with probability proportional to c-i, c>1. We establish both a “strong law of large numbers” and a “central limit theorem” for the vector X(t)=(Xi(t)), where Xi(t) is the proportion of nodes of height i that are available at time t. We show, in fact, that there is a deterministic process xi(t) such that $$sum {|X_i (t) - x_i (t)|} { ext{ converges to 0 a}}{ ext{.s}}{ ext{.,}}$$ and such that if c2 $$ frac{1}{2}$$ , $$Z_i^n (t) = 2^{n/2} { X_{n + 1} (tc^n ) - x_{n + 1} (tc^n )} ,$$ and Zn(t)=(Zin(t)), then Zn(t) converges weakly to a Gaussian diffusion Z(t). The results are applied to establish asymptotic normality in the unbiased coin-tossing case for an entropy estimation procedure due to J. Ziv, and to obtain results on the growth of the maximum height of the tree.