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

DOI10.1214/16-AAP1188zbMATH Open1367.60028arXiv1410.0469OpenAlexW2964043144MaRDI QIDQ511484FDOQ511484

Authors: Rudolf Grübel, Zakhar Kabluchko 

Publication date: 21 February 2017

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: Let $$ be the limit of the Biggins martingale $$ associated to a supercritical branching random walk with mean number of offspring $m$. We prove a functional central limit theorem stating that as $noinfty$ the process ${\displaystyle }$ D_n(u):= m^{frac 12 n} left(W_{infty}left(frac{u}{sqrt n} ight) - W_{n}left(frac{u}{sqrt n} ight) ight) ${\displaystyle }$ 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 [Refined Quicksort Asymptotics, Rand. Struct. and Alg., to appear], 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 ${\displaystyle }$ Lleft{sqrt{frac{n}{2log n}} left(EPL_{infty} - frac{EPL_n-2nlog n}{n} ight)Bigg | G_{n} ight} o {omegamapsto N_{0,1}}, quad ext{a.s.w.},${\displaystyle }$ where $EP{L}_n$ is the external path length of a binary search tree $X_n$ with $n$ vertices, $EP{L}_{infty}$ is the limit of the R'egnier martingale, and $L(,cdot,|G_n)$ denotes the conditional distribution w.r.t. the $sigma$-algebra $G_n$ generated by $X_1,ldots,X_n$. A.s.w. 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'olya urn.

Full work available at URL: https://arxiv.org/abs/1410.0469

Recommendations

• Functional central limit theorem for random walks in random environment defined on regular trees
• The central limit theorem for the supercritical branching random walk, and related results
• Almost sure convergence for stochastically biased random walks on trees
• scientific article; zbMATH DE number 953133
• Almost sure central limit theorem for branching random walks in random environment
• Limit theorems for reinforced random walks on certain trees
• A central limit theorem for almost local additive tree functionals
• Publication:4939961
• A central limit theorem for additive functionals of increasing trees

zbMATH Keywords

functional central limit theoremstable convergenceGalton-Watson processesrandom recursive treesbranching random walks[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=P%EF%BF%BD%EF%BF%BDlya+urns&go=Go P��lya urns]Gaussian analytic functionbinary search treesalmost sure weak convergencemixing convergencequicksort distribution

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Central limit and other weak theorems (60F05) Martingales with discrete parameter (60G42) Sums of independent random variables; random walks (60G50) Searching and sorting (68P10) Functional limit theorems; invariance principles (60F17) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cited In (12)

• Asymptotic expansions in the central limit theorem for a branching Wiener process
• Edgeworth expansions for profiles of lattice branching random walks
• Functional central limit theorem for random walks in random environment defined on regular trees
• A central limit theorem for almost local additive tree functionals
• On \(L^p\)-convergence of the Biggins martingale with complex parameter
• Logarithmic integrals, zeta values, and tiered binomial coefficients
• Branching random walks on binary search trees: convergence of the occupation measure
• Central limit theorems for additive functionals and fringe trees in tries
• On martingale tail sums in affine two-color urn models with multiple drawings
• On martingale tail sums for the path length in random trees
• A central limit theorem for additive functionals of increasing trees
• General Edgeworth expansions with applications to profiles of random trees

This page was built for publication: A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511484)