Details
| Original language | English |
|---|---|
| Pages (from-to) | 3659-3698 |
| Number of pages | 40 |
| Journal | Annals of Applied Probability |
| Volume | 26 |
| Issue number | 6 |
| Publication status | Published - Dec 2016 |
Abstract
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.
Keywords
- Almost sure weak convergence, Binary search trees, Branching random walk, Functional central limit theorem, Galton-Watson processes, Gaussian analytic function, Mixing convergence, Pólya urns, Quicksort distribution, Random recursive trees, Stable convergence
ASJC Scopus subject areas
- Mathematics(all)
- Statistics and Probability
- Decision Sciences(all)
- Statistics, Probability and Uncertainty
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Annals of Applied Probability, Vol. 26, No. 6, 12.2016, p. 3659-3698.
Research output: Contribution to journal › Article › Research › peer review
}
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 -