Approximating fixation probabilities in the generalized Moran process
From MaRDI portal
Publication:472467
DOI10.1007/S00453-012-9722-7zbMATH Open1303.92095arXiv1111.3321OpenAlexW3099831495MaRDI QIDQ472467FDOQ472467
Authors: Leslie Ann Goldberg, George B. Mertzios, David Richerby, P. G. Spirakis, J. Díaz, Maria Serna 
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 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 ) and of extinction (for all ).
Full work available at URL: https://arxiv.org/abs/1111.3321
Recommendations
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Population dynamics (general) (92D25) Approximation algorithms (68W25)
Cites Work
- Networks, crowds and markets. Reasoning about a highly connected world.
- Evolutionary game dynamics in finite populations
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Evolutionary dynamics. Exploring the equations of life.
- Automata, Languages and Programming
- Title not available (Why is that?)
- Learning, Mutation, and Long Run Equilibria in Games
- Two results on evolutionary processes on general non-directed graphs
- Stochastic evolutionary game dynamics
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dynamic monopolies of constant size
- Evolutionary dynamics on small-world networks
- 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 (29)
- A survey of the modified Moran process and evolutionary graph theory
- Run-time analysis of population-based evolutionary algorithm in noisy environments
- 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
- Asymptotically optimal amplifiers for the Moran process
- 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
- Insights from adversarial fitness functions
- Self-adapting the Brownian radius in a differential evolution algorithm for dynamic environments
- Convergence of strategies in simple co-adapting games
- On the black-box complexity of example functions: the real jump function
- Hypomixability Elimination In Evolutionary Systems
- Approximating fixation probabilities in the generalized Moran process
- Absorption time of the Moran process
- Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process
- Absorption time of the Moran process
- Parallel Evolutionary Algorithms Performing Pairwise Comparisons
- Partition Crossover for Pseudo-Boolean Optimization
- Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms
- A more efficient rank-one covariance matrix update for evolution strategies
- 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
- A glimpse at Paul G. Spirakis
- Phase transitions of the Moran process and algorithmic consequences
- Title not available (Why is that?)
- Evolution strategies with additive noise: a convergence rate lower bound
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)
