Large deviations for the leaves in some random trees

DOI10.1239/AAP/1253281066MaRDI QIDQ3644307zbMATH OpenOpenAlexFDO

Authors Włodek Bryc, D. Minda, Sunder Sethuraman

Publication date 4 November 2009

Published in Advances in Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

central limitlarge deviationsMarkov chainspreferential attachmentrandom graphsrandom trees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Large deviations (60F10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Large deviation principles and related results are given for a class of Markov chains associated to the "leaves" in random recursive trees and preferential attachment random graphs, as well as the "cherries" in Yule trees. In particular, the method of proof, combining analytic and Dupuis-Ellis type path arguments, allows for an explicit computation of the large deviation pressure.

Recommendations

• Large deviations for random trees
• scientific article; zbMATH DE number 1087333
• scientific article; zbMATH DE number 953136
• Large deviations of the height of a random tree
• Large deviation theorem for branches of the random binary tree in the Horton-Strahler analysis
• Large deviations for the weighted height of an extended class of trees
• Large deviations of Markov chains indexed by random trees
• scientific article; zbMATH DE number 953137
• Limit theorems for random trees.
• scientific article; zbMATH DE number 834695

Cites work

• A Brief History of Generative Models for Power Law and Lognormal Distributions
• A course on the web graph
• A general model of web graphs
• A new class of scale free random graphs
• A remark on the connection between the large deviation principle and the central limit theorem
• Analytic urns
• Complex graphs and networks
• Distributions of cherries for two models of trees
• Emergence of Scaling in Random Networks
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Gaussian approximations for phylogenetic branch length statistics under stochastic models of biodiversity
• Generalized Stirling permutations, families of increasing trees and urn models
• Growth of preferential attachment random graphs via continuous-time branching processes
• scientific article; zbMATH DE number 3811922 (Why is no real title available?)
• scientific article; zbMATH DE number 4053643 (Why is no real title available?)
• scientific article; zbMATH DE number 3676229 (Why is no real title available?)
• scientific article; zbMATH DE number 3474264 (Why is no real title available?)
• scientific article; zbMATH DE number 1153603 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 953136 (Why is no real title available?)
• scientific article; zbMATH DE number 1409903 (Why is no real title available?)
• scientific article; zbMATH DE number 3077948 (Why is no real title available?)
• Large deviation asymptotics for occupancy problems.
• Large deviations for random trees
• Large deviations for the weighted height of an extended class of trees
• Large deviations of Markov chains indexed by random trees
• Large-Deviation Approximations for General Occupancy Models
• Martingales et grandes déviations pour les arbres binaires de recherche
• On random trees
• On statistical tests of phylogenetic tree imbalance: The Sackin and other indices revisited
• On the number of terminal vertices in certain random trees with an application to stemma construction in philology
• Plane recursive trees, Stirling permutations and an urn model
• Random graph dynamics
• Random networks with sublinear preferential attachment: degree evolutions
• Random trees and general branching processes
• Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley
• Singularity Analysis of Generating Functions
• Statistical mechanics of complex networks
• Stirling polynomials
• Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today.
• The degree sequence of a scale-free random graph process
• The mean and variance of the numbers of \(r\)-pronged nodes and \(r\)-caterpillars in Yule-generated genealogical trees
• The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance

Cited in

(12)

• Large deviations for the degree structure in preferential attachment schemes
• Large deviations for generalized Polya urns with arbitrary urn function
• Large deviations of Markov chains indexed by random trees
• Some probability inequalities of least-squares estimator in non linear regression model with strong mixing errors
• scientific article; zbMATH DE number 1087333 (Why is no real title available?)
• Sharp large deviations and concentration inequalities for the number of descents in a random permutation
• Sharp analysis on the joint distribution of the number of descents and inverse descents in a random permutation
• Large deviations for empirical measures of self-interacting Markov chains
• Moderate deviations for the number of descents in a random permutation
• Large deviations for random trees and the branching of RNA secondary structures
• Large deviations for the weighted height of an extended class of trees
• Large deviations for random trees

This page was built for publication: Large deviations for the leaves in some random trees

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