A new family of Markov branching trees: the alpha-gamma model

Bo Chen (University of Oxford)
Daniel Ford (Google Inc.)
Matthias Winkel (University of Oxford)


We introduce a simple tree growth process that gives rise to a new two-parameter family of discrete fragmentation trees that extends Ford's alpha model to multifurcating trees and includes the trees obtained by uniform sampling from Duquesne and Le Gall's stable continuum random tree. We call these new trees the alpha-gamma trees. In this paper, we obtain their splitting rules, dislocation measures both in ranked order and in size-biased order, and we study their limiting behaviour.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 400-430

Publication Date: February 9, 2009

DOI: 10.1214/EJP.v14-616


  1. D. Aldous. The continuum random tree. I. Ann. Probab., 19(1):1--28, 1991. Math. Review 91i:60024
  2. D. Aldous. The continuum random tree. III. Ann. Probab., 21(1):248--289, 1993. Math. Review 94c:60015
  3. D. Aldous. Probability distributions on cladograms. In Random discrete structures (Minneapolis, MN, 1993), volume 76 of IMA Vol. Math. Appl., pages 1--18. Springer, New York, 1996. Math. Review 98d:60018
  4. J. Bertoin. Homogeneous fragmentation processes. Probab. Theory Related Fields, 121(3):301--318, 2001. Math. Review 2002j:60127
  5. J. Bertoin. Self-similar fragmentations. Ann. Inst. H. Poincaré Probab. Statist., 38(3):319--340, 2002. Math. Review 2003h:60109
  6. J. Bertoin. Random fragmentation and coagulation processes, volume 102 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006. Math. Review 2007k:60004
  7. T. Duquesne and J.-F. Le Gall. Random trees, Lévy processes and spatial branching processes. Astérisque, (281):vi+147, 2002. Math. Review 2003m:60239
  8. T. Duquesne and J.-F. Le Gall. Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields, 131(4):553--603, 2005. Math. Review 2006d:60123
  9. S. N. Evans, J. Pitman, and A. Winter. Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Related Fields, 134(1):81--126, 2006. Math. Review 2007d:60003
  10. S. N. Evans and A. Winter. Subtree prune and regraft: a reversible real tree-valued Markov process. Ann. Probab., 34(3):918--961, 2006. Math. Review 2007k:60233
  11. W. Feller. An introduction to probability theory and its applications. Vol. I. Third edition. John Wiley & Sons Inc., New York, 1968. Math. Review 0228020
  12. D. J. Ford. Probabilities on cladograms: introduction to the alpha model. 2005. Preprint, arXiv:math.PR/0511246. Math. Review number not available.
  13. A. Greven, P. Pfaffelhuber, and A. Winter. Convergence in distribution of random metric measure spaces (Lambda-coalescent measure trees). Probability Theory and Related Fields -- Online First, DOI 10.1007/s00440-008-0169-3, 2008. Math. Review number not available.
  14. R. C. Griffiths. Allele frequencies with genic selection. J. Math. Biol., 17(1):1--10, 1983. Math. Review 84h:92019
  15. B. Haas and G. Miermont. The genealogy of self-similar fragmentations with negative index as a continuum random tree. Electron. J. Probab., 9:no. 4, 57--97 (electronic), 2004. Math. Review 2004m:60086
  16. B. Haas, G. Miermont, J. Pitman, and M. Winkel. Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models. Ann. Probab., 36(5):1790--1837, 2008. Math. Review 2440924
  17. B. Haas, J. Pitman, and M. Winkel. Spinal partitions and invariance under re-rooting of continuum random trees. Preprint, arXiv:0705.3602, 2007, to appear in Annals of Probability. Math. Review number not available.
  18. D. E. Knuth. The art of computer programming. Vol. 1: Fundamental algorithms. Second printing. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. Math. Review 0286317
  19. P. Marchal. A note on the fragmentation of a stable tree. In Fifth Colloquium on Mathematics and Computer Science, volume AI, pages 489--500. Discrete Mathematics and Theoretical Computer Science, 2008. Math. Review number not available.
  20. P. McCullagh, J. Pitman, and M. Winkel. Gibbs fragmentation trees. Bernoulli, 14(4):988--1002, 2008. Math. Review number not available.
  21. G. Miermont. Self-similar fragmentations derived from the stable tree. I. Splitting at heights. Probab. Theory Related Fields, 127(3):423--454, 2003. Math. Review 2005m:60163
  22. G. Miermont. Self-similar fragmentations derived from the stable tree. II. Splitting at nodes. Probab. Theory Related Fields, 131(3):341--375, 2005. Math. Review 2006e:60107
  23. J. Pitman. Combinatorial stochastic processes, volume 1875 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2006. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7--24, 2002. Math. Review 2008c:60001
  24. J. Pitman and M. Winkel. Regenerative tree growth: binary self-similar continuum random trees and Poisson-Dirichlet compositions. Preprint, arXiv:0803.3098, 2008, to appear in Annals of Probability. Math. Review number not available.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.