Precise logarithmic asymptotics for the right tails of some limit random variables for random trees

DOI10.1007/S00026-009-0006-0zbMATH Open1232.60021arXivmath/0701259OpenAlexW2077379817MaRDI QIDQ659772FDOQ659772

Authors: James Allen Fill, Svante Janson 

Publication date: 24 January 2012

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: For certain random variables that arise as limits of functionals of random finite trees, we obtain precise asymptotics for the logarithm of the right-hand tail. Our results are based on the facts (i) that the random variables we study can be represented as functionals of a Brownian excursion and (ii) that a large deviation principle with good rate function is known explicitly for Brownian excursion. Examples include limit distributions of the total path length and of the Wiener index in conditioned Galton-Watson trees (also known as simply generated trees). In the case of Wiener index (where we recover results proved by Svante Janson and Philippe Chassaing by a different method) and for some other examples, a key constant is expressed as the solution to a certain optimization problem, but the constant's precise value remains unknown.

Full work available at URL: https://arxiv.org/abs/math/0701259

Recommendations

• Tail asymptotics of maximums on trees in the critical case
• Almost sure asymptotic expansions for profiles of simply generated random trees
• Limit theorems for random trees.
• Limit theorems for sequences of random trees
• Precise asymptotics in \(\log\log\) law for \(\rho\)-mixing random variables
• Limits of random trees. II
• A functional limit theorem for the profile of random recursive trees
• On tail bounds for random recursive trees
• Tree limits and limits of random trees
• Limits of random trees

zbMATH Keywords

large deviationstail asymptoticsvariational problemsWiener indexBrownian excursionGalton-Watson treestotal path lengthsimply generated families of trees

Mathematics Subject Classification ID

Large deviations (60F10) Brownian motion (60J65) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Gaussian Hilbert Spaces
• Transformations of Wiener integrals under translations
• The rotation correspondence is asymptotically a dilatation
• The Distribution of Heights of Binary Trees and Other Simple Trees
• Excursions in Brownian motion
• The continuum random tree. III
• Limiting distributions for additive functionals on Catalan trees
• Random cutting and records in deterministic and random trees
• Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excur\-sions
• Title not available (Why is that?)
• The distribution of the maximum Brownian excursion
• Left and right pathlengths in random binary trees
• The Wiener Index of simply generated random trees
• Tauberian theorems of exponential type
• Title not available (Why is that?)
• A relation between Brownian bridge and Brownian excursion
• Title not available (Why is that?)
• The center of mass of the ISE and the Wiener index of trees
• A large deviation principle for the Brownian snake
• Some asymptotic properties of the local time of the uniform empirical process
• Title not available (Why is that?)
• The density of the ISE and local limit laws for embedded trees

Cited In (9)

• Cost functionals for large (uniform and simply generated) random trees
• Patterns in random permutations avoiding the pattern 132
• On the joint distribution of the area and the number of peaks for Bernoulli excursions
• The Integral of the Supremum Process of Brownian Motion
• On tail bounds for random recursive trees
• Several topological indices of random caterpillars
• A large deviation principle for the normalized excursion of an \(\alpha\)-stable Lévy process without negative jumps
• The Wiener index of random digital trees
• The sum of powers of subtree sizes for conditioned Galton-Watson trees

This page was built for publication: Precise logarithmic asymptotics for the right tails of some limit random variables for random trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659772)