## Abstract

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.

## 1. Introduction

Evolutionary graph theory was introduced to analyse the fixation probability of mutations in structured populations [1,2]. Though it has since expanded its focus and potential applications, this remains one of its core problems of interest [3]. Fixation probabilities of evolutionary graphs are traditionally obtained with Markov chains or state transition-based approaches [4,5], diffusion approximations [2] or simulation [6]. These approaches are suitable for evolutionary graphs that are highly asymmetric, such as those with directed and weighted connections [7]. Asymmetric graphs are not conducive to tractable mathematical analysis, and it is best to obtain fixation probabilities on such graphs by making simplifying assumptions or employing brute-force approaches. However, some evolutionary graphs have symmetries that make them mathematically tractable. Martingales can be used to obtain exact, simple and closed-form expressions for the fixation probabilities of such graphs, often within a few lines of straightforward mathematics.

Martingales exploit symmetry in the steps of a random walk to obtain its global statistics, for example fixation probabilities. See [8] for a readable introduction to martingale theory. When martingale theory is applicable to an evolutionary graph, it has clear advantages over other approaches such as state transition-based Markov chains or diffusion approximations. When we obtain fixation probabilities using Markov chains, our resultant expressions necessarily contain matrices and matrix operations. This is undesirable because the parameter dependence of such expressions for fixation probabilities is obscured (e.g. [9, ch. 11]). State transition-based methods require solving a system of linear equations that increases exponentially in size with the order of the graph [10]. Some graphs are sufficiently symmetric to allow inductive evaluation of recursive equations, but this results in complex expressions for fixation probabilities [4,11]. Diffusion approximations yield tractable and parameter-dependent expressions for fixation probabilities, but they require simplifying assumptions such as large population sizes or weak selection to do so [12–14]. Martingales, when they are applicable, are exempt from these drawbacks; they yield exact and tractable expressions for fixation probabilities that make parameter dependence explicit, and they do not require simplifying assumptions to do so.

In this paper, we will show how to use martingales to obtain fixation probabilities on highly symmetric evolutionary graphs. All graphs we analyse are undirected and unweighted with constant selection. Polynomial bounds on fixation probabilities, and even the time to fixation, have been obtained for such graphs [10], but we will show that at least some of these graphs can be analysed exactly. We will first investigate very simple graphs whose fixation probabilities are well known, and we will verify the validity of the martingale approach by checking our expressions for fixation probabilities with those that have already been obtained. We will then investigate more complex graphs to highlight the advantages of the martingale approach.

## 2. Fixation probabilities on evolutionary graphs from martingales

In discrete time, a sequence of random variables **Y**_{t} is a martingale with respect to another sequence **X**_{t} if it satisfies satisfies for any *t*≥1
If a sequence **Y**_{t} is not a martingale, we might be able to apply a function *f* so that the transformed sequence *f*(**Y**_{t}) is a martingale
We will show below how to obtain such transformations for some evolutionary graphs of interest. First, we show how to extract fixation probabilities from martingales when such a transformation exists.

Let **S**_{t} represent the mutant population on an evolutionary graph at time step *t* (i.e. the state of the graph at time step *t*). For unstructured graphs such as the Moran process, **S**_{t} is a scalar representing the total number of mutants at time step *t* (§3*a*). For heterogeneous graphs such as the star graph, **S**_{t} is a vector representing the numbers of mutants at different types of vertices (§3*b*,*c*).

We can write , where **X**_{i} is the change in the state of the graph at time step *i*, and **S**_{0} is the initial state of the graph. Let **a** and **b** represent the absorbing states of the graph, with **a** being the state where mutants have achieved fixation, and **b** the state where mutants have become extinct. For example, in an unstructured Moran process with population size *N*, we would have **a**=*N* and **b**=0. Finally, let *T* be the random stopping time at which the population reaches one of the absorbing states; that is, *T* is the first time step where the population consists either entirely of the mutant type or entirely of the resident type.

In order to calculate fixation probabilities with this method, we need the transforming function *f* to be exponential, which is the only continuous function with the property *f*(**X**+**Y**)=*f*(**X**)*f*(**Y**) (see [15, ch. 8, exercise 6]).

### Theorem 2.1

*Let* *represent the state of an evolutionary process on a graph. Suppose we have some (non-constant) exponential function f such that* *for all t, and we have a stopping time T with* *(the time to fixation or extinction is finite). Then the fixation probability of the graph is
*

### Proof.

As *f* is an exponential function, the conditional expectation of *f*(**S**_{t}) is given by
and so the sequence *f*(**S**_{t}) is a martingale with respect to **X**_{t}.

Now let this martingale be stopped at some random finite time . Doob’s optional stopping theorem [8,15] gives us
On an evolutionary graph, the stopping time *T* is the first time step for which the process reaches one of two possible absorbing states, **a** or **b**, representing fixation and extinction. Therefore
Inserting and rearranging we get
2.1 □

This paper only considers undirected evolutionary graphs, which must absorb in finite time [10]. Thus, the crucial condition we require for equation (2.1) to give us fixation probabilities is for all *t*.

At any given time, the transition probabilities of evolutionary graphs depend only on the current state of the graph. That is, **X**_{t} depends on {**X**_{1},…**X**_{t−1}} only through their cumulative sum **S**_{t−1}. Thus, the condition reduces to .

## 3. Applications of martingales to evolutionary graphs

### (a) The Moran process

Readers unfamiliar with the Moran process, or birth–death processes, are advised to consult [1].

Let **S**_{t} be the size of the mutant population (i.e. the state of the graph) at time *t*, and let **X**_{t} be the change in the graph’s state on the *t*th time step. The probabilities that the state increases, decreases or remains the same on a time step, conditional on the current state, are
To use equation (2.1) to obtain an expression for the fixation probability, we need to show that for an exponential function *f*, for all *t*
Inserting *f*(0)=1 (since any exponential function evaluated at 0 is 1), the conditional probability expressions, and simplifying
Let the exponential function *f* have the form *f*(**X**)=*h*^{X}, with *h* as a free variable
3.1Solving for *h*, we find that for *h*=1/*r* or 1. The solution *h*=1 is trivial so we discard it. As *h*=1/*r* is not dependent on *t*, we have a suitable transformation *f*(**X**)=*h*^{X} such that for all *t*. We may now use theorem 2.1 to write down the fixation probability of the Moran process directly from equation (2.1).

The Moran process terminates when the mutant population goes extinct (**b**=0) or fixates (**a**=*N*). Inserting *f*(**X**)=*h*^{X}=*r*^{−X}, **b**=0 and **a**=*N* into equation (2.1) returns the well-known probability of fixation [1]
3.2

It is straightforward to show that if we choose the dying individual without replacement (i.e. the reproducing individual cannot also be the dying individual), we obtain the same probability of fixation.

### (b) The star graph

Figure 1 depicts the star graph, where one individual occupies the centre of a star and *V* individuals occupy vertices surrounding the centre [2]. The individual at the centre is connected with all individuals at the vertices, but individuals at the vertices are not connected with each other.

We will represent the state of the graph at time step *t* by **S**_{t}=[*S*_{c,t},*S*_{v,t}] where *S*_{c,t} is 0 or 1, depending on whether the centre is occupied by a resident or a mutant, respectively, and *S*_{v,t} is the number of vertices occupied by mutants (out of a total of *V*). **X**_{t}=[*X*_{c,t},*X*_{v,t}] is the change in state at time step *t*, so that . For compact notation, let be the total fitness of the graph
and also define

The probabilities that the graph will change state on a time step, conditional on the current state, are

Let the exponential function *f* have the form . We need to determine *h*_{c} and *h*_{v} such that . Let us divide all possible states into those with a mutant at the centre (*S*_{c}=1) and those with a resident at the centre (*S*_{c}=0). We can write as
If both cases equal 1, then as well. Setting both cases to 1 and simplifying gives us
With two equations, we can solve for the two unknowns *h*_{c} and *h*_{v} (ignoring the trivial solution *h*_{c}=*h*_{v}=1)
As *h*_{c} and *h*_{v} are not dependent on *t*, we have a suitable transformation such that for all *t*. We may now use theorem 2.1 to write down the fixation probability of the star graph directly from equation (2.1).

The star graph terminates when the mutants go extinct (**b**=[0,0]) or occupy the centre and all vertices (**a**=[1,*V* ]). Inserting , **b**=[0,0], **a**=[1,*V* ], and initial state **S**_{0}=[*S*_{c,0},*S*_{v,0}] into equation (2.1) returns the fixation probability
3.3

This is the same result as that reported by Broom & Rychtar [4], but in a simpler form, and generalized to allow for any initial state **S**_{0}. Also note that as , *h*_{c}→1 and *h*_{v}→*r*^{−2}. If the starting state is a single mutant located at a vertex, then **S**_{0}=[0,1], and for large *V*
3.4which is the same result as that reported by Lieberman *et al*. [2].

Figure 2 displays plots of equation (3.3) for several values of *V* as well as equation (3.4). Broom & Rychtar [4] similarly compared the exact fixation probability of star graphs with that of the Moran process, and with Lieberman *et al*.’s approximation. However, it was not explicitly shown how sensitive the star graph’s fixation probability is with respect to the initial state **S**_{0}.^{1} For example, consider neutral drift in stars by taking the limit of equation (3.3) as *r*→1:
In a Moran process with the same number of individuals as a star graph with *V* vertices (i.e. *N*=*V* +1), the fixation probability of a neutral mutation is
The reader can easily verify that if the star graph’s starting state is one neutral mutant on the ring (**S**_{0}=[0,1]), then that mutant is more likely to fixate on the star graph than in the equivalent Moran process, for all *V* >1. However, if that neutral mutant occupies the centre of the star graph (**S**_{0}=[1,0]), then that mutant is less likely to fixate on the star graph than in the equivalent Moran process.

### (c) The complete bipartite graph

Complete bipartite graphs are graphs comprising two groups of individuals. All individuals in one group share connections with all individuals in the other group. However, no individuals are connected with any other individuals in their own group.

Figure 3 is an example of a complete bipartite graph. It depicts a star graph with any number *C* of individuals in the centre, surrounded by *V* individuals at the vertices. Every individual in the centre shares a connection with every individual at the vertices, but not to others in the centre. Individuals at the vertices are not connected to each other.

Let **S**_{t}=[*S*_{c,t},*S*_{v,t}] and **X**_{t}=[*X*_{c,t},*X*_{v,t}] be defined as they were in §3*b*, except that *S*_{c,t} is now defined on the integers from 0 through *C*. Again, let be the fitness of the graph,
and define
Note that when *C*=1, these expressions reduce to those of the previous section. The probabilities that the graph will change state on a time step, conditional on the current state, are
Let the exponential function *f* have the form . Consider three cases: the central partition has no mutants (*S*_{c}=0), the central partition has no residents (*S*_{c}=*C*) or the central partition is mixed (0<*S*_{c}<*C*). We can write as
If all three cases equal 1, then as well. Setting the first two cases to 1 and simplifying gives us
which have the non-trivial solution
The third case gives us the equation
which will be satisfied by any *h*_{c},*h*_{v} that satisfiy the first two equations—in particular, by the values obtained above.

As *h*_{c} and *h*_{v} are not dependent on *t*, we have a suitable transformation such that for all *t*. We may now use theorem 2.1 to write down the fixation probability of the complete bipartite graph directly from equation (2.1).

The complete bipartite graph terminates when the mutants go extinct (**b**=[0,0]) or occupy all centres and vertices (**a**=[*C*,*V* ]). Inserting , **b**=[0,0], **a**=[*C*,*V* ] and the initial state **S**_{0}=[*S*_{c,0},*S*_{v,0}] into equation (2.1)

This is the same result as that reported by Voorhees & Murray [16], but in a simpler form.

Figure 4 shows three plots of *p*_{fix} as a function of *V* for three different initial states **S**_{0}=[0,1] or [1,1] or [1,0], each with three different values of *C*. We see that *p*_{fix} is extremely sensitive to the initial state **S**_{0}; in fact, comparing the *C*=1 traces, we see that the star graph (§3*b*) can only amplify selection with respect to the Moran process if *S*_{v,0}>0. For the more general bipartite graph, if the starting state is a single mutant, then selection is amplified when that mutant appears in the larger partition and suppressed when that mutant appears in the smaller partition. Notice that, when *C*=*V* , *p*_{fix}=*p*_{fix Moran} as demanded by the isothermal theorem [2].

## 4. Discussion

We have shown how to use martingales to calculate fixation probabilities on evolutionary graphs. Martingales yield clean, tractable and exact expressions for these fixation probabilities. Martingales do not require us to make simplifying assumptions such as large population sizes or weak selection to facilitate tractable analysis. We can often obtain fixation probabilities within a few lines of mathematics, even if the random walk is multi-dimensional (such as the star graph or the complete bipartite graph). These attributes of martingales make them an attractive method to study evolutionary graphs. Martingales are particularly useful if we are interested in how the fixation probability depends on the initial state of the graph.

The star graph provides a recent example that illustrates the advantages of martingales over other approaches to study evolutionary graphs, such as Markov matrix methods and diffusion approximations (§3*b*). The star graph was introduced by Lieberman *et al*. in 2005 [2] and their result for the fixation probability on star graphs, equation (3.4), was obtained by taking a limit of a large number of vertices. The exact result for the fixation probability of mutants on star graphs with any number of vertices was subsequently reported by Broom & Rychtar [4]. Broom & Rychtar used a recurrence relation-based approach to obtain fixation probabilities on star graphs. Our equation (3.3) for the fixation probability is equivalent to, but less complex than, their expression. Also, our expression is more general in that it explicitly allows for any starting state, and we showed that the amplifying effect of star graphs is very sensitive to that starting state. Furthermore, we can generalize the result to star graphs with any number of individuals at the centre (i.e. complete bipartite graphs). While Markov matrix techniques or diffusion approximations are widely applicable to evolutionary graphs, martingales have clear advantages over these approaches when a graph possesses suitable symmetry.

Another possible approach to studying absorbing random walks is by exhaustive simulation. Simulation and search methods are constrained only by the time it takes to carry out the necessary computations. In principle, it must be possible to simulate a well-defined model, so in that sense simulation is a general solution to problems of this kind. However, even in an age of rapidly advancing computing technology, it is important to continue to develop and apply analytical methods and models for three reasons. First, in practice, computation time remains a serious constraint on simulation-based approaches, even for seemingly simple models. Second, an analytic model allows us to generalize our results beyond the specific parameter values of our simulations. Third, one way of checking the correctness of simulation code is to verify its consistency with analysable cases.

The drawback of martingales is that seemingly small changes to the structure of a graph can destroy the symmetry required for one to exist. For example, consider the star graph from §3*b*. If we drop the assumption that the connections are unweighted, then transforming the **X**_{t} with an exponential function *f* no longer yields a martingale. In this case, we must either search for a different transformation (which can be time-consuming), or find a limit or special conditions under which a martingale exists, or defer to other methods of analysis. However, although the presence or absence of a martingale is sensitive to the structure of an evolutionary graph, when a suitable transformation is available, the required calculations become very simple. Therefore, when studying an evolutionary graph, it might be worthwhile to check whether a martingale exists before deferring to other methods of analysis.

We hope that this approach can be applied to further examples. Possible extensions include finding martingale transformations for *k*-partite graphs, directed graphs and graphs with weighted edges.

Evolutionary graph theory, though still in its infancy, has been applied to a diversity of fields. Many researchers have investigated individuals that play classic evolutionary games while being constrained by the topology of a graph [5,17–21]. Many evolutionary biological processes can be modelled as bi-level graphs, including examples of symbiosis and commensalism [22]. Outside of evolutionary biology, graph theory or similar concepts have been applied to model economic networks [23], the spread of epidemics in populations [24] and brain connectivity networks [25]. As evolutionary graph theory expands its breadth of applications, it will become increasingly important to develop mathematical methods that analyse the global statistics of evolutionary graphs such as fixation probabilities. Martingales are an excellent candidate for this task.

## Footnotes

↵1 Though Broom & Rychtar did explicitly investigate the sensitivity of the fixation probability with respect to the initial state for line graphs.

- Received November 2, 2013.
- Accepted February 10, 2014.

- © 2014 The Author(s) Published by the Royal Society. All rights reserved.