A new family of Markov branching trees: the alpha-gamma model
Daniel Ford (Google Inc.)
Matthias Winkel (University of Oxford)
Abstract
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
References
- D. Aldous. The continuum random tree. I. Ann. Probab., 19(1):1--28, 1991. Math. Review 91i:60024
- D. Aldous. The continuum random tree. III. Ann. Probab., 21(1):248--289, 1993. Math. Review 94c:60015
- 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
- J. Bertoin. Homogeneous fragmentation processes. Probab. Theory Related Fields, 121(3):301--318, 2001. Math. Review 2002j:60127
- J. Bertoin. Self-similar fragmentations. Ann. Inst. H. Poincaré Probab. Statist., 38(3):319--340, 2002. Math. Review 2003h:60109
- J. Bertoin. Random fragmentation and coagulation processes, volume 102 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006. Math. Review 2007k:60004
- 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
- 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
- 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
- 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
- W. Feller. An introduction to probability theory and its applications. Vol. I. Third edition. John Wiley & Sons Inc., New York, 1968. Math. Review 0228020
- D. J. Ford. Probabilities on cladograms: introduction to the alpha model. 2005. Preprint, arXiv:math.PR/0511246. Math. Review number not available.
- 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.
- R. C. Griffiths. Allele frequencies with genic selection. J. Math. Biol., 17(1):1--10, 1983. Math. Review 84h:92019
- 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
- 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
- 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.
- 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
- 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.
- P. McCullagh, J. Pitman, and M. Winkel. Gibbs fragmentation trees. Bernoulli, 14(4):988--1002, 2008. Math. Review number not available.
- 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
- 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
- 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
- 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.
This work is licensed under a Creative Commons Attribution 3.0 License.