Research Repository

Phase transitions of the Moran process and algorithmic consequences

Goldberg, Leslie and Lapinskas, John and Richerby, David (2020) 'Phase transitions of the Moran process and algorithmic consequences.' Random Structures and Algorithms, 56 (3). pp. 597-647. ISSN 1042-9832

1804.02293.pdf - Accepted Version

Download (561kB) | Preview


The Moran process is a random process that models the spread of genetic mutations through graphs. On connected graphs, the process eventually reaches “fixation”, where all vertices are mutants, or “extinction”, where none are. Our main result is an almost-tight upper bound on expected absorption time. For all ε > 0, we show that the expected absorption time on an n-vertex graph is o(n3+ε). Specifically, it is at most n3eO((log log n)3), and there is a family of graphs where it is Ω(n3). In proving this, we establish a phase transition in the probability of fixation, depending on mutants’ fitness r. We show that no similar phase transition occurs for digraphs, where it is already known that the expected absorption time can be exponential. Finally, we give an improved FPRAS for approximating the probability of fixation. On degree-bounded graphs where some basic properties are given, its running time is independent of the number of vertices.

Item Type: Article
Uncontrolled Keywords: absorption time; evolutionary dynamics; fixation probability; Moran process
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 06 Oct 2020 14:10
Last Modified: 21 Jan 2022 11:36

Actions (login required)

View Item View Item