 |
|
|
| | | | | |
|
|
|
|
|
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
|
Abstract
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 → ∞, 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 →
∞. 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: PDF
Pages: 718-745
Published on: July 14, 2005
|
Bibliography
| | 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) |
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context