Phase transitions of the Moran process and algorithmic consequences. Issue 3 (28th October 2019)

• Record Type: Journal Article
• Authors: Ann Goldberg, Leslie; Lapinskas, John; Richerby, David
• Is Part Of: Random structures & algorithms. Volume 56:Issue 3(2020)
• Page Start: 597
• Page End: 647
• Publication Date: 2019-10-28
• Subjects: absorption time -- evolutionary dynamics -- fixation probability -- Moran process; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20890
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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 ( n 3+ ϵ ). Specifically, it is at most n 3 e O ( ( log log n ) 3 ), and there is a family of graphs where it is Ω( n 3 ). In proving this, we establish a phase transition in the probability of fixation, depending on the 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 fully polynomial randomized approximation scheme (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.