×

zbMATH — the first resource for mathematics

Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. (English) Zbl 1244.60013
Summary: We give a unified treatment of the limit, as the size tends to infinity, of simply generated random trees, including both the well-known result in the standard case of critical Galton-Watson trees and similar but less well-known results in the other cases (i.e., when no equivalent critical Galton-Watson tree exists). There is a well-defined limit in the form of an infinite random tree in all cases; for critical Galton-Watson trees this tree is locally finite but for the other cases the random limit has exactly one node of infinite degree. The proofs use a well-known connection to a random allocation model that we call balls-in-boxes, and we prove corresponding theorems for this model. This survey paper contains many known results from many different sources, together with some new results.

MSC:
60C05 Combinatorial probability
05C05 Trees
60F05 Central limit and other weak theorems
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] L. Addario-Berry, L. Devroye & S. Janson, Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees. Ann. Probab. , to appear. arXiv: · Zbl 1278.60128 · arxiv.org
[2] D. Aldous, Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 (1991), no. 2, 228-266. · Zbl 0733.60016 · doi:10.1214/aoap/1177005936
[3] D. Aldous, The continuum random tree I. Ann. Probab. 19 (1991), no. 1, 1-28. · Zbl 0722.60013 · doi:10.1214/aop/1176990534
[4] D. Aldous, The continuum random tree II: an overview. Stochastic Analysis (Durham, 1990) , 23-70, London Math. Soc. Lecture Note Ser. 167, Cambridge Univ. Press, Cambridge, 1991. · Zbl 0791.60008 · doi:10.1017/CBO9780511662980.003
[5] D. Aldous, The continuum random tree III. Ann. Probab. 21 (1993), no. 1, 248-289. · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[6] D. Aldous & J. Pitman, Tree-valued Markov chains derived from Galton-Watson processes. Ann. Inst. H. Poincaré Probab. Statist. 34 (1998), no. 5, 637-686. · Zbl 0917.60082 · doi:10.1016/S0246-0203(98)80003-4 · numdam:AIHPB_1998__34_5_637_0 · eudml:77616
[7] R. Arratia, A. D. Barbour & S. Tavaré, Logarithmic Combinatorial Structures: a Probabilistic Approach , EMS, Zürich, 2003. · Zbl 1040.60001
[8] K. B. Athreya & P. E. Ney, Branching Processes . Springer-Verlag, Berlin, 1972.
[9] M. T. Barlow & T. Kumagai, Random walk on the incipient infinite cluster on trees. Illinois J. Math. 50 (2006), no. 1-4, 33-65. · Zbl 1110.60090 · www.math.uiuc.edu
[10] D. Beihoffer, J. Hendry, A. Nijenhuis & S. Wagon, Faster algorithms for Frobenius numbers. Electron. J. Combin. 12 (2005), R27. · Zbl 1077.11085 · emis:journals/EJC/Volume_12/Abstracts/v12i1r27.html · eudml:125373
[11] J. Bennies & G. Kersting, A random walk approach to Galton-Watson trees. J. Theoret. Probab. 13 (2000), no. 3, 777-803. · Zbl 0977.60083 · doi:10.1023/A:1007862612753
[12] E. S. Bernikovich & Yu. L. Pavlov, On the maximum size of a tree in a random unlabelled unrooted forest. Diskret. Mat. 23 (2011), no. 1, 3-20 (Russian). English transl.: Discrete Math. Appl. 21 (2011), no. 1, 1-21. · Zbl 1219.05041 · doi:10.4213/dm1126
[13] P. Bialas & Z. Burda, Phase transition in fluctuating branched geometry. Physics Letters B 384 (1996), 75-80. · doi:10.1016/0370-2693(96)00795-2
[14] P. Bialas, Z. Burda & D. Johnston, Condensation in the backgammon model. Nuclear Physics 493 (1997), 505-516. · Zbl 0942.82033
[15] P. Billingsley, Convergence of Probability Measures . Wiley, New York, 1968. · Zbl 0172.21201
[16] N. H. Bingham, C. M. Goldie & J. L. Teugels, Regular Variation . Cambridge Univ. Press, Cambridge, 1987. · Zbl 0617.26001
[17] C. W. Borchardt, Ueber eine der Interpolation entsprechende Darstellung der Eliminations-Resultante. J. reine und angewandte Mathematik 57 (1860), 111-121. · ERAM 057.1508cj
[18] É. Borel, Sur l’emploi du théorème de Bernoulli pour faciliter le calcul d’une infinité de coefficients. Application au problème de l’attente à un guichet. C. R. Acad. Sci. Paris 214 (1942), 452-456. · Zbl 0026.33002
[19] A. V. Boyd, Formal power series and the total progeny in a branching process. J. Math. Anal. Appl. 34 (1971), 565-566. · Zbl 0212.19701 · doi:10.1016/0022-247X(71)90096-5
[20] V. E. Britikov, Asymptotic number of forests from unrooted trees. Mat. Zametki 43 (1988), no. 5, 672-684, 703 (Russian). English transl.: Math. Notes 43 (1988), no. 5-6, 387-394. · Zbl 0695.05025
[21] R. Carr, W. M. Y. Goh & E. Schmutz, The maximum degree in a random tree and related problems. Random Struct. Alg. 5 (1994), no. 1, 13-24. · Zbl 0797.60015
[22] A. Cayley, A theorem on trees. Quart. J. Math. 23 (1889), 376-378. · JFM 21.0687.01
[23] P. Chassaing & B. Durhuus, Local limit of labeled trees and expected volume growth in a random quadrangulation. Ann. Probab. 34 (2006), no. 3, 879-917. · Zbl 1102.60007 · doi:10.1214/009117905000000774
[24] P. Chassaing & G. Louchard, Phase transition for parking blocks, Brownian excursion and coalescence. Random Struct. Alg. 21 (2002), no. 1, 76-119. · Zbl 1032.60003
[25] P. Chassaing, J.-F. Marckert & M. Yor, The height and width of simple trees. Mathematics and Computer Science (Versailles, 2000) , 17-30, Trends Math., Birkhäuser, Basel, 2000. · Zbl 0965.68067
[26] R. M. Corless, G. H. Gonnet, D. E. Hare, D. J. Jeffrey & D. E. Knuth, On the Lambert W function. Adv. Comput. Math. 5 (1996), no. 4, 329-359. · Zbl 0863.65008 · doi:10.1007/BF02124750
[27] H. Cramér, Sur un noveau théorème-limite de la théorie des probabilités. Les sommes et les fonctions de variables aléatoires , Actualités Scientifiques et Industrielles 736, Hermann, Paris, 1938, pp. 5-23. · JFM 64.0529.01
[28] D. Croydon, Convergence of simple random walks on random discrete trees to Brownian motion on the continuum random tree. Ann. Inst. H. Poincaré Probab. Statist. 44 (2008), no. 6, 987-1019. · Zbl 1187.60083 · doi:10.1214/07-AIHP153 · eudml:78009
[29] D. Croydon, Scaling limits for simple random walks on random ordered graph trees. Adv. Appl. Probab. 42 (2010), no. 2, 528-558. · Zbl 1202.60162 · doi:10.1239/aap/1275055241
[30] D. Croydon & T. Kumagai, Random walks on Galton-Watson trees with infinite variance offspring distribution conditioned to survive. Electron. J. Probab. 13 (2008), no. 51, 1419-1441. · Zbl 1191.60121 · doi:10.1214/EJP.v13-536 · emis:journals/EJP-ECP/_ejpecp/viewarticlec7c7.html · eudml:228659
[31] A. Dembo & O. Zeitouni, Large Deviations Techniques and Applications. 2nd ed., Springer, New York, 1998. · Zbl 0896.60013
[32] L. Devroye, Branching processes and their applications in the analysis of tree structures and tree algorithms. Probabilistic Methods for Algorithmic Discrete Mathematics , eds. M. Habib, C. McDiarmid, J. Ramirez and B. Reed, Springer, Berlin, 1998, pp. 249-314. · Zbl 0924.60077
[33] M. Drmota, Random Trees , Springer, Vienna, 2009. · Zbl 1170.05022
[34] T. Duquesne, A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab. 31 (2003), no. 2, 996-1027. · Zbl 1025.60017 · doi:10.1214/aop/1048516543
[35] B. Durhuus, T. Jonsson & J. F. Wheater, The spectral dimension of generic trees. J. Stat. Phys. 128 (2007), 1237-1260. · Zbl 1136.82006 · doi:10.1007/s10955-007-9348-3
[36] M. Dwass, The total progeny in a branching process and a related random walk. J. Appl. Probab. 6 (1969), 682-686. · Zbl 0192.54401 · doi:10.2307/3212112
[37] F. Eggenberger & G. Pólya, Über die Statistik verketteter Vorgänge. Zeitschrift Angew. Math. Mech. 3 (1923), 279-289. · JFM 49.0382.01
[38] W. Feller, An Introduction to Probability Theory and its Applications, Volume I , 2nd ed., Wiley, New York, 1957. · Zbl 0077.12201
[39] W. Feller, An Introduction to Probability Theory and its Applications, Volume II , 2nd ed., Wiley, New York, 1971. · Zbl 0219.60003
[40] P. Flajolet & R. Sedgewick, Analytic Combinatorics . Cambridge Univ. Press, Cambridge, UK, 2009. · Zbl 1165.05001
[41] S. Franz & F. Ritort, Dynamical solution of a model without energy barriers. Europhysics Letters 31 (1995), 507-512
[42] S. Franz & F. Ritort, Glassy mean-field dynamics of the backgammon model. J. Stat. Phys. 85 (1996), 131-150. · Zbl 0937.82054
[43] I. Fujii & T. Kumagai, Heat kernel estimates on the incipient infinite cluster for critical branching processes. Proceedings of German-Japanese Symposium in Kyoto 2006 , RIMS Kôkyûroku Bessatsu B6 (2008), pp. 8-95. · Zbl 1135.60060
[44] J. Geiger, Elementary new proofs of classical limit theorems for Galton-Watson processes. J. Appl. Probab. 36 (1999), no. 2, 301-309. · Zbl 0942.60071 · doi:10.1239/jap/1032374454
[45] J. Geiger & L. Kauffmann, The shape of large Galton-Watson trees with possibly infinite variance. Random Struct. Alg. 25 (2004), no. 3, 311-335. · Zbl 1071.60078
[46] B. V. Gnedenko & A. N. Kolmogorov, Limit Distributions for Sums of Independent Random Variables . Gosudarstv. Izdat. Tehn.-Teor. Lit., Moscow-Leningrad, 1949 (Russian). English transl.: Addison-Wesley, Cambridge, Mass., 1954. · Zbl 0056.36001
[47] G. R. Grimmett, Random labelled trees and their branching networks. J. Austral. Math. Soc. Ser. A 30 (1980/81), no. 2, 229-237. · Zbl 0455.05028 · doi:10.1017/S1446788700016517
[48] G. R. Grimmett, The Random-Cluster Model , Springer, Berlin, 2006. · Zbl 1122.60087
[49] A. Gut, Probability: A Graduate Course . Springer, New York, 2005. · Zbl 1076.60001
[50] G. H. Hardy, J. E. Littlewood & G. Pólya, Inequalities . 2nd ed., Cambridge, at the University Press, 1952.
[51] T. E. Harris, A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc. 56 (1960), 13-20. · Zbl 0122.36403 · doi:10.1017/S0305004100034241
[52] L. Holst, Two conditional limit theorems with applications. Ann. Statist. 7 (1979), no. 3, 551-557. · Zbl 0406.62008 · doi:10.1214/aos/1176344676
[53] L. Holst, A unified approach to limit theorems for urn models. J. Appl. Probab. 16 (1979), 154-162. · Zbl 0396.60027 · doi:10.2307/3213383
[54] I. A. Ibragimov & Yu. V. Linnik, Independent and Stationary Sequences of Random Variables . Nauka, Moscow, 1965 (Russian). English transl.: Wolters-Noordhoff Publishing, Groningen, 1971. · Zbl 0219.60027
[55] S. Janson, Moment convergence in conditional limit theorems. J. Appl. Probab. 38 (2001), no. 2, 421-437. · Zbl 0990.60017 · doi:10.1239/jap/996986753
[56] S. Janson, Asymptotic distribution for the cost of linear probing hashing. Random Struct. Alg. 19 (2001), no. 3-4, 438-471. · Zbl 0992.68232 · doi:10.1002/rsa.10009
[57] S. Janson, Cycles and unicyclic components in random graphs. Combin. Probab. Comput. 12 (2003), 27-52. · Zbl 1010.05072 · doi:10.1017/S0963548302005412
[58] S. Janson, Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 (2004), no. 2, 177-245. · Zbl 1075.60109 · doi:10.1016/j.spa.2003.12.002
[59] S. Janson, Random cutting and records in deterministic and random trees. Random Struct. Alg. 29 (2006), no. 2, 139-179. · Zbl 1120.05083 · doi:10.1002/rsa.20086
[60] S. Janson, Rounding of continuous random variables and oscillatory asymptotics. Ann. Probab. 34 (2006), no. 5, 1807-1826. · Zbl 1113.60017 · doi:10.1214/009117906000000232
[61] S. Janson, On the asymptotic joint distribution of height and width in random trees, Studia Sci. Math. Hungar. 45 (2008), no. 4, 451-467. · Zbl 1199.60300 · doi:10.1556/SScMath.2007.1064
[62] S. Janson, Probability asymptotics: notes on notation. Institute Mittag-Leffler Report 12, 2009 spring. arXiv: · arxiv.org
[63] S. Janson, Stable distributions. Unpublished notes, 2011. arXiv: · arxiv.org
[64] S. Janson, T. Jonsson & S. Ö. Stefánsson, Random trees with superexponential branching weights. J. Phys. A: Math. Theor. 44 (2011), 485002. · Zbl 1236.05180 · doi:10.1088/1751-8113/44/48/485002
[65] S. Janson, T. Łuczak & A. Ruciński, Random Graphs . Wiley, New York, 2000.
[66] N. L. Johnson & S. Kotz, Urn Models and their Application . Wiley, New York, 1977. · Zbl 0352.60001
[67] T. Jonsson & S. Ö. Stefánsson, Condensation in nongeneric trees. J. Stat. Phys. 142 (2011), no. 2, 277-313. · Zbl 1225.60140 · doi:10.1007/s10955-010-0104-8
[68] O. Kallenberg, Random Measures . Akademie-Verlag, Berlin, 1983.
[69] O. Kallenberg, Foundations of Modern Probability. 2nd ed., Springer, New York, 2002. · Zbl 0996.60001
[70] N. I. Kazimirov, On some conditions for absence of a giant component in the generalized allocation scheme. Diskret. Mat. 14 (2002), no. 2, 107-118 (Russian). English transl.: Discrete Math. Appl. 12 (2002), no. 3, 291-302. · Zbl 1046.60018 · doi:10.4213/dm245
[71] N. I. Kazimirov, Emergence of a giant component in a random permutation with a given number of cycles. Diskret. Mat. 15 (2003), no. 3, 145-159 (Russian). English transl.: Discrete Math. Appl. 13 (2003), no. 5, 523-535. · Zbl 1048.60008 · doi:10.4213/dm212
[72] N. I. Kazimirov & Yu. L. Pavlov, A remark on the Galton-Watson forests. Diskret. Mat. 12 (2000), no. 1, 47-59 (Russian). English transl.: Discrete Math. Appl. 10 (2000), no. 1, 49-62. · Zbl 0967.60088 · doi:10.4213/dm320
[73] D. P. Kennedy, The Galton-Watson process conditioned on the total progeny. J. Appl. Probab. 12 (1975), 800-806. · Zbl 0322.60072 · doi:10.2307/3212730
[74] H. Kesten, Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 4, 425-487. · Zbl 0632.60106 · numdam:AIHPB_1986__22_4_425_0 · eudml:77287
[75] D. E. Knuth, The Art of Computer Programming. Vol. 3: Sorting and Searching . 2nd ed., Addison-Wesley, Reading, Mass., 1998. · Zbl 1178.68372
[76] V. F. Kolchin, Random Mappings . Nauka, Moscow, 1984 (Russian). English transl.: Optimization Software, New York, 1986.
[77] V. F. Kolchin, B. A. Sevast’yanov & V. P. Chistyakov, Random Allocations . Nauka, Moscow, 1976 (Russian). English transl.: Winston, Washington, D.C., 1978.
[78] T. Kurtz, R. Lyons, R. Pemantle & Y. Peres, A conceptual proof of the Kesten-Stigum Theorem for multi-type branching processes. Classical and Modern Branching Processes (Minneapolis, MN, 1994) , IMA Vol. Math. Appl., 84, Springer, New York, 1997, pp. 181-185. · Zbl 0868.60068 · doi:10.1007/978-1-4612-1862-3_14
[79] J.-L. Lagrange, Nouvelle méthode pour résoudre les équations littérales par le moyen des séries. Mémoires de l’Académie royale des Sciences et Belles-Lettres de Berlin , XXIV (1770), 5-73.
[80] J.-F. Le Gall, Random trees and applications. Probab. Surveys 2 (2005), 245-311. · Zbl 1189.60161 · doi:10.1214/154957805100000140 · eudml:229216
[81] J.-F. Le Gall, Random real trees. Ann. Fac. Sci. Toulouse Math. (6) 15 (2006), no. 1, 35-62. · Zbl 1129.60047 · doi:10.5802/afst.1112
[82] M. R. Leadbetter, G. Lindgren & H. Rootzén, Extremes and Related Properties of Random Sequences and Processes . Springer-Verlag, New York, 1983. · Zbl 0518.60021
[83] T. Łuczak & B. Pittel, Components of random forests. Combin. Probab. Comput. 1 (1992), no. 1, 35-52. · Zbl 0793.05109 · doi:10.1017/S0963548300000067
[84] R. Lyons, R. Pemantle & Y. Peres, Conceptual proofs of L log L criteria for mean behavior of branching processes. Ann. Probab. 23 (1995), no. 3, 1125-1138. · Zbl 0840.60077 · doi:10.1214/aop/1176988176
[85] A. Meir & J. W. Moon, On the altitude of nodes in random trees. Canad. J. Math. , 30 (1978), 997-1015. · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0
[86] A. Meir & J. W. Moon, On the maximum out-degree in random trees. Australas. J. Combin. 2 (1990), 147-156. · Zbl 0757.05043
[87] A. Meir & J. W. Moon, On nodes of large out-degree in random trees. Congr. Numer. 82 (1991), 3-13. · Zbl 0765.05039
[88] A. Meir & J. W. Moon, A note on trees with concentrated maximum degrees. Utilitas Math. 42 (1992), 61-64. Coorigendum: Utilitas Math. 43 (1993), 253. · Zbl 0821.05013
[89] N. Minami, On the number of vertices with a given degree in a Galton-Watson tree. Adv. Appl. Probab. 37 (2005), no. 1, 229-264. · Zbl 1075.60113 · doi:10.1239/aap/1113402407
[90] J. W. Moon, On the maximum degree in a random tree. Michigan Math. J. 15 (1968), 429-432. · Zbl 0176.22403 · doi:10.1307/mmj/1029000098
[91] J. Neveu, Arbres et processus de Galton-Watson. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 2, 199-207. · Zbl 0601.60082 · numdam:AIHPB_1986__22_2_199_0 · eudml:77276
[92] R. Otter, The number of trees. Ann. of Math. (2) 49 (1948), 583-599. · Zbl 0032.12601 · doi:10.2307/1969046
[93] R. Otter, The multiplicative process. Ann. Math. Statistics 20 (1949), 206-224. · Zbl 0033.38301 · doi:10.1214/aoms/1177730031
[94] Yu. L. Pavlov, The asymptotic distribution of maximum tree size in a random forest. Teor. Verojatnost. i Primenen. 22 (1977), no. 3, 523-533 (Russian). English transl.: Th. Probab. Appl. 22 (1977), no. 3, 509-520.
[95] Yu. L. Pavlov, The limit distributions of the maximum size of a tree in a random forest. Diskret. Mat. 7 (1995), no. 3, 19-32 (Russian). English transl.: Discrete Math. Appl. 5 (1995), no. 4, 301-315. · Zbl 0842.60085
[96] Yu. L. Pavlov, Random Forests . Karelian Centre Russian Acad. Sci., Petrozavodsk, 1996 (Russian). English transl.: VSP, Zeist, The Netherlands, 2000.
[97] Yu. L. Pavlov, Limit theorems on sizes of trees in a random unlabelled forest. Diskret. Mat. 17 (2005), no. 2, 70-86 (Russian). English transl.: Discrete Math. Appl. 15 (2005), no. 2, 153-170. · doi:10.4213/dm99
[98] Yu. L. Pavlov & E. A. Loseva, Limit distributions of the maximum size of a tree in a random recursive forest. Diskret. Mat. 14 (2002), no. 1, 60-74 (Russian). English transl.: Discrete Math. Appl. 12 (2002), no. 1, 45-59. · Zbl 1054.60005 · doi:10.4213/dm230
[99] J. Pitman, Enumerations of trees and forests related to branching processes and random walks. Microsurveys in Discrete Probability (Princeton, NJ, 1997) , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 41, Amer. Math. Soc., Providence, RI, 1998, pp. 163-180. · Zbl 0908.05027
[100] F. Ritort, Glassiness in a model without energy barriers. Physical Review Letters 75 (1995), 1190-1193.
[101] W. Rudin, Real and Complex Analysis . McGraw-Hill, London, 1970 · Zbl 0194.54703
[102] S. Sagitov & M. C. Serra, Multitype Bienaymé-Galton-Watson processes escaping extinction. Adv. Appl. Probab. 41 (2009), no. 1, 225-246. · Zbl 1161.60031 · doi:10.1239/aap/1240319583
[103] R. P. Stanley, Enumerative Combinatorics, Volume 2 . Cambridge Univ. Press, Cambridge, 1999.
[104] J. J. Sylvester, On the change of systems of independent variables, Quart J. Math. 1 (1857), 42-56.
[105] L. Takács, A generalization of the ballot problem and its application in the theory of queues. J. Amer. Statist. Assoc. 57 (1962), 327-337. · Zbl 0109.36702 · doi:10.2307/2281642
[106] L. Takács, Ballots, queues and random graphs. J. Appl. Probab. 26 (1989), no. 1, 103-112. · Zbl 0673.60012 · doi:10.2307/3214320
[107] J.C. Tanner, A derivation of the Borel distribution. Biometrika 48 (1961), 222-224. · Zbl 0139.35101 · doi:10.1093/biomet/48.1-2.222
[108] J. G. Wendel, Left-continuous random walk and the Lagrange expansion. Amer. Math. Monthly 82 (1975), 494-499. · Zbl 0304.60040 · doi:10.2307/2319745
[109] Herbert S. Wilf, generatingfunctionology . 2nd ed., Academic Press, 1994.
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.