License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.630
URN: urn:nbn:de:0030-drops-47279
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4727/
Go to the corresponding LIPIcs Volume Portal

Díaz, Josep ; Goldberg, Leslie Ann ; Richerby, David ; Serna, Maria

Absorption Time of the Moran Process

pdf-format:
44.pdf (0.5 MB)

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 polynomial 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 give the expected absorption time is blog n lower bound and an explicit quadratic upper bound. 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.

BibTeX - Entry

@InProceedings{daz_et_al:LIPIcs:2014:4727,
  author =	{Josep D{\'i}az and Leslie Ann Goldberg and David Richerby and Maria Serna},
  title =	{{Absorption Time of the Moran Process}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{630--642},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4727},
  URN =		{urn:nbn:de:0030-drops-47279},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.630},
  annote =	{Keywords: Moran Process}
}

Keywords: Moran Process
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI