Document Open Access Logo

Mixing Time of Markov Chains, Dynamical Systems and Evolution

Authors Ioannis Panageas, Nisheeth K. Vishnoi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.63.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Ioannis Panageas
Nisheeth K. Vishnoi

Cite As Get BibTex

Ioannis Panageas and Nisheeth K. Vishnoi. Mixing Time of Markov Chains, Dynamical Systems and Evolution. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.63

Abstract

In this paper we study the mixing time of evolutionary Markov chains over populations of a fixed size (N) in which each individual can be one of m types. These Markov chains have the property that they are guided by a dynamical system from the m-dimensional probability simplex to itself. Roughly, given the current state of the Markov chain, which can be viewed as a probability distribution over the m types, the next state is generated by applying this dynamical system to this distribution, and then sampling from it N times. Many processes in nature, from biology to sociology, are evolutionary and such chains can be used to model them. In this study, the mixing time is of particular interest as it determines the speed of evolution and whether the statistics of the steady state can be efficiently computed. In a recent result [Panageas, Srivastava, Vishnoi, Soda, 2016], it was suggested that the mixing time of such Markov chains is connected to the geometry of this guiding dynamical system. In particular, when the dynamical system has a fixed point which is a global attractor, then the mixing is fast. The limit sets of dynamical systems, however, can exhibit more complex behavior: they could have multiple fixed points that are not necessarily stable, periodic orbits, or even chaos. Such behavior arises in important evolutionary settings such as the dynamics of sexual evolution and that of grammar acquisition. In this paper we prove that the geometry of the dynamical system can also give tight mixing time bounds when the dynamical system has multiple fixed points and periodic orbits. We show that the mixing time continues to remain small in the presence of several unstable fixed points and is exponential in N when there are two or more stable fixed points. As a consequence of our results, we obtain a phase transition result for the mixing time of the sexual/grammar model mentioned above. We arrive at the conclusion that in the interesting parameter regime for these models, i.e., when there are multiple stable fixed points, the mixing is slow. Our techniques strengthen the connections between Markov chains and dynamical systems and we expect that the tools developed in this paper should have a wider applicability.

Subject Classification

Keywords
  • Markov chains
  • Mixing time
  • Dynamical Systems
  • Evolutionary dynamics
  • Language evolution

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. L. Baum and J. Eagon. An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull. Amer. Math. Soc., 73:360-363, 1967. Google Scholar
  2. Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de probabilites XXXIII, pages 1-68. Springer, 1999. Google Scholar
  3. Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani. Algorithms, games, and evolution. Proceedings of the National Academy of Sciences, 2014. Google Scholar
  4. Noam A. Chomsky. Rules and Representations. Behavioral and Brain Sciences, 3(127):1-61, 1980. Google Scholar
  5. Narendra Dixit, Piyush Srivastava, and Nisheeth K. Vishnoi. A finite population model of molecular evolution: Theory and computation. Journal of Computational Biology, 19(10):1176-1202, 2012. Google Scholar
  6. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. Google Scholar
  7. Richard Durrett. Probability models for DNA sequence evolution. Springer, 2008. Google Scholar
  8. Stewart N Ethier and Thomas G Kurtz. Markov processes: characterization and convergence, volume 282. John Wiley &Sons, 2009. Google Scholar
  9. Warren J. Ewens. Mathematical Population Genetics I. Theoretical Introduction. Springer, 2004. Google Scholar
  10. W.T. Fitch. The Evolution of Language. Approaches to the Evolution of Language. Cambridge University Press, 2010. Google Scholar
  11. J. Hofbauer and K. Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, 1998. Google Scholar
  12. Natalia L. Komarova and Martin A. Nowak. Language dynamics in finite populations. Journal of Theoretical Biology, 221(3):445-457, 2003. Google Scholar
  13. Erwin Kreyszig. Introductory Functional Analysis with Applications. Wiley, 1978. Google Scholar
  14. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2008. Google Scholar
  15. Yun Long, Asaf Nachmias, and Yuval Peres. Mixing time power laws at criticality. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS'07, pages 205-214, Washington, DC, USA, 2007. IEEE Computer Society. Google Scholar
  16. J. Maynard-Smith and E. Szathmary. The Major Transitions in Evolution. New York: Oxford University Press, 1997. Google Scholar
  17. Ruta Mehta, Ioannis Panageas, and Georgios Piliouras. Natural selection as an inhibitor of genetic diversity: Multiplicative weights updates algorithm and a conjecture of haploid genetics. In Innovations in Theoretical Computer Science, 2015. Google Scholar
  18. M.A. Nowak. Evolutionary Dynamics. Harvard University Press, 2006. Google Scholar
  19. Martin A. Nowak, Natalia L. Komarova, and Partha Niyogi. Evolution of universal grammar. Science, 2001. Google Scholar
  20. Ioannis Panageas, Piyush Srivastava, and Nisheeth K. Vishnoi. Evolutionary dynamics in finite populations mix rapidly. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016. Google Scholar
  21. Christos H. Papadimitriou and Nisheeth K. Vishnoi. On the computational complexity of limit cycles in dynamical systems. In Proceedings of the 2016 Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, page 403, 2016. Google Scholar
  22. Robin Pemantle. When are touchpoints limits for generalized Pólya urns? Proceedings of the American Mathematical Society, pages 235-243, 1991. Google Scholar
  23. Georgios Piliouras, Carlos Nieto-Granda, Henrik I. Christensen, and Jeff S. Shamma. Persistent patterns: Multi-agent learning beyond equilibrium and utility. In AAMAS, pages 181-188, 2014. Google Scholar
  24. Kushal Tripathi, Rajesh Balagam, Nisheeth K. Vishnoi, and Narendra M. Dixit. Stochastic simulations suggest that HIV-1 survives close to its error threshold. PLoS Comput Biol, 8(9):e1002684, 09 2012. Google Scholar
  25. Nisheeth K. Vishnoi. The speed of evolution. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1590-1601, 2015. Google Scholar
  26. Nicholas C Wormald. Differential equations for random processes and random graphs. The annals of applied probability, pages 1217-1235, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact