A central limit theorem for almost local additive tree functionals
From MaRDI portal
Publication:2292863
Abstract: An additive functional of a rooted tree is a functional that can be calculated recursively as the sum of the values of the functional over the branches, plus a certain toll function. Janson recently proved a central limit theorem for additive functionals of conditioned Galton-Watson trees under the assumption that the toll function is local, i.e. only depends on a fixed neighbourhood of the root. We extend his result to functionals that are "almost local" in a certain sense, thus covering a wider range of functionals. The notion of almost local functional intuitively means that the toll function can be approximated well by considering only a neighbourhood of the root. Our main result is illustrated by several explicit examples including natural graph theoretic parameters such as the number of independent sets, the number of matchings, and the number of dominating sets. We also cover a functional stemming from a tree reduction process that was studied by Hackl, Heuberger, Kropf, and Prodinger.
Recommendations
- A central limit theorem for additive functionals of increasing trees
- Central limit theorems for additive functionals and fringe trees in tries
- Central limit theorems for additive tree parameters with small toll functions
- A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees
- On central limit theory for random additive functions under weak dependence restrictions
- scientific article; zbMATH DE number 431868
- Functional central limit theorem for random walks in random environment defined on regular trees
- Limiting distributions for additive functionals on Catalan trees
Cites work
- scientific article; zbMATH DE number 1713116 (Why is no real title available?)
- scientific article; zbMATH DE number 3961646 (Why is no real title available?)
- scientific article; zbMATH DE number 3745213 (Why is no real title available?)
- scientific article; zbMATH DE number 3274494 (Why is no real title available?)
- A central limit theorem for additive functionals of increasing trees
- Asymptotic normality of almost local functionals in conditioned Galton-Watson trees
- Central limit theorems for additive tree parameters with small toll functions
- Conditional limit theorems for branching processes
- Correlation of Graph‐Theoretical Indices
- Fringe analysis of plane trees related to cutting and pruning
- Limit laws for functions of fringe trees for binary search trees and random recursive trees
- Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
- On the number of matchings of a tree
- Random Trees
- Random cutting and records in deterministic and random trees
- Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
- Subdiffusive behavior of random walk on a random cluster
- Trees with extremal numbers of dominating sets
- Twelve countings with rooted plane trees
Cited in
(11)- A central limit theorem for additive functionals of increasing trees
- Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees
- The distribution of the number of automorphisms of random trees
- Additive tree functionals with small toll functions and subtrees of random trees
- Limiting distributions for additive functionals on Catalan trees
- Central limit theorems for additive tree parameters with small toll functions
- Central limit theorems for additive functionals and fringe trees in tries
- On general subtrees of a conditioned Galton-Watson tree
- Additive functionals of \(d\)-ary increasing trees
- Asymptotic normality of almost local functionals in conditioned Galton-Watson trees
- A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees
This page was built for publication: A central limit theorem for almost local additive tree functionals
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292863)
