The Strong Convergence of Maximal Degrees in Uniform Random Recursive Trees and Dags
The Strong Convergence of Maximal Degrees in Uniform Random Recursive Trees and Dags
复制标题
均匀随机递归树和DAG中最大度的强收敛性
DOI：
10.1002/rsa.3240070102
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Jiang
中科院分区：
文献类型：
--
作者：
L. Devroye;Jiang
证明了均匀随机递归树的最大度几乎必然是(1+o(1))log2n。通过将每个i>；m的第i个节点与其前辈的r个节点均匀且随机地连接，定义了n个节点上的随机有向无环图。证明了最大次数几乎必然为(1+o(1))log1+1/Rn。
We show that the maximal degree in a uniform random recursive tree is almost surely (1 + o(1)) log2n. A random directed acyclic graph on n nodes is defined by connecting the ith node for each i > m with r of its predecessors uniformly and at random. The maximal degree is shown to be almost surely (1 + o(1))log1+1/rn.