A general limit theorem for recursive algorithms and combinatorial structures

• 成果类型: Article
• 署名作者: Neininger, R; Rüschendorf, L
• 署名单位: McGill University; University of Freiburg
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2004
• 页码: 378-418
• 关键词: internal path-length; search-trees; contraction method; CONVERGENCE; sums; LAWS; distributions; quickselect; recurrence; mergesort

摘要

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 l(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.