Winter 2015: Theory Seminar
ICS, Room 243, 1:00pm
February 27, 2015:

The Speed of Evolution

Jenny Lam

In this paper we study the mixing times of a Wright- Fisher model for an asexual population. Typically, such models consist of a population of several genotypes where each genotype reproduces at a different rate, genotypes can mutate to each other, and the population is subject to the evolutionary pressure of selection. While such models have been used extensively to study different types of populations, recently, such stochastic finite population models have been used to model viral populations with the goal of understanding the effect of mutagenic drugs. Here, the time it takes for the population to reach a steady state is important both for carrying out simulations and to determine treatment strength and duration. Despite their importance, and having been widely studied, there has been a lack of such bounds for many relevant ranges of model parameters even for the case of two genotypes (single locus); primarily due to their difficulty, see [Eth11]. The main result of this paper is an analytical bound on the mixing time of a Wright-Fisher model for two genotypes when there is no restriction on the mutation rate or the fitness. Our bound explains (in this setting) the observed phenomena that the mixing time is fast (logarithmic in the state space) for any fitness parameter when the mutation rate is high enough. Theoretically, we overcome the difficulty in proving mixing time bounds by showing that different forces are responsible for the rapid mixing depending on how close it is to its steady state. If the chain is sufficiently close to its stationary distribution, an intricate coupling argument establishes rapid mixing. To show that the chain reaches this state quickly, we connect it to the convergence time of a deterministic model for evolution proposed by Eigen. We are hopeful that our insights and techniques will be helpful in establishing rigorous bounds for more general versions of this model.

This paper is by Nisheeth K. Vishnoi from SODA 2015