Transfer theorems and asymptotic distributional results for m-ary search trees
Transfer theorems and asymptotic distributional results for m-ary search trees
复制标题
多维搜索树的传递定理和渐近分布结果
DOI：
10.1002/rsa.v26:4
复制
发表时间：
2005
影响因子：
1
通讯作者：
Nevin Kapur
中科院分区：
文献类型：
--
作者：
J. A. Fill;Nevin Kapur
我们在 m 元搜索树上的随机排列模型下推导矩的渐近并识别极限分布，以获得满足简单加法形式的递归关系的函数。许多重要的函数，包括空间要求、内部路径长度和所谓的形状函数都属于这个框架。该方法基于建立转移定理，将特定（确定性）递归的输入增长顺序与输出增长顺序联系起来。传递定理与矩量法结合使用来建立极限定律。结果表明： (i) 对于小收费序列 (tn) [粗略地说，tn = O(n1/2)]，如果 m ≤ 26，我们具有渐近正态性；如果 m ≥ 27，我们具有典型的周期性行为； (ii) 对于中等收费序列[粗略地，tn = ω(n1/2) 但 tn = o(n)]，如果 m ≤ m0 （其中 m0 ≥ 26），我们收敛到非正态分布，并且如果 m ≥ m0 + 1，则收敛到典型的周期性行为； (iii) 对于大型收费序列[粗略地，tn = ω(n)]，我们对于所有 m 值都收敛到非正态分布。 © 2004 Wiley periodicals, Inc. 随机结构。 Alg.，2005年两位作者的研究均由 NSF 拨款 DMS-9803780 和 DMS-0104167 以及约翰·霍普金斯大学的 Acheson J. Duncan 统计研究促进基金支持。研究由 NSF 拨款 0049092 支持，主要在作者隶属于现在的约翰·霍普金斯大学应用数学与统计系时进行大学。
We derive asymptotics of moments and identify limiting distributions, under the random permutation model on m-ary search trees, for functionals that satisfy recurrence relations of a simple additive form. Many important functionals including the space requirement, internal path length, and the so-called shape functional fall under this framework. The approach is based on establishing transfer theorems that link the order of growth of the input into a particular (deterministic) recurrence to the order of growth of the output. The transfer theorems are used in conjunction with the method of moments to establish limit laws. It is shown that: (i) for small toll sequences (tn) [roughly, tn = O(n1/2)] we have asymptotic normality if m ≤ 26 and typically periodic behavior if m ≥ 27; (ii) for moderate toll sequences [roughly, tn = ω(n1/2) but tn = o(n)] we have convergence to nonnormal distributions if m ≤ m0 (where m0 ≥ 26) and typically periodic behavior if m ≥ m0 + 1; and (iii) for large toll sequences [roughly, tn = ω(n)] we have convergence to nonnormal distributions for all values of m. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005Research for both authors supported by NSF Grants DMS-9803780 and DMS-0104167, and by The Johns Hopkins University's Acheson J. Duncan Fund for the Advancement of Research in Statistics.Research supported by NSF Grant 0049092 and carried out primarily while this author was affiliated with what is now the Department of Applied Mathematics and Statistics at The Johns Hopkins University.