Martingales and fixation probabilities of evolutionary graphs

Evolutionary graph theory is the study of birth–death processes that are constrained by population structure. A principal problem in evolutionary graph theory is to obtain the probability that some initial population of mutants will fixate on a graph, and to determine how that fixation probability depends on the structure of that graph. A fluctuating mutant population on a graph can be considered as a random walk. Martingales exploit symmetry in the steps of a random walk to yield exact analytical expressions for fixation probabilities. They do not require simplifying assumptions such as large population sizes or weak selection. In this paper, we show how martingales can be used to obtain fixation probabilities for symmetric evolutionary graphs. We obtain simpler expressions for the fixation probabilities of star graphs and complete bipartite graphs than have been previously reported and show that these graphs do not amplify selection for advantageous mutations under all conditions.