Tree-valued Markov chains derived from Galton-Watson processes

David Aldous; Jim Pitman

Annales de l'I.H.P. Probabilités et statistiques (1998)

  • Volume: 34, Issue: 5, page 637-686
  • ISSN: 0246-0203

How to cite


Aldous, David, and Pitman, Jim. "Tree-valued Markov chains derived from Galton-Watson processes." Annales de l'I.H.P. Probabilités et statistiques 34.5 (1998): 637-686. <>.

author = {Aldous, David, Pitman, Jim},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {Galton-Watson trees; inhomogeneous Markov chain; Poisson offspring distribution; Borel distributions; Martin boundary},
language = {eng},
number = {5},
pages = {637-686},
publisher = {Gauthier-Villars},
title = {Tree-valued Markov chains derived from Galton-Watson processes},
url = {},
volume = {34},
year = {1998},

AU - Aldous, David
AU - Pitman, Jim
TI - Tree-valued Markov chains derived from Galton-Watson processes
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 1998
PB - Gauthier-Villars
VL - 34
IS - 5
SP - 637
EP - 686
LA - eng
KW - Galton-Watson trees; inhomogeneous Markov chain; Poisson offspring distribution; Borel distributions; Martin boundary
UR -
ER -


  1. [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. Zbl0913.60067MR1630406
  2. [2] D.J. Aldous, A random tree model associated with random graphs, Random Structures Algorithms, Vol. 1, 1990, pp. 383-402. Zbl0747.05077MR1138431
  3. [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. Zbl0717.05028MR1069105
  4. [4] D.J. Aldous, Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab., Vol. 1, 1991, pp. 228-266. Zbl0733.60016MR1102319
  5. [5] D.J. Aldous, The continuum random tree I, Ann. Probab., Vol. 19, 1991, pp. 1-28. Zbl0722.60013MR1085326
  6. [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. Zbl0791.60008MR1166406
  7. [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, 1997. Zbl0930.60096MR1673235
  8. [8] N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, New York, 1992. Zbl0767.05001MR1140703
  9. [9] K.B. Athreya and P. Ney, Branching Processes, Springer, 1972. Zbl0259.60002MR373040
  10. [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. Zbl0815.60010MR1166603
  11. [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. Zbl0721.60007MR1067027
  12. [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. Zbl0026.33002MR8126JFM68.0276.01
  13. [13] P.C. Consul, Generalized Poisson Distributions, Dekker, 1989. Zbl0691.62015MR974108
  14. [14] N. Dershowitz and S. Zaks, Enumerations of ordered trees, Discrete Mathematics, Vol. 31, 1980, pp. 9-28. Zbl0443.05049MR578057
  15. [15] M. Dwass, The total progeny in a branching process, J. Appl. Probab., Vol. 6, 1969, pp. 682-686. Zbl0192.54401MR253433
  16. [16] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3rd ed., Wiley, New York, 1968. Zbl0155.23101MR228020
  17. [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. Zbl0844.60054MR1278079
  18. [18] L. Gordon, A stochastic approach to the gamma function, Amer. Math. Monthly, Vol. 101, 1994, pp. 858-865. Zbl0823.33001MR1300491
  19. [19] G.R. Grimmett, Random labelled trees and their branching networks, J. Austral. Math. Soc. (Ser. A), Vol. 30, 1980, pp. 229-237. Zbl0455.05028MR607933
  20. [20] H. Haase, On the incipient cluster of the binary tree, Arch. Math. (Basel), Vol. 63, 1994, pp. 465-471. Zbl0807.60088MR1300743
  21. [21] F.A. Haight and M.A. Breuer, The Borel-Tanner distribution, Biometrika, Vol. 47, 1960, pp. 143-150. Zbl0117.14001MR111078
  22. [22] T.E. Harris, The Theory of Branching Processes, Springer-Verlag, New York, 1963. Zbl0117.13002
  23. [23] A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math., Vol. 42, 1981, pp. 1-82. Zbl0491.05007MR633783
  24. [24] D.P. Kennedy, The Galton-Watson process conditioned on the total progeny, J. Appl. Probab., Vol. 12, 1975, pp. 800-806. Zbl0322.60072MR386042
  25. [25] H. Kesten, Subdiffusive behavior of random walk on a random cluster, Ann. Inst. H. PoincaréProbab. Statist., Vol. 22, 1987, pp. 425-487. Zbl0632.60106MR871905
  26. [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. Zbl0401.60082
  27. [27] V.F. Kolchin, Random Mappings, Optimization Software, New York, 1986. (Translation of Russian original). Zbl0605.60010MR865130
  28. [28] G. Labelle, Une nouvelle démonstration combinatoire des formules d'inversion de Lagrange, Adv. in Math., Vol. 42, 1981, pp. 217-247. Zbl0477.05007MR642392
  29. [29] R. Lyons, Random walks, capacity, and percolation on trees, Ann. Probab., Vol. 20, 1992, pp. 2043-2088. Zbl0766.60091MR1188053
  30. [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. Zbl0840.60077MR1349164
  31. [31] R. Lyons and Y. Peres, Probability on trees and networks, Book in preparation, available at, 1996. 
  32. [32] A. Meir and J.W. Moon, The distance between points in random trees, J. Comb. Theory, Vol. 8, 1970, pp. 99-103. Zbl0185.47001MR263685
  33. [33] J.W. Moon, A problem on random trees, J. Comb. Theory B, Vol. 10, 1970, pp. 201-205. Zbl0175.20903MR276133
  34. [34] J. Neveu, Arbres et processus de Galton-Watson, Ann. Inst. H. Poincaré Probab. Statist., Vol. 22, 1986, pp. 199-207. Zbl0601.60082MR850756
  35. [35] R. Otter, The multiplicative process, Ann. Math. Statist., Vol. 20, 1949, pp. 206-224. Zbl0033.38301MR30716
  36. [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. Zbl0358.60033MR433559
  37. [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. Zbl0866.60058MR1410532
  38. [38] J. Pitman, Coalescent random forests, Technical Report 457, Dept. Statistics, U.C. Berkeley, 1996. Available via To appear in J. Comb. Theory A. Zbl0918.05042MR1673928
  39. [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. Zbl0908.05027MR1630413
  40. [40] C.R. Rao and H. Rubin, On a characterization of the Poisson distribution, Sankhyā, Ser. A, Vol. 26, 1964, pp. 294-298. Zbl0137.36604MR184320
  41. [41] L.C.G. Rogers and D. Williams, Diffusions, Markov Processes and Martingales, Vol. I: Foundations, Wiley, 1994, 2nd. edition. Zbl0826.60002MR1331599
  42. [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. [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. [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. [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. Zbl0805.60012MR1274725
  46. [46] R. Stanley, Enumerative combinatorics, Vol. 2, Book in preparation, to be published by Cambridge University Press, 1996. MR1676282
  47. [47] L. Takács, Queues, random graphs and branching processes, J. Applied Mathematics and Simulation, Vol. 1, 1988, pp. 223-243. Zbl0655.60088MR964808
  48. [48] L. Takács, Limit distributions for queues and random rooted trees, J. Applied Mathematics and Stochastic Analysis, Vol. 6, 1993, pp. 189-216. Zbl0791.60084MR1238599
  49. [49] J.C. Tanner, A problem of interference between two queues, Biometrika, Vol. 40, 1953, pp. 58-69. Zbl0053.40705MR55622
  50. [50] J.C. Tanner, A derivation of the Borel distribution, Biametrika, Vol. 48, 1961, pp. 222- 224. Zbl0139.35101MR125648
  51. [51] S.S. Wilks, Certain generalizations in the analysis of variance, Biometrika, Vol. 24, 1932, pp. 471-494. Zbl0006.02301JFM58.1172.02

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.