#  Fixation times on directed graphs

David A. Brewster  John A. Paulson School of Engineering and Applied Sciences,
Harvard University, Cambridge, MA 02138, USA  Martin A. Nowak  Department of
Mathematics, Harvard University, Cambridge, MA 02138, USA  Department of
Organismic and Evolutionary Biology, Harvard University, Cambridge MA 02138,
USA  Josef Tkadlec  Department of Mathematics, Harvard University, Cambridge,
MA 02138, USA  Computer Science Institute, Charles University, Prague, Czech
Republic

###### Abstract

Computing the rate of evolution in spatially structured populations can be
difficult. A key quantity that describes evolutionary dynamics is the fixation
time of a single mutant with relative reproduction rate $r\geqslant 1$ who
invades a population of residents. We say that the fixation time is “fast” if
it is at most polynomial in terms of the population size $N$. In this work, we
study fixation times of advantageous mutants ($r>1$) and neutral mutants
($r=1$) on directed graphs, which are defined as those graphs that have at
least some one-way connections. We obtain three main results. First, we prove
that for any directed graph the fixation time is fast, provided that $r$ is
sufficiently large. Second, we devise an efficient algorithm that gives an
upper bound for the fixation time for any graph and any $r\geqslant 1$. Third,
we identify a broad class of directed graphs with fast fixation times for any
$r\geqslant 1$. This class includes previously studied amplifiers of
selection, such as Superstars and Metafunnels. We also show that on some
graphs fixation time is not a monotonically declining function of $r$; in
particular, neutral fixation can occur faster than fixation for small
selective advantages. Our results have important algorithmic consequences and
enable efficient computational exploration of various properties of directed
graphs.

##  1 Introduction

Evolution is a stochastic process that acts on populations of reproducing
individuals. Two main driving forces of evolutionary dynamics are mutation and
selection [1, 2, 3]. Mutation generates new variants and selection prunes
them. When new mutations are sufficiently rare, the evolutionary dynamics are
characterized by the fate of a single new mutant. The mutant can either take
over the whole population or become extinct. Even when the mutation grants its
bearer a relative fitness advantage $r\geqslant 1$, it might still go extinct
due to random fluctuations [4]. Two key parameters that quantify the fate of
the newly occurring mutation are the fixation probability and the fixation
time [5, 6].

Spatial structure has profound effects on both the fixation probability and
the fixation time. Those effects are studied within the framework of
Evolutionary Graph Theory [7, 8, 9]. There, individuals are represented as
nodes of a graph (network). The edges (connections) of the graph represent the
migration patterns of offspring. The edges can be one-way or two-way. Graphs
can represent the well-mixed population, spatial lattices, island sub-
populations, or arbitrary complex spatial structures.

Previous research investigated population structures with various effects on
fixation probability and time [10, 11, 12, 13, 14]. For example, isothermal
graphs have the same fixation probability as the well-mixed population [7],
suppressors of selection reduce the fixation probability of advantageous
mutants [15], and amplifiers of selection enhance the fixation probability of
advantageous mutants [16]. Amplifiers are population structures that could
potentially accelerate the evolutionary search [17]. Known classes of
amplifiers include families such as Stars [18, 19, 20], Comets [21],
Superstars [22, 23], or Megastars [24].

Interestingly, the amplification typically comes at a cost of increasing the
fixation time [25], sometimes substantially [26]. This is problematic, since
when fixation times are extremely long, fixation is not a relevant event any
more, and thus the fixation probability alone is not the most representative
quantity [27, 28]. It is therefore paramount to understand how the population
structure affects the fixation time and, in particular, what are the
population structures for which the fixation time is “reasonably fast.”

Borrowing standard concepts from computer science [29], in this work we say
that fixation time is fast if the fixation time is (at most) polynomial in
terms of the population size $N$. Otherwise we say that the fixation time is
long, and the corresponding population structure is slow. Two important known
results are: (i) for all undirected graphs the fixation time is fast [30, 31];
and (ii) if some edges are one-way (if the graph is directed), then the
fixation time can be exponentially long [32]. The latter result has an
important negative consequence: when the fixation time is exponentially long,
we know no tool to efficiently simulate the process. Therefore, computing or
approximating any relevant quantities for realistic population sizes is in
practice infeasible.

In this work, we present three positive results that concern fixation times on
directed graphs (where some or all edges are one-way). First, we prove that
for any directed graph the fixation time is fast, provided that the mutant
fitness advantage $r$ is sufficiently large. Second, we devise an efficient
algorithm that gives an upper bound on the fixation time, for any graph and
any $r\geqslant 1$. The bound can be used to estimate how long one needs to
run the simulations until they terminate. Third, we identify a broad class of
directed graphs for which the fixation times are fast for any $r\geqslant 1$.
This class includes many previously studied amplifiers of selection, such as
Superstars and Metafunnels. To conclude, we discuss important algorithmic
consequences that enable efficient computational exploration of various
properties of directed graphs.

##  2 Model

In this section we define the notions we use later, such as the population
structure (represented by a graph), the evolutionary dynamics (Moran Birth-
death process), and the key quantities (fixation probability and fixation
time).

###  2.1 Population structure

The spatial population structure is represented by a graph (network)
$G=(V,E)$, where $V$ is the set of $N$ nodes (vertices) labeled
$v_{1},\dots,v_{N}$ and $E$ is the set of directed one-way edges (links)
connecting pairs of different nodes. A two-way connection between nodes $u$
and $v$ is represented by two one-way edges $u\to v$ and $v\to u$. We assume
that the graph is connected. For any node $v$, the number of edges incoming to
$v$ is called the indegree (denoted $\operatorname{deg}^{-}(v)$), and the
number of outgoing edges is called the outdegree (denoted
$\operatorname{deg}^{+}(v)$). When the two numbers coincide, we call them the
degree (denoted $\operatorname{deg}(v)$).

###  2.2 Graph classes

We say that a graph is undirected if for every edge $u\to v$ there is also an
edge $v\to u$ in the opposite direction. Otherwise we say that a graph is
directed. We say that a graph is regular if all nodes have the same degree,
that is, there exists a number $d$ such that
$\operatorname{deg}^{-}(v)=\operatorname{deg}^{+}(v)=d$ for all nodes $v\in
V$. We say that a graph $G$ is Eulerian (also known as a circulation) if
$\operatorname{deg}^{-}(v)=\operatorname{deg}^{+}(v)$ for each node $v$.
Finally, in this work we say that a graph is balanced if an equality

$\frac{1}{\operatorname{deg}^{+}(v)}\cdot\sum_{w\in V\colon v\to w\in
E}\frac{1}{\operatorname{deg}^{-}(w)}=\frac{1}{\operatorname{deg}^{-}(v)}\cdot\sum_{u\in
V\colon u\to v\in E}\frac{1}{\operatorname{deg}^{+}(u)}$

holds for all nodes $v$. It is straightforward to check that the class of
balanced graphs includes the regular graphs and the undirected graphs, as well
as other graph classes such as Superstars or Metafunnels[7], see Appendices.
Below we will prove that the fixation times on all balanced graphs are fast
for any $r\geqslant 1$.

###  2.3 Moran Bd process

To model the evolutionary dynamics we consider the standard Moran Birth-death
process. Each node of the graph is occupied by a single individual. Initially,
all individuals are wild-type residents with normalized fitness equal to $1$,
except for a single individual who is a mutant with relative fitness advantage
$r\geqslant 1$. We assume that the initial mutant inhabits a node selected
uniformly at random. Given a graph $G$ and a relative fitness advantage
$r\geqslant 1$, Moran Birth-death process is a discrete-time stochastic
process, where in each step:

  1. 1.

First (Birth), we select an individual with probability proportional to its
fitness. Suppose we selected node $u$.

  2. 2.

Second (death), we select a neighbor of $u$ uniformly at random. Suppose we
selected node $v$.

  3. 3.

Finally (update), we replace the individual at node $v$ by a copy of
individual at node $u$.

At each time-step, the current configuration is the subset of nodes occupied
by mutants. Since the graph is connected, with probability 1 we eventually
obtain a configuration where either all nodes are mutants (we say that mutants
fixed), or all nodes are residents (we say that mutants went extinct).

###  2.4 Fixation probability and fixation time

The key quantities that we consider in this work are fixation probability and
fixation time.

Given a graph $G$, a mutant fitness advantage $r\geqslant 1$, and a current
configuration $X$ of nodes occupied by mutants, the fixation probability
$\rho^{r}(G,X)$ is the probability that starting from $X$, the mutants
eventually fix (as opposed to going extinct). Morever, we define an auxiliary
quantity $\rho_{\rm min}$ that turns out to be useful later in our results.
Formally, given a graph $G$ and $r=1$, for $i=1,\dots,N$ denote by
$\rho_{i}(G)=\rho^{r=1}(G,\\{v_{i}\\})$ the fixation probability of a single
neutral mutant who initially appears at node $v_{i}$. We define $\rho_{\rm
min}(G)=\min_{i}\rho_{i}(G)$ to be the smallest of those $N$ fixation
probabilities.

To measure the duration of the process until fixation (or extinction) occurs,
different notions are used. The absorption time $\operatorname{AT}^{r}(G,X)$
is the expected number of steps of the Moran Birth-death process until the
process terminates, regardless of what is the outcome (mutant fixation or
extinction). In contrast, fixation time $\operatorname{T}^{r}(G,X)$ is the
expected number of steps averaged over only those evolutionary trajectories
that terminate with mutant fixation. Similarly, one can define the extinction
time $\operatorname{ET}^{r}(G,X)$ averaging over only those trajectories that
terminate with the mutant going extinct. By linearity of expectation, the
three quantities are related as
$\operatorname{AT}^{r}(G,X)=\rho^{r}(G,X)\cdot\operatorname{T}^{r}(G,X)+(1-\rho^{r}(G,X))\cdot\operatorname{ET}^{r}(G,X)$.
Our objective in this work is to provide upper bounds on the absorption time
and on the fixation time. To that end, given a graph $G$ and a mutant fitness
advantage $r\geqslant 1$, let
$\operatorname{T}^{r}(G)=\max_{X}\operatorname{T}^{r}(G,X)$ be the largest
fixation time among all possible starting configurations $X$. In the limit of
strong selection $r\to\infty$ we also define
$\operatorname{T}^{\infty}(G)=\lim_{r\to\infty}T^{r}(G)$. This regime is
called the ecological scenario [33] and corresponds to new invasive species
populating an existing ecosystem.

###  2.5 Asymptotic notation

Recall that a function $f(N)$ is (at most) polynomial if there exists a
positive constant $c$ such that $f(N)\leqslant N^{c}$ for all large enough
$N$. Examples of polynomial functions are $f(N)=\frac{1}{2}N(N+1)$ and
$f_{2}(N)=10\cdot N\log N$, whereas functions such as $g(N)=1.1^{N}$ and
$g_{2}(N)=2^{\sqrt{N}}$ are not polynomial, since they grow too quickly. In
computer science, problems that can be solved using polynomially many
elementary computations are considered tractable. In alignment with that,
given a population structure $G$ with $N$ nodes, we say that fixation time is
fast if it is at most polynomial in terms of the population size $N$.

##  3 Results

We present three main types of results.

###  3.1 Fixation time is fast when selection advantage is strong enough

As our first main result, we prove that the fixation time on any directed
graph is fast, provided that the mutant fitness advantage $r$ is large enough.

As an illustration, for every $N=2k$ consider a two-layer graph
$\operatorname{TL}_{N}$ depicted in Fig. 1(a). It consists of two layers of
$k-1$ nodes each, a source node $v_{0}$ and a final node $v_{2k}$. The grey
segments represent two-way edges. Starting from node $v_{0}$, mutants
eventually propagate through the first layer, through the second layer, and to
the final node. But while spreading through the first layer, they are under an
increased pressure due to the resident nodes in the second layer. As a
consequence, the fixation time crucially depends on $r$. When $r=1.1$, Fig.
1(b) shows that the fixation time scales exponentially in $N$ (that is, it is
long). In contrast, in the limit of large $r$ the fixation time scales
polynomially in $N$, that is, it is fast.

Figure 1:  Fast and long fixation times on a two-layer graph. a, For $N=2k$, a
two-layer graph $\operatorname{TL}_{N}$ consists of a single source node
$v_{1}$, two layers of $k-1$ nodes each, and a final node $v_{N}$. The edges
within the layers are two-way (grey) and the edges between corresponding nodes
of the two layers are one-way (black). Here $N=12$. As mutants (red nodes)
spread from the source node $v_{1}$ through the bottom layer rightward, they
can propagate along only one edge, whereas residents (blue nodes) fight back
along multiple edges. b, Since the mutant at $v_{1}$ never goes extinct,
eventual mutant fixation is guaranteed, but the timescale crucially depends on
the mutant fitnes sadvantage $r$. When $r=1.1$, the fixation time
$\operatorname{T}^{r}(\operatorname{TL}_{N},v_{1})$ is exponential in $N$,
whereas when $r=100$ it is polynomial. (Each data point is an average over
$10^{3}$ simulations.)

In general, we can prove the following result about an arbitrary population
structure.

######  Theorem 1.

Let $G_{N}$ be an arbitrary graph on $N$ nodes. Suppose that $r\geqslant
N^{2}$. Then $\operatorname{T}^{r}(G_{N})\leqslant N^{4}$.

Theorem 1 implies that while the fixation time on certain graphs can be long
for some values of $r$, this effect is inevitably transient, and the fixation
time becomes fast once $r$ exceeds a certain threshold. The intuition behind
the proof is that if $r$ is large enough, the size of the mutant subpopulation
is always more likely to increase then to decrease regardless of which nodes
are currently occupied by mutants. Thus, the evolutionary process can be
mapped to a random walk with a constant forward bias. It is known that such
biased random walks absorb polynomially quickly. See Appendices for details.

An attractive feature of Theorem 1 is that it applies to all directed graphs.
An obvious limitation is that the condition $r\geqslant N^{2}$ is rather
stringent. For graphs with certain structural features, we prove that the
constraint on $r$ can be considerably relaxed. Recall that a directed graph is
said to be Eulerian (also called a circulation) if each node has the same
indegree as outdegree. In that case, we refer to the number
$\operatorname{deg}^{-}(v)=\operatorname{deg}^{+}(v)$ simply as a degree of
node $v$.

######  Theorem 2.

Let $G_{N}$ be an Eulerian graph on $N$ nodes with smallest degree $\delta$
and largest degree $\Delta$. Suppose $r\geqslant\Delta/\delta$. Then
$\operatorname{T}^{r}(G_{N})\leqslant 4\Delta^{2}N^{8}$.

We point out two special cases of Theorem 7 (for its proof see Appendices).

First, consider any regular graph $G_{N}$, that is, a graph where all nodes
have the same indegree and outdegree equal to $d$. Then, the graph is Eulerian
and we have $d=\Delta=\delta$, and thus Theorem 7 implies that
$\operatorname{T}^{r}(G_{N})$ is at most a polynomial in $N$ and $d$ for any
$r\geqslant 1$. In other words, fixation time on any regular graph is fast for
any $r\geqslant 1$ (we note that this result is known[32]).

Second, consider an Eulerian graph that is “close to being regular”, in the
sense that each node has degree either 4 or 5. An example of such a graph is a
square lattice with several additional long-range connections (and all edges
two-way). Then, Theorem 7 implies that the fixation time is fast for every
$r\geqslant 5/4=1.25$.

###  3.2 Fixation time for small selective advantage

Our transience result shows that for any fixed graph $G$, the fixation time is
fast when $r$ is sufficiently large. It is natural to hope that perhaps for
any fixed graph $G$ the fixation time is a monotonically decreasing function
of $r$ for $r\geqslant 1$. However, this is not the case, as shown in Fig. 2.

Figure 2:  Fixation time is not monotone in $r$. a, In an (undirected) star
graph $S_{4}$ on 4 nodes, one node (center) is connected to three leaf nodes
by two-way edges. When the initial mutant appears at a leaf $v$, the fixation
time $\operatorname{T}^{r}(S_{4},v)$ increases as $r$ increases from $r=1$ to
roughly $r=1.023$. Then it starts to decrease. c, Normalized fixation time
$\operatorname{T}^{r}(G,v)/\operatorname{T}^{r=1}(G,v)$ as a function of
$r\in[1,1.3]$, for all 83 connected graphs $G$ with 4 nodes, and all four
possible mutant starting nodes $v$. As $r$ increases, the fixation time goes
up for 182 of the possible $4\cdot 83=332$ initial conditions. The increase is
most pronounced for the so-called lollipop graph $L_{4}$ and a starting node
$u$. In contrast, for the same lollipop graph and a different starting node
$w$, the fixation time decreases the fastest.

Briefly speaking, the effect responsible for the increase in fixation time
when $r=1+\varepsilon$ is that by increasing the mutant fitness advantage,
certain evolutionary trajectories that used to lead to mutant extinction
instead lead to mutant fixation. Since those “newly fixating” trajectories
might generally take relatively long to fix, the average length of the
fixating trajectories can go up. Similarly, the absorption time can also go up
as we increase $r$.

Despite the lack of monotonicity, we can show that the fixation time can not
go up too much as we increase $r$. Recall that $\rho_{\rm
min}(G_{N})=\min\\{\rho^{r=1}(G_{N},\\{v\\})\mid v\in G_{N}\\}$ denotes the
fixation probability under neutral drift ($r=1$), when the initial mutant
appears at a node $v$ with the smallest fixation probability. Note that for
any graph with $N$ nodes we have $\rho_{\rm min}(G_{N})\leqslant 1/N$, but
$\rho_{\rm min}(G_{N})$ could in general be substantially smaller than $1/N$.
Finally, recall that the quantity $\rho_{\rm min}(G_{N})$ can be computed
efficiently by solving a linear system of $N$ equations [9, 12, 34].

We can now state our second main result.

######  Theorem 3.

Fix a graph $G_{N}$ and $r\geqslant 1$. Then
$\operatorname{T}^{r}(G_{N})\leqslant\left(\frac{N}{\rho_{\rm
min}(G_{N})}\right)^{4}.$

We note that Theorem 3 yields an efficiently computable upper bound on
$\operatorname{T}^{r}(G_{N})$. In the next section we elaborate on the
computational consequences of this result. In the rest of this section, we
give a brief intuition behind the proof of Theorem 3.

The proof relies on two ingredients. First, instead of considering the process
with mutant fitness advantage $r$, we consider the neutral process that
corresponds to $r=1$. There, using a martingale argument we show that the
fixation time $\operatorname{T}^{r=1}(G_{N})$ can be bounded from above in
terms of the quantity $\rho_{\rm min}$. The intuition is that as long as all
fixation probabilities are non-negligible, all steps of the stochastic process
have substantial magnitude either towards fixation or towards extinction. As a
consequence, we are able to argue that either fixation or extinction will
occur after not too many steps. All in all, this yields an upper bound on
fixation time $\operatorname{T}^{r=1}(G_{N})$ of the neutral process in terms
of the quantity $\rho_{\rm min}$. See Appendices for details.

As our second ingredient, we translate the bound on
$\operatorname{T}^{r=1}(G_{N})$ into a bound on $\operatorname{T}^{r}(G_{N})$
for any $r\geqslant 1$. We note that, as indicated in Fig. 2, for a fixed
graph $G_{N}$ the fixation time is in general not a monotonically decreasing
function of $r$. Nevertheless, the two processes can be coupled in a certain
specific way, which allows us to argue that while
$\operatorname{T}^{r}(G_{N})$ can be somewhat larger than
$\operatorname{T}^{r=1}(G_{N})$, it can not be substantially larger. In this
step, we again use the quantity $\rho_{\rm min}$. See Appendices for details.

###  3.3 Fixation time is fast when the graph is balanced

As noted above, Theorem 3 provides an upper bound on the fixation time for any
graph $G_{N}$ and any mutant fitness advantage $r\geqslant 1$, in terms of the
quantity $\rho_{\rm min}(G_{N})$. By definition, we have $0\leqslant\rho_{\rm
min}(G_{N})\leqslant 1/N$. When the quantity $\rho_{\rm min}(G_{N})$ is
exponentially small, the upper bound from Theorem 3 becomes exponentially
large, and thus not particularly interesting. However, for many graphs the
quantity $\rho_{\rm min}(G_{N})$ turns out to be much larger, namely inversely
proportional to a polynomial in $N$. In those cases, Theorem 3 implies that
the fixation time $\operatorname{T}(G_{N},r)$ is fast for any $r\geqslant 1$.

In particular, as our third main result we prove that this occurs for a broad
class of graphs which we call balanced graphs. Formally, we say that a graph
$G_{N}$ is balanced if an equality

$\frac{1}{\operatorname{deg}^{+}(v)}\cdot\sum_{w:v\to w\in
E}\frac{1}{\operatorname{deg}^{-}(w)}=\frac{1}{\operatorname{deg}^{-}(v)}\cdot\sum_{u:(u,v)\in
E}\frac{1}{\operatorname{deg}^{+}(u)}$

holds for all nodes $v$. We note that the family of balanced graphs includes
many classes of graphs studied in the context of Moran process in the existing
literature, such as the undirected graphs [30], regular (possibly directed)
graphs [32], as well as Superstars and Metafunnels [7]. It also includes other
classes of directed graphs of general interest, such as cyclic complete
multipartite graphs, book graphs, or directed fans [35], see Fig. 3.

Figure 3:  Types of balanced graphs. The class of balanced graphs includes a,
Superstars; b, Cyclic complete multipartite graphs; c, Book graphs; and d,
Directed fans. Theorem 4 implies that the fixation time on all those graphs is
fast for all $r\geqslant 1$.

We have the following theorem.

######  Theorem 4.

Let $G_{N}$ be a balanced graph. Then:

  1. 1.

$\rho^{r=1}(G_{N},u)=\frac{1/\operatorname{deg}^{-}(u)}{\sum_{v\in
V}1/\operatorname{deg}^{-}(v)}\geqslant 1/N^{2}$ for any node $u$.

  2. 2.

$\operatorname{T}^{r}(G_{N})\leqslant N^{12}$ for any $r\geqslant 1$.

Theorem 4 implies that the fixation time on all balanced graphs is fast for
all $r\geqslant 1$. Similarly, we can prove that it is fast for Megastars [24]
and all $r\geqslant 1$ (see Appendices).

The proof of the first part of Theorem 4 relies on the fact that in the
neutral case $r=1$ the fixation probability is additive. This allows us to
reduce the size of the linear system that describes the underlying Markov
chain from $2^{N}$ equations to $N$ equations. For balanced graphs, this
system takes a special form that admits an explicit solution. The second part
then follows directly from Theorem 3. See Appendices for details.

We note that the second part of Theorem 3 has an important computational
consequence. Since the fixation time on any balanced graph is bounded from
above for any $r\geqslant 1$, individual-based simulations of the evolutionary
process are guaranteed to terminate quickly with high probability [30]. Any
relevant quantities of interest, such as the fixation probability of the
mutant with $r\gneq 1$, can thus be efficiently approximated to arbitrary
precision. In particular, Theorem 3 yields a fully-polynomial randomized
approximation scheme (FPRAS) for the fixation probability on balanced graphs
with any $r\geqslant 1$.

######  Theorem 5.

There is a FPRAS for fixation probability on balanced graphs for any
$r\geqslant 1$.

We note that Theorem 5 applies also to any (not necessarily balanced) graph
$G_{N}$, provided that the quantity $\rho_{\rm min}(G_{N})$ is inversely
proportional to a polynomial. This is the case e.g. for Megastars. Moreover,
when $\rho_{\rm min}(G_{N})$ is smaller than that, Theorem 3 still gives an
explicit, efficiently computable upper bound on the fixation time that can be
used to bound the running time of any individual-based simulations.

###  3.4 Computational experiments

Finally, to further illustrate the scope of our results we run several
computational experiments on graphs with small population size $N$. We use
nauty [36] to perform such enumerations. Since already for $N=6$ there are
more than one million non-isomorphic strongly connected directed graphs, we
consider $N=5$. For each of the 5048 graphs with $N=5$ we compute the fixation
time and the fixation probability under uniform initialization by solving the
underlying Markov chain using numerical methods (Fig. 4).

Figure 4:  Fixation time and fixation probability under uniform initialization
for all 5048 graphs with $N=5$ nodes, for a, $r=1.1$ and b, $r=2$. Each graph
is represented as a colored dot. The undirected graphs (with all edges two-
way) are labeled in blue. The oriented graphs (with no edges two-way) are
labeled in green. All other directed graphs are labeled in orange. The slowest
graph is the (undirected) Star graph $S_{5}$. Among the oriented graphs, the
slowest graph is the Fan graph $F_{5}$.

The slowest graph is the (undirected) Star graph. Note that when $N$ is large
the fixation time on a Star graph is known to be proportional to roughly
$N^{2}$ [25].

Among the graphs that do not contain any two-way edges, the slowest graphs are
variants of either a fan graph $F_{N}$, or a vortex graph $V_{N}$. Since both
the fan graphs and the vortex graphs belong to the class of balanced graphs,
the fixation time on those graphs is fast for any population size $N$ and any
mutant fitness advantage $r\geqslant 1$ due to Theorem 4. The fixation time
appears to be proportional to roughly $N^{2}$ (see Fig. 5).

Figure 5:  Fixation time on slow oriented graphs. a, The Fan graph with $k$
blades has $N=2k+1$ nodes and $3k$ one-way edges (here $k=5$ which yields
$N=11$). The Vortex graph with batch size $k$ has $N=2k+2$ nodes and $4k$
edges (here $k=3$ which yields $N=8$). b-c, For both the Fan graphs and the
Vortex graphs the fixation time scales roughly as $N^{2}$, both for $r=1.1$
and $r=100$. (Each data point is an average over 100 simulations.)

Together, those results suggest that even though directed graphs with
exponentially long fixation times do exist, in practice most small directed
graphs reach fixation reasonably quickly.

##  4 Discussion

Studying the evolutionary dynamics in spatially structured populations is
notoriously hard. An important aspect is to understand the fixation time of a
newly occurring mutant. When the fixation time is exponentially long, the
process is expensive to simulate, and moreover various commonly studied
quantities such as fixation probability are largely irrelevant. It is thus
paramount to delineate settings in which the fixation time is “relatively
fast”, as opposed to being “exceedingly long.”

In this work, we consider spatial structures in which some (or all) edges are
one-way. It is known that on such structures the fixation time can be
exceedingly long [32]. Nevertheless, here we present three results which
indicate that fixation times on spatial structures with one-way edges are
often fast.

First, we prove that on any population structure the fixation time is fast,
provided that the mutant fitness advantage $r$ exceeds a certain threshold
value $r^{\star}$ (see Theorem 1). In the special case when the population
structure is represented by a regular graph, the threshold value simplifies to
$r^{\star}=1$, and we recover a known result that the fixation time on regular
graphs is short for all $r\geqslant 1$ [32]. As another corollary, for any
Eulerian graph whose degrees are sandwiched between $\delta$ and $\Delta$ we
can set $r^{\star}=\Delta/\delta$ (see Theorem 7).

Second, somewhat counter-intuitively we show that fixation time sometimes goes
up as we increase $r$. That is, on certain spatial structures fixation of a
neutral mutant occurs faster than fixation of a mutant with a small selective
advantage. Nevertheless, we show that the magnitude of this effect can be
bounded. In particular, in the spirit of parametrized complexity, given a
graph structure $G_{N}$ we define a certain efficiently computable quantity
$\rho_{\rm min}(G_{N})$, and we bound the fixation time for any $r\geqslant 1$
from above using $\rho_{\rm min}(G_{N})$ and $N$ (see Theorem 3). This has
important consequences for performing individual-based simulations that
typically run the process several times and report an empirical average. The
limitation of naive individual-based simulations is that, a priori, it is not
clear how much time will be needed until the simulations converge, and
deciding to stop the simulations mid-way may bias the empirical average, e.g.
by over-representing the evolutionary trajectories that quickly go extinct.
Using Theorem 3, this limitation can be circumvented by first efficiently
computing an upper bound on the expected fixation time without having to
simulate the process even once.

Third, we identify a class of population structures show fixation times are
fast for any $r\geqslant 1$. This class is surprisingly broad. To start with,
it includes several families of graph that had been studied in the context of
Evolutionary Graph Theory earlier, such as Superstars and Metafunnels [7], or
directed Fans [35]. Furthermore, the class also includes several other graph
families of general interest, such as book graphs or cyclic complete
multipartite graphs. Similarly, we prove that the fixation times on Megastars
are fast for all $r\geqslant 1$ too.

While the focus of this work is to identify regimes and population structures
that lead to fast fixation times, population structures with long fixation
times may also bedesirable, e.g. in conservation ecology to maintain high
levels of ecological diversity [37, 38, 39, 40, 41].

We note that throughout this work we considered the standard model of Moran
process with Birth-death updating. A natural direction for future research is
to consider related models, such as those with location-dependent fitness [42,
43, 41] or those with death-Birth updating. It is known that in terms of
fixation probabilities the Birth-death and the death-Birth processes behave
quite differently [44, 18, 10, 45, 46]. However, in terms of fixation time
they are qualitatively similar [47].

A decade ago, a foundational work by Diaz et. al. showed that fixation time on
any undirected population structure is fast [30]. This result enabled
extensive computational exploration of undirected graphs that later lead to
several inspiring research outputs [10, 48, 49, 50, 27]. It is our hope that
by enabling computational exploration of population structures with some (or
all) one-way connections, this work will serve the same purpose.

##  5 Data and code availability

Code for the figures and the computational experiments is available from the
Figshare repository: https://doi.org/10.6084/m9.figshare.23802531.

##  6 Acknowledgements

We thank Brendan McKay for helpful instructions on using nauty and Salil
Vadhan for insightful discussions about random walks on directed graphs. J.T.
was supported by Center for Foundations of Modern Computer Science (Charles
Univ. project UNCE/SCI/004).

## References

  * [1] Kimura M.  Evolutionary rate at the molecular level.  Nature. 1968;217:624-6.
  * [2] Moran PAP.  Random processes in genetics.  In: Mathematical proceedings of the cambridge philosophical society. vol. 54. Cambridge University Press; 1958. p. 60-71.
  * [3] Ewens WJ.  Mathematical population genetics: theoretical introduction. vol. 27.  Springer; 2004.
  * [4] Durrett R, Levin S.  The importance of being discrete (and spatial).  Theoretical population biology. 1994;46(3):363-94.
  * [5] Whitlock MC.  Fixation probability and time in subdivided populations.  Genetics. 2003;164(2):767-79.
  * [6] Slatkin M.  Fixation probabilities and fixation times in a subdivided population.  Evolution. 1981:477-88.
  * [7] Lieberman E, Hauert C, Nowak MA.  Evolutionary dynamics on graphs.  Nature. 2005;433(7023):312-6.
  * [8] Díaz J, Mitsche D.  A survey of the modified Moran process and evolutionary graph theory.  Computer Science Review. 2021;39:100347.
  * [9] Donnelly P, Welsh D.  Finite particle systems and infection models.  In: Mathematical Proceedings of the Cambridge Philosophical Society. vol. 94. Cambridge University Press; 1983. p. 167-82.
  * [10] Hindersin L, Traulsen A.  Most undirected random graphs are amplifiers of selection for birth-death dynamics, but suppressors of selection for death-birth dynamics.  PLoS computational biology. 2015;11(11):e1004437.
  * [11] Broom M, Hadjichrysanthou C, Rychtář J.  Evolutionary games on graphs and the speed of the evolutionary process.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2010;466(2117):1327-46.
  * [12] Broom M, Hadjichrysanthou C, Rychtář J, Stadler B.  Two results on evolutionary processes on general non-directed graphs.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2010;466(2121):2795-8.
  * [13] Monk T, van Schaik A.  Wald’s martingale and the conditional distributions of absorption time in the Moran process.  Proceedings of the Royal Society A. 2020;476(2241):20200135.
  * [14] Monk T, van Schaik A.  Martingales and the characteristic functions of absorption time on bipartite graphs.  Royal Society Open Science. 2021;8(10):210657.
  * [15] Nowak MA, Michor F, Iwasa Y.  The linear process of somatic evolution.  Proceedings of the National Academy of Sciences. 2003;100(25):14966-9.
  * [16] Nowak MA.  Evolutionary dynamics: exploring the equations of life.  Harvard University Press; 2006.
  * [17] Adlam B, Chatterjee K, Nowak MA.  Amplifiers of selection.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2015;471(2181):20150114.
  * [18] Hadjichrysanthou C, Broom M, Rychtár J.  Evolutionary games on star graphs under various updating rules.  Dynamic Games and Applications. 2011;1(3):386-407.
  * [19] Monk T, Green P, Paulin M.  Martingales and fixation probabilities of evolutionary graphs.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2014;470(2165):20130730.
  * [20] Chalub FA.  Asymptotic expression for the fixation probability of a mutant in star graphs.  arXiv preprint arXiv:14043944. 2014.
  * [21] Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak MA.  Amplification on undirected population structures: comets beat stars.  Scientific reports. 2017;7(1):82.
  * [22] Díaz J, Goldberg LA, Mertzios GB, Richerby D, Serna M, Spirakis PG.  On the fixation probability of superstars.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2013;469(2156):20130193.
  * [23] Jamieson-Lane A, Hauert C.  Fixation probabilities on superstars, revisited and revised.  Journal of Theoretical Biology. 2015;382:44-56.
  * [24] Galanis A, Göbel A, Goldberg LA, Lapinskas J, Richerby D.  Amplifiers for the Moran process.  Journal of the ACM (JACM). 2017;64(1):1-90.
  * [25] Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA.  Population structure determines the tradeoff between fixation probability and fixation time.  Communications biology. 2019;2(1):138.
  * [26] Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak MA.  Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory.  Communications biology. 2018;1(1):71.
  * [27] Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA.  Fast and strong amplifiers of natural selection.  Nature Communications. 2021;12(1):4009.
  * [28] Sharma N, Traulsen A.  Suppressors of fixation can increase average fitness beyond amplifiers of selection.  Proceedings of the National Academy of Sciences. 2022;119(37):e2205424119.
  * [29] Cormen TH, Leiserson CE, Rivest RL, Stein C.  Introduction to algorithms.  MIT press; 2022.
  * [30] Díaz J, Goldberg LA, Mertzios GB, Richerby D, Serna M, Spirakis PG.  Approximating fixation probabilities in the generalized moran process.  Algorithmica. 2014;69:78-91.
  * [31] Goldberg LA, Lapinskas J, Richerby D.  Phase transitions of the Moran process and algorithmic consequences.  Random Structures & Algorithms. 2020;56(3):597-647.
  * [32] Díaz J, Goldberg LA, Richerby D, Serna M.  Absorption time of the Moran process.  Random Structures & Algorithms. 2016;49(1):137-59.
  * [33] Ibsen-Jensen R, Chatterjee K, Nowak MA.  Computational complexity of ecological and evolutionary spatial dynamics.  Proceedings of the National Academy of Sciences. 2015;112(51):15636-41.
  * [34] Maciejewski W.  Reproductive value in graph-structured populations.  Journal of Theoretical Biology. 2014;340:285-93.
  * [35] Allen B, Sample C, Jencks R, Withers J, Steinhagen P, Brizuela L, et al.  Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs.  PLoS computational biology. 2020;16(1):e1007529.
  * [36] McKay BD, Piperno A.  Practical graph isomorphism, II.  Journal of symbolic computation. 2014;60:94-112.
  * [37] Levene H.  Genetic equilibrium when more than one ecological niche is available.  The American Naturalist. 1953;87(836):331-3.
  * [38] Bulmer M.  Multiple niche polymorphism.  The American Naturalist. 1972;106(948):254-7.
  * [39] Felsenstein J.  The theoretical population genetics of variable selection and migration.  Annual review of genetics. 1976;10(1):253-80.
  * [40] Yeaman S, Otto SP.  Establishment and maintenance of adaptive genetic divergence under migration, selection, and drift.  Evolution. 2011;65(7):2123-9.
  * [41] Svoboda J, Tkadlec J, Kaveh K, Chatterjee K.  Coexistence times in the Moran process with environmental heterogeneity.  Proceedings of the Royal Society A. 2023;479(2271):20220685.
  * [42] Maciejewski W, Puleo GJ.  Environmental evolutionary graph theory.  Journal of theoretical biology. 2014;360:117-28.
  * [43] Kaveh K, McAvoy A, Nowak MA.  Environmental fitness heterogeneity in the Moran process.  Royal Society open science. 2019;6(1):181661.
  * [44] Sood V, Antal T, Redner S.  Voter models on heterogeneous networks.  Physical Review E. 2008;77(4):041121.
  * [45] Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA.  Limits on amplifiers of natural selection under death-Birth updating.  PLoS computational biology. 2020;16(1):e1007494.
  * [46] Brendborg J, Karras P, Pavlogiannis A, Rasmussen AU, Tkadlec J.  Fixation maximization in the positional moran process.  In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 36; 2022. p. 9304-12.
  * [47] Durocher L, Karras P, Pavlogiannis A, Tkadlec J.  Invasion dynamics in the biased voter process.  In: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence; 2022. p. 265-71.
  * [48] Möller M, Hindersin L, Traulsen A.  Exploring and mapping the universe of evolutionary graphs identifies structural properties affecting fixation probability and time.  Communications biology. 2019;2(1):137.
  * [49] Allen B, Lippner G, Chen YT, Fotouhi B, Momeni N, Yau ST, et al.  Evolutionary dynamics on any population structure.  Nature. 2017;544(7649):227-30.
  * [50] Goldberg LA, Lapinskas J, Lengler J, Meier F, Panagiotou K, Pfister P.  Asymptotically optimal amplifiers for the Moran process.  Theoretical Computer Science. 2019;758:73-93.
  * [51] He J, Yao X.  Drift analysis and average time complexity of evolutionary algorithms.  Artificial intelligence. 2001;127(1):57-85.
  * [52] Kötzing T, Krejca MS.  First-hitting times under drift.  Theoretical Computer Science. 2019;796:51-69.

## Appendices

This is a supplementary information to the manuscript Fixation times on
directed graphs. It contains formal proofs of the theorems listed in the main
text. In Appendices A and B we formally introduce the model and recall results
that we will use in our proofs. In the following sections we prove Theorems 1
to 5 from the main text.

##  Appendix A Preliminaries

A _graph_ $\mathsf{G}$ is a tuple $(\mathsf{V},\mathsf{E})$ where $\mathsf{V}$
is a set of _vertices_ and $\mathsf{E}$ is a set of _edges_ between vertices.
Unless otherwise specified, graphs are directed, unweighted, strongly
connected, do not have self-loops, and do not have multiple edges between
vertices. Given a graph, its population size is $N:=|\mathsf{V}|$. To model
the evolutionary dynamics we consider the Moran Birth-death processes on
graphs. In this process, each vertex has an associated _type_ at every time
step: it is either a _resident_ or a _mutant_. Each type has an associated
reproductive fitness: residents have fitness 1, mutants have fitness
$r\geqslant 1$.

The _Moran Birth-death process_ is defined as follows: At each time step we

  1. 1.

Pick a random vertex $u\in\mathsf{V}$ proportional to its type’s reproductive
fitness.

  2. 2.

Pick an outgoing edge of $u$ uniformly at random; denote its endpoint
$v\in\mathsf{V}$.

  3. 3.

Update the type of $v$ to be the type of $u$.

Formally, the process is represented as a sequence
$X_{0},X_{1},X_{2},\dots\subseteq V$, where $X_{0}$ is the set of vertices
that are initially occupied by mutants, and $X_{t}$ is the set of vertices
occupied by mutants after $t$ steps.

We define some relevant quantities when studying evolutionary dynamics in a
structured population. Each quantity depends on the mutant fitness advantage
$r\geqslant 1$; on the underlying population structure, represented by a graph
$G_{N}$; and on the set $X_{0}$ of vertices that are occupied by mutants.

The _fixation probability_ , denoted $\rho:=\rho^{r}(G_{N},X_{0})$, is the
probability that the mutants eventually take over the population forever. In
contrast, the _extinction probability_ is the probability that the mutants
eventually die out forever. If the graph is connected, fixation or extinction
will happen with probability 1 after finitely many steps. When the processes
reaches fixation or extinction, we say that the process has _absorbed_. We can
also study the time it takes for each of these events to happen: the _expected
absorption time_ $\operatorname{AT}^{r}(G,X_{0})$ is the expected amount of
time steps until the process absorbs. The _expected fixation time_
$\operatorname{T}^{r}(G,X_{0})$ is the expected amount of time steps
conditional on fixation occurring. We also define
$\operatorname{T}^{r}(G)=\max_{X_{0}\neq\emptyset}\\{\operatorname{T}^{r}(G,X_{0})\\}$
as the slowest possible fixation time, across all possible initial conditions.
That is, we average over only those evolutionary trajectories that terminate
with the mutant fixating (going extinct). When the mutant fitness advantage
$r\geqslant 1$, the underlying graph $G$, or the initial condition $X$ are
clear from the context we omit it. Finally, we say that if the expected
absorption or fixation time is bounded from above by some polynomial in terms
of the population size $N$ then the time is _fast_ ; otherwise the time is
_slow_.

##  Appendix B Drift Theory

What follows is an adaptation of Theorem 6 of [22] and Theorem 1 of [51] to be
applied to the case of advantageous mutants in the Moran birth-death process.

######  Lemma 1 (Fixation time for positive drift).

Let $\mathscr{X}\equiv(X_{t})_{t\geqslant 0}$ be a Markov chain from the state
space $\Omega$ with $X_{0}\neq\emptyset$. Suppose $\mu$ is probability measure
on $\Omega$ such that there is some $\varepsilon>0$ with
$\mathbb{E}\left[\mu(X_{t+1})-\mu(X_{t})\mid X_{t}\right]\geqslant\varepsilon$
for each $t\geqslant 0$ with $X_{t}\not\in\\{\emptyset,\Omega\\}$. Let
$\tau:=\inf\\{t\geqslant 0\mid\mu(X_{t})\in\\{0,1\\}\\}$ with
$p:=\Pr[X_{\tau}=1]$. Then

$\mathbb{E}\left[\tau\mid
X_{0}\right]\leqslant\frac{p-\mu(X_{0})}{\varepsilon}.$ (1)

###### Proof.

For any time $t\geqslant 1$ by the total law of expectation

$\mathbb{E}\left[\mu(X_{t})\mid
X_{0}\right]=\mathbb{E}\left[\mathbb{E}\left[\mu(X_{t-1})+(\mu(X_{t})-\mu(X_{t-1}))\mid
X_{t-1}\right]\mid X_{0}\right]$ (2)

and by linearity of expectation

$\mathbb{E}\left[\mu(X_{t-1})+(\mu(X_{t})-\mu(X_{t-1}))\mid
X_{t-1}\right]\geqslant\mathbb{E}\left[\mu(X_{t-1})\mid
X_{t-1}\right]+\varepsilon=\mu(X_{t-1})+\varepsilon.$ (3)

By induction on $t$

$\mathbb{E}\left[\mu(X_{t})\mid
X_{0}\right]\geqslant\mathbb{E}\left[\mu(X_{t-1})+\varepsilon\mid
X_{0}\right]\geqslant\mathbb{E}\left[\mu(X_{0})+t\varepsilon\mid
X_{0}\right]=\mu(X_{0})+\mathbb{E}\left[t\varepsilon\mid X_{0}\right].$ (4)

We know that $\mu(\mathscr{X})$ is a sub-martingale since by linearity of
expectation,

$\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]\geqslant\mathbb{E}\left[\mu(X_{t})\mid
X_{t}\right]+\varepsilon\geqslant\mu(X_{t})$ (5)

for each $t\geqslant 0$. Since $\tau$ is finite, we get

$\lim_{t\to\infty}\mathbb{E}\left[\mu(X_{t})\mid X_{0}\right]=p.$ (6)

Then since $\mathscr{X}$ is a discrete-time sub-martingale, there must exists
some time $t^{*}$ such that $\mathbb{E}\left[\mu(X_{t^{*}})\mid
X_{0}\right]=1$ and $\mathbb{E}\left[\mu(X_{t})\mid X_{0}\right]<1$ for all
$t<t^{*}$. Notice that $\tau=t^{*}$ by definition. Finally we have

$p=\mathbb{E}\left[\mu(X_{\tau})\mid
X_{0}\right]\geqslant\mu(X_{0})+\mathbb{E}\left[\tau\varepsilon\mid
X_{0}\right]=\mu(X_{0})+\varepsilon\cdot\mathbb{E}\left[\tau\mid
X_{0}\right].$ (7)

Rearranging the terms gives the claim. ∎

######  Lemma 2.

Let $\mathscr{X}\equiv(X_{t})_{t\geqslant 0}$ be a Markov chain from the state
space $\Omega$. Suppose $\mu$ is probability measure on $\Omega$ such that
$\mathbb{E}\left[\mu(X_{t+1})\mid X_{t}\right]\geqslant\mu(X_{t})$ for each
$t\geqslant 0$. Let $Y_{t}:=\frac{1}{2}\cdot\mu(X_{t})(1+\mu(X_{t}))$ for each
$t\geqslant 0$. Then

$\mathbb{E}\left[Y_{t+1}-Y_{t}\mid
X_{t}\right]\geqslant\frac{1}{2}\cdot\mathrm{Var}\left[\mu(X_{t+1})\mid
X_{t}\right]$ (8)

for all $t\geqslant 0$.

###### Proof.

See Corollary 26 of [52] for the inspiration. We have

$\displaystyle 2\cdot\mathbb{E}\left[Y_{t+1}-Y_{t}\mid X_{t}\right]$
$\displaystyle=\left(\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]+\mathbb{E}\left[\mu(X_{t+1})^{2}\mid
X_{t}\right]\right)-\left(\mu(X_{t})+\mu(X_{t})^{2}\right)$ (9)
$\displaystyle=\left(\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]-\mu(X_{t})\right)+\left(\mathbb{E}\left[\mu(X_{t+1})^{2}\mid
X_{t}\right]-\mu(X_{t})^{2}\right)$ (10)
$\displaystyle\geqslant\mathbb{E}\left[\mu(X_{t+1})^{2}\mid
X_{t}\right]-\mu(X_{t})^{2}$ (11)
$\displaystyle\geqslant\mathbb{E}\left[\mu(X_{t+1})^{2}\mid
X_{t}\right]-\left(\mathbb{E}\left[\mu(X_{t+1})\mid X_{t}\right]\right)^{2}$
(12) $\displaystyle=\mathrm{Var}\left[\mu(X_{t+1})\mid X_{t}\right].$ (13)

∎

######  Lemma 3 (Fixation time for non-negative drift).

Let $\mathscr{X}\equiv(X_{t})_{t\geqslant 0}$ be a Markov chain from the state
space $\Omega$ with $X_{0}\neq\emptyset$. Suppose $\mu$ is probability measure
on $\Omega$ such that there is some $\eta>0$ with
$\mathbb{E}\left[\mu(X_{t+1})\mid X_{t}\right]\geqslant\mu(X_{t})$ and
$\mathrm{Var}\left[\mu(X_{t+1})\mid X_{t}\right]\geqslant\eta$ for each
$t\geqslant 0$ with $X_{t}\not\in\\{\emptyset,\Omega\\}$. Let
$\tau=\inf\\{t\geqslant 0\mid\mu(X_{t})=1\\}$ with $p:=\Pr[X_{\tau}=1]$. Then

$\mathbb{E}\left[\tau\mid
X_{0}\right]\leqslant\frac{p-\mu(X_{0})(1+\mu(X_{0}))}{\eta/2}.$ (14)

###### Proof.

This follows from Lemmas 1 and 2. ∎

######  Lemma 4.

Let $\mathscr{X}\equiv(X_{t})_{t\geqslant 0}$ be a Markov chain from the state
space $\Omega$. Suppose $\mu$ is probability measure on $\Omega$ such that
$\mathbb{E}\left[\mu(X_{t+1})\mid X_{t}\right]=\mu(X_{t})$ for each
$t\geqslant 0$. Let $Y_{t}:=1-\mu(X_{t})(1-\mu(X_{t}))$ for each $t\geqslant
0$. Then

$\mathbb{E}\left[Y_{t+1}-Y_{t}\mid
X_{t}\right]=\mathrm{Var}\left[\mu(X_{t+1})\mid X_{t}\right]$ (15)

for all $t\geqslant 0$.

###### Proof.

This is similar to the proof of Lemma 2. We have

$\displaystyle\cdot\mathbb{E}\left[Y_{t+1}-Y_{t}\mid X_{t}\right]$
$\displaystyle=\left(\mu(X_{t})-\mu(X_{t})^{2}\right)-\left(\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]-\mathbb{E}\left[\mu(X_{t+1})^{2}\mid X_{t}\right]\right)$ (16)
$\displaystyle=\left(\mathbb{E}\left[\mu(X_{t+1})^{2}\mid
X_{t}\right]-\mu(X_{t})^{2}\right)-\left(\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]-\mu(X_{t})\right)$ (17)
$\displaystyle=\mathbb{E}\left[\mu(X_{t+1})^{2}\mid
X_{t}\right]-\mu(X_{t})^{2}$ (18)
$\displaystyle=\mathbb{E}\left[\mu(X_{t+1})^{2}\mid
X_{t}\right]-\left(\mathbb{E}\left[\mu(X_{t+1})\mid X_{t}\right]\right)^{2}$
(19) $\displaystyle=\mathrm{Var}\left[\mu(X_{t+1})\mid X_{t}\right].$ (20)

∎

######  Lemma 5 (Absorption time for zero drift).

Let $\mathscr{X}\equiv(X_{t})_{t\geqslant 0}$ be a Markov chain from the state
space $\Omega$. Suppose $\mu$ is probability measure on $\Omega$ such that
there is some $\eta>0$ with $\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]=\mu(X_{t})$ and $\mathrm{Var}\left[\mu(X_{t+1})\mid
X_{t}\right]\geqslant\eta$ for each $t\geqslant 0$. Let
$\tau=\inf\\{t\geqslant 0\mid\mu(X_{t})\in\\{0,1\\}\\}$. Then

$\mathbb{E}\left[\tau\mid
X_{0}\right]\leqslant\frac{\mu(X_{0})(1-\mu(X_{0}))}{\eta}.$ (21)

###### Proof.

This follows from Lemmas 1 and 4. ∎

######  Lemma 6 (Naive variance lower bound).

Let $\mathscr{X}\equiv(X_{t})_{t\geqslant 0}$ be a Markov chain from the state
space $\Omega$. For each $t\geqslant 0$, let $\mathcal{E}_{t}$ be the event
$\mu(X_{t+1})<\mu(X_{t})$. Suppose $\mu$ is probability measure on $\Omega$
such that $\mathbb{E}\left[\mu(X_{t+1})\mid X_{t}\right]\geqslant\mu(X_{t})$
with $\Pr[\mathcal{E}_{t}|X_{t}]\geqslant\nu_{t}$ and, given
$\mathcal{E}_{t}$, $|\mu(X_{t+1})-\mu(X_{t})|\geqslant\ell_{t}$ for each
$t\geqslant 0$. Then

$\mathrm{Var}\left[\mu(X_{t+1})\mid
X_{t}\right]\geqslant\left(\nu_{t}\ell_{t}\right)^{2}$ (22)

for all $t\geqslant 0$ with $X_{t}\not\in\\{\emptyset,\Omega\\}$.

###### Proof.

We have

$\displaystyle\mathrm{Var}\left[\mu(X_{t+1})\mid X_{t}\right]$
$\displaystyle=\mathbb{E}\left[\left(\mu(X_{t+1})-\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]\right)^{2}\mid X_{t}\right]$ (23)
$\displaystyle\geqslant\left(\mathbb{E}\left[\big{|}\mu(X_{t+1})-\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]\big{|}\mid X_{t}\right]\right)^{2}$ (24)

by Jensen’s inequality. Then

$\displaystyle\mathbb{E}\left[\big{|}\mu(X_{t+1})-\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]\big{|}\mid X_{t}\right]$
$\displaystyle\geqslant\nu_{t}\cdot\ell_{t}$ (25)

since the expectation is non-negative and $\mu(\mathscr{X})$ is a
submartingale. ∎

######  Lemma 7 (Naive variance lower bound, zero drift).

Let $\mathscr{X}\equiv(X_{t})_{t\geqslant 0}$ be a Markov chain from the state
space $\Omega$. For each $t\geqslant 0$, let $\mathcal{E}_{t}$ be the event
$\mu(X_{t+1})\neq\mu(X_{t})$. Suppose $\mu$ is probability measure on $\Omega$
such that $\mathbb{E}\left[\mu(X_{t+1})\mid X_{t}\right]=\mu(X_{t})$ with
$\Pr[\mathcal{E}_{t}|X_{t}]\geqslant\nu_{t}$ and, given $\mathcal{E}_{t}$,
$|\mu(X_{t+1})-\mu(X_{t})|\geqslant\ell_{t}$ for each $t\geqslant 0$. Then

$\mathrm{Var}\left[\mu(X_{t+1})\mid
X_{t}\right]\geqslant\left(\nu_{t}\ell_{t}\right)^{2}$ (26)

for all $t\geqslant 0$ with $X_{t}\not\in\\{\emptyset,\Omega\\}$.

###### Proof.

We have

$\displaystyle\mathrm{Var}\left[\mu(X_{t+1})\mid X_{t}\right]$
$\displaystyle=\mathbb{E}\left[\left(\mu(X_{t+1})-\mathbb{E}\left[\mu(X_{t+1})\mid
X_{t}\right]\right)^{2}\mid X_{t}\right]$ (27)
$\displaystyle=\mathbb{E}\left[\left(\mu(X_{t+1})-\mu(X_{t})\right)^{2}\mid
X_{t}\right]$ (28)
$\displaystyle\geqslant\left(\mathbb{E}\left[\big{|}\mu(X_{t+1})-\mu(X_{t})\big{|}\mid
X_{t}\right]\right)^{2}$ (29)

by Jensen’s inequality. Then

$\displaystyle\mathbb{E}\left[\big{|}\mu(X_{t+1})-\mu(X_{t})\big{|}\mid
X_{t}\right]$ $\displaystyle\geqslant\nu_{t}\ell_{t}$ (30)

since the expectation is non-negative and $\mu(\mathscr{X})$ is a martingale.
∎

##  Appendix C Fixation always occurs quickly when selection advantage is
strong enough

In this section we prove Theorem 1 from the main text. That is, we show that
if the mutant fitness advantage is large enough then the process terminates
fast, regardless of the underlying spatial structure.

To that end, we first prove the following key lemma.

######  Lemma 8.

Let $\mathsf{G}=(\mathsf{V},\mathsf{E})$ be a graph and $r\geqslant N^{2}$.
Let $\phi(S)=|S|/N$. Then for each $\emptyset\subsetneq S\subsetneq\mathsf{V}$
and for any $t\geqslant 0$ we have

$\mathbb{E}\left[\phi(X_{t+1})-\phi(X_{t})\mid X_{t}=S\right]\geqslant
N^{-4}.$ (31)

###### Proof.

For $k=1,\dots,N-1$ let $W_{k}=N+(r-1)k$ be the total fitness of the
population. Note that $N<W_{k}<rN$. Next, for $k=1,\dots,N-1$ let
$p^{\uparrow}_{k}$ be the minimum probability that the number of mutants
increases in the next step given that there are currently $k$ mutants. Since
$G$ is strongly connected, there is at least one edge pointing from a mutant
vertex to a resident vertex, and the mutant vertex has degree at most $N-1$.
Therefore

$p^{\uparrow}_{k}\geqslant\frac{r}{W_{k}}\cdot\frac{1}{N-1}.$ (32)

Similarly, let $p^{\downarrow}_{k}$ be the maximum probability that the number
of mutants decreases in the next step given that there are currently $k$
mutants. Then

$p^{\downarrow}_{k}\leqslant\frac{N-k}{W_{k}}$ (33)

Combining the two bounds we get

$\mathbb{E}\left[\phi(X_{t+1})-\phi(X_{t})\mid
X_{t}=S,|S|=k\right]\geqslant\frac{p^{\uparrow}_{k}-p^{\downarrow}_{k}}{N}=\frac{r}{N\cdot
W_{k}}\cdot\left(\frac{1}{N-1}-\frac{N-k}{r}\right).$ (34)

Now since $W_{k}\leqslant rN$ we have $r/(NW_{k})\geqslant 1/N^{2}$. Moreover,
we have $(N-k)/r\leqslant(N-1)/(N^{2}-1)=1/(N+1)$, hence we get the desired

$\mathbb{E}\left[\phi(X_{t+1})-\phi(X_{t})\mid
X_{t}=S,|S|=k\right]\geqslant\frac{1}{N^{2}}\cdot\frac{2}{N^{2}-1}\geqslant\frac{1}{N^{4}}.$
(35)

∎

As an immediate consequence we obtain Theorem 1 from the main text.

######  Theorem 6.

Let $G_{N}$ be an arbitrary graph on $N$ nodes. Suppose that $r\geqslant
N^{2}$. Then $\operatorname{T}^{r}(G_{N})\leqslant N^{4}$.

###### Proof.

We apply Lemma 1 with $\mu(X_{t})=\phi(X_{t})$. By Lemma 8 we can set
$\varepsilon=N^{-4}$ and we obtain

$\operatorname{T}^{r}(G_{N})\leqslant 1/N^{-4}=N^{4}.\qed$

##  Appendix D Fixation occurs quickly on Eulerian graphs

In this section we prove Theorem 2 from the main text. That is, we show that
if a graph is Eulerian with degrees sandwiched between $\delta$ and $\Delta$
then the time is fast, provided that the mutant fitness advantage satisfies
$r\geqslant\Delta/\delta$. Recall that a graph is _Eulerian_ if
$\mathrm{deg}^{-}(v)=\mathrm{deg}^{+}(v)$ holds for each $v\in\mathsf{V}$.

First, We point out one useful property of such graphs. Let
$S\subseteq\mathsf{V}$. Let $E^{+}(S)$ be the set of the edges whose starting
vertex is in $S$. Let $E^{-}(S)$ be the set of the edges whose ending vertex
is in $S$. Let $m^{+}_{S}$ be the number edges outgoing from $S$ and incoming
to $\mathsf{V}\setminus S$. Similarly, let $m^{-}_{S}$ be the number edges
outgoing from $\mathsf{V}\setminus S$ and incoming to $S$.

######  Lemma 9.

A graph $\mathsf{G}=(\mathsf{V},\mathsf{E})$ is Eulerian if and only if
$m^{+}_{S}=m^{-}_{S}$ for every $S\subseteq\mathsf{V}$.

###### Proof.

Suppose $\mathsf{G}$ is Eulerian and let $S\subseteq\mathsf{V}$. We have that

$\displaystyle m^{+}_{S}$ $\displaystyle=|\mathsf{E}^{+}(S)|-\\#\\{u\to
v\in\mathsf{E}\mid u\in S,v\in S\\}\text{ \quad and}$ $\displaystyle
m^{-}_{S}$ $\displaystyle=|\mathsf{E}^{-}(S)|-\\#\\{u\to v\in\mathsf{E}\mid
u\in S,v\in S\\}.$

Noticing that

$|\mathsf{E}^{+}(S)|=\sum_{u\in S}\mathrm{deg}^{+}(u)=\sum_{u\in
S}\mathrm{deg}^{-}(u)=|\mathsf{E}^{-}(S)|$

since $\mathsf{G}$ is Eulerian completes one direction of the proof.

For the other direction, suppose we know that $m^{+}(S)=m^{-}(S)$ for each
$S\subseteq\mathsf{V}$. Then for every $u\in\mathsf{V}$ we know
$\mathrm{deg}^{-}(u)=m^{-}_{\\{u\\}}=m^{+}_{\\{u\\}}=\mathrm{deg}^{+}(u)$, so
$\mathsf{G}$ is Eulerian. ∎

######  Theorem 7.

Let $G_{N}$ be an Eulerian graph on $N$ nodes with smallest degree $\delta$
and largest degree $\Delta$. Suppose $r\geqslant\Delta/\delta$. Then
$\operatorname{T}^{r}(G_{N})\leqslant 4\Delta^{2}N^{8}$.

###### Proof.

Let $\gamma=\gamma(\mathsf{G}):=\Delta/\delta$. For $S\subseteq\mathsf{V}$,
let $\phi(S):=|S|/|\mathsf{V}|$. Let $W(S)$ be the total fitness of the
population. Let $X_{t+1}$ be the next set of mutants in the process given time
$t$ has mutants $X_{t}=S$. We have

$\displaystyle\mathbb{E}\left[\phi(X_{t+1})-\phi(X_{t})|X_{t}=S\right]$
$\displaystyle=\frac{1}{W(S)|\mathsf{V}|}\left[r\sum_{v\to
w\in\mathsf{E}(S,\mathsf{V}\setminus S)}\frac{1}{\mathrm{deg}(v)}-\sum_{u\to
v\in\mathsf{E}(\mathsf{V}\setminus S,S)}\frac{1}{\mathrm{deg}(u)}\right]$ (36)
$\displaystyle\geqslant\frac{m^{+}_{S}}{W(S)|\mathsf{V}|}\left(r/\Delta-1/\delta\right)$
(37)

where we used the fact that any cut in an Eulerian graph has the same number
of cross edges in either direction (Lemma 9). We examine two cases for $r$.
First suppose $r\geqslant N^{2}$. Then by Theorem 6

$T\leqslant N^{4}.$ (38)

Next, suppose $\gamma\leqslant r<N^{2}$. This means that

$\mathbb{E}\left[\phi(X_{t+1})-\phi(X_{t})|X_{t}=S\right]\geqslant 0$ (39)

since $r\geqslant\gamma$. Then

$\displaystyle\Pr[\phi(X_{t+1})<\phi(X_{t})|X_{t}=S]$
$\displaystyle\geqslant\frac{1}{W(S)}\cdot\frac{1}{\Delta}\geqslant\frac{1}{r\Delta
N}\geqslant\frac{1}{\Delta N^{3}}$ (40)

since $r<N^{2}$, and

$\displaystyle|\phi(X_{t+1})-\phi(S)|$
$\displaystyle\geqslant\frac{1}{|\mathsf{V}|}=\frac{1}{N}$ (41)

when $\phi(X_{t+1})<\phi(S)$. Thus by Lemma 6,

$\mathrm{Var}\left[\phi(X_{t+1})\mid\phi(X_{t})\right]\geqslant\left(\frac{1}{\Delta
N^{4}}\right)^{2}$ (42)

Given that we are interested in the conditional fixation time, the process
always fixates. By Lemma 3 and (42),

$T\leqslant 4\cdot(1-\phi(X_{0})(1+\phi(X_{0})))\Delta^{2}N^{8}$ (43)

Thus

$T\leqslant 4\Delta^{2}N^{8}$ (44)

for such $r$. In either case the latter bound holds.

∎

##  Appendix E Fixation can occur slightly faster for small selective
advantages

######  Lemma 10.

Let $\mathsf{G}=(\mathsf{V},\mathsf{E})$ and let $\rho_{\rm
min}:=\min_{S\subseteq\mathsf{V}}\mathrm{fp}(\mathsf{G},S,r=1)$. Then
$\operatorname{T}^{r}(G)\leqslant 4\operatorname{T}^{r=1}(G)/\rho_{\rm min}$.

###### Proof.

Consider the process $M_{1}$ with $r=1$ and the process $M_{r}$ with
$r\geqslant 1$. In $M_{1}$, there exist fixating trajectories with total
weight $\rho_{\rm min}$ that fixate on average in at most $T_{1}$ steps. By
Markov inequality, in $M_{1}$ there exist fixating trajectories with total
weight $\rho_{\rm min}/2$ that fixate in at most $2T_{1}$ steps each.

Let $\tilde{M}_{1}$ and $\tilde{M}_{r}$ denote the continuous-time versions of
the processes as described in [32]. Then by Lemma 5 of [32], there is a
coupling between the continuous-time versions of the two processes such that
if the processes start with the same set of mutants (i.e.
$\tilde{M}_{1}[0]=\tilde{M}_{r}[0]$), then
$\tilde{M}_{1}[t]\subseteq\tilde{M}_{r}[t]$ for all $t\geqslant 0$. Let
$\tilde{\tau}_{1}$ be one possible mutant set trajectory that fixates for
$\tilde{M}_{1}$. Then the coupling implies that the corresponding trajectory
$\tilde{\tau}_{r}$ for $\tilde{M}_{r}$ fixates at an even earlier time. The
same holds between the fixating trajectories $\tau_{1}$ and $\tau_{r}$ in the
discrete-time processes.

Thus, in $M_{r}$ there exist fixating trajectories with total weight
$\rho_{\rm min}/2$ that fixate in at most $2T_{1}$ steps each. Now imagine we
run $M_{r}$ for stages of $2T_{1}$ steps each. Within each stage, the process
fixates with probability at least $\rho_{\rm min}/2$ so in expectation we
observe fixation after at most $2/\rho_{\rm min}$ stages. In total, this gives
the desired

$T_{r}\leqslant\frac{2}{\rho_{\rm min}}\cdot 2T_{1}=4T_{1}/\rho_{\rm min}.$
(45)

∎

######  Lemma 11 (Bounding absorption time and fixation time when $r=1$).

Let $\mathsf{G}=(\mathsf{V},\mathsf{E})$. Then

$\mathrm{AT}^{r=1}(\mathsf{G})\leqslant\frac{N^{4}}{4\rho_{\rm
min}^{2}}\quad\text{and}\quad\operatorname{T}^{r=1}(\mathsf{G})\leqslant\frac{N^{4}}{4\rho_{\rm
min}^{3}}.$

###### Proof.

Note that the probability that the mutant set $S\subseteq\mathsf{V}$ changes
in one step is at least

$\frac{1}{W(S)}\frac{1}{N-1}=\frac{1}{N(N-1)}\geqslant\frac{1}{N^{2}}.$ (46)

Then by Lemmas 5 and 7, where we use the fixation probability $\mathrm{fp}(X)$
as the potential function $\mu(X)$, we get

$\mathrm{AT}^{r=1}(\mathsf{G},X)\leqslant\left(\frac{N^{2}}{\rho_{\rm
min}}\right)^{2}\cdot\mathrm{fp}(X)(1-\mathrm{fp}(X))\leqslant\frac{N^{4}}{4\rho_{\rm
min}^{2}}.$ (47)

Now we turn the bound on absorption time into a bound on fixation time. Let
$X$ be any configuration and denote by $\operatorname{ET}^{r=1}(G,X)$ the
extinction time starting from $X$. Then

$\operatorname{AT}^{r=1}(\mathsf{G},X)=\mathrm{fp}^{r=1}(\mathsf{G},X)\cdot\operatorname{T}^{r=1}(\mathsf{G},X)+\left(1-\mathrm{fp}^{r=1}(\mathsf{G},X)\right)\cdot\operatorname{ET}^{r=1}(\mathsf{G},X)\geqslant\rho_{\rm
min}\cdot\operatorname{T}^{r=1}(\mathsf{G},X),$

thus taking the maximum over $X$ we obtain
$\operatorname{T}^{r=1}(\mathsf{G})\leqslant\operatorname{AT}^{r=1}(\mathsf{G})/\rho_{\rm
min}$. ∎

######  Theorem 8.

Fix a graph $G_{N}$ and $r\geqslant 1$. Then
$\operatorname{T}^{r}(G_{N})\leqslant\left(\frac{N}{\rho_{\rm
min}(G_{N})}\right)^{4}.$

###### Proof.

This follows from Lemma 10 and Lemma 11. ∎

##  Appendix F Balanced graphs (and others) fixate quickly

######  Lemma 12.

Let $\mathsf{G}=(\mathsf{V},\mathsf{E})$. Suppose there exist $|\mathsf{V}|$
numbers $\\{x_{v}\mid v\in\mathsf{V}\\}$ that satisfy

$x_{v}\cdot\sum_{u:u\to v\in
E}\frac{1}{\mathrm{deg}^{+}(u)}=\frac{1}{\mathrm{deg}^{+}(v)}\cdot\sum_{w:v\to
w\in E}x_{w}$ (48)

for each $v\in\mathsf{V}$. In addition, suppose
$\sum_{v\in\mathsf{V}}x_{v}=1$. Then $x_{v}=\mathrm{fp}(\\{v\\})$.

###### Proof.

Suppose $r=1$ and denote $N=|\mathsf{V}|$. Then the fixation probability is
additive, that is, $\rho(S)=\sum_{v\in S}\rho(\\{v\\})$ for every
$S\subseteq\mathsf{V}$ [12]. Thus, the list of $2^{N}$ fixation probabilities
$\mathrm{fp}(S)$ for $S\subseteq V$ is determined by the list of $N$ fixation
probabilities $\rho(\\{v\\})$ for $v\in\mathsf{V}$. The fixation probabilities
$\rho(\\{v\\})$ are the unique solutions to the linear system

$\mathrm{fp}(\\{v\\})=\frac{1}{N}\sum_{v\to
w\in\mathsf{E}}\frac{1}{\mathrm{deg}^{+}(v)}\cdot{\mathrm{fp}(\\{v,w\\})}+\frac{1}{N}\sum_{u\to
v\in\mathsf{E}}\frac{1}{\mathrm{deg}^{+}(u)}\cdot\mathrm{fp}(\emptyset)+\left(1-\frac{1}{N}-\frac{1}{N}\sum_{u\to
v\in\mathsf{E}}\frac{1}{\mathrm{deg}^{+}(u)}\right)\cdot\mathrm{fp}(\\{v\\}),$
(49)

where the first term on the right-hand side corresponds to the mutant
reproducing, the second term corresponds to the mutant being replaced, and the
third term corresponds to a resident replacing a resident. Using
$\rho(\emptyset)=0$ and $\rho(\\{v,w\\})=\rho(\\{v\\})+\rho(\\{w\\})$ we
obtain

$\mathrm{fp}(\\{v\\})\cdot\sum_{u:u\to v\in
E}\frac{1}{\mathrm{deg}^{+}(u)}=\frac{1}{\mathrm{deg}^{+}(v)}\cdot\sum_{w:v\to
w\in E}\mathrm{fp}(\\{w\\})$ (50)

which is precisely the system satisfied by $\\{x_{v}\mid v\in\mathsf{V}\\}$.

∎

######  Definition 1.

A graph $\mathsf{G}=(\mathsf{V},\mathsf{E})$ is _balanced_ if and only if

$\frac{1}{\mathrm{deg}^{-}(v)}\cdot\sum_{u:u\to v\in
E}\frac{1}{\mathrm{deg}^{+}(u)}=\frac{1}{\mathrm{deg}^{+}(v)}\cdot\sum_{w:v\to
w\in E}\frac{1}{\mathrm{deg}^{-}(w)}.$ (51)

######  Theorem 9.

Let $G_{N}$ be a balanced graph. Then:

  1. 1.

$\rho^{r=1}(G_{N},u)=\frac{1/\operatorname{deg}^{-}(u)}{\sum_{v\in
V}1/\operatorname{deg}^{-}(v)}\geqslant 1/N^{2}$ for any node $u$.

  2. 2.

$\operatorname{T}^{r}(G_{N})\leqslant N^{12}$ for any $r\geqslant 1$.

###### Proof.

The equality in Item 1 follows from Lemma 12 and the bound follows from the
fact that the numerator is at least $1/N$ and the denominator is at most $N$.
Item 2 follows immediately from Item 1 and Theorem 8. ∎

In the rest of this section we verify that the undirected graphs, carousels,
books, metafunnels, and superstars are all balanced. Thus, the fixation
probability under neutral drift ($r=1$) starting from node $v$ is inversely
proportional to $\operatorname{deg}^{-}(v)$. Moreover, we provide an explicit
formula for fixation probability on Megastars under neutral drift. This gives
an upper bound on the fixation time for any $r\geqslant 1$ by Theorem 8. We
use the notation $\mathrm{fp}(\\{v\\})\propto p_{v}$ to mean that
$\mathrm{fp}(\\{v\\})=p_{v}/\sum_{w\in\mathsf{V}}p_{w}$.;

Recall that a graph is undirected if all edges are two-way, that is, if $u\to
v\in\mathsf{E}$ then $v\to u\in\mathsf{E}$ as well.

######  Claim 1.

Suppose $\mathsf{G}=(\mathsf{V},\mathsf{E})$ is undirected. Then
$\mathrm{fp}(\\{v\\})\propto 1/\mathrm{deg}(v)$.

###### Proof.

Checking by substituting,

$\displaystyle\frac{1}{\mathrm{deg}(v)}\sum_{v\to
w\in\mathsf{E}}\frac{1}{\mathrm{deg}(w)}=\frac{1}{\mathrm{deg}(v)}\sum_{u\to
v\in\mathsf{E}}\frac{1}{\mathrm{deg}(u)}$ (52) $\displaystyle\iff$
$\displaystyle\frac{1}{\mathrm{deg}(v)}\sum_{\begin{subarray}{c}v\to
w\in\mathsf{E}\\\ w\to
v\in\mathsf{E}\end{subarray}}\frac{1}{\mathrm{deg}(w)}=\frac{1}{\mathrm{deg}(v)}\sum_{\begin{subarray}{c}u\to
v\in\mathsf{E}\\\ v\to u\in\mathsf{E}\end{subarray}}\frac{1}{\mathrm{deg}(u)}$
(53) $\displaystyle\iff$
$\displaystyle\frac{1}{\mathrm{deg}(v)}=\frac{1}{\mathrm{deg}(v)}$ (54)

which is always true. ∎

For the following theorems, we omit the proofs since the technique is similar
of that of the proof of claim 1.

######  Definition 2.

A _carousel_ is multipartite graph consisting of a partition of $\mathsf{V}$
into sets $S_{1},\ldots,S_{\ell}$ such that $u\to v\in\mathsf{E}$ if and only
if there exists an $i$ such that $u\in S_{i}$ and $v\in S_{i+1}$. We say that
$S_{\ell+1}:=S_{1}$, $S_{0}:=S_{\ell}$, $S_{-1}:=S_{\ell-1}$, etc.

######  Claim 2.

Suppose $\mathsf{G}=(\mathsf{V},\mathsf{E})$ is a carousel with sets
$S_{1},\ldots,S_{\ell}$. Then for $v\in S_{i}$ we have that
$\mathrm{fp}(\\{v\\})\propto|S_{i-1}|^{-1}$.

###### Proof.

We have

$\displaystyle|S_{i-1}|^{-1}\cdot\sum_{u\to
v\in\mathsf{E}}\frac{1}{\mathrm{deg}^{+}(u)}=|S_{i-1}|\cdot{|S_{i}|}^{-1}|S_{i-1}|^{-1}={|S_{i}|}^{-1}$
(55)

and

$\displaystyle\frac{1}{\mathrm{deg}^{+}(v)}\sum_{v\to
w\in\mathsf{E}}|S_{i}|^{-1}=|S_{i}|^{-1}.$ (56)

∎

######  Definition 3.

An _$(s_{1},\ldots,s_{\ell})$ -book_ is a graph with vertices $b$ (beginning),
$e$ (end), and $p^{i}_{j_{i}}$ for $i=1,\ldots,\ell$ and
$j_{i}=2,\ldots,s_{i-1}$. We say that $p^{i}_{1}=p^{i}_{s_{i}+1}=b$ and
$p^{i}_{s_{i}}=e$ for each $i$. We have $p^{i}_{j_{i}}\to
p^{i}_{j_{i}+1}\in\mathsf{E}$ for all $j_{i}=1,\ldots,s_{i}$

######  Claim 3.

Suppose $\mathsf{G}=(\mathsf{V},\mathsf{E})$ is a
$(s_{1},\ldots,s_{\ell})$-book. Then

  1. 1.

$\mathrm{fp}(\\{b\\})\propto\ell$

  2. 2.

$\mathrm{fp}(\\{e\\})\propto 1$

  3. 3.

$\mathrm{fp}(\\{p^{i}_{2}\\})\propto\ell$ for each $i$

  4. 4.

$\mathrm{fp}(\\{p^{i}_{j}\\})\propto 1$ for each $i$ and each $j>1$.

###### Proof.

This can be easily checked by plugging into the equations of (50). ∎

######  Definition 4.

See §1.1.1 of [24] for the definition of a _$(k,\ell,m)$ -metafunnel_.

######  Claim 4.

Suppose $\mathsf{G}=(\mathsf{V},\mathsf{E})$ is a $(k,\ell,m)$-metafunnel.
Then

  1. 1.

$\mathrm{fp}(\\{v\\})\propto m^{1-i}$ for each $v\in V_{i}$ such that $i\neq
1$

  2. 2.

$\mathrm{fp}(\\{v\\})\propto\ell$ for each $v\in V_{1}$.

######  Definition 5.

See §1.1.2 of [24] for the definition of a _$(k,\ell,m)$ -superstar_.

######  Claim 5.

Suppose $\mathsf{G}=(\mathsf{V},\mathsf{E})$ is a $(k,\ell,m)$-superstar. Then

  1. 1.

$\mathrm{fp}(\\{v_{i,j}\\})\propto 1$ for each $i$ and each $j>1$

  2. 2.

$\mathrm{fp}(\\{v_{i,1}\\})\propto 1/m$ for each $i$

  3. 3.

$\mathrm{fp}(\\{v\\})\propto\ell$ for each $v\in R_{i}$ for each $i$

  4. 4.

$\mathrm{fp}(\\{v^{*}\\})\propto 1$.

######  Corollary 1.

Undirected graphs, carousels, books, metafunnels, and superstars are balanced.

###### Proof.

This follows from Theorem 9, and Claims 1 to 5. ∎

######  Definition 6.

See §1.1.3 of [24] for the definition of a _$(k,\ell,m)$ -megastar_.

######  Claim 6.

Suppose $\mathsf{G}=(\mathsf{V},\mathsf{E})$ is a $(k,\ell,m)$-megastar. Then

  1. 1.

$\mathrm{fp}(\\{v^{*}\\})\propto m$

  2. 2.

$\mathrm{fp}(\\{v\\})\propto\ell m$ for each $v\in R_{1}\cup\cdots\cup
R_{\ell}$

  3. 3.

$\mathrm{fp}(\\{v\\})\propto m$ for each $v\in K_{1}\cup\cdots\cup K_{\ell}$

  4. 4.

$\mathrm{fp}(\\{a_{i}\\})\propto 1$ for each $i\in[\ell]$.

######  Corollary 2.

A $(k,\ell,m)$-megastar has $\rho_{\text{min}}\geqslant 1/h(N)$ for some
polynomial $N$ so long as

$1\cdot\ell+m\cdot(k\ell)+(\ell m)\cdot(\ell m)+m\leqslant h(N).$ (57)

In particular, so long as $k$, $\ell$, and $m$ are each bounded above by some
polynomial in $N$ then $\rho_{\text{min}}$ is bounded below by the inverse of
a polynomial.

##  Appendix G Quickly estimating fixation probabilities with provable
confidence

######  Theorem 10.

There is a FPRAS for fixation probability for $r\geqslant 1$ if there is some
polynomial $h$ such that $\rho_{\rm min}\geqslant 1/h(N)$.

###### Proof.

What follows is a standard technique. We aim to approximate the fixation
probability within a multiplicative factor of $\varepsilon>0$ with probability
$1-\nu$. Let $\nu_{1},\nu_{2}\geqslant 0$ be constants and let
$\nu:=\nu_{1}+\nu_{2}$. We first compute $\rho_{\rm min}$ and then $T_{1}$ in
$\text{poly}(N)$ time by Lemma 12. We run $s=\lceil 2(\ln
2/\nu_{1})/(\varepsilon\rho_{\text{min}})^{2}\rceil$ independent simulations
of the birth-death process on $\mathsf{G}$ for at most $t=\lceil
T_{1}s/\nu_{2}\rceil$ steps. If any simulation does not reach absorption in
the allocated time, we return some arbitrary number as the fixation
probability. Otherwise, take $X_{1},\ldots,X_{s}$ to be random $0$-$1$
indicator variables such that $X_{i}=1$ if and only if the simulation reaches
fixation. We estimate $\hat{\rho}:=\frac{1}{s}\sum_{i=1}^{s}X_{i}$ as the
fixation probability. Then $\Pr[|\hat{\rho}-\rho|>\varepsilon\rho]\leqslant
2\exp(-\varepsilon^{2}\rho^{2}s/2)\leqslant\nu_{1}$ by a Chernoff bound. The
probability that a simulation does not reach absorption in the allocated
amount of time is at most $\nu_{2}/s$ by Markov’s inequality. By a union
bound, the probability that there is some simulation that does not reach
absorption in the allocated time is at most $\nu_{2}$. Thus the probability of
error in this approximation algorithm is at most $\nu_{1}+\nu_{2}=\nu$. Both
$s$ and $t$ are polynomial in $N$ and each step of the birth-death process can
be computed in a constant amount of time. ∎