Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-10T10:46:08.975Z Has data issue: false hasContentIssue false
  • English
  • Français

Expected coalescence time for a nonuniform allocation process

Part of: Algorithms - Computer Science Markov processes Combinatorial probability Limit theorems

Published online by Cambridge University Press:  01 July 2016

John K. McSweeney  and
Boris G. Pittel
John K. McSweeney*
Affiliation:
The Ohio State University
Boris G. Pittel*
Affiliation:
The Ohio State University
*
∗ Postal address: Department of Mathematics, The Ohio State University, 231 W 18th Avenue, Columbus, OH 43210, USA.
∗ Postal address: Department of Mathematics, The Ohio State University, 231 W 18th Avenue, Columbus, OH 43210, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study a process where balls are repeatedly thrown into n boxes independently according to some probability distribution p . We start with n balls, and at each step, all balls landing in the same box are fused into a single ball; the process terminates when there is only one ball left (coalescence). Let c := ∑j p j 2, the collision probability of two fixed balls. We show that the expected coalescence time is asymptotically 2c −1, under two constraints on p that exclude a thin set of distributions p . One of the constraints is c = o(ln−2 n). This ln−2 n is shown to be a threshold value: for c = ω(ln−2 n), there exists p with c(p ) = c such that the expected coalescence time far exceeds c −1. Connections to coalescent processes in population biology and theoretical computer science are discussed.

Keywords

Coalescencemost recent common ancestorgeneralized Wright-Fisher modelrandom functionMarkov chainasymptotic behavior

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 60F10: Large deviations 60J05: Discrete-time Markov processes on general state spaces 68W40: Analysis of algorithms 92D25: Population dynamics (general)

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 40 , Issue 4 , December 2008 , pp. 1002 - 1032
Copyright
Copyright © Applied Probability Trust 2008 

References

Adler, I., Ahn, H.-S., Karp, R. M. and Ross, S. M. (2003). Coalescing times for iid random variables with applications to population biology. Random Structures Algorithms 23, 155–166.CrossRefGoogle Scholar
Dalal, A. and Schmutz, E. (2002). Compositions of random functions on a finite set. Electron J. Combinatorics 9, 7 pp.CrossRefGoogle Scholar
Donnelly, P. and Tavaré, S. (1995). Coalescents and genealogical structure under neutrality. Ann. Rev. Genet. 29, 401–421.Google Scholar
Fill, J. (2002). On compositions of random functions on a finite set. Unpublished manuscript. Available at http://www.mts.jhu.edu/fill/papers/compositions.ps.Google Scholar
Frieze, A. M. and Grimmett, G. R. (1985). The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10, 57–77.Google Scholar
Goh, W., Hitczenko, P. and Schmutz, E. (2006). Iterating random functions on a finite set. Unpublished manuscript. Available at http://front.math.ucdavis.edu/0207.5276.Google Scholar
Kingman, J. F. C. (1982). Exchangeability and the evolution of large populations. In Exchangeability in Probability and Statistics, eds Koch, G. and Spizzichino, F., North-Holland, Amsterdam, pp. 97–112.Google Scholar
Kingman, J. F. C. (1982). On the genealogy of large populations. In Essays in Statistical Science (J. Appl. Prob. Spec. Vol. 19A), eds Gani, J. and Hannan, E. J., Applied Probability Trust, pp. 27–43.Google Scholar
Kingman, J. F. C. (1982). The coalescent. Stoch. Process Appl. 13, 235–248.CrossRefGoogle Scholar
Knuth, D. E., Motwani, R. and Pittel, B. (1990). Stable husbands. Random Structures Algorithms 1, 1–14.Google Scholar
Mitzenmacher, M. and Upfal, E. (2005). Probability and Computing. Cambridge University Press.Google Scholar
Möhle, M. (1998). Robustness results for the coalescent. J. Appl. Prob. 35, 438–447.CrossRefGoogle Scholar
Möhle, M. (2004). The time back to the most recent common ancestor in exchangeable population models. Adv. Appl. Prob. 36, 78–97.Google Scholar
Möhle, M. and Sagitov, S. (2001). A classification of coalescent processes for haploid exchangeable population models. Ann. Prob. 29, 1547–1562.Google Scholar
Pitman, J. (1999). Coalescents with multiple collisions. Ann. Prob. 27, 1870–1902.Google Scholar
Pittel, B. (1987). On spreading a rumor. SIAM J. Appl. Math. 47, 213–223.Google Scholar
Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9, 223–252.Google Scholar
Propp, J. G. and Wilson, D. B. (1998). How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph. J. Algorithms 27, 170–217.Google Scholar
Sagitov, S. (1999). The general coalescent with asynchronous mergers of ancestral lines. J. Appl. Prob. 36, 1116–1125.Google Scholar
Schweinsberg, J. (2000). Coalescents with simultaneous multiple collisions. Electron. J. Prob. 5, 50 pp.Google Scholar