TY - JOUR

T1 - A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees

AU - Grübel, Rudolf

AU - Kabluchko, Zakhar

N1 - Publisher Copyright: © Institute of Mathematical Statistics, 2016.

PY - 2016/12

Y1 - 2016/12

N2 - Let W∞(β) be the limit of the Biggins martingale Wn(β) associated to a supercritical branching random walk with mean number of offspring m. We prove a functional central limit theorem stating that as n→∞the process {equation presented} 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 {equation presented} where EPLn is the external path length of a binary search tree Xn with n vertices, EPL∞ is the limit of the Régnier martingale and L{.|Gn} denotes the conditional distribution w.r.t. the σ-algebra Gn generated by X1, . . . , Xn. 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 Pólya urn.

AB - Let W∞(β) be the limit of the Biggins martingale Wn(β) associated to a supercritical branching random walk with mean number of offspring m. We prove a functional central limit theorem stating that as n→∞the process {equation presented} 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 {equation presented} where EPLn is the external path length of a binary search tree Xn with n vertices, EPL∞ is the limit of the Régnier martingale and L{.|Gn} denotes the conditional distribution w.r.t. the σ-algebra Gn generated by X1, . . . , Xn. 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 Pólya urn.

KW - Almost sure weak convergence

KW - Binary search trees

KW - Branching random walk

KW - Functional central limit theorem

KW - Galton-Watson processes

KW - Gaussian analytic function

KW - Mixing convergence

KW - Pólya urns

KW - Quicksort distribution

KW - Random recursive trees

KW - Stable convergence

UR - http://www.scopus.com/inward/record.url?scp=85008895093&partnerID=8YFLogxK

U2 - 10.48550/arXiv.1410.0469

DO - 10.48550/arXiv.1410.0469

M3 - Article

AN - SCOPUS:85008895093

VL - 26

SP - 3659

EP - 3698

JO - Annals of Applied Probability

JF - Annals of Applied Probability

SN - 1050-5164

IS - 6

ER -