CaltechAUTHORS
  A Caltech Library Service

Evolutionary Dynamics in Finite Populations Mix Rapidly

Panageas, Ioannis and Srivastava, Piyush and Vishnoi, Nisheet (2016) Evolutionary Dynamics in Finite Populations Mix Rapidly. In: Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , New York, NY, pp. 480-497. ISBN 978-1-611974-33-1. http://resolver.caltech.edu/CaltechAUTHORS:20160217-114318436

[img] PDF - Published Version
See Usage Policy.

684Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160217-114318436

Abstract

In this paper we prove that the mixing time of a broad class of evolutionary dynamics in finite, unstructured populations is roughly logarithmic in the size of the state space. An important special case of such a stochastic process is the Wright-Fisher model from evolutionary biology (with selection and mutation) on a population of size N over m genotypes. Our main result implies that the mixing time of this process is O(log N) for all mutation rates and fitness landscapes, and solves the main open problem from [4]. In particular, it significantly extends the main result in [18] who proved this for m = 2. Biologically, such models have been used to study the evolution of viral populations with applications to drug design strategies countering them. Here the time it takes for the population to reach a steady state is important both for the estimation of the steady-state structure of the population as well in the modeling of the treatment strength and duration. Our result, that such populations exhibit rapid mixing, makes both of these approaches sound. Technically, we make a novel connection between Markov chains arising in evolutionary dynamics and dynamical systems on the probability simplex. This allows us to use the local and global stability properties of the fixed points of such dynamical systems to construct a contractive coupling in a fairly general setting. We expect that our mixing time result would be useful beyond the evolutionary biology setting, and the techniques used here would find applications in bounding the mixing times of Markov chains which have a natural underlying dynamical system.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/1.9781611974331.ch36DOIArticle
http://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch36PublisherArticle
Additional Information:© 2016 by SIAM. Supported by NSF grant CCF-1415496, CCF-1415498. Supported by NSF grant CCF-1319745.
Funders:
Funding AgencyGrant Number
NSFCCF-1415496
NSFCCF-1415498
NSFCCF-1319745
Record Number:CaltechAUTHORS:20160217-114318436
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160217-114318436
Official Citation:Evolutionary Dynamics in Finite Populations Mix Rapidly Ioannis Panageas, Piyush Srivastava, and Nisheeth K. Vishnoi pp. 480-497 (18 pages) http://dx.doi.org/10.1137/1.9781611974331.ch36
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:64539
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:18 Feb 2016 18:19
Last Modified:18 Feb 2016 18:19

Repository Staff Only: item control page