The collision spectrum of \(\Lambda\)-coalescents. (English) Zbl 1404.60104

Gnedin, Alexander; Iksanov, Alexander; Marynych, Alexander; Möhle, Martin

Ann. Appl. Probab. 28, No. 6, 3857-3883 (2018).

Summary: \(\Lambda\)-coalescents model the evolution of a coalescing system in which any number of blocks randomly sampled from the whole may merge into a larger block. For the coalescent restricted to initially \(n\) singletons, we study the collision spectrum \((X_{n,k}:2\leq k\leq n)\), where \(X_{n,k}\) counts, throughout the history of the process, the number of collisions involving exactly \(k\) blocks. Our focus is on the large \(n\) asymptotics of the joint distribution of the \(X_{n,k}\)’s, as well as on functional limits for the bulk of the spectrum for simple coalescents. Similar to the previous studies of the total number of collisions, the asymptotics of the collision spectrum largely depends on the behaviour of the measure \(\Lambda\) in the vicinity of \(0\). In particular, for beta\((a,b)\)-coalescents different types of limit distributions occur depending on whether \(0<a\leq1\), \(1<a<2\), \(a=2\) or \(a>2\).

MSC:

60J25	Continuous-time Markov processes on general state spaces
60F17	Functional limit theorems; invariance principles
60C05	Combinatorial probability
60G09	Exchangeability for stochastic processes

Keywords:

collision spectrum; coupling; exchangeable coalescent; functional approximation

References:

[1]	Abraham, R. and Delmas, J.-F. (2013). A construction of a \(β\)-coalescent via the pruning of binary trees. J. Appl. Probab.50 772–790. · Zbl 1285.60078 · doi:10.1239/jap/1378401235
[2]	Abraham, R. and Delmas, J.-F. (2015). \(β\)-coalescents and stable Galton-Watson trees. ALEA Lat. Am. J. Probab. Math. Stat.12 451–476. · Zbl 1321.60170
[3]	Alsmeyer, G., Iksanov, A. and Marynych, A. (2017). Functional limit theorems for the number of occupied boxes in the Bernoulli sieve. Stochastic Process. Appl.127 995–1017. · Zbl 1366.60069 · doi:10.1016/j.spa.2016.07.007
[4]	Arratia, R., Barbour, A. D. and Tavaré, S. (2003). Logarithmic Combinatorial Structures: A Probabilistic Approach. European Mathematical Society (EMS), Zürich. · Zbl 1040.60001
[5]	Barbour, A. D. and Gnedin, A. V. (2006). Regenerative compositions in the case of slow variation. Stochastic Process. Appl.116 1012–1047. · Zbl 1114.60030 · doi:10.1016/j.spa.2005.12.006
[6]	Basdevant, A.-L. and Goldschmidt, C. (2008). Asymptotics of the allele frequency spectrum associated with the Bolthausen-Sznitman coalescent. Electron. J. Probab.13 486–512. · Zbl 1190.60006 · doi:10.1214/EJP.v13-494
[7]	Berestycki, J., Berestycki, N. and Limic, V. (2014). Asymptotic sampling formulae for \(Λ\)-coalescents. Ann. Inst. Henri Poincaré Probab. Stat.50 715–731. · Zbl 1321.60146 · doi:10.1214/13-AIHP546
[8]	Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1989). Regular Variation. Encyclopedia of Mathematics and Its Applications27. Cambridge Univ. Press, Cambridge.
[9]	Birkner, M. and Blath, J. (2008). Computing likelihoods for coalescents with multiple collisions in the infinitely many sites model. J. Math. Biol.57 435–465. · Zbl 1274.92039 · doi:10.1007/s00285-008-0170-6
[10]	Birkner, M., Blath, J. and Eldon, B. (2013). Statistical properties of the site-frequency spectrum associated with \(Λ\)-coalescents. Genetics195 1037–1053.
[11]	Blath, J., Cronjäger, M. C., Eldon, B. and Hammer, M. (2016). The site-frequency spectrum associated with \(Ξ\)-coalescents. Theor. Popul. Biol.110 36–50. · Zbl 1365.92072
[12]	Cooper, C. (2006). Distribution of vertex degree in web-graphs. Combin. Probab. Comput.15 637–661. · Zbl 1104.68081 · doi:10.1017/S096354830600753X
[13]	Delmas, J.-F., Dhersin, J.-S. and Siri-Jegousse, A. (2008). Asymptotic results on the length of coalescent trees. Ann. Appl. Probab.18 997–1025. · Zbl 1141.60007 · doi:10.1214/07-AAP476
[14]	Diehl, C. and Kersting, G. (2018). Tree lengths for general \(Λ\)-coalescents and the asymptotic site frequency spectrum around the Bolthausen–Sznitman coalescent. Preprint. Available at https://arxiv.org/abs/1804.00961.
[15]	Dong, R., Gnedin, A. and Pitman, J. (2007). Exchangeable partitions derived from Markovian coalescents. Ann. Appl. Probab.17 1172–1201. · Zbl 1147.60022 · doi:10.1214/105051607000000069
[16]	Drmota, M. and Gittenberger, B. (1999). The distribution of nodes of given degree in random trees. J. Graph Theory31 227–253. · Zbl 0929.05019 · doi:10.1002/(SICI)1097-0118(199907)31:3<227::AID-JGT6>3.0.CO;2-6
[17]	Drmota, M., Iksanov, A., Moehle, M. and Roesler, U. (2007). Asymptotic results concerning the total branch length of the Bolthausen-Sznitman coalescent. Stochastic Process. Appl.117 1404–1421. · Zbl 1129.60069 · doi:10.1016/j.spa.2007.01.011
[18]	Eldon, B., Birkner, M., Blath, J. and Freund, F. (2014). Can the site-frequency spectrum distinguish exponential population growth from multiple-merger coalescents? Genetics199 841–856.
[19]	Eldon, B. and Wakeley, J. (2006). Coalescent processes when the distribution of offspring number among individuals is highly skewed. Genetics172 2621–2633.
[20]	Faÿ, G., González-Arévalo, B., Mikosch, T. and Samorodnitsky, G. (2006). Modeling teletraffic arrivals by a Poisson cluster process. Queueing Syst.54 121–140. · Zbl 1119.60075
[21]	Feller, W. (1971). An Introduction to Probability Theory and Its Applications. Vol. II. 2nd ed. Wiley, New York. · Zbl 0219.60003
[22]	Gnedin, A. and Iksanov, A. (2012). Regenerative compositions in the case of slow variation: A renewal theory approach. Electron. J. Probab.17 Paper no. 77. · Zbl 1252.60025 · doi:10.1214/EJP.v17-2002
[23]	Gnedin, A., Iksanov, A. and Marynych, A. (2010). Limit theorems for the number of occupied boxes in the Bernoulli sieve. Theory Stoch. Process.16(32) 44–57. · Zbl 1249.60029
[24]	Gnedin, A., Iksanov, A. and Marynych, A. (2011). On \(Λ\)-coalescents with dust component. J. Appl. Probab.48 1133–1151. · Zbl 1242.60077 · doi:10.1239/jap/1324046023
[25]	Gnedin, A., Iksanov, A. and Marynych, A. (2014). \(Λ\)-coalescents: A survey. J. Appl. Probab.51A 23–40. · Zbl 1322.60152 · doi:10.1239/jap/1417528464
[26]	Gnedin, A., Iksanov, A., Marynych, A. and Möhle, M. (2014). On asymptotics of the beta coalescents. Adv. in Appl. Probab.46 496–515. · Zbl 1323.60021 · doi:10.1239/aap/1401369704
[27]	Gnedin, A., Iksanov, A. and Möhle, M. (2008). On asymptotics of exchangeable coalescents with multiple collisions. J. Appl. Probab.45 1186–1195. · Zbl 1159.60016 · doi:10.1239/jap/1231340242
[28]	Gnedin, A. and Pitman, J. (2005). Regenerative composition structures. Ann. Probab.33 445–479. · Zbl 1070.60034 · doi:10.1214/009117904000000801
[29]	Gnedin, A., Pitman, J. and Yor, M. (2006). Asymptotic laws for compositions derived from transformed subordinators. Ann. Probab.34 468–492. · Zbl 1142.60327 · doi:10.1214/009117905000000639
[30]	Gnedin, A., Pitman, J. and Yor, M. (2006). Asymptotic laws for regenerative compositions: Gamma subordinators and the like. Probab. Theory Related Fields135 576–602. · Zbl 1099.60023 · doi:10.1007/s00440-005-0473-0
[31]	Gnedin, A. and Yakubovich, Y. (2007). On the number of collisions in \(Λ\)-coalescents. Electron. J. Probab.12 1547–1567. · Zbl 1190.60061 · doi:10.1214/EJP.v12-464
[32]	Goldschmidt, C. and Martin, J. B. (2005). Random recursive trees and the Bolthausen-Sznitman coalescent. Electron. J. Probab.10 718–745. · Zbl 1109.60060 · doi:10.1214/EJP.v10-265
[33]	Haas, B. and Miermont, G. (2011). Self-similar scaling limits of non-increasing Markov chains. Bernoulli17 1217–1247. · Zbl 1263.92034 · doi:10.3150/10-BEJ312
[34]	Hu, Y., Boyd-Graber, J., Daumé, H. III and Ying, Z. I. (2013). Binary to bushy: Bayesian hierarchical clustering with the beta coalescent. Adv. Neural Inf. Process. Syst.26.
[35]	Iksanov, A., Marynych, A. and Meiners, M. (2017). Asymptotics of random processes with immigration I: Scaling limits. Bernoulli23 1233–1278. · Zbl 1386.60122 · doi:10.3150/15-BEJ776
[36]	Iksanov, A., Marynych, A. and Möhle, M. (2009). On the number of collisions in \(\operatorname{beta}(2,b)\)-coalescents. Bernoulli15 829–845. · Zbl 1208.60081 · doi:10.3150/09-BEJ192
[37]	Iksanov, A. and Möhle, M. (2007). A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Commun. Probab.12 28–35. · Zbl 1133.60012 · doi:10.1214/ECP.v12-1253
[38]	Iksanov, A. and Möhle, M. (2008). On the number of jumps of random walks with a barrier. Adv. in Appl. Probab.40 206–228. · Zbl 1157.60041 · doi:10.1239/aap/1208358893
[39]	Janson, S. (2005). Asymptotic degree distribution in random recursive trees. Random Structures Algorithms26 69–83. · Zbl 1059.05094 · doi:10.1002/rsa.20046
[40]	Kersting, G., Schweinsberg, J. and Wakolbinger, A. (2018). The size of the last merger and time reversal in \(Λ\)-coalescents. Ann. Inst. Henri Poincaré Probab. Stat.54 1527–1555. · Zbl 1404.60108
[41]	Möhle, M. (2018). On strictly monotone Markov chains with constant hitting probabilities and applications to a class of beta coalescents. Markov Process. Related Fields24 107–130. · Zbl 1417.60063
[42]	Neher, R. A. and Hallatschek, A. (2013). Genealogies of rapidly adapting populations. Proc. Natl. Acad. Sci. USA110 437–442.
[43]	Pitman, J. (1999). Coalescents with multiple collisions. Ann. Probab.27 1870–1902. · Zbl 0963.60079 · doi:10.1214/aop/1022874819
[44]	Pitman, J. (2006). Combinatorial Stochastic Processes. Lecture Notes in Math.1875. Springer, Berlin. · Zbl 1103.60004
[45]	Sagitov, S. (1999). The general coalescent with asynchronous mergers of ancestral lines. J. Appl. Probab.36 1116–1125. · Zbl 0962.92026 · doi:10.1239/jap/1032374759
[46]	Schweinsberg, J. and Durrett, R. (2005). Random partitions approximating the coalescence of lineages during a selective sweep. Ann. Appl. Probab.15 1591–1651. · Zbl 1073.92029 · doi:10.1214/105051605000000430
[47]	Shiryaev, A. N. (1989). Probability, Vol. I, 4th ed. Nauka, Moscow. · Zbl 0682.60001
[48]	Spence, J. P., Kamm, J. A. and Song, Y. S. (2016). The site frequency spectrum for general coalescents. Genetics202 1549–1561.
[49]	Teh, Y. W., Daumé, H. III and Roy, D. M. (2008). Bayesian agglomerative clustering with coalescents. Adv. Neural Inf. Process. Syst.20 1473–1480.