DROPS

Document

Extended Abstract

DOI: 10.4230/LIPIcs.ITCS.2026.29

The Mixed Birth-Death/death-Birth Moran Process (Extended Abstract)

Authors: David A. Brewster, Yichen Huang, Michael Mitzenmacher, and Martin A. Nowak

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We study evolutionary dynamics on graphs in which each step consists of one birth and one death, referred to generally as Moran processes. In standard simplified models, there are two types of individuals: residents, who have a fitness of 1, and mutants, who have a fitness of r. Two standard update rules are used in the literature. In Birth–death (Bd), a vertex is chosen to reproduce proportional to fitness, and one of its neighbors is selected uniformly at random to die and be replaced by the offspring. In death–Birth (dB), a vertex is chosen uniformly to die, and then one of its neighbors is chosen, proportional to fitness, to place an offspring into the vacancy. Two crucial quantities are: the unconditional absorption time, which is the expected time until only residents or only mutants remain, and the fixation probability of the mutant, which is the probability that at some time the mutants occupy the whole graph. Birth-death and death-Birth rules can yield significantly different outcomes for these quantities on the same graph, rendering conclusions dependent on the update rule. We formalize and study a unified model, the λ-mixed Moran process, in which each step is independently a Bd step with probability λ ∈ [0,1] and a dB step otherwise. We analyze this mixed process and establish a few results that form a starting point for its further study. All of our results are for undirected, connected graphs. As an interesting special case, we show at λ = 1/2 for any graph that the fixation probability when r = 1 with a single mutant initially on the graph is exactly 1/n, and also at λ = 1/2 that the absorption time for any r is O_r(n⁴) (that is, with an r-dependent constant). We also show results for graphs that are "almost regular," in a manner defined in the paper. We use this to show that for suitable random graphs from G∼ G(n,p) and fixed r > 1, with high probability over the choice of graph, the absorption time is O_r(n⁴), the fixation probability is Ω_r(n^{-2}), and we can approximate the fixation probability in polynomial time. Another special case is when the graph has only two possible values for the degree {d₁, d₂} with d₁ ≤ d₂. For those graphs, we give exact formulas for fixation probabilities under r = 1 and any λ, and establish O_r(n⁴ α⁴) absorption time regardless of λ, where α = d₂/d₁. We also provide explicit formulas for the star and cycle under any r or λ.

Cite as

David A. Brewster, Yichen Huang, Michael Mitzenmacher, and Martin A. Nowak. The Mixed Birth-Death/death-Birth Moran Process (Extended Abstract). In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 29:1-29:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brewster_et_al:LIPIcs.ITCS.2026.29,
  author =	{Brewster, David A. and Huang, Yichen and Mitzenmacher, Michael and Nowak, Martin A.},
  title =	{{The Mixed Birth-Death/death-Birth Moran Process}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{29:1--29:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.29},
  URN =		{urn:nbn:de:0030-drops-253161},
  doi =		{10.4230/LIPIcs.ITCS.2026.29},
  annote =	{Keywords: Moran process, Approximation algorithms, Random graphs}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2017.61

Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs

Authors: Krishnendu Chatterjee, Rasmus Ibsen-Jensen, and Martin A. Nowak

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract

Evolutionary graph theory studies the evolutionary dynamics in a population structure given as a connected graph. Each node of the graph represents an individual of the population, and edges determine how offspring are placed. We consider the classical birth-death Moran process where there are two types of individuals, namely, the residents with fitness 1 and mutants with fitness r. The fitness indicates the reproductive strength. The evolutionary dynamics happens as follows: in the initial step, in a population of all resident individuals a mutant is introduced, and then at each step, an individual is chosen proportional to the fitness of its type to reproduce, and the offspring replaces a neighbor uniformly at random. The process stops when all individuals are either residents or mutants. The probability that all individuals in the end are mutants is called the fixation probability, which is a key factor in the rate of evolution. We consider the problem of approximating the fixation probability. The class of algorithms that is extremely relevant for approximation of the fixation probabilities is the Monte-Carlo simulation of the process. Previous results present a polynomial-time Monte-Carlo algorithm for undirected graphs when $r$ is given in unary. First, we present a simple modification: instead of simulating each step, we discard ineffective steps, where no node changes type (i.e., either residents replace residents, or mutants replace mutants). Using the above simple modification and our result that the number of effective steps is concentrated around the expected number of effective steps, we present faster polynomial-time Monte-Carlo algorithms for undirected graphs. Our algorithms are always at least a factor O(n^2/log n) faster as compared to the previous algorithms, where n is the number of nodes, and is polynomial even if r is given in binary. We also present lower bounds showing that the upper bound on the expected number of effective steps we present is asymptotically tight for undirected graphs.

Cite as

Krishnendu Chatterjee, Rasmus Ibsen-Jensen, and Martin A. Nowak. Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.MFCS.2017.61,
  author =	{Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Nowak, Martin A.},
  title =	{{Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{61:1--61:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.61},
  URN =		{urn:nbn:de:0030-drops-81213},
  doi =		{10.4230/LIPIcs.MFCS.2017.61},
  annote =	{Keywords: Graph algorithms, Evolutionary biology, Monte-Carlo algorithms}
}

Search Results

Documents authored by Nowak, Martin A.

The Mixed Birth-Death/death-Birth Moran Process (Extended Abstract)

Abstract

Cite as

Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message