Tree-valued Markov chains derived from Galton-Watson processes

Aldous, David; Pitman, Jim

Annales de l'I.H.P. Probabilités et statistiques, Tome 34 (1998) no. 5, pp. 637-686.

[1] D. Aldous, Tree-valued Markov chains and Poisson-Galton-Watson distributions, In D. Aldous and J. Propp, editors, Microsurveys in Discrete Probability, number 41 in DIMACS Ser. Discrete Math. Theoret. Comp. Sci, 1998, pp. 1-20. | MR | Zbl

[2] D.J. Aldous, A random tree model associated with random graphs, Random Structures Algorithms, Vol. 1, 1990, pp. 383-402. | MR | Zbl

[3] D.J. Aldous, The random walk construction of uniform spanning trees and uniform labelled trees, SIAM J. Discrete Math., Vol. 3, 1990, pp. 450-465. | MR | Zbl

[4] D.J. Aldous, Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab., Vol. 1, 1991, pp. 228-266. | MR | Zbl

[5] D.J. Aldous, The continuum random tree I, Ann. Probab., Vol. 19, 1991, pp. 1-28. | MR | Zbl

[6] D.J. Aldous, The continuum random tree II: an overview, In M. T. Barlow and N. H. Bingham, editors, Stochastic Analysis, Cambridge University Press, 1991, pp. 23-70. | MR | Zbl

[7] D.J. Aldous, Deterministic and stochastic models for coalescence: a review of the mean-field theory for probabilists, To appear in Bernoulli. Available via homepage http://www.stat.berkeley.edu/users/aldous, 1997. | MR | Zbl

[8] N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, New York, 1992. | MR | Zbl

[9] K.B. Athreya and P. Ney, Branching Processes, Springer, 1972. | MR | Zbl

[10] S. Berg and J. Jaworski, Probability distributions related to the local structure of a random mapping, In A. Frieze and T. Luczak, editors, Random Graphs, Vol. 2, Wiley, 1992, pp. 1-21. | MR | Zbl

[11] S. Berg and L. Mutafchiev, Random mappings with an attracting center: Lagrangian distributions and a regression function, J. Appl. Probab., Vol. 27, 1990, pp. 622-636. | MR | Zbl

[12] E. Borel, Sur l'emploi du théorème de Bernoulli pour faciliter le calcul d'un infinité de coefficients. Application au probleme de l'attente á un guichet, C. R. Acad. Sci. Paris, Vol. 214, 1942, pp. 452-456. | JFM | MR | Zbl

[13] P.C. Consul, Generalized Poisson Distributions, Dekker, 1989. | MR | Zbl

[14] N. Dershowitz and S. Zaks, Enumerations of ordered trees, Discrete Mathematics, Vol. 31, 1980, pp. 9-28. | MR | Zbl

[15] M. Dwass, The total progeny in a branching process, J. Appl. Probab., Vol. 6, 1969, pp. 682-686. | MR | Zbl

[16] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3rd ed., Wiley, New York, 1968. | MR | Zbl

[17] P. Fitzsimmons, J. Pitman and M. Yor, Markovian bridges: construction, Palm interpretation, and splicing, In E. Çinlar, K.L. Chung, and M.J. Sharpe, editors, Seminar on Stochastic Processes, 1992, Birkhäuser, Boston, 1993, , pp. 101-134. | MR | Zbl

[18] L. Gordon, A stochastic approach to the gamma function, Amer. Math. Monthly, Vol. 101, 1994, pp. 858-865. | MR | Zbl

[19] G.R. Grimmett, Random labelled trees and their branching networks, J. Austral. Math. Soc. (Ser. A), Vol. 30, 1980, pp. 229-237. | MR | Zbl

[20] H. Haase, On the incipient cluster of the binary tree, Arch. Math. (Basel), Vol. 63, 1994, pp. 465-471. | MR | Zbl

[21] F.A. Haight and M.A. Breuer, The Borel-Tanner distribution, Biometrika, Vol. 47, 1960, pp. 143-150. | MR | Zbl

[22] T.E. Harris, The Theory of Branching Processes, Springer-Verlag, New York, 1963. | Zbl

[23] A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math., Vol. 42, 1981, pp. 1-82. | MR | Zbl

[24] D.P. Kennedy, The Galton-Watson process conditioned on the total progeny, J. Appl. Probab., Vol. 12, 1975, pp. 800-806. | MR | Zbl

[25] H. Kesten, Subdiffusive behavior of random walk on a random cluster, Ann. Inst. H. Poincaré Probab. Statist., Vol. 22, 1987, pp. 425-487. | Numdam | MR | Zbl

[26] V.F. Kolchin, Branching processes, random trees, and a generalized scheme of arrangements of particles, Mathematical Notes of the Acad. Sci. USSR, Vol. 21, 1977, pp. 386-394. | Zbl

[27] V.F. Kolchin, Random Mappings, Optimization Software, New York, 1986. (Translation of Russian original). | MR | Zbl

[28] G. Labelle, Une nouvelle démonstration combinatoire des formules d'inversion de Lagrange, Adv. in Math., Vol. 42, 1981, pp. 217-247. | MR | Zbl

[29] R. Lyons, Random walks, capacity, and percolation on trees, Ann. Probab., Vol. 20, 1992, pp. 2043-2088. | MR | Zbl

[30] R. Lyons, R. Pemantle and Y. Peres, Conceptual proof of L log L criteria for mean behavior of branching processes, Ann. Probab., Vol. 23, 1995, pp. 1125-1138. | MR | Zbl

[31] R. Lyons and Y. Peres, Probability on trees and networks, Book in preparation, available at http://www.ma.huji.ac.il/ lyons/prbtree.html, 1996.

[32] A. Meir and J.W. Moon, The distance between points in random trees, J. Comb. Theory, Vol. 8, 1970, pp. 99-103. | MR | Zbl

[33] J.W. Moon, A problem on random trees, J. Comb. Theory B, Vol. 10, 1970, pp. 201-205. | MR | Zbl

[34] J. Neveu, Arbres et processus de Galton-Watson, Ann. Inst. H. Poincaré Probab. Statist., Vol. 22, 1986, pp. 199-207. | Numdam | MR | Zbl

[35] R. Otter, The multiplicative process, Ann. Math. Statist., Vol. 20, 1949, pp. 206-224. | MR | Zbl

[36] A.G. Pakes and T.P. Speed, Lagrange distributions and their limit theorems, SIAM Journal on Applied Mathematics, Vol. 32, 1977, pp. 745-754. | MR | Zbl

[37] R. Pemantle, Uniform random spanning trees, In J. Laurie Snell, editor, Topics in Contemporary Probability, Boca Raton, FL, 1995. CRC Press, pp. 1-54. | MR | Zbl

[38] J. Pitman, Coalescent random forests, Technical Report 457, Dept. Statistics, U.C. Berkeley, 1996. Available via http://www.stat.berkeley.edu/users/pitman. To appear in J. Comb. Theory A. | MR | Zbl

[39] J. Pitman, Enumerations of trees and forests related to branching processes and random walks, in Microsurveys in Discrete Probability edited by D. Aldous and J. Propp. number 41 in DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc., Providence RI, 1998, pp. 163-180. | MR | Zbl

[40] C.R. Rao and H. Rubin, On a characterization of the Poisson distribution, Sankhyā, Ser. A, Vol. 26, 1964, pp. 294-298. | MR | Zbl

[41] L.C.G. Rogers and D. Williams, Diffusions, Markov Processes and Martingales, Vol. I: Foundations, Wiley, 1994, 2nd. edition. | MR | Zbl

[42] R.K. Sheth, Merging and hierarchical clustering from an initially Poisson distribution, Mon. Not. R. Astron. Soc., Vol. 276, 1995, pp. 796-824.

[43] R.K. Sheth, Galton-Watson branching processes and the growth of gravitational clustering, Mon. Not. R. Astron. Soc., Vol. 281, 1996, pp. 1277-1289.

[44] R.K. Sheth and J. Pitman, Coagulation and branching process models of gravitational clustering, Mon. Not. R. Astron. Soc., Vol. 289, 1997, pp. 66-80.

[45] M. Sibuya, N. Miyawaki and U. Sumita, Aspects of Lagrangian probability distributions, Studies in Applied Probability. Essays in Honour of Lajos Takács (J. Appl. Probab.), Vol. 31A, 1994, pp. 185-197. | MR | Zbl

[46] R. Stanley, Enumerative combinatorics, Vol. 2, Book in preparation, to be published by Cambridge University Press, 1996. | MR

[47] L. Takács, Queues, random graphs and branching processes, J. Applied Mathematics and Simulation, Vol. 1, 1988, pp. 223-243. | MR | Zbl

[48] L. Takács, Limit distributions for queues and random rooted trees, J. Applied Mathematics and Stochastic Analysis, Vol. 6, 1993, pp. 189-216. | MR | Zbl

[49] J.C. Tanner, A problem of interference between two queues, Biometrika, Vol. 40, 1953, pp. 58-69. | MR | Zbl

[50] J.C. Tanner, A derivation of the Borel distribution, Biametrika, Vol. 48, 1961, pp. 222- 224. | MR | Zbl

[51] S.S. Wilks, Certain generalizations in the analysis of variance, Biometrika, Vol. 24, 1932, pp. 471-494. | JFM | Zbl