License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.63
URN: urn:nbn:de:0030-drops-62213
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6221/
Panageas, Ioannis ;
Vishnoi, Nisheeth K.
Mixing Time of Markov Chains, Dynamical Systems and Evolution
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.
BibTeX - Entry
@InProceedings{panageas_et_al:LIPIcs:2016:6221,
author = {Ioannis Panageas and Nisheeth K. Vishnoi},
title = {{Mixing Time of Markov Chains, Dynamical Systems and Evolution}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {63:1--63:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6221},
URN = {urn:nbn:de:0030-drops-62213},
doi = {10.4230/LIPIcs.ICALP.2016.63},
annote = {Keywords: Markov chains, Mixing time, Dynamical Systems, Evolutionary dynamics, Language evolution}
}
|
Keywords: |
|
Markov chains, Mixing time, Dynamical Systems, Evolutionary dynamics, Language evolution |
|
Collection: |
|
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
23.08.2016 |
