2011arXiv (Cornell University)Open access

Invariance principles for conditioned Galton-Watson trees

Igor Kortchemski

Open full text 5 citations

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. Secondly, 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.

About this research paper

What this paper is about

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. Secondly, 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.

Why it matters

OpenAlex reports 5 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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. Secondly, 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.

Key concepts: Mathematics, Tree (set theory), Combinatorics, Distribution (mathematics), Invariance principle, Degree (music), Mathematical analysis, Physics

Related papers

Back to paper searchBrowse research topicsOriginal source
Invariance principles for conditioned Galton-Watson trees — Research Paper | ScholarLens