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

DOI10.1007/S00026-009-0006-0MaRDI QIDQ659772zbMATH OpenOpenAlexFDO

Authors James Allen Fill, Svante Janson

Publication date 24 January 2012

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

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

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)

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.

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

Cites work

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

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)