We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Approximating fixation probabilities in the generalized Moran process.

Díaz, J. and Goldberg, L.A. and Mertzios, G.B. and Richerby, D. and Serna, M. and Spirakis, P.G. (2014) 'Approximating fixation probabilities in the generalized Moran process.', Algorithmica., 69 (1). pp. 78-91.


We consider the Moran process, as generalized by Lieberman et al. (Nature 433:312–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 r>0 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 r>0).

Item Type:Article
Additional Information:A preliminary version of this work appeared in Proceedings of the ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 954–960, 2012.
Keywords:Evolutionary dynamics, Markov-chain Monte Carlo, Approximation algorithm.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:09 September 2014
Date of first online publication:May 2014
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar