Approximating fixation probabilities in the generalized Moran process
From MaRDI portal
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 ).
Recommendations
Cites work
- scientific article; zbMATH DE number 5869530 (Why is no real title available?)
- scientific article; zbMATH DE number 3148873 (Why is no real title available?)
- scientific article; zbMATH DE number 5485445 (Why is no real title available?)
- scientific article; zbMATH DE number 5543872 (Why is no real title available?)
- scientific article; zbMATH DE number 193169 (Why is no real title available?)
- scientific article; zbMATH DE number 3493681 (Why is no real title available?)
- scientific article; zbMATH DE number 3538599 (Why is no real title available?)
- scientific article; zbMATH DE number 3892344 (Why is no real title available?)
- A symmetry of fixation times in evoultionary dynamics
- An analysis of the fixation probability of a mutant on special classes of non-directed graphs
- Automata, Languages and Programming
- Bounds on variances of recovery times of decision feedback equalizers
- Drift analysis and average time complexity of evolutionary algorithms
- Dynamic monopolies of constant size
- Evolutionary Games and Population Dynamics
- Evolutionary dynamics on small-order graphs
- Evolutionary dynamics on small-world networks
- Evolutionary dynamics. Exploring the equations of life.
- Evolutionary game dynamics in finite populations
- Evolutionary games on graphs and the speed of the evolutionary process
- Fixation of strategies for an evolutionary game in finite populations
- Hitting-time and occupation-time bounds implied by drift analysis with applications
- Learning, Mutation, and Long Run Equilibria in Games
- Markov chain algorithms for planar lattice structures
- Networks, crowds and markets. Reasoning about a highly connected world.
- On the independence number and Hamiltonicity of uniform random intersection graphs
- Random generation of combinatorial structures from a uniform distribution
- Stochastic evolutionary game dynamics
- The long-run behavior of the stochastic replicator dynamics
- Two results on evolutionary processes on general non-directed graphs
Cited in
(29)- Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms
- Information Geometry of the Gaussian Distribution in View of Stochastic Optimization
- A glimpse at Paul G. Spirakis
- Evolution strategies with additive noise: a convergence rate lower bound
- Absorption time of the Moran process
- Asymptotically optimal amplifiers for the Moran process
- A survey of the modified Moran process and evolutionary graph theory
- Absorption time of the Moran process
- Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process
- Fixed Budget Performance of the (1+1) EA on Linear Functions
- Parallel Evolutionary Algorithms Performing Pairwise Comparisons
- Run-time analysis of population-based evolutionary algorithm in noisy environments
- 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
- Random walk Green kernels in the neutral Moran model conditioned on survivors at a random time to origin
- On the black-box complexity of example functions: the real jump function
- Strong bounds for evolution in networks
- Phase transitions of the Moran process and algorithmic consequences
- Quantitative approximation of the discrete Moran process by a Wright-Fisher diffusion
- Hypomixability Elimination In Evolutionary Systems
- Understanding Simple Asynchronous Evolutionary Algorithms
- (1+1) EA on Generalized Dynamic OneMax
- Black-box Complexity of Parallel Search with Distributed Populations
- Convergence time to the Ewens sampling formula in the infinite alleles Moran model
- Partition Crossover for Pseudo-Boolean Optimization
- Approximating fixation probabilities in the generalized Moran process
- scientific article; zbMATH DE number 7204395 (Why is no real title available?)
- A more efficient rank-one covariance matrix update for evolution strategies
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)
