论文标题
尝试添加功能和边缘树的中心限制定理
Central limit theorems for additive functionals and fringe trees in tries
论文作者
论文摘要
我们为由一系列独立字符串序列产生的随机尝试的渐近正态性提供了一般定理。这些定理用于显示随机trie中随机条纹树的分布的渐近正态性。给出了渐近平均值和方差的公式。特别是，大小$ k $（定义为密钥数）的边缘树的比例是渐近的，忽略了振荡，$ c/（k（k-1））$ $ k \ ge2 $，其中$ c = 1/（1+h）$，带有$ h $ h $ h $。另一个应用程序给出了随机trie中受$ K $保护节点数量的渐近正态性。对于对称的尝试，据表明，受$ K $受保护的节点（忽略振荡）的渐近比例以$ k \ to \ is \ infty $的几何减少。
We give general theorems on asymptotic normality for additive functionals of random tries generated by a sequence of independent strings. These theorems are applied to show asymptotic normality of the distribution of random fringe trees in a random trie. Formulas for asymptotic mean and variance are given. In particular, the proportion of fringe trees of size $k$ (defined as number of keys) is asymptotically, ignoring oscillations, $c/(k(k-1))$ for $k\ge2$, where $c=1/(1+H)$ with $H$ the entropy of the digits. Another application gives asymptotic normality of the number of $k$-protected nodes in a random trie. For symmetric tries, it is shown that the asymptotic proportion of $k$-protected nodes (ignoring oscillations) decreases geometrically as $k\to\infty$.
