Overview
This research investigates the asymptotic distribution of rare local patterns within critical Bienaymé–Galton-Watson trees, which are conditioned to possess a large number of vertices. The offspring distribution $\mu$ of these trees is specified to be within the domain of attraction of a stable law. The study establishes a general Poisson approximation for the count of these rare patterns under specific conditions, addressing the global dependencies introduced by size conditioning.
Research Context
The core problem addressed is the statistical characterization of rare local patterns occurring in large, size-conditioned Bienaymé–Galton-Watson trees. These trees are critical, meaning their offspring distribution has a mean of 1, and their offspring distribution $\mu$ belongs to the domain of attraction of a stable law. The conditioning on a large number of vertices introduces global dependencies that complicate the analysis of local pattern occurrences. Previous methods for analyzing such patterns faced challenges due to this global dependence, especially when considering non-fringe patterns where occurrences can form clusters.
Approach
The methodology employed in this study combines several techniques to address the challenges posed by size conditioning and pattern clustering:
- Cyclic-shift representation: This technique is utilized to manage the global dependence within the conditioned trees.
- Refined Chen–Stein bound: A more advanced form of the Chen–Stein method is applied to establish Poisson approximation for pattern counts. This method is crucial when the mean count remains bounded.
- Bridge-removal estimate: This estimate is used to control the interaction between a local mark (indicating a pattern) and the remainder of the conditioned random walk. This helps to quantify the independence or dependence of pattern occurrences.
- Declumped indicators: For non-fringe patterns, where overlapping occurrences can form clusters, the researchers introduce "declumped indicators." These indicators are designed to select boundary witnesses of clusters, allowing for a general Poisson approximation for their count. This approach effectively addresses the issue of non-asymptotically Poisson raw counts for non-fringe patterns.
Findings
Poisson Approximation for Fringe Patterns
For patterns defined by a sequence-dependent mark on fringe subtrees, a general Poisson approximation is established for their count. This approximation holds under the following conditions:
- Marked fringe subtrees remain microscopic.
- Nearby marked occurrences exhibit negligible clustering.
- The mean count of these patterns remains bounded, in which case the approximation is asymptotic Poisson in total variation.
If the mean count diverges, the count satisfies a law of large numbers.
Poisson Approximation for Non-Fringe Patterns
For non-fringe patterns, where raw counts may not be asymptotically Poisson due to overlapping occurrences forming clusters, the study introduces declumped indicators. These indicators select specific boundary witnesses within clusters. A general Poisson approximation is demonstrated for the count of these declumped indicators.
Asymptotic Applications
The developed framework yields sharp asymptotics for several specific tree characteristics:
- Maximum leaf-height: This is found to be equivalent to the maximum protection number.
- Height of the largest complete $r$-ary tree: This applies to complete $r$-ary trees appearing as non-fringe subtrees.
Specific findings regarding behavior of maxima include:
- Unary-chain maxima and maximum leaf-height (when $\mu_1 \neq 0$): These exhibit lattice-modulated Gumbel behavior.
- Complete $r$-ary patterns for $r \geq 2$ and maximum leaf-height (when $\mu_1 = 0$): These features are localized on one or two consecutive integers.
Generalizability of Results
The results of this research are applicable even without assuming an exponential moment for the offspring distribution. This includes cases where the offspring distributions may possess infinite variance.