Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality
Evolutionary graph theory (EGT) investigates the Moran birth–death process constrained by graphs. Its two principal goals are to find the fixation probability and time for some initial population of mutants on the graph. The fixation probability of graphs has received considerable attention. Less is...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
The Royal Society
2022-05-01
|
| Series: | Royal Society Open Science |
| Subjects: | |
| Online Access: | https://royalsocietypublishing.org/doi/10.1098/rsos.220011 |
| _version_ | 1797837662018600960 |
|---|---|
| author | Travis Monk André van Schaik |
| author_facet | Travis Monk André van Schaik |
| author_sort | Travis Monk |
| collection | DOAJ |
| description | Evolutionary graph theory (EGT) investigates the Moran birth–death process constrained by graphs. Its two principal goals are to find the fixation probability and time for some initial population of mutants on the graph. The fixation probability of graphs has received considerable attention. Less is known about the distribution of fixation time. We derive clean, exact expressions for the full conditional characteristic functions (CCFs) of a close proxy to fixation and extinction times. That proxy is the number of times that the mutant population size changes before fixation or extinction. We derive these CCFs from a product martingale that we identify for an evolutionary graph with any number of partitions. The existence of that martingale only requires that the connections between those partitions are of a certain type. Our results are the first expressions for the CCFs of any proxy to fixation time on a graph with any number of partitions. The parameter dependence of our CCFs is explicit, so we can explore how they depend on graph structure. Martingales are a powerful approach to study principal problems of EGT. Their applicability is invariant to the number of partitions in a graph, so we can study entire families of graphs simultaneously. |
| first_indexed | 2024-04-09T15:28:20Z |
| format | Article |
| id | doaj.art-bd666e9bb7aa4387b35a1b09e1f4839a |
| institution | Directory Open Access Journal |
| issn | 2054-5703 |
| language | English |
| last_indexed | 2024-04-09T15:28:20Z |
| publishDate | 2022-05-01 |
| publisher | The Royal Society |
| record_format | Article |
| series | Royal Society Open Science |
| spelling | doaj.art-bd666e9bb7aa4387b35a1b09e1f4839a2023-04-28T10:43:18ZengThe Royal SocietyRoyal Society Open Science2054-57032022-05-019510.1098/rsos.220011Martingales and the fixation time of evolutionary graphs with arbitrary dimensionalityTravis Monk0André van Schaik1International Centre for Neuromorphic Systems, The MARCS Institute, Western Sydney University, Sydney, AustraliaInternational Centre for Neuromorphic Systems, The MARCS Institute, Western Sydney University, Sydney, AustraliaEvolutionary graph theory (EGT) investigates the Moran birth–death process constrained by graphs. Its two principal goals are to find the fixation probability and time for some initial population of mutants on the graph. The fixation probability of graphs has received considerable attention. Less is known about the distribution of fixation time. We derive clean, exact expressions for the full conditional characteristic functions (CCFs) of a close proxy to fixation and extinction times. That proxy is the number of times that the mutant population size changes before fixation or extinction. We derive these CCFs from a product martingale that we identify for an evolutionary graph with any number of partitions. The existence of that martingale only requires that the connections between those partitions are of a certain type. Our results are the first expressions for the CCFs of any proxy to fixation time on a graph with any number of partitions. The parameter dependence of our CCFs is explicit, so we can explore how they depend on graph structure. Martingales are a powerful approach to study principal problems of EGT. Their applicability is invariant to the number of partitions in a graph, so we can study entire families of graphs simultaneously.https://royalsocietypublishing.org/doi/10.1098/rsos.220011Moran processstochastic processbirth–death processevolutionary modelfixation time |
| spellingShingle | Travis Monk André van Schaik Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality Royal Society Open Science Moran process stochastic process birth–death process evolutionary model fixation time |
| title | Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality |
| title_full | Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality |
| title_fullStr | Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality |
| title_full_unstemmed | Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality |
| title_short | Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality |
| title_sort | martingales and the fixation time of evolutionary graphs with arbitrary dimensionality |
| topic | Moran process stochastic process birth–death process evolutionary model fixation time |
| url | https://royalsocietypublishing.org/doi/10.1098/rsos.220011 |
| work_keys_str_mv | AT travismonk martingalesandthefixationtimeofevolutionarygraphswitharbitrarydimensionality AT andrevanschaik martingalesandthefixationtimeofevolutionarygraphswitharbitrarydimensionality |