zbMATH — the first resource for mathematics

A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees. (English) Zbl 1367.60028
Authors’ abstract: Let \(W_{\infty }(\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\rightarrow \infty \) the process \[ D_{n}\left( u\right) :=m^{\frac{1}{2}n}\left( W_{\infty }\left( \frac{u}{ \sqrt{n}}\right) -W_{n}\left( \frac{u}{\sqrt{n}}\right) \right) \] 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 Struct. Algorithms 46, No. 2, 346–361 (2015; Zbl 1327.68086)], 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 \[ \mathcal{L}\left\{ \sqrt{\frac{n}{2\log n}}\left( \mathrm{EPL}_{\infty }- \frac{\mathrm{EPL}_{n}-2n\log n}{n}\right) |\mathcal{G}_{n}\right\}@>\mathrm{a.s}.w> n\rightarrow \infty>\left\{ \omega \longmapsto \mathcal{N}_{0,1}\right\}, \] where EPL\(_{n}\) is the external path length of a binary search tree \(X_{n}\) with \(n\) vertices, EPL\(_{\infty }\) is the limit of the Régnier martingale, and \(\mathcal{L}(\cdot |Gn)\) denotes the conditional distribution w.r.t. the \(\sigma \)-algebra \(\mathcal{G}_{n}\) generated by \( X_{1},\ldots ,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 Pólya urn.

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