J. Díaz
Approximating Fixation Probabilities in the Generalized Moran Process
Díaz, J.; Goldberg, L.A.; Mertzios, G.B.; Richerby, D.; Serna, M.; Spirakis, P.G.
Authors
L.A. Goldberg
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
D. Richerby
M. Serna
P.G. Spirakis
Abstract
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).
Citation
Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. Algorithmica, 69(1), 78-91. https://doi.org/10.1007/s00453-012-9722-7
Journal Article Type | Article |
---|---|
Publication Date | May 1, 2014 |
Deposit Date | Sep 5, 2014 |
Publicly Available Date | Mar 29, 2024 |
Journal | Algorithmica |
Print ISSN | 0178-4617 |
Electronic ISSN | 1432-0541 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 69 |
Issue | 1 |
Pages | 78-91 |
DOI | https://doi.org/10.1007/s00453-012-9722-7 |
Keywords | Evolutionary dynamics, Markov-chain Monte Carlo, Approximation algorithm. |
Files
Accepted Journal Article
(342 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-012-9722-7.
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search