Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 9 (2012) open journal systems 


Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation

Svante Janson, Uppsala University


Abstract
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.

AMS 2000 subject classifications: Primary 60C50; secondary 05C05, 60F05, 60J80.

Keywords: Random trees, simply generated trees, Galton–Watson trees, random allocations, balls in boxes, size-biased Galton–Watson tree, random forests.

Creative Common LOGO

Full Text: PDF


Janson, Svante, Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation, Probability Surveys, 9, (2012), 103-252 (electronic). DOI: 10.1214/11-PS188.

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:1011.4121

[2]    D. Aldous, Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 (1991), no. 2, 228–266. MR1102319

[3]    D. Aldous, The continuum random tree I. Ann. Probab. 19 (1991), no. 1, 1–28. MR1085326

[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. MR1166406

[5]    D. Aldous, The continuum random tree III. Ann. Probab. 21 (1993), no. 1, 248–289. MR1207226

[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. MR1641670

[7]    R. Arratia, A. D. Barbour & S. Tavaré, Logarithmic Combinatorial Structures: a Probabilistic Approach, EMS, Zürich, 2003. MR2032426

[8]    K. B. Athreya & P. E. Ney, Branching Processes. Springer-Verlag, Berlin, 1972. MR0373040

[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. MR2247823

[10]    D. Beihoffer, J. Hendry, A. Nijenhuis & S. Wagon, Faster algorithms for Frobenius numbers. Electron. J. Combin. 12 (2005), R27. MR2156681

[11]    J. Bennies & G. Kersting, A random walk approach to Galton–Watson trees. J. Theoret. Probab. 13 (2000), no. 3, 777–803. MR1785529

[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. MR2830693

[13]    P. Bialas & Z. Burda, Phase transition in fluctuating branched geometry. Physics Letters B 384 (1996), 75–80. MR1410422

[14]    P. Bialas, Z. Burda & D. Johnston, Condensation in the backgammon model. Nuclear Physics 493 (1997), 505–516.

[15]    P. Billingsley, Convergence of Probability Measures. Wiley, New York, 1968. MR0233396

[16]    N. H. Bingham, C. M. Goldie & J. L. Teugels, Regular Variation. Cambridge Univ. Press, Cambridge, 1987. MR0898871

[17]    C. W. Borchardt, Ueber eine der Interpolation entsprechende Darstellung der Eliminations-Resultante. J. reine und angewandte Mathematik 57 (1860), 111–121.

[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. MR0008126

[19]    A. V. Boyd, Formal power series and the total progeny in a branching process. J. Math. Anal. Appl. 34 (1971), 565–566. MR0281270

[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. MR0954351

[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. MR1248172

[22]    A. Cayley, A theorem on trees. Quart. J. Math. 23 (1889), 376–378.

[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. MR2243873

[24]    P. Chassaing & G. Louchard, Phase transition for parking blocks, Brownian excursion and coalescence. Random Struct. Alg. 21 (2002), no. 1, 76–119. MR1913079

[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. MR1798284

[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. MR1414285

[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.

[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. MR2469332

[29]    D. Croydon, Scaling limits for simple random walks on random ordered graph trees. Adv. Appl. Probab. 42 (2010), no. 2, 528–558. MR2675115

[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. MR2438812

[31]    A. Dembo & O. Zeitouni, Large Deviations Techniques and Applications. 2nd ed., Springer, New York, 1998. MR1619036

[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. MR1678582

[33]    M. Drmota, Random Trees, Springer, Vienna, 2009. MR2484382

[34]    T. Duquesne, A limit theorem for the contour process of conditioned Galton–Watson trees. Ann. Probab. 31 (2003), no. 2, 996–1027. MR1964956

[35]    B. Durhuus, T. Jonsson & J. F. Wheater, The spectral dimension of generic trees. J. Stat. Phys. 128 (2007), 1237–1260. MR2348795

[36]    M. Dwass, The total progeny in a branching process and a related random walk. J. Appl. Probab. 6 (1969), 682–686. MR0253433

[37]    F. Eggenberger & G. Pólya, Über die Statistik verketteter Vorgänge. Zeitschrift Angew. Math. Mech. 3 (1923), 279–289.

[38]    W. Feller, An Introduction to Probability Theory and its Applications, Volume I, 2nd ed., Wiley, New York, 1957. MR0088081

[39]    W. Feller, An Introduction to Probability Theory and its Applications, Volume II, 2nd ed., Wiley, New York, 1971. MR0270403

[40]    P. Flajolet & R. Sedgewick, Analytic Combinatorics. Cambridge Univ. Press, Cambridge, UK, 2009. MR2483235

[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.

[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. MR2407556

[44]    J. Geiger, Elementary new proofs of classical limit theorems for Galton–Watson processes. J. Appl. Probab. 36 (1999), no. 2, 301–309. MR1724856

[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. MR2086163

[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. MR0062975

[47]    G. R. Grimmett, Random labelled trees and their branching networks. J. Austral. Math. Soc. Ser. A 30 (1980/81), no. 2, 229–237. MR0607933

[48]    G. R. Grimmett, The Random-Cluster Model, Springer, Berlin, 2006. MR2243761

[49]    A. Gut, Probability: A Graduate Course. Springer, New York, 2005. MR2125120

[50]    G. H. Hardy, J. E. Littlewood & G. Pólya, Inequalities. 2nd ed., Cambridge, at the University Press, 1952. MR0046395

[51]    T. E. Harris, A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc. 56 (1960), 13–20. MR0115221

[52]    L. Holst, Two conditional limit theorems with applications. Ann. Statist. 7 (1979), no. 3, 551–557. MR0527490

[53]    L. Holst, A unified approach to limit theorems for urn models. J. Appl. Probab. 16 (1979), 154–162. MR0520945

[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. MR0322926

[55]    S. Janson, Moment convergence in conditional limit theorems. J. Appl. Probab. 38 (2001), no. 2, 421–437. MR1834751

[56]    S. Janson, Asymptotic distribution for the cost of linear probing hashing. Random Struct. Alg. 19 (2001), no. 3–4, 438–471. MR1871562

[57]    S. Janson, Cycles and unicyclic components in random graphs. Combin. Probab. Comput. 12 (2003), 27–52. MR1967484

[58]    S. Janson, Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 (2004), no. 2, 177–245. MR2040966

[59]    S. Janson, Random cutting and records in deterministic and random trees. Random Struct. Alg. 29 (2006), no. 2, 139–179. MR2245498

[60]    S. Janson, Rounding of continuous random variables and oscillatory asymptotics. Ann. Probab. 34 (2006), no. 5, 1807–1826. MR2271483

[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. MR2641443

[62]    S. Janson, Probability asymptotics: notes on notation. Institute Mittag-Leffler Report 12, 2009 spring. arXiv:1108.3924

[63]    S. Janson, Stable distributions. Unpublished notes, 2011. arXiv:1112.0220

[64]    S. Janson, T. Jonsson & S. Ö. Stefánsson, Random trees with superexponential branching weights. J. Phys. A: Math. Theor. 44 (2011), 485002.

[65]    S. Janson, T. Łuczak & A. Ruciński, Random Graphs. Wiley, New York, 2000. MR1782847

[66]    N. L. Johnson & S. Kotz, Urn Models and their Application. Wiley, New York, 1977. MR0488211

[67]    T. Jonsson & S. Ö. Stefánsson, Condensation in nongeneric trees. J. Stat. Phys. 142 (2011), no. 2, 277–313. MR2764126

[68]    O. Kallenberg, Random Measures. Akademie-Verlag, Berlin, 1983. MR0818219

[69]    O. Kallenberg, Foundations of Modern Probability. 2nd ed., Springer, New York, 2002. MR1876169

[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. MR1937012

[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. MR2021211

[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. MR1778765

[73]    D. P. Kennedy, The Galton–Watson process conditioned on the total progeny. J. Appl. Probab. 12 (1975), 800–806. MR0386042

[74]    H. Kesten, Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 4, 425–487. MR0871905

[75]    D. E. Knuth, The Art of Computer Programming. Vol. 3: Sorting and Searching. 2nd ed., Addison-Wesley, Reading, Mass., 1998. MR0445948

[76]    V. F. Kolchin, Random Mappings. Nauka, Moscow, 1984 (Russian). English transl.: Optimization Software, New York, 1986. MR0865130

[77]    V. F. Kolchin, B. A. Sevastyanov & V. P. Chistyakov, Random Allocations. Nauka, Moscow, 1976 (Russian). English transl.: Winston, Washington, D.C., 1978. MR0471016

[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. MR1601737

[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. MR2203728

[81]    J.-F. Le Gall, Random real trees. Ann. Fac. Sci. Toulouse Math. (6) 15 (2006), no. 1, 35–62. MR2225746

[82]    M. R. Leadbetter, G. Lindgren & H. Rootzén, Extremes and Related Properties of Random Sequences and Processes. Springer-Verlag, New York, 1983. MR0691492

[83]    T. Łuczak & B. Pittel, Components of random forests. Combin. Probab. Comput. 1 (1992), no. 1, 35–52. MR1167294

[84]    R. Lyons, R. Pemantle & Y. Peres, Conceptual proofs of Llog L criteria for mean behavior of branching processes. Ann. Probab. 23 (1995), no. 3, 1125–1138. MR1349164

[85]    A. Meir & J. W. Moon, On the altitude of nodes in random trees. Canad. J. Math., 30 (1978), 997–1015. MR0506256

[86]    A. Meir & J. W. Moon, On the maximum out-degree in random trees. Australas. J. Combin. 2 (1990), 147–156. MR1126991

[87]    A. Meir & J. W. Moon, On nodes of large out-degree in random trees. Congr. Numer. 82 (1991), 3–13. MR1152053

[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. MR1199088

[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. MR2135161

[90]    J. W. Moon, On the maximum degree in a random tree. Michigan Math. J. 15 (1968), 429–432. MR0233729

[91]    J. Neveu, Arbres et processus de Galton–Watson. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 2, 199–207. MR0850756

[92]    R. Otter, The number of trees. Ann. of Math. (2) 49 (1948), 583–599. MR0025715

[93]    R. Otter, The multiplicative process. Ann. Math. Statistics 20 (1949), 206–224. MR0030716

[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. MR0461619

[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. MR1361491

[96]    Yu. L. Pavlov, Random Forests. Karelian Centre Russian Acad. Sci., Petrozavodsk, 1996 (Russian). English transl.: VSP, Zeist, The Netherlands, 2000. MR1651128

[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. MR2167801

[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. MR1919856

[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. MR1630413

[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

[102]    S. Sagitov & M. C. Serra, Multitype Bienaymé–Galton–Watson processes escaping extinction. Adv. Appl. Probab. 41 (2009), no. 1, 225–246. MR2514952

[103]    R. P. Stanley, Enumerative Combinatorics, Volume 2. Cambridge Univ. Press, Cambridge, 1999. MR1676282

[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. MR0138139

[106]    L. Takács, Ballots, queues and random graphs. J. Appl. Probab. 26 (1989), no. 1, 103–112. MR0981255

[107]    J.C. Tanner, A derivation of the Borel distribution. Biometrika 48 (1961), 222–224. MR0125648

[108]    J. G. Wendel, Left-continuous random walk and the Lagrange expansion. Amer. Math. Monthly 82 (1975), 494–499. MR0381000

[109]    Herbert S. Wilf, generatingfunctionology. 2nd ed., Academic Press, 1994. MR1277813




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787