Skip to main content

Research Repository

Advanced Search

Approximating Fixation Probabilities in the Generalized Moran Process

Díaz, J.; Goldberg, L.A.; Mertzios, G.B.; Richerby, D.; Serna, M.; Spirakis, P.G.

Approximating Fixation Probabilities in the Generalized Moran Process Thumbnail


Authors

J. Díaz

L.A. Goldberg

D. Richerby

M. Serna

P.G. Spirakis



Contributors

Yuval Rabani
Editor

Abstract

We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (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).

Citation

Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2012). Approximating Fixation Probabilities in the Generalized Moran Process. In Y. Rabani (Ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan, January 17-19, 2012 (954-960). https://doi.org/10.1137/1.9781611973099.76

Conference Name Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012
Conference Location Kyoto, Japan
Publication Date Nov 28, 2012
Deposit Date Dec 8, 2011
Publicly Available Date Mar 28, 2024
Pages 954-960
Series ISSN 1557-9468
Book Title Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan, January 17-19, 2012.
DOI https://doi.org/10.1137/1.9781611973099.76
Keywords Evolutionary dynamics, Markov-chain Monte Carlo, Approximation algorithm.
Public URL https://durham-repository.worktribe.com/output/1157489

Files

Published Conference Proceeding (348 Kb)
PDF

Copyright Statement
Copyright © 2011 by the Society for Industrial and Applied Mathematics.





You might also like



Downloadable Citations