RECORD
Phase Transitions of the Moran Process and Algorithmic Consequences
Probability · Submitted 6 Apr 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Our main result is an almost-tight bound on expected absorption time.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
The Moran process is a random process that models the spread of genetic mutations through graphs. If the graph is connected, the process eventually reaches "fixation", where every vertex is a mutant, or "extinction", where no vertex is a mutant. Our main result is an almost-tight bound on expected absorption time. For all epsilon > 0, we show that the expected absorption time on an n-vertex graph is o(n^(3+epsilon)). In fact, we show that it is at most n^3 * exp(O((log log n)^3)) and that there is a family of graphs where it is Omega(n^3). In the course of proving our main result, we also establish a phase transition in the probability of fixation, depending on the fitness parameter r of the mutation. We show that no similar phase transition occurs for digraphs, where it is already known that the expected absorption time can also be exponential. Finally, we give an improved FPRAS for approximating the probability of fixation. Its running time is independent of the size of the graph when the maximum degree is bounded and some basic properties of the graph are given.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The Moran process is a random process that models the spread of genetic mutations through graphs. | background 1.00 | 0.04 | 0.01 | asserted 1.00 |
| s1 | If the graph is connected, the process eventually reaches "fixation", where every vertex is a mutant, or "extinction", where no vertex is a mutant. | background 1.00 | 0.07 | 0.02 | asserted 1.00 |
| s2 | Our main result is an almost-tight bound on expected absorption time. | contribution 0.53 | 0.96 | 0.91 | asserted 1.00 |
| s3 | For all epsilon > 0, we show that the expected absorption time on an n-vertex graph is o(n^(3+epsilon)). | result 0.98 | 0.96 | 0.63 | asserted 1.00 |
| s4 | In fact, we show that it is at most n^3 * exp(O((log log n)^3)) and that there is a family of graphs where it is Omega(n^3). | result 0.99 | 0.96 | 0.32 | asserted 1.00 |
| s5 | In the course of proving our main result, we also establish a phase transition in the probability of fixation, depending on the fitness parameter r of the mutation. | result 0.88 | 0.96 | 0.04 | asserted 1.00 |
| s6 | We show that no similar phase transition occurs for digraphs, where it is already known that the expected absorption time can also be exponential. | result 0.92 | 0.81 | 0.03 | asserted 1.00 |
| s7 | Finally, we give an improved FPRAS for approximating the probability of fixation. | contribution 0.94 | 0.95 | 0.03 | asserted 1.00 |
| s8 | Its running time is independent of the size of the graph when the maximum degree is bounded and some basic properties of the graph are given. | result 0.69 | 0.90 | 0.03 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v4
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
The Moran process is a random process that models the spread of genetic mutations through graphs. If the graph is connected, the process eventually reaches "fixation", where every vertex is a mutant, or "extinction", where no vertex is a mutant. Our main result is an almost-tight bound on expected absorption time. For all epsilon > 0, we show that the expected absorption time on an n-vertex graph is o(n^(3+epsilon)). In fact, we show that it is at most n^3 * exp(O((log log n)^3)) and that there is a family of graphs where it is Omega(n^3). In the course of proving our main result, we also establish a phase transition in the probability of fixation, depending on the fitness parameter r of the mutation. We show that no similar phase transition occurs for digraphs, where it is already known that the expected absorption time can also be exponential. Finally, we give an improved FPRAS for approximating the probability of fixation. Its running time is independent of the size of the graph when the maximum degree is bounded and some basic properties of the graph are given.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.