Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees (Q1951700): Difference between revisions

For a rooted tree \(T\) (deterministic or random), its width is \(W(T):=\max_{k\geq 0}Z_k(T)\), where \(Z_k(T)\) is the number of nodes at level \(k\), and its height is \(H(T):=\max\{k: Z_k(T)>0\}\). Let \(T_n\) be a critical Galton-Watson tree, conditional on having exactly \(n\) nodes. Assuming that the offspring distribution has finite second moment and is not degenerate at \(1\), the authors prove uniform sub-Gaussian upper tail bounds for \(n^{-1/2}W(T_n)\) and \(n^{-1/2}H(T_n)\) which are optimal up to constant factors in the exponent. As corollaries, bounds for \(\mathbb{E}(W(T_n))^r\) and \(\mathbb{E}(H(T_n))^r\), \(r>0\), are obtained, and upper tail bounds for \(Z_k(T_n)\), \(1\leq k\leq n\), are given. The list of technical tools used includes the breadth-first search and the lexicographic depth-first search of Galton-Watson trees; using a truncated version of the size-biased Galton-Watson trees and exploiting a precise bound for \(\mathbb{P}\{\xi_1+\ldots+\xi_n=n-m\}\), where \(\xi_1,\xi_2,\ldots\) are i.i.d. non-negative integer-valued random variables with mean one and finite variance.