Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-28T08:42:37.250Z Has data issue: false hasContentIssue false
  • English
  • Français

Large deviations for the leaves in some random trees

Part of: Graph theory Limit theorems

Published online by Cambridge University Press:  01 July 2016

Wlodek Bryc ,
David Minda  and
Sunder Sethuraman
Wlodek Bryc*
Affiliation:
University of Cincinnati
David Minda*
Affiliation:
University of Cincinnati
Sunder Sethuraman*
Affiliation:
Iowa State University
*
∗ Postal address: Department of Mathematical Sciences, University of Cincinnati, 2855 Campus Way, PO Box 210025, Cincinnati, OH 45221-0025, USA.
∗ Postal address: Department of Mathematical Sciences, University of Cincinnati, 2855 Campus Way, PO Box 210025, Cincinnati, OH 45221-0025, USA.
∗∗∗∗ Postal address: Department of Mathematics, 396 Carver Hall, Iowa State University, Ames, IA 50011, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

Large deviationcentral limitpreferential attachmentplanar orienteduniformly random treesleavescherriesYulerandom Stirling permutations

MSC classification

Primary: 60F10: Large deviations
Secondary: 05C80: Random graphs
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 41 , Issue 3 , September 2009 , pp. 845 - 873
Copyright
Copyright © Applied Probability Trust 2009 

References

Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys. 74, 47–97.Google Scholar
Aldous, D. J. (2001). Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today. Statist. Sci. 16, 23–34.Google Scholar
Athreya, K. B., Ghosh, A. P. and Sethuraman, S. (2008). Growth of preferential attachment random graphs via continuous-time branching processes. Proc. Indian Acad. Sci. 118, 473–494.Google Scholar
Bakhtin, Y. and Heitsch, C. (2008). Large deviations for random trees. J. Statist. Phys. 132, 551–560.Google Scholar
Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.Google Scholar
Benassi, A. (1996). Arbres et grandes déviations. In Trees (Versailles, 1995; Progress Prob. 40), Birkhäuser, Basel, pp. 135–140.Google Scholar
Blum, M. G. B. and François, O. (2005). On statistical tests of phylogenetic tree imbalance: the Sackin and other indices revisited. Math. Biosci. 195, 141–153.Google Scholar
Blum, M. G. B., François, O. and Janson, S. (2006). The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance. Ann. Appl. Prob. 16, 2195–2214.Google Scholar
Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18, 279–290.Google Scholar
Bona, M. (2008/09). Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley. SIAM J. Discrete Math. 23, 401–406.Google Scholar
Bonato, A. (2008). A Course on the Web Graph (Graduate Stud. Math. 89). American Mathematical Society, Providence, RI.Google Scholar
Broutin, N. and Devroye, L. (2006). Large deviations for the weighted height of an extended class of trees. Algorithmica 46, 271–297.Google Scholar
Bryc, W. (1993). A remark on the connection between the large deviation principle and the central limit theorem. Statist. Prob. Lett. 18, 253–256.CrossRefGoogle Scholar
Burckel, R. B. (1979). An Introduction to Classical Complex Analysis. Vol. 1 (Pure Appl. Math. 82) Academic Press, New York.Google Scholar
Chung, F. and Lu, L. (2006). Complex Graphs and Networks (CBMS Regional Conf. Ser. Math. 107). American Mathematical Society, Providence, RI.Google Scholar
Cooper, C. and Frieze, A. (2003). A general model of web graphs. Random Structures Algorithms 22, 311–335.Google Scholar
Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications, 2nd edn. (Appl. Math. 38). Springer, New York.CrossRefGoogle Scholar
Dembo, A., Mörters, P. and Sheffield, S. (2005). Large deviations of Markov chains indexed by random trees. Ann. Inst. H. Poincaré Prob. Statist. 41, 971–996.CrossRefGoogle Scholar
Dereich, S. and Mörters, P. (2009). Random networks with sublinear preferential attachment: degree evolutions. Electron. J. Prob. 14, 1222–1267.CrossRefGoogle Scholar
Dupuis, P. and Ellis, R. S. (1997). A Weak Convergence Approach to the Theory of Large Deviations. John Wiley, New York.CrossRefGoogle Scholar
Dupuis, P., Nuzman, C. and Whiting, P. (2004). Large deviation asymptotics for occupancy problems. Ann. Prob. 32, 2765–2818.Google Scholar
Duren, P. L. (1983). Univalent Functions. Springer, New York.Google Scholar
Durrett, R. (2007). Random Graph Dynamics. Cambridge University Press.Google Scholar
Flajolet, P. and Odlyzko, A. (1990). Singularity analysis of generating functions. SIAM J. Discrete Math. 3, 216–240.Google Scholar
Flajolet, P., Gabarró, J. and Pekari, H. (2005). Analytic urns. Ann. Prob. 33, 1200–1233.CrossRefGoogle Scholar
François, O. and Mioland, C. (2007). Gaussian approximations for phylogenetic branch length statistics under stochastic models of biodiversity. Math. Biosci. 209, 108–123.Google Scholar
Gessel, I. and Stanley, R. P. (1978). Stirling polynomials. J. Combinatorial Theory A 24, 24–33.CrossRefGoogle Scholar
Jabbour-Hattab, J. (1999). Martingales et grandes deviations pour les arbres binaires de recherche. C. R. Acad. Sci. Paris 328, 805–810.CrossRefGoogle Scholar
Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stoch. Process. Appl. 110, 177–245.Google Scholar
Janson, S. (2008). Plane recursive trees, Stirling permutations and an urn model. In Proc. 5th Colloquium Math. Comput. Sci. (Blaubeuren, 2008), Discrete Mathematics and Theoretical Computer Science Proceedings, Nancy, AI, pp. 541–547.Google Scholar
Janson, S., Kuba, M. and Panholzer, A. (2008). Generalized Stirling permutations, families of increasing trees and urn models. Preprint. Available at http://arxiv.org/abs/0805.4084.Google Scholar
Katona, Z. and Móri, T. F. (2006). A new class of scale free random graphs. Statist. Prob. Lett. 76, 1587–1593.CrossRefGoogle Scholar
Kober, H. (1952). Dictionary of Conformal Representations. Dover Publications, New York.Google Scholar
McKenzie, A. and Steel, M. (2000). Distributions of cherries for two models of trees. Math. Biosci. 164, 81–92.Google Scholar
Mitzenmacher, M. (2006). A brief history of generative models for power law and lognormal distributions. Internet Math. 1, 226–251.CrossRefGoogle Scholar
Móri, T. F. (2002). On random trees. Studia Sci. Math. Hung. 39, 143–155.Google Scholar
Najock, D. and Heyde, C. C. (1982). On the number of terminal vertices in certain random trees with an application to stemma construction in philology. J. Appl. Prob. 19, 675–680.Google Scholar
Olver, F. W. J. (1974). Asymptotics and Special Functions. Academic Press, New York.Google Scholar
Rosenberg, N. A. (2006). The mean and variance of the numbers of r-pronged nodes and r-caterpillars in Yule-generated genealogical trees. Ann. Combinatorics 10, 129–146.Google Scholar
Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31, 186–202.Google Scholar
Smythe, R. T. and Mahmoud, H. M. (1994). A survey of recursive trees. Teor. Īmovı¯r. Mat. Statist. 1–29 (in Ukranian). English translation: Theory Prob. Math. Statist. 51, 1-27.Google Scholar
Szymański, J. (1987). On a nonuniform random recursive tree. In Random Graphs (Poznań, 1985; 144 of North-Holland Math. Stud. 144), North-Holland, Amsterdam, pp. 297–306.CrossRefGoogle Scholar
Yule, G. U. (1924). A mathematical theory of evolution, based on the conclusions of Dr. J.C. Willis. Phil. Trans. R. Soc. London B 213, 21–87.Google Scholar
Zhang, J. X. and Dupuis, P. (2008). Large-deviation approximations for general occupancy models. Combin. Prob. Comput. 17, 437–470.Google Scholar