Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
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. We present faster polynomial-time Monte-Carlo algorithms for finidng the fixation probability on 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fast and asymptotic computation of the fixation probability for Moran processes on graphs
Evolutionary dynamics has been classically studied for homogeneous populations, but now there is a growing interest in the non-homogenous case. One of the most important models has been proposed by Lieberman, Hauert and …
Suppressors of selection
Inspired by recent works on evolutionary graph theory, an area of growing interest in mathematical and computational biology, we present the first known examples of undirected structures acting as suppressors of selectio…
Regime-Switching Langevin Monte Carlo Algorithms
Langevin Monte Carlo (LMC) algorithms are popular Markov Chain Monte Carlo (MCMC) methods to sample a target probability distribution, which arises in many applications in machine learning. Inspired by regime-switching s…
Quasi-Monte Carlo Variational Inference
Many machine learning problems involve Monte Carlo gradient estimators. As a prominent example, we focus on Monte Carlo variational inference (MCVI) in this paper. The performance of MCVI crucially depends on the varianc…
Variational InferenceFast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
Hamiltonian Monte Carlo (HMC) is a state-of-the-art Markov chain Monte Carlo sampling algorithm for drawing samples from smooth probability densities over continuous spaces. We study the variant most widely used in pract…