zbMATH — the first resource for mathematics

On the maximal offspring in a subcritical branching process. (English) Zbl 07252698
Summary: We consider a subcritical Galton-Watson tree \(\mathsf{T}_n^{\Omega}\) conditioned on having \(n\) vertices with outdegree in a fixed set \(\Omega \). The offspring distribution is assumed to have a regularly varying density such that it lies in the domain of attraction of an \(\alpha\)-stable law for \(1<\alpha \le 2\). Our main results consist of a local limit theorem for the maximal degree of \(\mathsf{T}_n^{\Omega}\), and various limits describing the global shape of \(\mathsf{T}_n^{\Omega}\). In particular, we describe the joint behaviour of the fringe subtrees dangling from the vertex with maximal degree. We provide applications of our main results to establish limits of graph parameters, such as the height, the non-maximal vertex outdegrees, and fringe subtree statistics.
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60F17 Functional limit theorems; invariance principles
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI Euclid
[1] R. Abraham and J.-F. Delmas, Local limits of conditioned Galton-Watson trees: the condensation case, Electron. J. Probab., 19 (2014), no. 56, 29. · Zbl 1304.60091
[2] R. Abraham and J.-F. Delmas, Local limits of conditioned Galton-Watson trees: the infinite spine case, Electron. J. Probab., 19 (2014), no. 2, 19. · Zbl 1285.60085
[3] R. Abraham, J.-F. Delmas, and H. He, Pruning Galton-Watson trees and tree-valued Markov processes, Ann. Inst. Henri Poincaré Probab. Stat., 48 (2012), pp. 688-705. · Zbl 1256.60028
[4] L. Addario-Berry, A probabilistic approach to block sizes in random maps, ALEA Lat. Am. J. Probab. Math. Stat., 16 (2019), pp. 1-13. · Zbl 1405.60014
[5] K. S. Alexander and Q. Berger, Local limit theorems and renewal theory with no moments., Electron. J. Probab., 21 (2016), p. 18. Id/No 66. · Zbl 1354.60107
[6] I. Armendáriz and M. Loulakis, Conditional distribution of heavy tailed random variables on large deviations of their sum, Stochastic Process. Appl., 121 (2011), pp. 1138-1147. · Zbl 1218.60021
[7] C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria, Random maps, coalescing saddles, singularity analysis, and Airy phenomena, Random Structures Algorithms, 19 (2001), pp. 194-246. Analysis of algorithms (Krynica Morska, 2000). · Zbl 1016.68179
[8] J. Bertoin, Lévy processes, vol. 121 of Cambridge Tracts in Mathematics, Cambridge University Press, Cambridge, 1996. · Zbl 0861.60003
[9] J. Bertoin, On the maximal offspring in a critical branching process with infinite variance, J. Appl. Probab., 48 (2011), pp. 576-582. · Zbl 0931.41017
[10] J. Bertoin, On largest offspring in a critical branching process with finite variance, J. Appl. Probab., 50 (2013), pp. 791-800. · Zbl 1277.60045
[11] N. Curien and I. Kortchemski, Random non-crossing plane configurations: a conditioned Galton-Watson tree approach, Random Structures Algorithms, 45 (2014), pp. 236-260. · Zbl 1301.05310
[12] N. Curien and I. Kortchemski, Random stable looptrees, Electron. J. Probab., 19 (2014), no. 108, 35. · Zbl 1307.60061
[13] D. Denisov, A. B. Dieker, and V. Shneer, Large deviations for random walks under subexponentiality: the big-jump domain, Ann. Probab., 36 (2008), pp. 1946-1991. · Zbl 1155.60019
[14] L. Devroye, Simulating size-constrained Galton-Watson trees, SIAM J. Comput., 41 (2012), pp. 1-11. · Zbl 1243.65005
[15] T. Duquesne, A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab., 31 (2003), pp. 996-1027. · Zbl 1025.60017
[16] R. Ehrenborg and M. Méndez, Schröder parenthesizations and chordates, J. Combin. Theory Ser. A, 67 (1994), pp. 127-139. · Zbl 0804.05021
[17] W. Feller, An introduction to probability theory and its applications. Vol. II., Second edition, John Wiley & Sons, Inc., New York-London-Sydney, 1971. · Zbl 0219.60003
[18] S. Foss, D. Korshunov, and S. Zachary, An introduction to heavy-tailed and subexponential distributions, Springer Series in Operations Research and Financial Engineering, Springer, New York, second ed., 2013. · Zbl 1274.62005
[19] O. Giménez, M. Noy, and J. Rué, Graph classes with given 3-connected components: asymptotic enumeration and random graphs, Random Structures Algorithms, 42 (2013), pp. 438-479. · Zbl 1269.05060
[20] X. He, Conditioning Galton-Watson trees on large maximal outdegree, J. Theoret. Probab., 30 (2017), pp. 842-851. · Zbl 1386.60292
[21] C. R. Heathcote, E. Seneta, and D. Vere-Jones, A refinement of two theorems in the theory of branching processes, Teor. Verojatnost. i Primenen., 12 (1967), pp. 341-346. · Zbl 0185.44902
[22] I. A. Ibragimov and Y. V. Linnik, Independent and stationary sequences of random variables, Wolters-Noordhoff Publishing, Groningen, 1971. With a supplementary chapter by I. A. Ibragimov and V. V. Petrov, Translation from the Russian edited by J. F. C. Kingman. · Zbl 0219.60027
[23] S. Janson, Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probab. Surv., 9 (2012), pp. 103-252. · Zbl 1296.60234
[24] S. Janson and S. Ö. Stefánsson, Scaling limits of random planar maps with a unique large face, Ann. Probab., 43 (2015), pp. 1045-1081. · Zbl 1320.05112
[25] T. Jonsson and S. Ö. Stefánsson, Condensation in nongeneric trees, J. Stat. Phys., 142 (2011), pp. 277-313. · Zbl 1225.60140
[26] I. Kortchemski, Invariance principles for Galton-Watson trees conditioned on the number of leaves, Stochastic Process. Appl., 122 (2012), pp. 3126-3172. · Zbl 1259.60103
[27] I. Kortchemski, Limit theorems for conditioned non-generic Galton-Watson trees, Ann. Inst. Henri Poincaré Probab. Stat., 51 (2015), pp. 489-511. · Zbl 1315.60091
[28] I. Kortchemski and L. Richier, Condensation in critical Cauchy Bienaymé-Galton-Watson trees, To appear in Ann. Appl. Probab. · Zbl 1427.60178
[29] M. R. Leadbetter, G. Lindgren, and H. Rootzén, Extremes and related properties of random sequences and processes, Springer Series in Statistics, Springer-Verlag, New York-Berlin, 1983. · Zbl 0518.60021
[30] N. Minami, On the number of vertices with a given degree in a Galton-Watson tree, Adv. in Appl. Probab., 37 (2005), pp. 229-264. · Zbl 0931.41017
[31] A. A. Mogul’skij, Local limit theorem for the first crossing time of a fixed level by a random walk., Mat. Tr., 12 (2009), pp. 126-138. · Zbl 0931.41017
[32] E. Neuman and X. Zheng, On the maximal displacement of subcritical branching random walks., Probab. Theory Relat. Fields, 167 (2017), pp. 1137-1164. · Zbl 1374.60170
[33] D. Rizzolo, Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set, Ann. Inst. Henri Poincaré Probab. Stat., 51 (2015), pp. 512-532. · Zbl 1319.60170
[34] F. Spitzer, Principles of random walk, Springer-Verlag, New York-Heidelberg, second ed., 1976. Graduate Texts in Mathematics, Vol. 34. · Zbl 0359.60003
[35] B. Stufler, Limits of random tree-like discrete structures, To appear in Probability Surveys. · Zbl 1454.60019
[36] B. Stufler, Gibbs partitions: The convergent case, Random Structures & Algorithms, 53 (2018), pp. 537-558. · Zbl 0931.41017
[37] H. Sun and L. Zhang, Large deviation principle for the maximal positions in critical branching random walks with small drifts., Stat. Probab. Lett., 139 (2018), pp. 31-39. · Zbl 1391.60215
[38] L. · Zbl 0931.41017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.