Invariance principles for Galton-Watson trees conditioned on the number of leaves

By Igor Kortchemski. 2011

82 citations recorded by the source corpus.

Abstract We are interested in the asymptotic behavior of critical Galton–Watson trees whose offspring distribution may have infinite variance, which are conditioned on having a large fixed number of leaves. We first find an asymptotic estimate for the probability of a Galton–Watson tree having n leaves. Second, we let t n be a critical Galton–Watson tree whose offspring distribution is in the domain of attraction of a stable law, and conditioned on having exactly n leaves. We show that the rescaled Lukasiewicz path and contour function of t n converge respectively to X exc and H exc , where X exc is the normalized excursion of a strictly stable spectrally positive Levy process and H exc is its associated continuous-time height function. As an application, we investigate the distribution of the maximum degree in a critical Galton–Watson tree conditioned on having a large number of leaves. We also explain how these results can be generalized to the case of Galton–Watson trees which are conditioned on having a large fixed number of vertices with degree in a given set, thus extending results obtained by Aldous, Duquesne and Rizzolo.

Subfields: Artificial Intelligence, Finance, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/33461e96fbde6460a3dbcf8428eff05296a82740

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Finance

In Mathematical Physics

Citations in the corpus

A Simple Proof of Duquesne’s Theorem on Contour Processes of Conditioned Galton–Watson Trees (2011, methodology): “For instance, using the same ideas, we have established invariance theorems for Galton-Watson trees having n vertices whose degrees are prescribed to belong to a fixed subset of the nonnegative integers [15].”
Universal limits of substitution-closed permutation classes (2017, methodology): “[34] I. Kortchemski.”
The Brownian limit of separable permutations (2016, background): “It is known(1) from [11] or [13] that the contours of Schröder trees converge to the Brownian excursion.”
Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set (2011, result): “We note, however, that subsequent to the appearance of a draft of this article on the arXiv [12], Kortchemski obtained similar results by different techniques in [7] and that local (rather than scaling) limits have been obtained in [1].”
Sub-exponential tail bounds for conditioned stable Bienaymé–Galton–Watson trees (2015, background): “1 in [29] for similar arguments), the dominated convergence theorem combined with the local limit theorem (8) yields”