Approximating fixation probabilities in the generalized Moran process

DOI10.1007/S00453-012-9722-7zbMATH Open1303.92095arXiv1111.3321OpenAlexW3099831495MaRDI QIDQ472467FDOQ472467

David Richerby, P. G. Spirakis, Maria Serna, George B. Mertzios, J. Díaz, Leslie Ann Goldberg

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned 'fitness' value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness $r>0$ placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when $rgeq1$) and of extinction (for all $r>0$).

Full work available at URL: https://arxiv.org/abs/1111.3321

zbMATH Keywords

Markov chainMonte Carloapproximation algorithmevolutionary dynamics

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Population dynamics (general) (92D25) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Evolutionary game dynamics in finite populations
• Evolutionary Games and Population Dynamics
• Random generation of combinatorial structures from a uniform distribution
• The long-run behavior of the stochastic replicator dynamics
• Markov chain algorithms for planar lattice structures
• Automata, Languages and Programming
• Learning, Mutation, and Long Run Equilibria in Games
• Two results on evolutionary processes on general non-directed graphs
• Fixation of strategies for an evolutionary game in finite populations
• A symmetry of fixation times in evoultionary dynamics
• Evolutionary games on graphs and the speed of the evolutionary process
• An analysis of the fixation probability of a mutant on special classes of non-directed graphs
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Drift analysis and average time complexity of evolutionary algorithms
• Dynamic monopolies of constant size
• Evolutionary dynamics on small-order graphs
• Bounds on variances of recovery times of decision feedback equalizers
• On the independence number and Hamiltonicity of uniform random intersection graphs

Cited In (27)

• A More Efficient Rank-one Covariance Matrix Update for Evolution Strategies
• A survey of the modified Moran process and evolutionary graph theory
• Understanding Simple Asynchronous Evolutionary Algorithms
• Fixed Budget Performance of the (1+1) EA on Linear Functions
• Random walk Green kernels in the neutral Moran model conditioned on survivors at a random time to origin
• Strong bounds for evolution in networks
• A Glimpse at Paul G. Spirakis
• Asymptotically optimal amplifiers for the Moran process
• Evolution Strategies with Additive Noise
• Information Geometry of the Gaussian Distribution in View of Stochastic Optimization
• (1+1) EA on Generalized Dynamic OneMax
• Black-box Complexity of Parallel Search with Distributed Populations
• Run-Time Analysis of Population-Based Evolutionary Algorithm in Noisy Environments
• Hypomixability Elimination In Evolutionary Systems
• Absorption time of the Moran process
• Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process
• An extension of the Moran process using type-specific connection graphs
• Parallel Evolutionary Algorithms Performing Pairwise Comparisons
• Convergence of Strategies in Simple Co-Adapting Games
• Insights From Adversarial Fitness Functions
• Partition Crossover for Pseudo-Boolean Optimization
• Self-Adapting the Brownian Radius in a Differential Evolution Algorithm for Dynamic Environments
• On the Black-Box Complexity of Example Functions
• Quantitative approximation of the discrete Moran process by a Wright-Fisher diffusion
• Convergence time to the Ewens sampling formula in the infinite alleles Moran model
• Title not available (Why is that?)
• Efficient Optimisation of Noisy Fitness Functions with Population-based Evolutionary Algorithms

This page was built for publication: Approximating fixation probabilities in the generalized Moran process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472467)