Authors: Josep Díaz Leslie Ann Goldberg George B Mertzios David Richerby Maria Serna Paul G Spirakis
Publish Date: 2012/11/28
Volume: 69, Issue: 1, Pages: 78-91
Abstract
We consider the Moran process as generalized by Lieberman et al Nature 433312–316 2005 A population resides on the vertices of a finite connected undirected graph and at each time step an individual is chosen at random with probability proportional to its assigned “fitness” value It reproduces placing a copy of itself on a neighbouring vertex chosen uniformly at random replacing the individual that was there The initial population consists of a single mutant of fitness r0 placed uniformly at random with every other vertex occupied by an individual of fitness 1 The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph fixation and that they die out extinction almost surely these are the only possibilities In general exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible We show that with high probability the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph This bound allows us to construct fully polynomial randomized approximation schemes FPRAS for the probability of fixation when r≥1 and of extinction for all r0
Keywords: