A FUNCTIONAL CENTRAL LIMIT THEOREM FOR BRANCHING RANDOM WALKS, ALMOST SURE WEAK CONVERGENCE AND APPLICATIONS TO RANDOM TREES

• 成果类型: Article
• 署名作者: Gruebel, Rudolf; Kabluchko, Zakhar
• 署名单位: Leibniz University Hannover; University of Munster
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/16-AAP1188
• 发表日期: 2016
• 页码: 3659-3698
• 关键词: random-variables; martingales; zeros

摘要

Let W-infinity (beta) be the limit of the Biggins martingale W-n(beta) associated to a supercritical branching random walk with mean number of offspring m. We prove a functional central limit theorem stating that as n -> infinity the process D-n(u) := m(1/2n) (W-infinity(u/root n) - W-n(u/root n)) converges weakly, on a suitable space of analytic functions, to a Gaussian random analytic function with random variance. Using this result, we prove central limit theorems for the total path length of random trees. In the setting of binary search trees, we recover a recent result of R. Neininger [Random Structures Algorithms 46 (2015) 346-361], but we also prove a similar theorem for uniform random recursive trees. Moreover, we replace weak convergence in Neininger's theorem by the almost sure weak (a.s.w.) convergence of probability transition kernels. In the case of binary search trees, our result states that L{root n/2logn(EPL infinity - EPLn - 2n log n/n) vertical bar G(n)} ->(a.s.w)(n -> infinity) {omega bar right arrow N-0,N-1}, where EPLn is the external path length of a binary search tree X-n with n vertices, EPL infinity is the limit of the Regnier martingale and L{.vertical bar G(n)} denotes the conditional distribution w.r.t. the sigma-algebra G(n) generated by X-1, . . . , X-n. Almost sure weak convergence is stronger than weak and even stable convergence. We prove several basic properties of the a.s.w. convergence and study a number of further examples in which the a.s.w. convergence appears naturally. These include the classical central limit theorem for Galton-Watson processes and the Polya urn.