The Horton-Strahler number of conditioned Galton-Watson trees
type: Item
instance of: scholarly article
title: The Horton-Strahler number of conditioned Galton-Watson trees
zbMATH Open document ID: 1485.60009
DOI: 10.1214/21-EJP678
author: Anna Brandenberger
author: Tommy Reddad
author: Luc Devroye
published in: Electronic Journal of Probability
publication date: 2021-11-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/2010.08613
review text: The authors compute the asymptotics of the Horton-Strahler number for critical Galton-Watson trees whose offspring distribution has finite variance, conditioned to have \(n\) vertices, as \(n\to\infty\). The Horton-Strahler number \(H(T)\) -- or register function -- of a rooted tree \(T\) is defined recursively: \begin{itemize} \item a number \(0\) (or \(1\) in the computer science literature) is assigned to each leaf; \item a node with \(k\geq 1\) children having Horton--Strahler numbers \(H_1 \geq H_2 \geq \dots\geq H_k\) is assigned the number \(H_1 + 1_{\{H_1=H_2\}}\); \item \(H(T)\) is defined as the number assigned to the root. \end{itemize} The main result is that if \(T_n\) is a critical Galton-Watson tree whose offspring distribution has finite variance, then \(H(T_n) \sim \frac{1}{2}\log_2(n)\) in probability. This approach extends the results that were obtained in previous works for uniform plane binary trees to other classes of random trees -- for instance, to uniform (plane or non-plane) trees with \(n\) vertices. The main ingredients of the proofs are (a) the local limit of Galton-Watson trees (Kesten's tree), (b) estimates of the tail probability distribution of the Horton-Strahler number of an unconditioned Galton-Watson tree, and (c) the random walk view of a Galton-Watson tree (via its Lukasiewicz encoding) and rotationally invariant events. Finally, generalizations of the Horton-Strahler number are considered, using different recursive rules in their definitions, and studied using similar techniques.
reviewed by: Jean-Jil Duchamps
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 60F05
Mathematics Subject Classification ID: 60J80
zbMATH DE Number: 7424786
zbMATH Keywords: branching processes
zbMATH Keywords: Galton-Watson trees
zbMATH Keywords: Horton-Strahler number
zbMATH Keywords: probabilistic analysis
zbMATH Keywords: register function
MaRDI profile type: MaRDI publication profile
cites work: Q5674726
cites work: Q3154680
cites work: A self-similar invariance of critical binary Galton-Watson trees
cites work: A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees
cites work: Q4256498
cites work: A note on the Horton-Strahler number for random trees
cites work: The register function for \(t\)-ary trees
cites work: The total progeny in a branching process and a related random walk
cites work: On programming of arithmetic operations
cites work: The average height of binary trees and other simple trees
cites work: Register Allocation for Unary–Binary Trees
cites work: The number of registers required for evaluating arithmetic expressions
cites work: Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
cites work: The average number of registers needed to evaluate a binary tree optimally
cites work: The Galton-Watson process conditioned on the total progeny
cites work: Subdiffusive behavior of random walk on a random cluster
cites work: Q5541623
cites work: Q3742402
cites work: Random self-similar trees: a mathematical theory of Horton laws
cites work: On the Altitude of Nodes in Random Trees
cites work: On the Order of Random Channel Networks
cites work: On Horton's Law for Random Channel Networks
cites work: Q4085017
cites work: Local limits of large Galton-Watson trees rerooted at a random vertex
cites work: On Cumulative Sums of Random Variables
cites work: A Large Deviation Rate and Central Limit Theorem for Horton Ratios
cites work: Horton-Strahler ordering of random binary trees
OpenAlex ID: W3203966838
Recommended article: A note on the Horton-Strahler number for random trees
Recommended article: The sum of powers of subtree sizes for conditioned Galton-Watson trees
Recommended article: On general subtrees of a conditioned Galton-Watson tree
Recommended article: On the Number of Trees of a Given Size in a Galton--Watson Forest in the Critical Case
Recommended article: A note on the Horton-Strahler number for random binary search trees
Recommended article: Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
Recommended article: The Galton-Watson tree conditioned on its height
Recommended article: Limit theorems for conditioned non-generic Galton-Watson trees
Recommended article: Invariance principles for Galton-Watson trees conditioned on the number of leaves
Recommended article: Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation (extended abstract)
description: scientific article; zbMATH DE number 7424786