Coalescence on the real line
HTML articles powered by AMS MathViewer
- by Paul Balister, Béla Bollobás, Jonathan Lee and Bhargav Narayanan PDF
- Trans. Amer. Math. Soc. 371 (2019), 1583-1619 Request permission
Abstract:
We study a geometrically constrained coalescence model derived from spin systems. Given two probability distributions $\mathbb {P}_R$ and $\mathbb {P}_B$ on the positive reals with finite means, colour the real line alternately with red and blue intervals so that the lengths of the red intervals have distribution $\mathbb {P}_R$, the lengths of the blue intervals have distribution $\mathbb {P}_B$, and distinct intervals have independent lengths. Now, iteratively update this colouring of the line by coalescing intervals: change the colour of any interval that is surrounded by longer intervals so that these three consecutive intervals subsequently form a single monochromatic interval. We say that a colour (either red or blue) wins if every point of the line is eventually of that colour. Holroyd, in 2010, asked the following question: under what natural conditions on the initial distributions is one of the colours almost surely guaranteed to win? It turns out that the answer to this question can be quite counter-intuitive due to the non-monotone dynamics of the model. In this paper, we investigate various notions of “advantage” one of the colours might initially possess, and in the course of doing so, we determine which of the two colours emerges victorious for various non-trivial pairs of initial distributions.References
- M. Ajtai, J. Komlós, and G. Tusnády, On optimal matchings, Combinatorica 4 (1984), no. 4, 259–264. MR 779885, DOI 10.1007/BF02579135
- David J. Aldous, Deterministic and stochastic models for coalescence (aggregation and coagulation): a review of the mean-field theory for probabilists, Bernoulli 5 (1999), no. 1, 3–48. MR 1673235, DOI 10.2307/3318611
- Noga Alon and Joel H. Spencer, The probabilistic method, 3rd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2008. With an appendix on the life and work of Paul Erdős. MR 2437651, DOI 10.1002/9780470277331
- Paul Balister, Béla Bollobás, and Mark Walters, Continuum percolation with steps in the square or the disc, Random Structures Algorithms 26 (2005), no. 4, 392–403. MR 2139873, DOI 10.1002/rsa.20064
- Charles Blair, Every finite distributive lattice is a set of stable matchings, J. Combin. Theory Ser. A 37 (1984), no. 3, 353–356. MR 769224, DOI 10.1016/0097-3165(84)90056-6
- Béla Bollabás and Alan Stacey, Approximate upper bounds for the critical probability of oriented percolation in two dimensions based on rapidly mixing Markov chains, J. Appl. Probab. 34 (1997), no. 4, 859–867. MR 1484020, DOI 10.1017/s0021900200101573
- A. J. Bray, Theory of phase ordering kinetics, Physica A 194 (1993), 41–52.
- B. Derrida, C. Godrèche, and I. Yekutieli, Stable distributions of growing and coalescing droplets, Europhys. Lett. 12 (1990), 385–390.
- B. Derrida, C. Godrèche, and I. Yekutieli, Scale-invariant regimes in one-dimensional models of growing and coalescing droplets, Phys. Rev. A 44 (1991), 6241–6251.
- Michael Dzierzawa and Marie-José Oméro, Statistics of stable marriages, Phys. A 287 (2000), no. 1-2, 321–333. MR 1802748, DOI 10.1016/S0378-4371(00)00344-7
- A. Faggionato, F. Martinelli, C. Roberto, and C. Toninelli, Aging through hierarchical coalescence in the East model, Comm. Math. Phys. 309 (2012), no. 2, 459–495. MR 2864800, DOI 10.1007/s00220-011-1376-9
- Alessandra Faggionato, Fabio Martinelli, Cyril Roberto, and Cristina Toninelli, Universality in one-dimensional hierarchical coalescence processes, Ann. Probab. 40 (2012), no. 4, 1377–1435. MR 2978129, DOI 10.1214/11-AOP654
- A. Faggionato, C. Roberto, and C. Toninelli, Universality for one-dimensional hierarchical coalescence processes with double and triple merges, Ann. Appl. Probab. 24 (2014), no. 2, 476–525. MR 3178489, DOI 10.1214/12-AAP917
- G. H. Fredrickson and H. C. Andersen, Kinetic Ising model of the glass transition, Phys. Rev. Lett. 53 (1984), 1244–1247.
- D. Gale and L. S. Shapley, College Admissions and the Stability of Marriage, Amer. Math. Monthly 69 (1962), no. 1, 9–15. MR 1531503, DOI 10.2307/2312726
- A. E. Holroyd, Microsoft Research Theory Lunch, 2010.
- A. E. Holroyd, Personal communication, 2014.
- Alexander E. Holroyd, Geometric properties of Poisson matchings, Probab. Theory Related Fields 150 (2011), no. 3-4, 511–527. MR 2824865, DOI 10.1007/s00440-010-0282-y
- Alexander E. Holroyd, Robin Pemantle, Yuval Peres, and Oded Schramm, Poisson matching, Ann. Inst. Henri Poincaré Probab. Stat. 45 (2009), no. 1, 266–287 (English, with English and French summaries). MR 2500239, DOI 10.1214/08-AIHP170
- Toshiya Itoh and Osamu Watanabe, Weighted random popular matchings, Random Structures Algorithms 37 (2010), no. 4, 477–494. MR 2760360, DOI 10.1002/rsa.20316
- J. Jäckle and S. Eisinger, A hierarchically constrained kinetic Ising model, Z. Phys. B: Condens. Matter 84 (1991), 115–124.
- Donald E. Knuth, Stable marriage and its relation to other combinatorial problems, CRM Proceedings & Lecture Notes, vol. 10, American Mathematical Society, Providence, RI, 1997. An introduction to the mathematical analysis of algorithms; Translated from the French by Martin Goldstein and revised by the author. MR 1415126, DOI 10.1090/crmp/010
- Stephan Mertens, Random stable matchings, J. Stat. Mech. Theory Exp. 10 (2005), P10008, 12. MR 2185394, DOI 10.1088/1742-5468/2005/10/p10008
- Boris Pittel, The “stable roommates” problem with random preferences, Ann. Probab. 21 (1993), no. 3, 1441–1477. MR 1235424
- F. Ritort and P. Sollich, Glassy dynamics of kinetically constrained models, Adv. in Phys. 52 (2003), 219–342.
- I. G. Shevtsova, On absolute constants in inequalities of Berry-Esseen type, Dokl. Akad. Nauk 456 (2014), no. 6, 650–654 (Russian); English transl., Dokl. Math. 89 (2014), no. 3, 378–381. MR 3287912, DOI 10.1134/s1064562414030338
Additional Information
- Paul Balister
- Affiliation: Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee 38152
- MR Author ID: 340031
- Email: pbalistr@memphis.edu
- Béla Bollobás
- Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, United Kingdom – Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee 38152 – and – London Institute for Mathematical Sciences, 35a South Street, Mayfair, London W1K 2XF, United Kingdom
- Email: b.bollobas@dpmms.cam.ac.uk
- Jonathan Lee
- Affiliation: Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, United Kingdom
- Email: jonathan.lee@merton.ox.ac.uk
- Bhargav Narayanan
- Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, United Kingdom
- MR Author ID: 1058391
- Received by editor(s): October 24, 2016
- Received by editor(s) in revised form: June 18, 2017
- Published electronically: July 31, 2018
- Additional Notes: The first and second authors were partially supported by NSF grant DMS-1600742, and the second author also wishes to acknowledge support from EU MULTIPLEX grant 317532.
- © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 371 (2019), 1583-1619
- MSC (2010): Primary 60K35; Secondary 60D05, 60G55
- DOI: https://doi.org/10.1090/tran/7391
- MathSciNet review: 3894028