Asymptotics of the Allele Frequency Spectrum Associated with the Bolthausen-Sznitman Coalescent

Anne-Laure Basdevant (Université Paul Sabatier (Toulouse III))
Christina Goldschmidt (Department of Statistics, University of Oxford)


We consider a coalescent process as a model for the genealogy of a sample from a population. The population is subject to neutral mutation at constant rate $\rho$ per individual and every mutation gives rise to a completely new type. The allelic partition is obtained by tracing back to the most recent mutation for each individual and grouping together individuals whose most recent mutations are the same. The allele frequency spectrum is the sequence $(N_1(n), N_2(n), \ldots, N_n(n))$, where $N_k(n)$ is number of blocks of size $k$ in the allelic partition with sample size $n$. In this paper, we prove law of large numbers-type results for the allele frequency spectrum when the coalescent process is taken to be the Bolthausen-Sznitman coalescent. In particular, we show that $n^{-1}(\log n) N_1(n) {\stackrel{p}{\rightarrow}} \rho$ and, for $k \geq 2$, $n^{-1}(\log n)^2 N_k(n) {\stackrel{p}{\rightarrow}} \rho/(k(k-1))$ as $n \to \infty$. Our method of proof involves tracking the formation of the allelic partition using a certain Markov process, for which we prove a fluid limit.

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

Pages: 486-512

Publication Date: March 31, 2008

DOI: 10.1214/EJP.v13-494


  1. Barbour, A. D.; Gnedin, A. V. Regenerative compositions in the case of slow variation. Stochastic Process. Appl. 116 (2006), no. 7, 1012--1047. MR2238612 (2007m:60133)
  2. Basdevant, A.-L. Ruelle's probability cascades seen as a fragmentation process. Markov Process. Related Fields 12 (2006), no. 3, 447--474. MR2246260 (2007h:60068)
  3. Berestycki, Julien; Berestycki, Nathanaël; Schweinsberg, Jason. Beta-coalescents and continuous stable random trees. Ann. Probab. 35 (2007), no. 5, 1835--1887. MR2349577
  4. Berestycki, Julien; Berestycki, Nathanaël; Schweinsberg, Jason. Small-time behavior of Beta-coalescents. arXiv:math/0601032. To appear in Ann. Inst. H. Poincaré Probab. Statist. (2007).
  5. 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)
  6. Birkner, Matthias; Blath, Jochen; Capaldo, Marcella; Etheridge, Alison; Möhle, Martin; Schweinsberg, Jason; Wakolbinger, Anton. Alpha-stable branching and beta-coalescents. Electron. J. Probab. 10 (2005), no. 9, 303--325 (electronic). MR2120246 (2006c:60100)
  7. 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)
  8. Chen, Hong; Yao, David D. Fundamentals of queueing networks. Performance, asymptotics, and optimization. Applications of Mathematics (New York), 46. Stochastic Modelling and Applied Probability. Springer-Verlag, New York, 2001. xviii+405 pp. ISBN: 0-387-95166-0 MR1835969 (2003c:60149)
  9. Darling, R. W. R.; Norris, J. R. Structure of large random hypergraphs. Ann. Appl. Probab. 15 (2005), no. 1A, 125--152. MR2115039 (2006a:05105)
  10. Darling, R. W. R.; Norris, J. R. Differential equation approximations for Markov chains. arXiv:0710.3269 (2007).
  11. Delmas, J.-F.; Dhersin, J.-S.; Siri-Jegousse, A. Asymptotic results on the length of coalescent trees. arXiv:0706.0204. To appear in Ann. Appl. Probab. (2007).
  12. Dong, Rui; Gnedin, Alexander; Pitman, Jim. Exchangeable partitions derived from Markovian coalescents. Ann. Appl. Probab. 17 (2007), no. 4, 1172--1201. MR2344303
  13. Drmota, Michael; Iksanov, Alex; Moehle, Martin; Roesler, Uwe. Asymptotic results concerning the total branch length of the Bolthausen-Sznitman coalescent. Stochastic Process. Appl. 117 (2007), no. 10, 1404--1421. MR2353033
  14. Durrett, Rick. Probability models for DNA sequence evolution. Probability and its Applications (New York). Springer-Verlag, New York, 2002. viii+240 pp. ISBN: 0-387-95435-X MR1903526 (2003b:60003)
  15. Ewens, W. J. The sampling theory of selectively neutral alleles. Theoret. Population Biology 3 (1972), 87--112; erratum, ibid. 3 (1972), 240; erratum, ibid. 3 (1972), 376. MR0325177 (48 #3526)
  16. Ewens, Warren J. Mathematical population genetics. I. Theoretical introduction. Second edition. Interdisciplinary Applied Mathematics, 27. Springer-Verlag, New York, 2004. xx+417 pp. ISBN: 0-387-20191-2 MR2026891 (2004k:92001)
  17. Gnedin, Alexander. Regenerative composition structures: characterisation and asymptotics of block counts. Joint work with Jim Pitman and Marc Yor. Trends Math., Mathematics and computer science. III, 441--443, Birkhäuser, Basel, 2004. MR2090532
  18. Gnedin, Alexander; Hansen, Ben; Pitman, Jim. Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws. Probab. Surv. 4 (2007), 146--171 (electronic). MR2318403
  19. Gnedin, Alexander; Pitman, Jim. Regenerative partition structures. Electron. J. Combin. 11 (2004), no. 2, Research Paper 12, 21 pp. (electronic). MR2120107 (2005k:60113)
  20. Gnedin, Alexander; Pitman, Jim; Yor, Marc. Asymptotic laws for compositions derived from transformed subordinators. Ann. Probab. 34 (2006), no. 2, 468--492. MR2223948 (2007c:60040)
  21. Gnedin, Alexander; Pitman, Jim; Yor, Marc. Asymptotic laws for regenerative compositions: gamma subordinators and the like. Probab. Theory Related Fields 135 (2006), no. 4, 576--602. MR2240701 (2007m:60018)
  22. Gnedin, Alexander; Yakubovich, Yuri. On the number of collisions in Lambda-coalescents. Electron. J. Probab. 12 (2007), no. 56, 1547--1567 (electronic). MR2365877
  23. Gnedin, Alexander V. The Bernoulli sieve. Bernoulli 10 (2004), no. 1, 79--96. MR2044594 (2004k:60018)
  24. Gnedin, Alexander V.; Yakubovich, Yuri. Recursive partition structures. Ann. Probab. 34 (2006), no. 6, 2203--2218. MR2294980 (2008a:60016)
  25. Goldschmidt, Christina; Martin, James B. Random recursive trees and the Bolthausen-Sznitman coalescent. Electron. J. Probab. 10 (2005), no. 21, 718--745 (electronic). MR2164028 (2006g:60112)
  26. Iksanov, A.; Möhle, M. A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Comm. Probab. 12 (2007), 28--35 (electronic).
  27. Karlin, Samuel. Central limit theorems for certain infinite urn schemes. J. Math. Mech. 17 (1967) 373--401. MR0216548 (35 #7379)
  28. Kingman, J. F. C. Random partitions in population genetics. Proc. Roy. Soc. London Ser. A 361 (1978), no. 1704, 1--20. MR0526801 (58 #26167)
  29. Kingman, J. F. C. The representation of partition structures. J. London Math. Soc. (2) 18 (1978), no. 2, 374--380. MR0509954 (80a:05018)
  30. Kingman, J. F. C. The coalescent. Stochastic Process. Appl. 13 (1982), no. 3, 235--248. MR0671034 (84a:60079)
  31. Möhle, M. On sampling distributions for coalescent processes with simultaneous multiple collisions. Bernoulli 12 (2006), no. 1, 35--53. MR2202319
  32. Möhle, M. On the number of segregating sites for populations with large family sizes. Adv. in Appl. Probab. 38 (2006), no. 3, 750--767. MR2256876 (2008b:60164)
  33. Möhle, Martin. On a class of non-regenerative sampling distributions. Combin. Probab. Comput. 16 (2007), no. 3, 435--444. MR2312437 (2008c:60006)
  34. Pitman, Jim. Coalescents with multiple collisions. Ann. Probab. 27 (1999), no. 4, 1870--1902. MR1742892 (2001h:60016)
  35. Pitman, J. Combinatorial stochastic processes. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7--24, 2002. With a foreword by Jean Picard. Lecture Notes in Mathematics, 1875. Springer-Verlag, Berlin, 2006. x+256 pp. ISBN: 978-3-540-30990-1; 3-540-30990-X MR2245368 (2008c:60001)
  36. Pittel, Boris; Spencer, Joel; Wormald, Nicholas. Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B 67 (1996), no. 1, 111--151. MR1385386 (97e:05176)
  37. Sagitov, Serik. The general coalescent with asynchronous mergers of ancestral lines. J. Appl. Probab. 36 (1999), no. 4, 1116--1125. MR1742154 (2001f:92019)
  38. Schweinsberg, Jason. A necessary and sufficient condition for the Lambda-coalescent to come down from infinity. Electron. Comm. Probab. 5 (2000), 1--11 (electronic). MR1736720 (2001g:60025)
  39. Whitt, Ward. Stochastic-process limits. An introduction to stochastic-process limits and their application to queues. Springer Series in Operations Research. Springer-Verlag, New York, 2002. xxiv+602 pp. ISBN: 0-387-95358-2 MR1876437 (2003f:60005)
  40. Wormald, Nicholas C. Differential equations for random processes and random graphs. Ann. Appl. Probab. 5 (1995), no. 4, 1217--1235. MR1384372 (97c:05139)

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