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), p. 637-686 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{AIHPB_1998__34_5_637_0,
     author = {Aldous, David J. and Pitman, Jim},
     title = {Tree-valued Markov chains derived from Galton-Watson processes},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     volume = {34},
     year = {1998},
     pages = {637-686},
     mrnumber = {1641670},
     zbl = {0917.60082},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIHPB_1998__34_5_637_0}
}

Aldous, David; Pitman, Jim. Tree-valued Markov chains derived from Galton-Watson processes. Annales de l'I.H.P. Probabilités et statistiques, Tome 34 (1998) pp. 637-686. http://gdmltest.u-ga.fr/item/AIHPB_1998__34_5_637_0/

[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 1630406 | Zbl 0913.60067

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

[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 1069105 | Zbl 0717.05028

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

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

[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 1166406 | Zbl 0791.60008

[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 1673235 | Zbl 0930.60096

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

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

[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 1166603 | Zbl 0815.60010

[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 1067027 | Zbl 0721.60007

[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 68.0276.01 | MR 8126 | Zbl 0026.33002

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

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

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

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

[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 1278079 | Zbl 0844.60054

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

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

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

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

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

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

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

[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 871905 | Zbl 0632.60106

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

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

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

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

[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 1349164 | Zbl 0840.60077

[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 263685 | Zbl 0185.47001

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

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

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

[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 433559 | Zbl 0358.60033

[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 1410532 | Zbl 0866.60058

[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 1673928 | Zbl 0918.05042

[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 1630413 | Zbl 0908.05027

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

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

[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 1274725 | Zbl 0805.60012

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

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

[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 1238599 | Zbl 0791.60084

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

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

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