Absorption time of the Moran process

DOI10.1002/RSA.20617MaRDI QIDQ2818278zbMATH OpenOpenAlexFDO

Authors Leslie Ann Goldberg, David Richerby, J. Díaz, Maria Serna

Publication date 7 September 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.7631, https://drops.dagstuhl.de/opus/volltexte/2014/4727/

zbMATH Keywords

absorption timedigraphsevolutionary dynamicsMarkov chainsMoran process

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Problems related to evolution (92D15) Population dynamics (general) (92D25)

Abstract: The Moran process models the spread of mutations in populations on graphs. We investigate the absorption time of the process, which is the time taken for a mutation introduced at a randomly chosen vertex to either spread to the whole population, or to become extinct. It is known that the expected absorption time for an advantageous mutation is O(n^4) on an n-vertex undirected graph, which allows the behaviour of the process on undirected graphs to be analysed using the Markov chain Monte Carlo method. We show that this does not extend to directed graphs by exhibiting an infinite family of directed graphs for which the expected absorption time is exponential in the number of vertices. However, for regular directed graphs, we show that the expected absorption time is Omega(n log n) and O(n^2). We exhibit families of graphs matching these bounds and give improved bounds for other families of graphs, based on isoperimetric number. Our results are obtained via stochastic dominations which we demonstrate by establishing a coupling in a related continuous-time model. The coupling also implies several natural domination results regarding the fixation probability of the original (discrete-time) process, resolving a conjecture of Shakarian, Roos and Johnson.

Recommendations

• Absorption time of the Moran process
• Phase transitions of the Moran process and algorithmic consequences
• Approximating fixation probabilities in the generalized Moran process
• Approximating fixation probabilities in the generalized Moran process
• Amplifiers for the Moran process

Cites work

• An analysis of the fixation probability of a mutant on special classes of non-directed graphs
• Approximating fixation probabilities in the generalized Moran process
• Cubic graphs and the first eigenvalue of a Riemann surface
• Dynamic monopolies of constant size
• Evolutionary game dynamics in finite populations
• Evolutionary games on graphs and the speed of the evolutionary process
• Fixation of strategies for an evolutionary game in finite populations
• Fixation probabilities on superstars, revisited and revised
• Gossip algorithms
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3148873 (Why is no real title available?)
• scientific article; zbMATH DE number 5543872 (Why is no real title available?)
• scientific article; zbMATH DE number 1350307 (Why is no real title available?)
• Isoperimetric numbers of graphs
• Natural models for evolution on networks
• On the fixation probability of superstars
• Probability and Computing
• Probability and random processes.
• The bisection width and the isoperimetric number of arrays.
• The isoperimetric number of random regular graphs

Cited in

(8)

• Asymptotically optimal amplifiers for the Moran process
• Bernoulli and binomial proliferation on evolutionary graphs
• Absorption time of the Moran process
• scientific article; zbMATH DE number 7204395 (Why is no real title available?)
• Phase transitions of the Moran process and algorithmic consequences
• Wald's martingale and the conditional distributions of absorption time in the Moran process
• Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process
• A survey of the modified Moran process and evolutionary graph theory

This page was built for publication: Absorption time of the Moran process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2818278)