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

David A. Brewster, Yichen Huang, Michael Mitzenmacher, Martin A. NowakITCS 2026 · DOI

TL;DR

This paper introduces a unified model for evolutionary dynamics on graphs, combining two common update rules (birth-death and death-birth) into a single "mixed" process. They derive key theoretical results for this mixed process, offering a more general framework for understanding how evolution unfolds on networks and revealing how the choice of update rule can significantly impact outcomes.

What Problem Does This Paper Address?

Evolutionary dynamics, particularly how new traits or types spread through a population, are often modeled using processes on graphs. Two popular models are the "birth-death" (Bd) and "death-birth" (dB) processes. In Bd, a fitter individual reproduces, and a neighbor dies. In dB, an individual dies, and then a fitter neighbor fills the vacancy. The problem is that these two models, while seemingly similar, can lead to drastically different evolutionary outcomes (like how long it takes for one type to dominate or the probability of a new type taking over). This means conclusions drawn from one model might not hold for the other, creating a disconnect in our understanding. This paper aims to bridge this gap by creating a unified model that encompasses both and allows for a more general analysis.

Methods

The core of the paper is the introduction and analysis of the "A-mixed Moran process." This is a generalization where each step is either a standard birth-death step with probability $\lambda$ or a death-birth step with probability $1-\lambda$. The authors then analyze this mixed process for undirected, connected graphs. They focus on two critical quantities: the "unconditional absorption time" (the expected time until only one type remains) and the "fixation probability" (the probability that a new type eventually takes over the entire population). They derive theoretical results for these quantities, particularly for special cases of $\lambda$ and for specific graph structures.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Framework: The A-mixed Moran process provides a powerful generalization, allowing researchers to study the spectrum between pure Bd and pure dB dynamics. This is crucial because the choice of update rule isn't always arbitrary and can reflect different biological or social mechanisms.
  • Rule Dependence is Real: The paper explicitly demonstrates that the outcomes for fixation probability and absorption time can be significantly different depending on $\lambda$. This highlights that conclusions from simplified models should be treated with caution and that a more nuanced approach is needed.
  • Special Cases Reveal Structure: Analyzing specific values of $\lambda$ (like $\lambda=1/2$) and specific graph types (like regular graphs or graphs with only two degree values) yields concrete, often elegant, theoretical results. These special cases serve as important benchmarks and provide intuition for the behavior of the mixed process.
  • Fixation Probability at $\lambda=1/2$: A particularly neat result is that for $\lambda=1/2$ and $r=1$ (where all individuals have equal fitness), the fixation probability of a single mutant on any graph is exactly $1/n$. This is a simple, universal result that emerges from the balanced mixing of update rules.

Key Results

  • For the A-mixed Moran process with $\lambda=1/2$, the fixation probability of a single mutant on any graph with $n$ vertices, when all individuals have equal fitness ($r=1$), is exactly $1/n$.
  • For $\lambda=1/2$, the absorption time for any graph is $O(n)$ (meaning it grows linearly with the number of vertices, with a constant that depends on the fitness ratio $r$).
  • For graphs that are "almost regular," the absorption time is $O(n^2)$ and the fixation probability is $\Omega(n^{-2})$ for $r>1$.
  • For graphs with only two degree values ($d_1, d_2$), exact formulas for fixation probabilities are derived for $r=1$ and any $\lambda$. The absorption time is shown to be $O(n^a)$, where $a = d_2/d_1$. Explicit formulas are also given for star and cycle graphs.

Limitations and Future Work

The authors acknowledge that their results are primarily for undirected, connected graphs and represent a "starting point" for further study. They suggest that extending these analyses to directed graphs, disconnected graphs, or more complex fitness landscapes would be valuable future work. Additionally, exploring the computational complexity of these mixed processes for various graph classes and developing more efficient approximation algorithms are also promising directions.

Summary updated

BibTeX
@inproceedings{brewster2026mixed,
  author = {David A. Brewster and Yichen Huang and Michael Mitzenmacher and Martin A. Nowak},
  title = {{The Mixed Birth-Death/death-Birth Moran Process (Extended Abstract)}},
  booktitle = {ITCS},
  year = {2026},
  doi = {10.4230/lipics.itcs.2026.29},
}
Figure