Random Recursive Trees and the Bolthausen-Sznitman Coalesent

Christina Goldschmidt (Statistical Laboratory and Pembroke College, University of Cambridge, UK)
James B. Martin (CNRS and Université Paris 7, France)


We describe a representation of the Bolthausen-Sznitman coalescent in terms of the cutting of random recursive trees. Using this representation, we prove results concerning the final collision of the coalescent restricted to $[n]$: we show that the distribution of the number of blocks involved in the final collision converges as $n\to\infty$, and obtain a scaling law for the sizes of these blocks. We also consider the discrete-time Markov chain giving the number of blocks after each collision of the coalescent restricted to $[n]$; we show that the transition probabilities of the time-reversal of this Markov chain have limits as $n\to\infty$. These results can be interpreted as describing a ``post-gelation'' phase of the Bolthausen-Sznitman coalescent, in which a giant cluster containing almost all of the mass has already formed and the remaining small blocks are being absorbed.

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

Pages: 718-745

Publication Date: July 14, 2005

DOI: 10.1214/EJP.v10-265


Arratia, Richard; Barbour, A. D.; Tavaré, Simon. Logarithmic combinatorial structures: a probabilistic approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zürich, 2003. xii+363 pp. ISBN: 3-03719-000-0 MR2032426 (2004m:60004)

Basdevant, Anne-Laure. Ruelle's probability cascades seen as a fragmentation process. Preprint math.PR/0501088, 2005. Math. Review number not available.

Bertoin, Jean. Self-similar fragmentations. Ann. Inst. H. Poincaré Probab. Statist. 38 (2002), no. 3, 319--340. MR1899456 (2003h:60109)

Bertoin, Jean; Le Gall, Jean-François. The Bolthausen-Sznitman coalescent and the genealogy of continuous-state branching processes. Probab. Theory Related Fields 117 (2000), no. 2, 249--266. MR1771663 (2001h:60150)

Bolthausen, E.; Sznitman, A.-S. On Ruelle's probability cascades and an abstract cavity method. Comm. Math. Phys. 197 (1998), no. 2, 247--276. MR1652734 (99k:60244)

DeLaurentis, J. M.; Pittel, B. G. Random permutations and Brownian motion. Pacific J. Math. 119 (1985), no. 2, 287--301. MR0803120 (86m:60027)

Donnelly, Peter; Kurtz, Thomas G.; Tavaré, Simon. On the functional central limit theorem for the Ewens sampling formula. Ann. Appl. Probab. 1 (1991), no. 4, 539--545. MR1129773 (93e:60064)

Feng, Shui; Hoppe, Fred M. Large deviation principles for some random combinatorial structures in population genetics and Brownian motion. Ann. Appl. Probab. 8 (1998), no. 4, 975--994. MR1661315 (99k:60074)

Fill, James Allen; Kapur, Nevin; Panholzer, Alois. Destruction of very simple trees. Preprint math.PR/0412155, 2004. Math. Review number not available.

Hansen, Jennie C. A functional central limit theorem for the Ewens sampling formula. J. Appl. Probab. 27 (1990), no. 1, 28--43. MR1039182 (91b:60027)

Janson, Svante. Random cutting and records in deterministic and random trees. Tech. Report 2004:25, Department of Mathematics, Uppsala University; available from http://www.math.uu.se/~svante/papers/index.html, 2004. Math. Review number not available.

Janson, Svante. Random records and cuttings in complete binary trees. Mathematics and computer science. III, 241--253, Trends Math., Birkhäuser, Basel, 2004. MR2090513

Kingman, J. F. C. The representation of partition structures. J. London Math. Soc. (2) 18 (1978), no. 2, 374--380. MR0509954 (80a:05018)

Kingman, J. F. C. The coalescent. Stochastic Process. Appl. 13 (1982), no. 3, 235--248. MR0671034 (84a:60079)

Marchal, Philippe. Nested regenerative sets and their associated fragmentation process. Mathematics and computer science. III, 461--470, Trends Math., Birkhäuser, Basel, 2004. MR2090534

Meir, A.; Moon, J. W. Cutting down random trees. J. Austral. Math. Soc. 11 (1970), 313--324. MR0284370 (44 #1598)

Meir, A.; Moon. J.W. Cutting down recursive trees. Math. Bioscience 21 (1974), 173--181. Math. Review number not available.

Panholzer, Alois. Non-crossing trees revisited: cutting down and spanning subtrees. Discrete random walks (Paris, 2003), 265--276 (electronic), Discrete Math. Theor. Comput. Sci. Proc., AC, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003. MR2042393 (2004m:60017)

Panholzer, Alois. Destruction of recursive trees. Mathematics and computer science. III, 267--280, Trends Math., Birkhäuser, Basel, 2004. MR2090518 (2005e:60026)

Pippenger, N. An infinite product for e. Amer. Math. Monthly 87 (1980), no. 5, 391. Math. Review number not available.

Pitman, Jim. Coalescents with multiple collisions. Ann. Probab. 27 (1999), no. 4, 1870--1902. MR1742892 (2001h:60016)

Pitman, Jim. Combinatorial stochastic processes. To appear in Lectures on Probability Theory and Statistics (Saint-Flour). Springer-Verlag. Available at http://stat.berkeley.edu/users/pitman/621.pdf, 2002. Math. Review number not available.

Schweinsberg, Jason. A necessary and sufficient condition for the Λ-coalescent to come down from infinity. Electron. Comm. Probab. 5 (2000), 1--11 (electronic). MR1736720 (2001g:60025)

Smythe, Robert T.; Mahmoud, Hosam M. A survey of recursive trees. (Ukrainian) ; translated from Teor. u Imov=i r. Mat. Stat. No. 51 (1994), 1--29 Theory Probab. Math. Statist. No. 51, (1995), 1--27 (1996) MR1445048 (97k:60027)

Sondow, J. A faster product for π and a new integral for ln π/2. To appear in Amer. Math. Monthly; preprint math.NT/0401406, 2004. Math. Review number not available.

Stanley, Richard P. Enumerative combinatorics. Vol. 1. With a foreword by Gian-Carlo Rota. Corrected reprint of the 1986 original. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge, 1997. xii+325 pp. ISBN: 0-521-55309-1; 0-521-66351-2 MR1442260 (98a:05001)

van de Lune, J. An introduction to Tauberian theory: from Tauber to Wiener. CWI Syllabi, 12. Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1986. iv+102 pp. ISBN: 90-6196-309-5 MR0882005 (88j:40011)

Wilf, Herbert S. generatingfunctionology. Second edition. Academic Press, Inc., Boston, MA, 1994. x+228 pp. ISBN: 0-12-751956-4 MR1277813 (95a:05002)

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