Name
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.
|
Year | DOI | Venue |
|---|---|---|
2016 | 10.5555/2884435.2884471 | SODA '16: Symposium on Discrete Algorithms
Arlington
Virginia
January, 2016 |
Field | DocType | ISBN |
Population,Combinatorics,Fitness landscape,Markov chain,Stochastic process,Dynamical systems theory,Evolutionary dynamics,State space,Dynamical system,Mathematics | Conference | 978-1-61197-433-1 |
Citations | PageRank | References |
1 | 0.35 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ioannis Panageas | 1 | 81 | 14.30 |
| Piyush Srivastava | 2 | 65 | 4.55 |
| Nisheeth K. Vishnoi | 3 | 592 | 61.14 |