Colonization times in Moran process on graphs

2024/10/12 by Lenka Kopfová, Kopfová, Lenka, Josef Tkadlec +1 · 1 citation
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Biological sciences #FOS: Mathematics #Populations and Evolution (q-bio.PE) #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.2410.09476

openalex publication_date 2024/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Moran Birth-death process is a standard stochastic process that is used to model natural selection in spatially structured populations. A newly occurring mutation that invades a population of residents can either fixate on the whole population or it can go extinct due to random drift. The duration of the process depends not only on the total population size n, but also on the spatial structure of the population. In this work, we consider the Moran process with a single type of individuals who invade and colonize an otherwise empty environment. Mathematically, this corresponds to the setting where the residents have zero reproduction rate, thus they never reproduce. We present two main contributions. First, in contrast to the Moran process in which residents do reproduce, we show that the colonization time is always at most a polynomial function of the population size n. Namely, we show that colonization always takes at most \frac12n³-\frac12n² expected steps, and for each n, we exactly identify the unique slowest spatial structure where it takes exactly that many steps. Moreover, we establish a stronger bound of roughly n^2.5 steps for spatial structures that contain only two-way connections and an even stronger bound of roughly n² steps for lattice-like spatial structures. Second, we discuss various complications that one faces when attempting to measure fixation times and colonization times in spatially structured populations, and we propose to measure the real duration of the process, rather than counting the steps of the classic Moran process.

Cited by

• The selective advantage of neighborhood-aware mutants in Moran process

Related

• The Mixed Birth-death/death-Birth Moran Process
• Fixation probability in Moran-like Processes on graphs
• Absorption Time of the Moran Process
• Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
• Exact fixation probabilities for the Birth-Death and Death-Birth frequency-dependent Moran processes on the star graph