A general limit theorem for recursive algorithms and combinatorial structures
A general limit theorem for recursive algorithms and combinatorial structures
复制标题
递归算法和组合结构的一般极限定理
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
L. Rüschendorf
中科院分区：
文献类型：
--
作者：
Ralph Neininger;L. Rüschendorf
极限定律证明了由收缩方法的递归性质的随机向量，因为它们出现的参数组合结构，如随机树或递归算法，在那里我们使用Zolotarev度量。在比较以前的应用程序中，这种方法的一般转移定理推导出，使我们能够建立一个极限法的基础上的递归结构和渐近的第一和第二时刻的序列。特别是，一般的渐近正态性的结果是由这个定理，通常不能处理更常见的2度量。作为应用，我们可以非常自动地推导出许多渐进极限结果，从尝试或m元搜索树的大小和数字结构中的路径长度到随机递归树的合并排序和参数，这些结果之前已经通过不同的方法一一给出。我们还得到了一个相关的局部密度近似结果以及一个整体近似结果。为了证明这些结果，我们建立了一个平滑的密度距离以及平滑的总变差距离可以从上面估计的Zolotarev度量，这是本文的主要工具。
Limit laws are proven by the contraction method for random vectors of a recursive nature as they arise as parameters of combinatorial structures such as random trees or recursive algorithms, where we use the Zolotarev metric. In comparison to previous applications of this method, a general transfer theorem is derived which allows us to establish a limit law on the basis of the recursive structure and the asymptotics of the first and second moments of the sequence. In particular, a general asymptotic normality result is obtained by this theorem which typically cannot be handled by the more common 2 metrics. As applications we derive quite automatically many asymptotic limit results ranging from the size of tries or m-ary search trees and path lengths in digital structures to mergesort and parameters of random recursive trees, which were previously shown by different methods one by one. We also obtain a related local density approximation result as well as a global approximation result. For the proofs of these results we establish that a smoothed density distance as well as a smoothed total variation distance can be estimated from above by the Zolotarev metric, which is the main tool in this article.