Amplifiers of selection for the Moran process with both Birth-death and death-
Birth updating

Jakub Svoboda1, Soham Joshi1, Josef Tkadlec2,3, Krishnendu Chatterjee1

1 IST Austria, Klosterneuburg, Austria

2 Department of Mathematics, Harvard University, Cambridge, MA 02138, USA

3 Computer Science Institute, Charles University, Prague, Czech Republic

## Abstract

Populations evolve by accumulating advantageous mutations. Every population
has some spatial structure that can be modeled by an underlying network. The
network then influences the probability that new advantageous mutations
fixate. Amplifiers of selection are networks that increase the fixation
probability of advantageous mutants, as compared to the unstructured fully-
connected network. Whether or not a network is an amplifier depends on the
choice of the random process that governs the evolutionary dynamics. Two
popular choices are Moran process with Birth-death updating and Moran process
with death-Birth updating. Interestingly, while some networks are amplifiers
under Birth-death updating and other networks are amplifiers under death-Birth
updating, no network is known to function as an amplifier under both types of
updating simultaneously. In this work, we identify networks that act as
amplifiers of selection under both versions of the Moran process. The
amplifiers are robust, modular, and increase fixation probability for any
mutant fitness advantage in a range $r\in(1,1.2)$. To complement this positive
result, we also prove that for certain quantities closely related to fixation
probability, it is impossible to improve them simultaneously for both versions
of the Moran process. Together, our results highlight how the two versions of
the Moran process differ and what they have in common.

## Author summary

The long-term fate of an evolving population depends on its spatial structure.
Amplifiers of selection are spatial structures that enhance the probability
that a new advantageous mutation propagates through the whole population, as
opposed to going extinct. Many amplifiers of selection are known when the
population evolves according to the Moran Birth-death updating, and several
amplifiers are known for the Moran death-Birth updating. Interestingly, none
of the spatial structures that work for one updating seem to work for the
other one. Nevertheless, in this work we identify spatial structures that
function as amplifiers of selection for both types of updating. We also prove
two negative results that suggest that stumbling upon such spatial structures
by pure chance is unlikely.

## Introduction

Moran process is a classic stochastic process that models natural selection in
populations of asexually reproducing individuals, especially when new
mutations are rare [1, 2]. It is commonly used to understand the fate of a
single new mutant, as it attempts to invade a population of indistinguishable
residents. Eventually, the new mutation will either fixate on the whole
population, or it will go extinct. It is known that when the invading mutant
has relative fitness advantage $r>1$ as compared to the residents, this
fixation probability tends to a positive constant $1-1/r$ as the population
size $N$ grows large.

On spatially structured populations, fixation probability of an invading
mutant can both increase or decrease. In the framework of evolutionary graph
theory [3, 4], the spatial structure is represented by a graph (network) in
which nodes (vertices) correspond to individual sites, and edges (connections)
correspond to possible migration patterns. Each edge is assigned a weight that
represents the strength of the connection. Such network-based spatial
structures can represent island models, metapopulations, lattices, as well as
other arbitrarily complex structures [5, 6, 7, 8, 9]. Spatial structures that
increase the fixation probability of a randomly occurring advantageous mutant
beyond the constant $1-1/r$ are called amplifiers of selection [10]. The logic
behind the name is that living on such a structure effectively amplifies the
fitness advantage that the mutants has, as compared to living on the
unstructured (well-mixed) population. Identifying amplifiers is desirable,
since they could potentially serve as tools in accelerating the evolutionary
search, especially when new mutations are rare [11, 12].

When run on a spatial structure, Moran process can be implemented in two
distinct versions. They are called Moran Birth-death process and Moran death-
Birth process. In the Moran Birth-death process, first an individual is
selected for reproduction with probability proportional to its fitness, and
the offspring then replaces a random neighbor. In contrast, in the Moran
death-Birth process, first a random individual dies and then its neighbors
compete to fill up the vacant site (see Fig. 1). Both the Moran Bd-updating
[1, 3, 13] and the Moran dB-updating [14, 15, 16, 17] have been studied
extensively. While essentially identical on the unstructured population, the
two versions of the process yield different results when run on most spatial
structures [18, 19, 20].

Fig 1:  Moran Birth-death and death-Birth processes on a population structure.
a, Each node is occupied by a resident with fitness 1 (blue), or a mutant with
fitness $r\geq 1$ (red). Thicker edges denote higher edge weights (stronger
interactions). b, In Moran Birth-death process, a random individual
reproduces, and the produced offspring migrates along a random edge. c, In
Moran death-Birth process, a random individual dies, and the vacancy is filled
by a random neighbor. In both cases, edges with higher weight are selected
more often, and fitness plays a role in the Birth step but not in the death
step.

In the world of the Bd-updating, amplifiers are ubiquitous [21, 22, 12, 23,
24]. Almost all small spatial structures function as amplifiers of selection
[21]. A prime example of an amplifier under the Bd-updating is the Star graph,
which improves the mutant fixation probability to roughly $1-1/r^{2}$ [19, 25,
26, 27]. In particular, when $r=1+\varepsilon$, this is approximately a two-
fold increase over the baseline value $1-1/r$ given by the unstructured
population. Moreover, certain large spatial structures function as so-called
superamplifiers, that is, they increase the mutant fixation probability
arbitrarily close to 1, even when the mutant has only negligible fitness
advantage $r=1+\varepsilon$ [28]. Many other superamplifiers are known,
including Incubators [29], or Selection Reactors [30].

In contrast, in the world of dB-updating, only a handful of amplifiers are
known [31]. Perhaps the most prominent examples are the Fan graphs (see Fig.
2) that increase the fixation probability of near-neutral mutants by a factor
of up to $1.5$ [32]. Interestingly, all dB-amplifiers are necessarily
transient, meaning that the provided amplification effect disappears when the
mutant fitness advantage exceeds a certain threshold [33]. In particular,
large Fan graphs increase the fixation probability of the invading mutants for
$r\in(1,\varphi)$, where $\varphi\approx 1.618$ is the golden ratio, but
decrease it when $r>\varphi$ [32].

Unfortunately, the Fan graphs do not function as amplifiers when we instead
consider them under Bd-updating (see Fig. 2). This is unexpected, since
amplification in the Bd-world is so pervasive. And it begs a question. Do
there exist spatial structures that function as amplifiers both under the Bd-
updating and under the dB-updating? That is, do there exist structures for
which the amplification effect is robust with respect to the seemingly
arbitrary choice of which version of the Moran process we decide to run?

In this work, we first show three negative results that indicate that the
requirements for Bd-amplification and dB-amplification are often conflicting.
First, we show that known amplifiers of selection under the Bd-updating are
suppressors of selection for the dB-updating and vice versa. Second, we prove
that simultaneous Bd- and dB-amplification is impossible under neutral drift
($r=1$) when the initial mutant location is fixed to a specific starting node.
Third, we define a quantity that corresponds to the probability of “mutants
going extinct immediately”. We then prove that, roughly speaking, no graph
improves this quantity as compared to the complete graph under both Bd- and
dB-updating. Thus, improving fixation probability under both Bd- and dB-
udpating as compared to the complete graph might seem unlikely. Despite those
negative results, we identify a class of population structures that function
as amplifiers of selection under both Birth-death and death-Birth updating,
for any mutation that grants a relative fitness advantage $r\in(1,1.2)$. We
also present numerical computation that illustrates that the amplification
strength is substantial.

## Model

Here we formally introduce the terms and notation that we use later, such as
the evolutionary dynamics of Moran Birth-death and Moran death-Birth process,
the fixation probability, and the notion of an amplifier.

### Population structure

The spatial structure of the population is represented as a graph (network),
denoted $G_{N}=(V,E)$, where $V$ is a set of $N$ nodes (vertices) of $G_{N}$
that represent individual sites, and $E$ is a set of edges (connections) that
represent possible migration patterns for the offspring. The edges are
undirected (two-way) and may be weighted to distinguish stronger interactions
from the weaker ones, see Fig. 1a. The weight of an edge between nodes $u$ and
$v$ is denoted $w(u,v)$. If all edge weights are equal to 1 we say that the
graph is unweighted. At any given time, each site is occupied by a single
individual, who is either a resident with fitness 1, or a mutant with fitness
$r\geq 1$. The fitness of an individual at node $u$ is denoted $f(u)$.

### Moran process

Moran process is a classic discrete-time stochastic process that models the
evolutionary dynamics of selection in a population of asexually reproducing
individuals. Initially, each node is occupied either by a resident or by a
mutant. As long as both mutants and residents co-exist in the population, we
perform discrete time steps that change the state of (at most) one node at a
time.

There are two versions of the Moran process (see Fig. 1). In the Moran Birth-
death process, we first select an individual to reproduce (randomly,
proportionally to the fitness of the individual), and then the offspring
migrates along one adjacent edge (randomly, proportionally to the weight of
that edge) to replace the neighbor. Formally, denoting by $F=\sum_{u}f(u)$ the
total fitness of the population, node $u$ gets selected for reproduction with
probability $f(u)/F$, and then it replaces a neighbor $v$ with probability
$p_{u\to v}=w(u,v)/\sum_{v^{\prime}}w(u,v^{\prime})$.

In contrast, in the Moran death-Birth process, we first select an individual
to die (uniformly at random), and then the neighbors compete to fill in the
vacancy (randomly, proportionally to the edge weight and the fitness of the
neighbor). Formally, node $v$ dies with probability $1/N$ and it gets replaced
by a node $u$ with probability $p_{u\to v}=f(u)\cdot
w(u,v)/(\sum_{u^{\prime}}f(u^{\prime})\cdot w(u^{\prime},v))$. We note that in
both versions we capitalize the word “Birth” to signify that fitness plays a
role in the birth step (and not in the death step).

### Fixation probability and Amplifiers

If the graph $G_{N}$ that represents the population structure is connected
then the Moran process eventually reaches a “homogeneous state”, where either
all nodes are occupied by mutants (we say that mutants fixated), or all nodes
are occupied by residents (we say that mutants went extinct). Given a graph
$G_{N}$, a mutant fitness advantage $r\geq 1$, and a set $S\subseteq V$ of
nodes initially occupied by mutants, we denote by
$\rho^{\operatorname{Bd}}_{r}(G_{N},S)$ the fixation probability, that is, the
probability that mutants eventually reach fixation, under Moran Birth-death
process. We are particularly interested in the fixation probability of a
single mutant who appears at a node selected uniformly at random. We denote
this fixation probability under uniform initialization by
$\rho^{\operatorname{Bd}}_{r}(G_{N})=\frac{1}{N}\sum_{v\in
V}\rho^{\operatorname{Bd}}_{r}(G_{N},\\{v\\})$. We define
$\rho^{\operatorname{dB}}_{r}(G_{N},S)$ and
$\rho^{\operatorname{dB}}_{r}(G_{N})$ analogously.

In this work we focus on population structures that increase the fixation
probability of invading mutants. The base case is given by an unweighted
complete graph $K_{N}$ that includes all edges and represents an unstructured,
well-mixed population. It is known [4, 21, 20] that

$\rho^{\operatorname{Bd}}_{r}(K_{N})=\frac{1-\frac{1}{r}}{1-\frac{1}{r^{N}}}\quad\text{and}\quad\rho^{\operatorname{dB}}_{r}(K_{N})=\frac{N-1}{N}\cdot\frac{1-\frac{1}{r}}{1-\frac{1}{r^{N-1}}}.$

Given a graph $G_{N}$ and a mutant fitness advantage $r\geq 1$, we say that
$G_{N}$ is a Bdr-amplifier if
$\rho^{\operatorname{Bd}}_{r}(G_{N})>\rho^{\operatorname{Bd}}_{r}(K_{N})$. We
define dBr amplifiers analogously, that is, as those graphs $G_{N}$ that
satisfy
$\rho^{\operatorname{dB}}_{r}(G_{N})>\rho^{\operatorname{dB}}_{r}(K_{N})$.
Similarly, suppressors are graphs that decrease the fixation probability as
compared to the complete graph.

## Results

First, we present three negative results that illustrate that the two worlds
of Birth-death and death-Birth updating often present contradictory
requirements when it comes to enhancing the fixation probability of a single
newly occurring mutant. Nevertheless, as our main contribution in the positive
direction, we then present population structures that are both Bdr-amplifiers
and dBr-amplifiers for a range of mutant fitness advantages $r\in(1,1.2)$.

### Negative results

In this section, we present results that suggest that finding simultaneous
Bdr\- and dBr\- amplifiers is not easy. First, we show empirically that known
amplifiers for one process are suppressors for the other process. Second, we
show that in the neutral regime ($r=1$), any fixed vertex is a “good” starting
vertex for the mutant in at most one of the two processes. Finally, we show
that for any starting vertex, the chance of not dying immediately can be
enhanced in at most one of the two processes (see below for details).

#### Known amplifiers for one process

In this section we examine spatial structures that are known to amplify under
one of the two versions of the Moran process, in order to see whether they
amplify under the other version of the Moran process (spoiler alert: they
don’t).

First, we consider the smallest known unweighted dB-amplifier [17], which is a
certain graph on $N=11$ nodes (see Fig. 2). We call the graph $D_{11}$. The
graph $D_{11}$ is an extremely weak dBr-amplifier in a range of approximately
$r\in(1,1.00075)$, where it increases the fixation probability by a factor
less than $1.0000001\times$ (see [17, Fig.1]). For $r\in(1.01,1.1)$ the graph
$D_{11}$ appears to function as a very slight suppressor under both dB-
updating and Bd-updating. In particular, at $r=1.1$ we obtain
$\rho^{\operatorname{Bd}}_{r}(D_{11})/\rho^{\operatorname{Bd}}_{r}(K_{11})\doteq
0.996$ and
$\rho^{\operatorname{dB}}_{r}(D_{11})/\rho^{\operatorname{dB}}_{r}(K_{11})\doteq
0.997$.

Next, we examine the star graph $S_{11}$ on $11$ vertices which, to our
knowledge, is the strongest unweighted amplifier for Bd-updating at this
population size. The Star graph is a clear Bdr-amplifier for $r\in(1.01,1.1)$,
but an equally clear dBr-suppressor in that range.

The situation is reversed for the Fan graph $F_{11}$ [32]. While the Fan graph
clearly functions as an amplifier under the dB-updating when $r\in(1.01,1.1)$,
it lags behind the baseline given by the complete graph under the Bd-updating.

Fig 2: Known amplifiers are suppressors for the other process. a, We consider
four graphs on $N=11$ nodes, namely the Complete graph $K_{11}$, the star
graph $S_{11}$, the Fan graph $F_{11}$, and the smallest known undirected
suppressor $D_{11}$ (see [17]). b, Under Bd-updating, the only amplifier for
$r\in\\{1.01,\dots,1.1\\}$ is the Star graph $S_{11}$. c, Under dB-updating,
the only amplifier for $r\in\\{1.01,\dots,1.1\\}$ is the Fan graph $F_{11}$.
Values computed by numerically solving the underlying Markov chains.

#### Neutral regime ($r=1$)

The second negative result pertains to the case of neutral mutations ($r=1$).
Recall that $\rho^{\operatorname{Bd}}_{r}(G_{N},v)$ and
$\rho^{\operatorname{dB}}_{r}(G_{N},v)$ denote the fixation probabilities when
the initial mutant appears at node $v$. The following theorem states that for
neutral mutations ($r=1$), no initial mutant node increases the fixation
probability both for Birth-death and death-Birth updating.

######  Theorem 1.

Let $G_{N}$ be a graph and $v$ an initial mutant node. Then either

  1. 1.

$\rho^{\operatorname{Bd}}_{r=1}(G_{N},v)<\rho^{\operatorname{Bd}}_{r=1}(K_{N})$;
or

  2. 2.

$\rho^{\operatorname{dB}}_{r=1}(G_{N},v)<\rho^{\operatorname{dB}}_{r=1}(K_{N})$;
or

  3. 3.

$\rho^{\operatorname{Bd}}_{r=1}(G_{N},v)=\rho^{\operatorname{Bd}}_{r=1}(K_{N})$
and
$\rho^{\operatorname{dB}}_{r=1}(G_{N},v)=\rho^{\operatorname{dB}}_{r=1}(K_{N})$.

The idea behind the proof is that for neutral evolution there are explicit
formulas for fixation probabilities $\rho^{\operatorname{Bd}}_{r}(G_{N},v)$
and $\rho^{\operatorname{dB}}_{r}(G_{N},v)$ on any undirected graph $G_{N}$
[34, 35]. The result then follows by applying Cauchy-Schwarz inequality. See
Supplementary Information for details. In Supplementary Information, we also
note that Theorem 4 does not generalize to the case when instead of having one
initial mutant node we start with an initial subset $S$ of $k\geq 2$ nodes
occupied by mutants.

#### Immediate extinction and forward bias

In order to present our third and final negative result, we need to introduce
additional notions and notation. When tracking the evolutionary dynamics on a
given graph $G_{N}$ with a given mutant fitness advantage $r\geq 1$, it is
often useful to disregard the exact configuration of which nodes are currently
occupied by mutants, and only look at how many nodes are occupied by mutants.

One example of this is the celebrated Isothermal theorem [3] which states that
once $N$ and $r$ are fixed, the fixation probability under the Moran Birth-
death process on any regular graph is the same. Here, a graph is regular if
each node has the same total weight of adjacent edges. Examples of regular
graphs include the complete graph, the cycle graph, or any grid graph with
periodic boundary condition.

The intuition behind the proof of the Isothermal theorem is that for any
regular graph $R_{N}$, the Moran Birth-death process can be mapped to a random
walk that tracks just the number of mutants, instead of their exact positions
on the graph. It can be shown that this random walk has a constant forward
bias, that is, the probabilities $p^{+}$ (resp. $p^{-}$) that the size of the
mutant subpopulation increases (resp. decreases) satisfy $p^{+}/p^{-}=r$, for
any number of mutants in any particular mutant-resident configuration. A
natural approach to construct amplifiers is thus to construct graphs for which
this forward bias satisfies an inequality $p^{+}/p^{-}\geq r$ for the Moran
Birth-death process and an analogous inequality for the Moran death-Birth
process. Our final negative result shows that this goal can not be achieved
already in the first step.

Formally, consider the Moran Birth-death process on a graph $G_{N}$ with a
single initial mutant placed at node $u$. Let
$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)$ be the probability that the first
reproduction event that changes the size of the mutant subpopulation is the
initial mutant reproducing (as opposed to the initial mutant being replaced by
one of its neighbors). In other words,
$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)$ is the probability that the first
step that changes the configuration of the mutants does not eliminate the
initial mutant, leaving the options of later mutant extinction or mutant
fixation.

For the complete graph $K_{N}$ (and any single mutant node) it is not hard to
show that
$\gamma^{\operatorname{Bd}}_{r}(K_{N})=\gamma^{\operatorname{Bd}}_{r}(K_{N},u)=r/(r+1)$
for any node $u$. Moreover, by a slight extension of the Isothermal theorem,
we have $\gamma^{\operatorname{Bd}}_{r}(R_{N},u)=r/(r+1)$ for any regular
graph $R_{N}$ and any node $u$. For Moran death-Birth process, we define
$\gamma^{\operatorname{dB}}_{r}(G_{N},u)$ and
$\gamma^{\operatorname{dB}}_{r}(K_{N})$ analogously. To construct a graph that
is both a Bd- and a dB-amplifier, a natural approach is to look for a graph
and an initial mutant node $u$ such that
$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)>\gamma^{\operatorname{Bd}}_{r}(K_{N})$
and
$\gamma^{\operatorname{dB}}_{r}(G_{N},u)>\gamma^{\operatorname{dB}}_{r}(K_{N})$.
However, the following theorem states that no such graphs exist.

######  Theorem 2.

Let $G_{N}$ be a graph, $u$ an initial mutant node, and $r\geq 1$. Then either

  1. 1.

$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)<\gamma^{\operatorname{Bd}}_{r}(K_{N})$;
or

  2. 2.

$\gamma^{\operatorname{dB}}_{r}(G_{N},u)<\gamma^{\operatorname{dB}}_{r}(K_{N})$;
or

  3. 3.

$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)=\gamma^{\operatorname{Bd}}_{r}(K_{N})$
and
$\gamma^{\operatorname{dB}}_{r}(G_{N},u)=\gamma^{\operatorname{dB}}_{r}(K_{N})$.

The proof relies on the notion of the temperature of a node. Formally, given a
graph $G_{N}=(V,E)$ and a node $u\in V$, its temperature $T(u)$ is defined as
$T(u)=\sum_{v}1/\operatorname{deg}(v)$, where the sum goes over all the
neighboring nodes $v$ of $u$ in $G_{N}$. The temperature of a node represents
the rate at which the node is being replaced by its neighbors in the Moran
Birth-death process when $r=1$. Nodes with high temperature are replaced
often, whereas nodes with low temperature are replaced less frequently.
Building on this, it is straightforward to show that if a node $u$ has above-
average temperature, then
$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)<\gamma^{\operatorname{Bd}}_{r}(K_{N})$,
that is, in Moran Birth-death process with a single mutant at $u$ the forward
bias is lower than the forward bias on a complete graph. To complete the
proof, we then show that for any node $u$ with below-average temperature, we
have
$\gamma^{\operatorname{dB}}_{r}(G_{N},u)<\gamma^{\operatorname{dB}}_{r}(K_{N})$.
Our proof of the latter claim uses Jensen’s inequality for a certain concave
function. See Supplementary Information for details.

### Positive result

Despite the above negative results, in this section we identify population
structures $A_{N}$ that substantially amplify the fixation probability under
both Birth-death updating and death-Birth updating when the number $N$ of
nodes is sufficiently large.

The structures $A_{N}$ are composed of two large chunks
$A^{\operatorname{Bd}}$ and $A^{\operatorname{dB}}$ that are connected by a
single edge, see Fig. 3a for an illustration. The chunk
$A^{\operatorname{dB}}$ is a Fan graph [32], which is to our knowledge the
strongest currently known dB-amplifier. The chunk $A^{\operatorname{Bd}}$
could be any of the many strong Bd-amplifiers. For definiteness, in Fig. 3a we
use a Fan-like structure with $a$ nodes in a central hub and $b$ blades of two
nodes each surrounding it. The single connecting edge has a very low edge
weight so that the two chunks interact only rarely. For population size
$N=1001$, the resulting weighted graph is both a Bdr-amplifier and a dBr-
amplifier for any $r\in(1,1.09)$, see Fig. 3b.

Fig 3: Simultaneous Bd- and dB-amplifier $A_{N}$. a, The graph $A_{N}$ is
composed of two large chunks $A^{\operatorname{Bd}}$ and
$A^{\operatorname{dB}}$ that are connected by a single edge. The chunk
$A^{\operatorname{dB}}$ is a Fan graph on $f$ nodes. The chunk
$A^{\operatorname{Bd}}$ is a fan-like graph with $a$ vertices in a central hub
and $b$ blades of two nodes each. The total population size is $N=a+2b+f$
(here $a=b=5$, $f=11$, and $N=26$). The edge weights are defined such that
different circled units within the chunks interact only rarely, and the chunks
themselves interact even more rarely. b, Here we consider graph $A_{N}$ with
population size $N=1001$ and $(a,b,f)=(30,85,801)$. The fixation probabilities
under Bd- and dB-updating are computed by numerically solving the underlying
Markov chain. We find that the inequality
$\rho^{\operatorname{Bd}}_{r}(A_{N})>\rho^{\operatorname{Bd}}_{r}(K_{N})$ is
satisfied for $r\in(1,1.09)$ and the inequality
$\rho^{\operatorname{dB}}_{r}(A_{N})>\rho^{\operatorname{dB}}_{r}(K_{N})$ is
satisfied for $r\in(1,1.2)$. In particular, at $r=1.05$ the ratios satisfy
$\rho^{\operatorname{Bd}}_{r}(A_{N})/\rho^{\operatorname{Bd}}_{r}(K_{N})>1.44$
and
$\rho^{\operatorname{dB}}_{r}(A_{N})/\rho^{\operatorname{dB}}_{r}(K_{N})>1.14$.

Similarly, we identify large population structures that serve as both Bdr-
amplifiers and dBr-amplifiers for any $r\in(1,1.2)$.

######  Theorem 3 (Simultaneous Bd- and dB-amplifier).

For every large enough population size $N$ there exists a graph $A_{N}$ such
that for all $r\in(1,1.2)$ we have

$\rho^{\operatorname{Bd}}_{r}(A_{N})>\rho^{\operatorname{Bd}}_{r}(K_{N})\quad\text{and}\quad\rho^{\operatorname{dB}}_{r}(A_{N})>\rho^{\operatorname{dB}}_{r}(K_{N}).$

In what follows we provide intuition about the proof of Theorem 6.The fully
rigorous proof is relegated to Supplementary Information. Let $e$ be the edge
connecting the two chunks, $u$ its endpoint in $A^{\operatorname{Bd}}$, and
$v$ its endpoint in $A^{\operatorname{dB}}$.

First, observe that since $e$ has a low weight, the two chunks evolve mostly
independently. This means that, with high probability, each chunk resolves to
a homogeneous state in between any two interactions across the chunks. In
particular, if the initial mutant appears in the chunk where it is favored
(e.g. if it appears in the chunk $A^{\operatorname{Bd}}$ when Bd-updating is
run), the mutants fixate on that chunk with reasonable probability. If that
occurs, we say that mutants are “half done”.

Once the mutants are half done, the next relevant step occurs when the two
chunks interact. There are two cases. Either a mutant at $u$ reproduces and
the offspring migrates along $e$ to $v$, or a resident at $v$ reproduces and
the offspring migrates along $e$ to replace the mutant at $u$. In both cases,
the individual (mutant or resident) who “invades” the other half eventually
either succeeds in spreading through that half, or they fail at doing that. If
the latter occurs, we are back at the situation in which mutants are half done
and the situation repeats. By bounding all the relevant probabilities, we show
that once half done, mutants are overwhelmingly likely to fixate, as opposed
to going extinct.

We highlight an interesting phenomenon that occurs in our proof. As we run the
evolutionary dynamics, we can look at the flow along the connecting edge $e$.
Thanks to the edge weights, it turns out that the direction of the flow along
$e$ flips depending on whether we run the Moran Birth-death process or the
Moran death-Birth process. In particular, under the Bd-updating the edge $e$
is used mostly in the direction from $u$ to $v$. That is, many individuals
migrate from $u$ to $v$, whereas few individuals migrate from $v$ to $u$.
Under dB-updating the situation reverses. That is, many individuals migrate
from $v$ to $u$, whereas few of them migrate from $u$ to $v$. Thus, under the
Bd-updating the $A^{\operatorname{Bd}}$ chunk is effectively upstream of the
chunk $A^{\operatorname{dB}}$, whereas under the dB-updating the
$A^{\operatorname{dB}}$ chunk is effectively upstream of the chunk
$A^{\operatorname{Bd}}$. This asymmetry is a key factor that contributes to
the fact that once the mutants are half done, they are likely to fixate on the
whole graph (see Fig. 4).

Fig 4: Interactions between $A^{\operatorname{Bd}}$ and
$A^{\operatorname{dB}}$. a, The edge weights in the chunks
$A^{\operatorname{Bd}}$ (red) and $A^{\operatorname{dB}}$ (blue) are shown as
a function of $t$ (here $t\gg 1$ is large). For each of two versions of the
Moran process, the rates at which the offspring migrate from $u$ to $v$ and
from $v$ to $u$ can be calculated and are listed in the table. b, Under Birth-
death updating, the migration rate $p_{u\to v}$ from $u$ to $v$ is roughly
$t\times$ larger than the migration rate $p_{v\to u}$ from $v$ to $u$, so the
chunk $A^{\operatorname{Bd}}$ is upstream of the chunk
$A^{\operatorname{dB}}$, and a mutant who has fixated over
$A^{\operatorname{dB}}$ is likely to fixate over $A^{\operatorname{dB}}$ too.
c, In contrast, under death-Birth updating we have $p_{v\to u}\approx t\cdot
p_{u\to v}$, hence the chunk $A^{\operatorname{dB}}$ is upstream of
$A^{\operatorname{Bd}}$.

What remains in the proof is to balance out the sizes of the two chunks. For
small $r>1$, the strongest known dB-amplifiers are roughly $\frac{3}{2}\times$
stronger than the Complete graph (in terms of the fixation probability). Thus,
in order to achieve amplification under dB-updating, we need the chunk
$A^{\operatorname{dB}}$ to take up at least $2/3$ of the total population
size. The chunk $A^{\operatorname{Bd}}$ then takes up at most $1/3$ of the
total population size. In order to achieve Bd-amplification, fixation
probability on $A^{\operatorname{Bd}}$ under Bd-updating must therefore be at
least $3\times$ larger than that on the Complete graph. Interestingly, a Star
graph is not strong enough to do that (for $r\approx 1$ and large population
size $N$ it is only roughly $2\times$ stronger than the Complete graph), but
sufficiently strong Bd-amplifiers do exist (e.g. any superamplifier).

## Discussion

Population structure has a profound impact on the outcomes of evolutionary
processes and, in particular, on the probability that a novel mutation
achieves fixation [36, 3]. Population structures that increase the fixation
probability of beneficial mutants, when compared to the case of a well-mixed
population, are known as amplifiers of selection.

Somewhat surprisingly, to tell whether a specific spatial structure is an
amplifier or not, one needs to specify seemingly minor details of the
evolutionary dynamics. The well-studied Moran process comes in two versions,
namely Moran process with Birth-death updating and Moran process with death-
Birth updating. While many spatial structures are amplifiers under the Bd-
updating [21], only a handful of amplifiers under the dB-updating are known
[31]. Moreover, none of the dB-amplifiers that we checked amplify under the
Bd-updating.

In this work we help explain this phenomenon by proving mathematical results
which illustrate that the two objectives of amplifying under the Bd-updating
and amplifying under the dB-updating are often contradictory. Thus, one might
be tempted to conclude that perhaps there are no population structures that
amplify in both worlds, that is, regardless of the choice of the underlying
dynamics (Bd or dB). Nevertheless, we proceed to identify population
structures that serve as amplifiers of selection under both Bd-updating and
dB-updating.

The amplifiers we identify in this work have several interesting features.
First, they are robust in the sense that they amplify selection under both the
Bd-updating and the dB-updating. Second, they provide amplification for any
mutant fitness advantage $r$ in a range $r\in(1,1.2)$, which covers many
realistic values of the mutant fitness advantage, and the amplification is
non-negligible (for instance, for $r=1.05$ the fixation probability increases
by 14% and 44%, respectively. see Fig. 3). Third, the amplifiers are modular.
That is, they consist of two large chunks that serve as building blocks and
that interact rarely. For definiteness, in this work we specified the two
chunks and their relative sizes, but each chunk can be replaced by an
alternative building block and the relative sizes can be altered. For example,
the best currently known dB-amplifiers amplify by a factor of $1.5\times$ for
$r\approx 1$ and continue to amplify for $r$ in a range $r\in(1,\varphi)$,
where $\varphi=\frac{1}{2}(\sqrt{5}+1)\approx 1.618$ is the golden ratio [32].
If better dB-amplifiers are found, they can be used as a building block in
place of one of the chunks to improve the range $r\in(1,1.2)$ for which the
resulting structure amplifies in both worlds.

In this work, our objective was to increase the fixation probability of an
invading mutant in both worlds (Bd-updating and dB-updating). An interesting
direction for future work is to optimize other quantities in both worlds.

One such quantity is the duration of the process until fixation occurs [37,
38, 39]. For example, achieving short fixation times in combination with
increasing the fixation probability does not appear to be easy. Our proofs
rely on the existence of small edge weights to separate the time scales at
which different stages of the process happen. While using more uniform edge
weights might still lead to the same outcome, the proofs would need to become
more delicate. A possible approach to identify structures that serve as fast
amplifiers in both worlds would be to find unweighted amplifiers, because then
the time would be guaranteed to be at most polynomial [40, 41]. The first step
in this direction would be to identify large and substantially strong
unweighted dB-amplifiers. There are promising recent results in this direction
[31].

Looking beyond fixation time, there are other relevant quantities such as the
recently introduced rate at which beneficial mutations accumulate [42].
Existing research suggests that the two versions of the Moran process behave
quite differently in terms of the fixation probability [21], but quite
similarly in terms of the fixation time [40, 41]. Which of those two cases
occurs for other relevant quantities remains to be seen.

## Data and code availability

Code for the figures and the computational experiments is available from the
Figshare repository: https://figshare.com/s/4e08d78c892749f84201.

## Acknowledgements

We thank Gavin Rees for helpful discussions. J.T. was supported by Center for
Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004)
and by the project PRIMUS/24/SCI/012 from Charles University. J.S., K.C., and
S.J. were supported by the European Research Council (ERC) CoG 863818 (ForM-
SMArt).

## References

  * 1. Moran PAP.  Random processes in genetics.  In: Mathematical proceedings of the cambridge philosophical society. vol. 54. Cambridge University Press; 1958. p. 60–71.
  * 2. Ewens WJ.  Mathematical population genetics: theoretical introduction. vol. 27.  Springer; 2004.
  * 3. Lieberman E, Hauert C, Nowak MA.  Evolutionary dynamics on graphs.  Nature. 2005;433(7023):312–316.
  * 4. Nowak MA.  Evolutionary dynamics: exploring the equations of life.  Harvard University Press; 2006.
  * 5. Yagoobi S, Traulsen A.  Fixation probabilities in network structured meta-populations.  Scientific Reports. 2021;11(1):17979.
  * 6. Marrec L, Lamberti I, Bitbol AF.  Toward a universal model for spatially structured populations.  Physical review letters. 2021;127(21):218102.
  * 7. 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.
  * 8. Yagoobi S, Sharma N, Traulsen A.  Categorizing update mechanisms for graph-structured metapopulations.  Journal of the Royal Society Interface. 2023;20(200):20220769.
  * 9. Tkadlec J, Kaveh K, Chatterjee K, Nowak MA.  Evolutionary dynamics of mutants that modify population structure.  Journal of the Royal Society Interface. 2023;20(208):20230355.
  * 10. Adlam B, Chatterjee K, Nowak MA.  Amplifiers of selection.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2015;471(2181):20150114.
  * 11. Frean M, Rainey PB, Traulsen A.  The effect of population structure on the rate of evolution.  Proceedings of the Royal Society B: Biological Sciences. 2013;280(1762):20130211.
  * 12. 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.
  * 13. 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–9312.
  * 14. Clifford P, Sudbury A.  A model for spatial conflict.  Biometrika. 1973;60(3):581–588.
  * 15. Komarova NL.  Spatial stochastic models for cancer initiation and progression.  Bulletin of mathematical biology. 2006;68:1573–1599.
  * 16. 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–230.
  * 17. Richter H.  Spectral analysis of transient amplifiers for death–birth updating constructed from regular graphs.  Journal of Mathematical Biology. 2021;82(7):61.
  * 18. Antal T, Redner S, Sood V.  Evolutionary dynamics on degree-heterogeneous graphs.  Physical review letters. 2006;96(18):188104.
  * 19. Broom M, Rychtář J.  An analysis of the fixation probability of a mutant on special classes of non-directed graphs.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2008;464(2098):2609–2627.
  * 20. Kaveh K, Komarova NL, Kohandel M.  The duality of spatial death–birth and birth–death processes and limitations of the isothermal theorem.  Royal Society open science. 2015;2(4):140465.
  * 21. 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.
  * 22. 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.
  * 23. 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.
  * 24. Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak MA.  Amplification on undirected population structures: comets beat stars.  Scientific reports. 2017;7(1):82.
  * 25. 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.
  * 26. 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.
  * 27. Chalub FA.  Asymptotic expression for the fixation probability of a mutant in star graphs.  arXiv preprint arXiv:14043944. 2014;.
  * 28. 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.
  * 29. 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.
  * 30. Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA.  Fast and strong amplifiers of natural selection.  Nature Communications. 2021;12(1):4009.
  * 31. Richter H.  Spectral dynamics of guided edge removals and identifying transient amplifiers for death–Birth updating.  Journal of Mathematical Biology. 2023;87(1):3.
  * 32. 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.
  * 33. 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.
  * 34. 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–2798.
  * 35. Maciejewski W.  Reproductive value in graph-structured populations.  Journal of Theoretical Biology. 2014;340:285–293.
  * 36. Durrett R, Levin S.  The importance of being discrete (and spatial).  Theoretical population biology. 1994;46(3):363–394.
  * 37. Díaz J, Goldberg LA, Richerby D, Serna M.  Absorption time of the Moran process.  Random Structures & Algorithms. 2016;49(1):137–159.
  * 38. 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.
  * 39. Monk T, van Schaik A.  Martingales and the characteristic functions of absorption time on bipartite graphs.  Royal Society Open Science. 2021;8(10):210657.
  * 40. 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.
  * 41. 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–271.
  * 42. 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.

Supplementary Material: Amplifiers of selection for the Moran process with
both Birth-death and death-Birth updating

This is a supplementary information to the manuscript Amplifiers of selection
for the Moran process with both Birth-death and death-Birth updating. It
contains formal proofs of the theorems listed in the main text.

##  1 Preliminaries

Given an undirected graph $G_{N}=(V,E)$ on $N$ nodes, the degree of a node
$u$, denoted $\operatorname{deg}(u)$, is the number of neighbors of $u$ in
$G_{N}$. When the edges are weighted, we define the degree
$\operatorname{deg}(u)=\sum_{(u,v)\in E}w(u,v)$ as the sum of the weights of
all the adjacent edges. As a direct extension of [34, 35] we obtain the
following formula for fixation probability under neutral drift ($r=1$). For
completeness, we include a proof.

######  Lemma 1 (Fixation probability on edge-weighted undirected graphs when
$r=1$).

Let $G_{N}=(V,E)$ be an edge-weighted undirected graph on $N$ nodes and
$S\subset V$ any set of vertices occupied by mutants. Then

$\rho^{\operatorname{Bd}}_{r=1}(G_{N},S)=\frac{\sum_{u\in
S}1/\operatorname{deg}(u)}{\sum_{v\in
V}1/\operatorname{deg}(v)}\qquad\text{and}\qquad\rho^{\operatorname{dB}}_{r=1}(G_{N},S)=\frac{\sum_{u\in
S}\operatorname{deg}(u)}{\sum_{v\in V}\operatorname{deg}(v)}.$

###### Proof.

Let $p_{u\to v}$ be the probability that, in a single step, an individual at
node $u$ produces an offspring that replaces an individual at node $v$. For
Birth-death updating, it suffices to check that for any subset $S\subset V$ of
mutant nodes and any edge $(u,v)$ connecting a mutant node $u\in S$ and a non-
mutant node $v\not\in S$ we have

$p_{u\to v}\cdot\frac{1/\operatorname{deg}(v)}{\sum_{v^{\prime}\in
V}1/\operatorname{deg}(v^{\prime})}=p_{v\to
u}\cdot\frac{1/\operatorname{deg}(u)}{\sum_{v^{\prime}\in
V}1/\operatorname{deg}(v^{\prime})}.$

Since for Birth-death updating and $r=1$ we have $p_{u\to
v}=\frac{1}{N}\cdot\frac{w(u,v)}{\operatorname{deg}(u)}$, both sides rewrite
as

$\frac{\frac{1}{N}\cdot\frac{w(u,v)}{\operatorname{deg}(u)\operatorname{deg}(v)}}{\sum_{v^{\prime}\in
V}1/\operatorname{deg}(v^{\prime})},$

and so the claim is proved. Likewise, for death-Birth updating it suffices to
check that

$p_{u\to v}\cdot\frac{\operatorname{deg}(v)}{\sum_{v^{\prime}\in
V}\operatorname{deg}(v^{\prime})}=p_{v\to
u}\cdot\frac{\operatorname{deg}(u)}{\sum_{v^{\prime}\in
V}\operatorname{deg}(v^{\prime})}.$

Since for death-Birth updating and $r=1$ we have $p_{u\to
v}=\frac{1}{N}\cdot\frac{w(u,v)}{\operatorname{deg}(v)}$, this time both sides
rewrite as

$p_{u\to v}\cdot\frac{\frac{w(u,v)}{N}}{\sum_{v^{\prime}\in
V}\operatorname{deg}(v^{\prime})}.\qed$

The proof of our positive result relies on three existing results. For
convenience, we list them here. First, there exist unweighted graphs called
Incubators that are strong amplifiers under Birth-death updating [29, Theorem
2].

######  Lemma 2.

There exists a family of graphs $\mathcal{A}^{Bd}_{N}$ such that for all
$r>1$, we have

$\rho^{\operatorname{Bd}}_{r}(\mathcal{A}^{Bd}_{N})\geq
1-\mathcal{O}(n^{-1/3}).$

Second, there exist edge-weighted graphs called Separated Hubs that are
substantial amplifiers under death-Birth updating [32, Theorem 3].

######  Lemma 3.

There exists a family of graphs $\mathcal{A}^{dB}_{N}$ such that for all
$r>1$, we have

$\rho^{\operatorname{dB}}_{r}(G_{N})=\frac{n}{2n+1}\cdot\frac{1-\frac{1}{r^{3}}}{1-\frac{1}{r^{3n}}}.$

Third, the evolutionary dynamics terminates polynomially quickly in terms of
the population size $N$, under both the Birth-death updating [40, Theorem 9]
and the death-Birth updating [41, Theorem 1].

######  Lemma 4.

Fix $r>1$. For Bd and dB process on an undirected graph with $N$ vertices with
the highest ratio between edge weights $\frac{1}{\varepsilon}$, the expected
fixation time is in $\mathcal{O}(\frac{N^{4}}{\varepsilon})$.

##  2 Negative result 2

In this section, we show that one fixed neutral mutant cannot have a better
fixation probability in both processes than on a complete graph. This means
that even if we can choose the starting position, we are not guaranteed to
increase the fixation probability for both processes.

######  Theorem 4.

Let $G_{N}$ be a graph and $v$ an initial mutant node. Then one of the
following three cases occurs:

  1. 1.

$\rho^{\operatorname{Bd}}_{r=1}(G_{N},v)<\rho^{\operatorname{Bd}}_{r=1}(K_{N})$;

  2. 2.

$\rho^{\operatorname{dB}}_{r=1}(G_{N},v)<\rho^{\operatorname{dB}}_{r=1}(K_{N})$;

  3. 3.

$\rho^{\operatorname{Bd}}_{r=1}(G_{N},v)=\rho^{\operatorname{Bd}}_{r=1}(K_{N})$
and
$\rho^{\operatorname{dB}}_{r=1}(G_{N},v)=\rho^{\operatorname{dB}}_{r=1}(K_{N})$.

###### Proof.

First, note that
$\rho^{\operatorname{Bd}}_{r=1}(K_{N})=\rho^{\operatorname{dB}}_{r=1}(K_{N})=1/N$.
Next, recall the known formulas for the fixation probability on undirected
graphs under neutral drift (see Lemma 1 and [34, 35]], namely:

$\rho^{\operatorname{Bd}}_{r=1}(G_{N},v)=\frac{1/\operatorname{deg}(v)}{\sum_{u\in
V}1/\operatorname{deg}(u)}\quad\text{and}\quad\rho^{\operatorname{dB}}_{r=1}(G_{N},v)=\frac{\operatorname{deg}(v)}{\sum_{u\in
V}\operatorname{deg}(u)}.$

As the final ingredient, note that for any $N$ non-negative numbers
$x_{1},\dots,x_{N}$ we have a bound

$\left(\frac{1}{x_{1}}+\frac{1}{x_{2}}+\dots+\frac{1}{x_{N}}\right)\cdot(x_{1}+x_{2}+\dots+x_{N})\geq
N^{2}.$

This follows e.g. from the inequality between the arithmetic and harmonic mean
of numbers $x_{1},\dots,x_{N}$ (called AM-HM), or from Cauchy-Schwarz
inequality. Moreover, the equality occurs if and only if
$x_{1}=x_{2}=\dots=x_{N}$. Applying this bound to
$x_{i}=\operatorname{deg}(v_{i})$ we obtain

$\rho^{\operatorname{Bd}}_{r=1}(G_{N},v)\cdot\rho^{\operatorname{dB}}_{r=1}(G_{N},v)=\frac{1/\operatorname{deg}(v)}{\sum_{u\in
V}1/\operatorname{deg}(u)}\cdot\frac{\operatorname{deg}(v)}{\sum_{u\in
V}\operatorname{deg}(u)}=\frac{1}{\left(\sum_{u\in
V}1/\operatorname{deg}(u)\right)\cdot\left(\sum_{u\in
V}\operatorname{deg}(u)\right)}\leq\frac{1}{N^{2}}.$

If equalities occur everywhere then
$\operatorname{deg}(v_{1})=\dots=\operatorname{deg}(v_{N})$, thus
$\rho^{\operatorname{Bd}}_{r=1}(G_{N},v)=\rho^{\operatorname{dB}}_{r=1}(G_{N},v)=1/N$.
Otherwise, the right-hand side is strictly less than $1/N^{2}$, thus at least
one of $\rho^{\operatorname{Bd}}_{r=1}(G_{N},v)$ and
$\rho^{\operatorname{dB}}_{r=1}(G_{N},v)$ is strictly less than $1/N$. ∎

The following example illustrates that there exists a graph and a subset
$S=\\{u,v\\}$ of $k=2$ nodes, such that the fixation probability starting from
mutants at both $u$ and $v$ is strictly greater than fixation probability
starting from $k=2$ mutant nodes on a well-mixed population, both for the
Birth-death and for the death-Birth updating.

Fig 5:  Mutant subset that amplifies for both Bd and dB. a, With two neutral
mutants ($r=1$) on a complete graph $K_{N}$, the fixation probability is equal
to $2/N$ under both Birth-death and death-Birth updating. b, When two neutral
mutants initially occupy vertices $u$ and $v$ of the so-called dart graph
$D_{5}$, the fixation probability under both Birth-death and death-Birth
updating is increased. c, As $r$ increases above roughly $r\approx 1.24$, the
fixation probability on the Dart graph under death-Birth updating drops below
the reference value of two mutants on a complete graph $K_{5}$. Under Birth-
death updating, the effect persists for $r\geq 1$. (Data obtained by
numerically solving the underlying Markov chains.)

The intuition behind the result is that node $u$ is a really good initial
mutant node for Birth-death updating, and node $v$ is a really good initial
mutant node for death-Birth updating. Together, they form an above-average set
of two mutant nodes, even when compared to a complete graph with two initial
mutants.

##  3 Negative result 3

In this section, we prove that for any fixed vertex, in the first step, the
ratio between increasing and decreasing the number of mutants cannot be better
than in the complete graph in both processes. This means we cannot find a
vertex from which both processes spread better than in the complete graph. To
achieve amplification for both processes, we know that some vertices will be
better for Bd and some for dB amplification.

######  Theorem 5.

Let $G_{N}$ be a graph, $u$ an initial mutant node, and $r\geq 1$. Then one of
the following three cases occurs:

  1. 1.

$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)<\gamma^{\operatorname{Bd}}_{r}(K_{N})$;

  2. 2.

$\gamma^{\operatorname{dB}}_{r}(G_{N},u)<\gamma^{\operatorname{dB}}_{r}(K_{N})$;

  3. 3.

$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)=\gamma^{\operatorname{Bd}}_{r}(K_{N})$
and
$\gamma^{\operatorname{dB}}_{r}(G_{N},u)=\gamma^{\operatorname{dB}}_{r}(K_{N})$.

###### Proof.

Denote by $T(u)=\sum_{v\colon(u,v)\in E}\frac{w(u,v)}{\operatorname{deg}v}$
the so-called temperature of node $u$, that is, the rate at which node $u$ is
replaced by its neighbors in the neutral case.

Denote by $p_{\operatorname{Bd},r}^{+}=p_{\operatorname{Bd},r}^{+}(G_{N},u)$
the probability that in a single step of the Moran Birth-death process the
mutant reproduces, and by
$p_{\operatorname{Bd},r}^{-}=p_{\operatorname{Bd},r}^{-}(G_{N},u)$ the
probability that it gets replaced by a resident. Denoting the total fitness by
$F=N+(r-1)$ we have

$p_{\operatorname{Bd},r}^{+}=\frac{r}{F}\quad\text{and}\quad
p_{\operatorname{Bd},r}^{-}=\sum_{v\colon(u,v)\in
E}\frac{1}{F}\cdot\frac{w(u,v)}{\operatorname{deg}v},$

and thus

$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)=\frac{p_{\operatorname{Bd},r}^{+}}{p_{\operatorname{Bd},r}^{+}+p_{\operatorname{Bd},r}^{-}}=\frac{r}{r+\sum_{v\colon(u,v)\in
E}\frac{w(u,v)}{\operatorname{deg}v}}=\frac{r}{r+T(u)}.$

In particular, in the complete graph $K_{N}$ each node has temperature $1$,
and thus

$\gamma^{\operatorname{Bd}}_{r}(K_{N})=\frac{r}{r+1}.$

If $T(u)\geq 1$ then $r/(r+T(u))\leq r/(r+1)$ and hence
$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)\leq\gamma^{\operatorname{Bd}}_{r}(K_{N})$
with equality if and only if $T(u)=1$. From now on, suppose $T(u)\leq 1$.

Consider Moran death-Birth process and define the quantities
$p_{\operatorname{dB},r}^{+}=p_{\operatorname{dB},r}^{+}(G_{N},u)$ and
$p_{\operatorname{dB},r}^{-}=p_{\operatorname{dB},r}^{-}(G_{N},u)$ as above.
Then

$p_{\operatorname{Bd},r}^{+}=\sum_{v\colon(u,v)\in
E}\frac{1}{F}\cdot\frac{r\cdot
w(u,v)}{(r-1)w(u,v)+\operatorname{deg}(v)}\quad\text{and}\quad
p_{\operatorname{Bd},r}^{-}=\frac{1}{F},$

therefore

$\gamma^{\operatorname{dB}}_{r}(G_{N},u)=\frac{\sum_{v\colon(u,v)\in
E}\frac{r\cdot
w(u,v)}{(r-1)w(u,v)+\operatorname{deg}(v)}}{1+\sum_{v\colon(u,v)\in
E}\frac{r\cdot w(u,v)}{(r-1)w(u,v)+\operatorname{deg}(v)}}.$

In particular, for the complete graph $K_{N}$ and any its node $u$ we have

$\sum_{v\colon(u,v)\in E}\frac{r\cdot
w(u,v)}{(r-1)w(u,v)+\operatorname{deg}(v)}=(N-1)\cdot\frac{r}{(r-1)+(N-1)}.$

Hence in order to prove
$\gamma^{\operatorname{dB}}_{r}(G_{N},u)\leq\gamma^{\operatorname{dB}}_{r}(K_{N})$,
it suffices to prove

$\sum_{v\colon(u,v)\in E}\frac{r\cdot
w(u,v)}{(r-1)w(u,v)+\operatorname{deg}(v)}\leq\frac{(N-1)r}{(r-1)+(N-1)}.$

We rearrange

$\sum_{v\colon(u,v)\in
E}\frac{\frac{w(u,v)}{\operatorname{deg}(v)}}{(r-1)\frac{w(u,v)}{\operatorname{deg}(v)}+1}\leq\frac{1}{\frac{r-1}{N-1}+1}.$

When $r=1$, the desired claim reduces precisely to $T(u)\leq 1$. Suppose
$r>1$, that is $r-1>0$, and consider a function
$f\colon(0,\infty)\to(0,\infty)$ defined by $f(x)=\frac{x}{(r-1)x+1}$. Then
$f$ is concave and increasing, therefore by Jensen’s inequality we have

$\sum_{v\colon(u,v)\in
E}\frac{\frac{w(u,v)}{\operatorname{deg}(v)}}{(r-1)\frac{w(u,v)}{\operatorname{deg}(v)}+1}\leq|N(u)|\cdot\frac{\frac{1}{|N(u)|}\sum_{v\colon(u,v)\in
E}\frac{w(u,v)}{\operatorname{deg}(v)}}{(r-1)\frac{1}{|N(u)|}\sum_{v\colon(u,v)\in
E}\frac{w(u,v)}{\operatorname{deg}(v)}+1}=\frac{T(u)}{\frac{r-1}{|N(u)|}\cdot
T(u)+1},$

where $|N(u)|=|\\{v\colon(u,v)\in E\\}|$ is the number of neighbors of $u$ in
$G$.

Finally, since the function $f$ is increasing, using bounds $T(u)\leq 1$ and
$|N(u)|\leq N-1$, the right-hand side is at most

$\frac{T(u)}{\frac{r-1}{|N(u)|}\cdot
T(u)+1}\leq\frac{1}{\frac{r-1}{|N(u)|}+1}\leq\frac{1}{\frac{r-1}{N-1}+1}$

as desired. For the equality to occur everywhere, we must in particular have
$T(u)=1$, in which case the other equality
$\gamma^{\operatorname{Bd}}_{r}(G_{N},u)=\gamma^{\operatorname{Bd}}_{r}(K_{N})$
holds too. ∎

##  4 Positive result

In this section, we prove the main positive result which states that there
exists an undirected, edge-weighted graph that is simultaneously an amplifier
of selection for Birth-death Moran process and for death-Birth Moran process
(under uniform mutant initialization). We first bound the number of steps
until fixation or extinction for both processes (Bd and dB) and any graph.
Second, we show that for any graph, there is a good starting vertex where a
mutant has fixation probability at least $\frac{1}{N}$. Then we construct the
graph and we prove that it is indeed an amplifier for both processes.

###  4.1 Auxiliary statements

######  Lemma 5.

For Bd and dB process for any $r$ on an undirected graph with $N$ vertices
with the ratio between edge weights at most $\frac{1}{\varepsilon}$, the
probability that the process is not completed after
$\mathcal{O}(N^{5}/\varepsilon)$ steps is in $\mathcal{O}(\frac{1}{2^{N}})$.

###### Proof.

From Lemma 4, we can take constant $c$ such that for both processes and all
graphs with $N$ vertices, the expected time is at most $cN^{4}/\varepsilon$.
From Markov’s inequality, the probability that the process takes more than
$2cN^{4}/\varepsilon$ steps is at most $\frac{1}{2}$. If the process does not
finish, the expected time is again $cN^{4}/\varepsilon$. That means we can
take $N$ epochs of size $2cN^{4}/\varepsilon$ each, and the probability that
the process does not finish in any epoch is at most $\frac{1}{2^{N}}$. ∎

######  Lemma 6.

For any graph $G_{N}$ with $N$ vertices any $r\geq 1$, and a process
$p\in\\{\text{Bd, dB}\\}$ there exists a vertex $v$ such that
$\rho^{\operatorname{p}}_{r}(G_{N},v)\geq\frac{1}{N}$.

###### Proof.

It suffices to prove the statement for $r=1$, since increasing the mutant
fitness advantage $r$ increases its fixation probability [37, Theorem 6].

In the neutral case ($r=1$), we have $\sum_{v\in V}\rho_{r=1}(G_{N},v)=1$,
thus there exists at least one vertex with fixation probability at least
$\frac{1}{N}$. ∎

Note that in some cases, no starting vertex $v$ satisfies both
$\rho^{\operatorname{Bd}}_{r}(G_{N},v)\geq 1/N$ and
$\rho^{\operatorname{dB}}_{r}(G_{N},v)\geq 1/N$ simultaneously. An example is
a Star graph $S_{3}$ on $N=3$ vertices with center $c$ and leaves $l_{1}$,
$l_{2}$ when $r=1$. Then $\rho^{\operatorname{Bd}}_{r}(S_{3},c)=1/5<1/3$ and
$\rho^{\operatorname{dB}}_{r}(S_{3},l_{1})=\rho^{\operatorname{dB}}_{r}(S_{3},l_{2})=1/4<1/3$.
In fact, later we prove that in the neutral case no starting vertex is a
strict improvement under both Bd and dB, see Theorem 4.

###  4.2 Construction

For given $N$ and $\gamma\in(0,1)$, we describe how to construct graph
$A_{N,\gamma}$. We show that for some $\gamma$, this graph is an amplifier for
both processes for $r\in(1,1.2)$. The graph $A_{N,\gamma}$ has two parts. The
first part is a graph $\mathcal{A}^{Bd}_{(1-\gamma)N}$ (from Lemma 2) on
$(1-\gamma)N$ vertices, the second part is a graph $\mathcal{A}^{dB}_{\gamma
N}$ (from Lemma 3) on $\gamma N$ vertices. Let $\varepsilon$ be the smallest
weight among edges when both graphs are independently scaled such that the
largest edge weight is $1$.

We will connect the two parts by a single edge. To that end, we select a
vertex $v$ from $\mathcal{A}^{Bd}_{(1-\gamma)N}$ such that the fixation
probability starting from $v$ in $\mathcal{A}^{Bd}_{(1-\gamma)N}$ in dB-
process is at least $\frac{1}{N}$, (such vertex exists from Lemma 6).
Similarly, we select a vertex $v^{\prime}$ from $\mathcal{A}^{dB}_{\gamma N}$
such that the fixation probability starting from $v^{\prime}$ in the graph
under Bd-process is at least $\frac{1}{N}$, (existence follows from Lemma 6).
Then, we connect $v$ and $v^{\prime}$ by an edge of weight
$w=\frac{\varepsilon^{3}}{N^{9}}$.

Finally, we scale all edges in the first part $\mathcal{A}^{Bd}_{(1-\gamma)N}$
by a factor of $\frac{\varepsilon}{N^{3}}$. That is, the heaviest edge in
$\mathcal{A}^{dB}_{\gamma N}$ has weight $1$, and the heaviest edge in
$\mathcal{A}^{Bd}_{(1-\gamma)N}$ has weight $\frac{\varepsilon}{N^{3}}$.
Observe that the scaling of edges in $\mathcal{A}^{Bd}_{(1-\gamma)N}$ does not
influence the fixation time.

Before we turn to the main proof, we show several properties of the graph we
$A_{N,\gamma}$ we have just constructed. The first property is that the two
parts $\mathcal{A}^{Bd}_{(1-\gamma)N}$ and $\mathcal{A}^{dB}_{\gamma N}$
interact so rarely that most of the time they interact, the population on
either part is already homogeneous (all mutants or all residents). Then we
show Lemma 8 and Lemma 9. The lemmas show that in both processes, the
probability of an individual reproducing over the edge between $v$ and
$v^{\prime}$ is unbalanced and in both processes, the individual in the
respective amplifier is more likely to spread the the other graph.

######  Lemma 7.

For any $N$, $\gamma$, both processes, and randomly placed mutant in
$A_{N,\gamma}$ with the probability of at least

$1-\mathcal{O}(1/N^{2})$

mutants become extinct or fixate on their part of $A_{N,\gamma}$ before any
reproduction over edge $v,v^{\prime}$.

###### Proof.

First, we bound the probability that edge $v,v^{\prime}$ is selected in both
processes and then we use the union bound.

For Bd, the edge $v,v^{\prime}$ is used either by (i) selecting the individual
at $v$ and spreading over $v,v^{\prime}$, or (ii) selecting the individual at
$v^{\prime}$ and spreading over $v^{\prime},v$. Event (i) happens with
probability at most
$\frac{r}{N+(r-1)}\cdot\frac{\varepsilon^{3}/N^{9}}{\varepsilon^{3}/N^{9}+\varepsilon^{2}/N^{3}}<\frac{r\varepsilon}{N^{7}}$.
Event (ii) happens with probability at most
$\frac{r}{N+(r-1)}\cdot\frac{\varepsilon^{3}/N^{9}}{\varepsilon^{3}/N^{9}+\varepsilon}<\frac{r\varepsilon^{2}}{N^{10}}$.
The sum of these probabilities is at most $\frac{2\varepsilon}{N^{7}}$.

For dB, the edge $v,v^{\prime}$ is used either if (i) individual at $v$ dies
and is replaced individual at $v^{\prime}$, or (ii) individual at $v^{\prime}$
dies and is replaced by individual at $v$. Event (i) happens with probability
at most
$\frac{1}{N}\cdot\frac{r\varepsilon^{3}/N^{9}}{\varepsilon^{3}/N^{9}+\varepsilon^{2}/N^{3}}<\frac{r\varepsilon}{N^{7}}$.
Event (ii) happens with probability at most
$\frac{1}{N}\cdot\frac{r\varepsilon^{3}/N^{9}}{\varepsilon^{3}/N^{9}+\varepsilon}<\frac{r\varepsilon^{2}}{N^{10}}$.
The sum of these probabilities is at most $\frac{2\varepsilon}{N^{7}}$.

From Lemma 5, we know that with high probability the process ends in
$\mathcal{O}(N^{5}/\varepsilon)$ steps. In every step the probability of using
edge $v,v^{\prime}$ is at most $\frac{2\varepsilon}{N^{7}}$, that gives
probability of using $v,v^{\prime}$ at most $\mathcal{O}(\frac{1}{N^{2}})$ at
first $N^{5}/\varepsilon$ steps from union bound. Since the probability that
the process does not end during these steps is also in
$\mathcal{O}(\frac{1}{N^{2}})$, we have that the randomly placed mutant
resolves on one part of the graph before using edge $v,v^{\prime}$ with a
probability at least $1-\mathcal{O}(\frac{1}{N^{2}})$ ∎

######  Lemma 8.

In the graph $A_{N,\gamma}$ under the Bd process, if edge $v,v^{\prime}$ is
used, then with probability at least $1-\frac{r^{2}}{N^{2}}$ occupant of $v$
spreads to $v^{\prime}$.

###### Proof.

At one step, individual at $v$ spreads to $v^{\prime}$ with probability at
least
$\frac{1}{rN}\cdot\frac{\varepsilon^{3}/N^{9}}{\varepsilon^{3}/N^{9}+(N-1)\cdot\varepsilon/N^{3}}>\frac{\varepsilon^{2}}{rN^{8}}$.
Individual at $v^{\prime}$ spreads to $v$ with probability at most
$\frac{r}{N+(r-1)}\cdot\frac{\varepsilon^{3}/N^{9}}{\varepsilon^{3}/N^{9}+\varepsilon}<\frac{r\varepsilon^{2}}{N^{10}}$.
Conditioned that the spread over $v,v^{\prime}$ happens, it is from
$v^{\prime}$ to $v$ with probability at most

$\frac{\frac{r\varepsilon^{2}}{N^{10}}}{\frac{\varepsilon^{2}}{rN^{8}}+\frac{r\varepsilon^{2}}{N^{10}}}<\frac{r^{2}}{N^{2}}\,.$

The opposite event, $v$ spreading to $v^{\prime}$ happens with probability at
least $1-\frac{r^{2}}{N^{2}}$. ∎

######  Lemma 9.

In the graph $A_{N,\gamma}$ under the dB process, if edge $v,v^{\prime}$ is
used, then with probability at least $1-\frac{r^{2}}{N^{2}}$ occupant of
$v^{\prime}$ spreads to $v$.

###### Proof.

At one step, individual at $v^{\prime}$ spreads to $v$ with probability at
least
$\frac{1}{N}\cdot\frac{\varepsilon^{3}/N^{9}}{\varepsilon^{3}/N^{9}+r(N-1)\cdot\varepsilon/N^{3}}>\frac{\varepsilon^{2}}{rN^{8}}$.
Individual at $v^{\prime}$ spreads to $v$ with probability at most
$\frac{1}{N}\cdot\frac{r\varepsilon^{3}/N^{9}}{r\varepsilon^{3}/N^{9}+\varepsilon}<\frac{r\varepsilon^{2}}{N^{10}}$.
Conditioned that the spread over $v,v^{\prime}$ happens, it is from $v$ to
$v^{\prime}$ with probability at most

$\frac{\frac{r\varepsilon^{2}}{N^{10}}}{\frac{r\varepsilon^{2}}{N^{8}}+\frac{r\varepsilon^{2}}{N^{10}}}<\frac{r^{2}}{N^{2}}\,.$

The opposite event, $v$ spreading to $v^{\prime}$ happens with probability at
least $1-\frac{r^{2}}{N^{2}}$. ∎

###  4.3 Proof of Amplification

######  Lemma 10 (Amplification under Bd).

For every $r$ and Bd updating, the fixation probability on $A_{N,\gamma}$ is
at least

$1-\gamma-\mathcal{O}(N^{-1/3})\,.$

###### Proof.

For Bd, we first bound the probability that mutants conquer
$\mathcal{A}^{Bd}_{(1-\gamma)N}$. For this to happen, it suffices if:

  1. 1.

The initial mutant appears at the correct part of the graph:
$\mathcal{A}^{Bd}_{(1-\gamma)N}$.

  2. 2.

In the next $N^{5}/\varepsilon$ steps, the process ends in
$\mathcal{A}^{Bd}_{(1-\gamma)N}$ without edge $v,v^{\prime}$ being used.

  3. 3.

Mutants conquer $\mathcal{A}^{Bd}_{(1-\gamma)N}$ within $N^{5}/\varepsilon$
steps.

The first condition is fulfilled with probability $1-\gamma$ since the
initialization is uniformly random. The process resolves on
$\mathcal{A}^{Bd}_{(1-\gamma)N}$ without edges $v,v^{\prime}$ interference
with probability $1-\mathcal{O}(\frac{1}{N^{2}})$, from Lemma 7. If the
process is finished, the mutants spread with probability at least
$1-\mathcal{O}(N^{-1/3})$, from Lemma 2.

Putting these probabilities together gives a probability at least

$\left(1-\gamma\right)\cdot\left(1-\mathcal{O}\left(N^{-2}\right)\right)\cdot\left(1-\mathcal{O}(N^{-1/3})\right)>1-\gamma-\mathcal{O}(N^{-1/3})$

that the mutants conquer $\mathcal{A}^{Bd}_{(1-\gamma)N}$.

After the graph $\mathcal{A}^{Bd}_{(1-\gamma)N}$ is occupied by mutants, we
bound from below the probability that the mutants fixate in the rest of the
graph. We wait until the edge $(v,v^{\prime})$ is used for reproduction, in
one of its two directions. For fixation on the whole graph to occur, it
suffices if:

  1. 1.

The edge $v,v^{\prime}$ was used in the right direction (from $v$ to
$v^{\prime}$).

  2. 2.

In the next $N^{5}/\varepsilon$ steps, edge $v,v^{\prime}$ is not used for
reproduction.

  3. 3.

Mutants fixate on $\mathcal{A}^{dB}_{\gamma N}$ within $N^{5}/\varepsilon$
steps.

The first condition happens with probability at least $1-\frac{r^{2}}{N^{2}}$,
from Lemma 8. The edge $v,v^{\prime}$ is not used within $N^{5}/\varepsilon$
steps with probability at least $1-\mathcal{O}(N^{-2})$, again from Lemma 7.
If both of those occur, the mutants fixate with probability at least
$\frac{1}{N}$, from Lemma 6 and since the process finishes within
$N^{5}/\varepsilon$ steps with probability at least $1-2^{-N}$, by Union Bound
the fixation probability is at least $\frac{1}{N}-2^{-N}$.

This gives the probability at least

$\left(1-\frac{r^{2}}{N^{2}}\right)\cdot\left(1-\mathcal{O}(N^{-2})\right)\cdot\left(\frac{1}{N}-2^{-N}\right)>\frac{1}{N}-\frac{1}{N^{2}}$

that if the edge $(v,v^{\prime})$ is used, the process finishes with mutant
fixation on the whole graph without edge $(v,v^{\prime})$ being used again.

In contrast, if condition 1. fails, that is, the edge $(v,v^{\prime})$ is
instead used in the wrong direction (from $v^{\prime}$ to $v$), we declare a
failure (even though some of those evolutionary trajectories might eventually
lead to mutant fixation). By Lemma 8, this happens with probability at most
$\frac{r^{2}}{N^{2}}$. Similarly, we declare a failure if condition 2. fails,
that is, when the edge $(v,v^{\prime})$ is used (in either direction) during
the $N^{5}/\varepsilon$ steps, potentially interrupting the process. Note that
when condition 3. fails, that is, the mutants do not fixate in
$\mathcal{A}^{dB}_{\gamma N}$ (but the edge $v,v^{\prime}$ is not used), we
are in the same state as before, where we can compute the fixation versus
failure probability.

The failure probability is in $\mathcal{O}(N^{-2})$, the immediate fixation
probability is at least $\frac{1}{N}-\frac{1}{N^{2}}$, otherwise, we can
retry. This gives the fixation probability at least

$\frac{\frac{1}{N}-\frac{1}{N^{2}}}{\mathcal{O}(N^{-2})+\left(\frac{1}{N}-\frac{1}{N^{2}}\right)}=1-\mathcal{O}\left(\frac{1}{N}\right).$

Overall, the fixation probability of a randomly placed mutant on
$A_{N,\gamma}$ is thus at least

$\left(1-\gamma-\mathcal{O}(N^{-1/3})\right)\cdot\left(1-\mathcal{O}\left(\frac{1}{N}\right)\right)\geq
1-\gamma-\mathcal{O}(N^{-1/3}).$

∎

######  Lemma 11 (Amplification under dB).

For every $r$ and dB updating, the fixation probability on $A_{N,\gamma}$ is
at least

$\left(\frac{1}{2}\gamma(1-r^{-3})-\mathcal{O}(N^{-1})\right)\,.$

###### Proof.

For dB, we proceed similarly as in the previous lemma. First, we again bound
the probability that mutants conquer $\mathcal{A}^{dB}_{\gamma N}$. For this
to happen, it suffices if:

  1. 1.

The initial mutant appears at the correct part of the graph:
$\mathcal{A}^{dB}_{\gamma N}$.

  2. 2.

In the next $N^{5}/\varepsilon$ steps, the process ends in
$\mathcal{A}^{dB}_{\gamma N}$ without edge $v,v^{\prime}$ being used.

  3. 3.

Mutants conquer $\mathcal{A}^{dB}_{\gamma N}$ within $N^{5}/\varepsilon$
steps.

The first condition is fulfilled with probability $\gamma$ since the
initialization is uniformly random. The process resolves on
$\mathcal{A}^{dB}_{\gamma N}$ without edges $v,v^{\prime}$ interference with
probability $1-\mathcal{O}(\frac{1}{N^{2}})$, from Lemma 7. If the process has
resolved on $\mathcal{A}^{dB}_{\gamma N}$, the mutants conquer it with
probability at least
$\frac{N}{2N+1}\cdot\frac{1-\frac{1}{r^{3}}}{1-\frac{1}{r^{3N}}}-\mathcal{O}(2^{-N})$,
from Lemma 3 and Union Bound.

Putting these probabilities together gives a probability at least

$\gamma\cdot\left(1-\mathcal{O}\left(N^{-2}\right)\right)\cdot\left(\frac{N}{2N+1}\cdot\frac{1-\frac{1}{r^{3}}}{1-\frac{1}{r^{3N}}}-\mathcal{O}(2^{-N})\right)>\frac{1}{2}\gamma(1-r^{-3})-\mathcal{O}(N^{-1})$

that the mutants conquer $\mathcal{A}^{dB}_{\gamma N}$.

After the graph $\mathcal{A}^{dB}_{\gamma N}$ is occupied by mutants, we bound
the probability that the mutants fixate in the rest of the graph. Conditioned
on the fact that the edge $v,v^{\prime}$ is used, it happens when

  1. 1.

The edge $v,v^{\prime}$ was used in the right direction (from $v^{\prime}$ to
$v$).

  2. 2.

In the next $N^{5}/\varepsilon$ steps, edge $v,v^{\prime}$ is not used.

  3. 3.

Mutants fixate on $\mathcal{A}^{Bd}_{(1-\gamma)N}$ within $N^{5}/\varepsilon$
steps.

If the edge $v,v^{\prime}$ is used in the wrong direction, we call it a fail,
this happens with probability at most $\frac{r^{2}}{N^{2}}$, from Lemma 8 (if
the edge is used).

The first condition happens with probability at least $1-\frac{r^{2}}{N^{2}}$,
from Lemma 9. The edge $v,v^{\prime}$ is not used within $N^{5}/\varepsilon$
steps with probability at least $1-\mathcal{O}(N^{-2})$, again from Lemma 7.
The mutants fixate with probability at least $\frac{1}{N}$, from Lemma 6 and
since process finishes within $N^{5}/\varepsilon$ steps with probability at
least $1-2^{-N}$, the fixation is at least $\frac{1}{N}-2^{-N}$.

This gives the probability at least

$\left(1-\frac{r^{2}}{N^{2}}\right)\cdot\left(1-\mathcal{O}(N^{-2})\right)\cdot\left(\frac{1}{N}-2^{-N}\right)>\frac{1}{N}-\frac{1}{N^{2}}$

that if the edge $v,v^{\prime}$ is used, the process finishes without edge
$v,v^{\prime}$ being used again.

However, when the mutants do not fixate in $\mathcal{A}^{dB}_{\gamma N}$ (but
the edge $v,v^{\prime}$ is not used), we are in the same state as before,
where we can compute the fixation versus fail probability.

The fail probability is in $\mathcal{O}(N^{-2})$, the immediate fixation
probability is at least $\frac{1}{N}-\frac{1}{N^{2}}$, otherwise, we can
retry. This gives total fixation $1-\mathcal{O}(\frac{1}{N})$.

Overall, the fixation probability of a randomly placed mutant on $A_{N,r}$ is
at least

$\left(\frac{1}{2}\gamma(1-r^{-3})-\mathcal{O}(N^{-1})\right)\cdot\left(1-\mathcal{O}(\frac{1}{N})\right)\geq\left(\frac{1}{2}\gamma(1-r^{-3})-\mathcal{O}(N^{-1})\right)\,.$

∎

The following theorem shows that for a particular $\gamma$, our construction
is an amplifier for both processes for $r\in(1,1.2)$.

######  Theorem 6 (Simultaneous Bd- and dB-amplifier).

For every large enough population size $N$, graph $A_{N,\gamma}$ for graph
$A_{N,\gamma}$, where $\gamma=\frac{2\cdot 1.2^{3}}{3\cdot
1.2^{3}-1}=0.826004$ we have

$\rho^{\operatorname{Bd}}_{r}(A_{N,\gamma})>\rho^{\operatorname{Bd}}_{r}(K_{N})\quad\text{and}\quad\rho^{\operatorname{dB}}_{r}(A_{N,\gamma})>\rho^{\operatorname{dB}}_{r}(K_{N})$

for every $r\in(1,1.2)$.

###### Proof.

We know that $\rho^{\operatorname{Bd}}_{r}(K_{N})=\frac{1-r^{-1}}{1-r^{-N}}$
and
$\rho^{\operatorname{dB}}_{r}(K_{N})=\frac{N-1}{N}\frac{1-r^{-1}}{1-r^{-N+1}}$.
Setting $N$ so big that $\frac{1}{1-r^{-N+1}}<1.00001$, we have that
$\rho^{\operatorname{Bd}}_{r}(K_{N})<(1-r^{-1})\cdot 1.00001<0.16667$ and
$\rho^{\operatorname{dB}}_{r}(K_{N})<(1-r^{-1})\cdot 1.00001$.

From Lemma 10, plugging $\gamma$, we have that the fixation probability is at
least $1-0.826004-\mathcal{O}(N^{-1/3})=0.173996-\mathcal{O}(N^{-1/3})$ for
the Birth-death process which is bigger than the maximal fixation probability
for $K_{N}$ ($0.16667$).

From Lemma 11, plugging $\gamma$, we have that the fixation probability is at
least $\left(\frac{1}{2}0.826004(1-r^{-3})-\mathcal{O}(N^{-1})\right)$ for the
death-Birth process. We have

$\displaystyle(1-r^{-1})\cdot 1.00001$
$\displaystyle<\left(\frac{1}{2}0.826004(1-r^{-3})-\mathcal{O}(N^{-1})\right)$
$\displaystyle 1.00001$
$\displaystyle<\left(\frac{1}{2}0.826004(1+r^{-1}+r^{-2})\right)-\mathcal{O}(N^{-1})$
$\displaystyle 1.00001$ $\displaystyle<\left(\frac{1}{2}0.826004\cdot
2.52778\right)-\mathcal{O}(N^{-1})$ $\displaystyle 1.00001$
$\displaystyle<1.04-\mathcal{O}(N^{-1})\,,$

which proves the theorem. ∎

The following theorem shows how to choose $\gamma$ to achieve the best
amplification so that the fixation probability of the amplifier is at least
$1.04$ times better than the complete graph for both processes.

######  Theorem 7 (Optimal Bd- and dB-amplifier).

For any $r\in(1,1.2)$, and every large enough population size $N$, graph
$A_{N,\gamma}$ for graph $A_{N,\gamma}$, where
$\gamma=\frac{2r^{3}}{3r^{3}-1}$ we have

$\rho^{\operatorname{Bd}}_{r}(A_{N,\gamma})>X\cdot\rho^{\operatorname{Bd}}_{r}(K_{N})\quad\text{and}\quad\rho^{\operatorname{dB}}_{r}(A_{N,\gamma})>X\cdot\rho^{\operatorname{dB}}_{r}(K_{N}).$

for $X=1.04$.

###### Proof.

Again, $\rho^{\operatorname{Bd}}_{r}(K_{N})=\frac{1-r^{-1}}{1-r^{-N}}$ and
$\rho^{\operatorname{dB}}_{r}(K_{N})=\frac{N-1}{N}\frac{1-r^{-1}}{1-r^{-N+1}}$.
Setting $N$ so big that $\frac{1}{1-r^{-N+1}}<1.00001$, we have that
$\rho^{\operatorname{Bd}}_{r}(K_{N})<(1-r^{-1})\cdot 1.00001$ and
$\rho^{\operatorname{dB}}_{r}(K_{N})<(1-r^{-1})\cdot 1.00001$.

From Lemma 10, plugging $\gamma$, we have that the fixation probability is at
least $\frac{r^{3}-1}{3r^{3}-1}-\mathcal{O}(N^{-1/3})$ for the Birth-death
process. We have

$\displaystyle(1-r^{-1})\cdot 1.00001\cdot X$
$\displaystyle<\frac{r^{3}-1}{3r^{3}-1}-\mathcal{O}(N^{-1/3})$ $\displaystyle
1.00001\cdot X$
$\displaystyle<\frac{r(1+r+r^{2})}{3r^{3}-1}-\mathcal{O}(N^{-1/3})$
$\displaystyle 1.00001\cdot X$
$\displaystyle<1.04398-\mathcal{O}(N^{-1/3})\,.$

From Lemma 11, plugging $\gamma$, we have that the fixation probability is at
least
$\left(\frac{1}{2}\frac{2r^{3}}{3r^{3}-1}(1-r^{-3})-\mathcal{O}(N^{-1})\right)$
for the death-Birth process. We have

$\displaystyle(1-r^{-1})\cdot 1.00001X$
$\displaystyle<\left(\frac{1}{2}\frac{2r^{3}}{3r^{3}-1}(1-r^{-3})-\mathcal{O}(N^{-1})\right)$
$\displaystyle 1.00001X$
$\displaystyle<\left(\frac{1}{2}\frac{2r^{3}}{3r^{3}-1}(1+r^{-1}+r^{-2})-\mathcal{O}(N^{-1})\right)$
$\displaystyle 1.00001X$
$\displaystyle<\left(\frac{r(1+r+r^{2})}{3r^{3}-1}-\mathcal{O}(N^{-1})\right)$
$\displaystyle 1.00001\cdot X$ $\displaystyle<1.04398-\mathcal{O}(N^{-1})\,.$

∎


# Comparing Formulaic Language in Human and Machine Translation: Insight from
a Parliamentary Corpus

###### Abstract

A recent study has shown that, compared to human translations, neural machine
translations contain more strongly-associated formulaic sequences made of
relatively high-frequency words, but far less strongly-associated formulaic
sequences made of relatively rare words. These results were obtained on the
basis of translations of quality newspaper articles in which human
translations can be thought to be not very literal. The present study attempts
to replicate this research using a parliamentary corpus. The text were
translated from French to English by three well-known neural machine
translation systems: DeepL, Google Translate and Microsoft Translator. The
results confirm the observations on the news corpus, but the differences are
less strong. They suggest that the use of text genres that usually result in
more literal translations, such as parliamentary corpora, might be preferable
when comparing human and machine translations. Regarding the differences
between the three neural machine systems, it appears that Google translations
contain fewer highly collocational bigrams, identified by the CollGram
technique, than Deepl and Microsoft translations.

Keywords: neural machine translation, human translation, parliamentary corpus,
multiword unit

languageresourceLanguage Resources

Comparing Formulaic Language in Human and Machine Translation: Insight from a
Parliamentary Corpus

Yves Bestgen
---
Laboratoire d’analyse statistique des textes
Université catholique de Louvain
Place Cardinal Mercier, 10 1348 Louvain-la-Neuve, Belgium
<EMAIL_ADDRESS>

Abstract content

## 1\. Introduction

Due to the success of neural machine translation systems, more and more
research is being conducted to compare their translations to human
translations. Most of these studies take a global view of quality [Popel et
al., 2020, Läubli et al., 2018, Wu et al., 2016], but others focus on much
more specific dimensions that could be further improved, such as lexical
diversity and textual cohesion [De Clercq et al., 2021, Vanmassenhove et al.,
2019].

In a recent study, ?) analyzed the frequency of use of a specific category of
formulaic sequences, the ”habitually occurring lexical combinations” [Laufer
and Waldman, 2011], which are statistically typical of the language because
they are observed ”with markedly high frequency, relative to the component
words” [Baldwin and Kim, 2010]. To identify them, he used the CollGram
technique which relies on two lexical association indices: mutual information
(MI) and t-score, calculated on the basis of the frequencies in a reference
corpus [Bernardini, 2007, Bestgen and Granger, 2014, Durrant and Schmitt,
2009]. A discussion of two automatic procedures that at least partially
implement this technique is given in ?). He showed that neural machine
translations contain more strongly-associated formulaic sequences made of
relatively high-frequency words, identified by the t-score, such as you know,
out of or more than, but far less strongly-associated formulaic sequences made
of relatively rare words, identified by the MI, such as self-fulfilling
prophecy, sparsely populated or sunnier climes.

These observations can be linked with a series of studies that have shown
similar differences in foreign language learning [Bestgen and Granger, 2014,
Durrant and Schmitt, 2009] and which have proposed to interpret them in the
framework of the usage-based model of language learning which ”hold that a
major determining force in the acquisition of formulas is the frequency of
occurrence and co-occurrence of linguistic forms in the input” [Durrant and
Schmitt, 2009]. It is obviously tempting to use the same explanation for
differences in translation, as neural models also seem to be affected by
frequency of use [Koehn and Knowles, 2017, Li et al., 2020].

A competing explanation is however possible. All the texts analyzed in ?) were
quality newspaper articles written in French and published in Le Monde
diplomatique, and then translated in English for one of its international
editions. However, as ?) pointed out following ?), “Translation of news
implies a higher degree of re-writing and re-telling than in any other type of
translation” (p.40) and “International news, however, tends to prefer
domestication of information instead of translation accuracy, which also has
its particular reasons” (p.35). As it is important in this kind of texts that
the translated version is as relevant and interesting as possible for the
target readers, often from another culture, lexical and syntactic
modifications, deletions and additions are frequent. All these modifications
make the translation of this kind of texts less literal than the one expected
from a machine translation system and thus risk to affect the differences in
the use of formulaic sequences.

Figure 1: Human and machine translation of a French excerpt from each of the
two corpora.

In this context, parliamentary corpora are a perfectly justified point of
comparison. Translation accuracy is the main objective. For example, the
criteria that European parliamentary debates translations must meet include:
“the delivered target text is complete (no omissions nor additions are
permitted)” and “the target text is a faithful, accurate and consistent
translation of the source text” [Sosoni, 2011].

Figure 1 illustrates this difference in translation between these two types of
texts. It shows a brief extract from each corpus in its original and
translated versions. The excerpt from the news corpus shows the different
translation strategies used by the human and the machine, with the human
version showing several reformulations affecting both the lexicon and the
syntax and the deletion of one constituent in the last sentence. Such
differences are not present in the extract from the parliamentary corpus.

The objective of the present study is to determine whether machine
translations of parliamentary texts differ from human translations in the use
of phraseology, in order to confirm or refute the findings from the news
corpus. The three following hypotheses are tested: compared to human
translations, machine translations will contain more strongly-associated
collocations made of high-frequency words, less strongly-associated formulaic
sequences made of rare words and thus a larger ratio between these two
indices. An positive conclusion, in addition to confirming the links between
machine translation and foreign language learning, will suggest a way to make
machine translations more similar to human translations, especially since the
fully automatic nature of the analysis facilitates its large-scale use.

## 2\. Method

### 2.1. Parliamentary Corpus

The material for this study is taken from the Europarl corpus v7 [Koehn, 2005]
available at https://www.statmt.org/europarl. In order to have parallel texts
of which the original is in French and the translation in English, information
rarely directly provided in the Europarl corpus because it was not developed
for this purpose [Cartoni and Meyer, 2012, Islam and Mehler, 2012], I employed
the preprocessed version, freely available at
https://zenodo.org/record/1066474#.WnnEM3wiHcs, obtained by means of the
EuroparlExtract toolkit [Ustaszewski, 2019].

Two hundred texts of 3,500 to 4,500 characters, for a total of 120,000 words,
were randomly selected among all texts written in French and translated into
English. These thresholds were set in order to have texts long enough for
collocation analysis, but not exceeding the 5,000-character limit imposed by
the automatic translators used so that the document could be translated in a
single operation.

Between February 14 and 16, 2022, three neural machine translation systems
were used to translate these texts into English: the online version of DeepL
(https://deepl.com/translator) and Google Translate
(https://translate.google.com) and the Office 365 version of Microsoft
Translator.

### 2.2. Procedure

All contiguous word pairs (bigrams) were extracted from the CLAWS7 tokenized
version [Rayson, 1991] of each translated text. Bigrams, not including a
proper noun, that could be found in the British National Corpus (BNC,
https://www.natcorp.ox.ac.uk), were assigned an MI and a t-score on the basis
of the frequencies in this reference corpus. Bigrams with $MI\geq 5$ or with
$t\geq 6$ were deemed to be highly collocational [Bestgen, 2018, Durrant and
Schmitt, 2009]. On this basis, three GollGram indices were calculated for each
translated text: the percentage of highly collocational bigrams for MI, the
same percentage for the t-score and the ratio between these two percentages
(%t-score $/$ %MI).

This procedure is in all points identical to the one used in the analysis of
the news corpus [Bestgen, 2021]. The only difference is that the machine
translations of the news corpus were undertaken in March-April 2021. According
to ?) terminology, the present study is thus an approximate replication that
“might help us generalize, for example, the findings from the original study
to a new population, setting, or modality” (p.11).

Figure 2: Mean percentages of highly collocational bigrams for MI. Figure 3: Mean percentages of highly collocational bigrams for t-score. Figure 4: Mean ratio between t-score and MI. MI | Micro. | DeepL | Google
---|---|---|---
| MI |
Human Di | -0.50 | -0.59 | -1.24
d | 0.38 | 0.44 | 0.89
p | 0.67 | 0.69 | 0.81
Micro. Di |  | -0.09 | -0.74
d |  | 0.11 | 0.67
p |  | 0.55 | 0.76
DeepL Di |  |  | -0.65
d |  |  | 0.61
p |  |  | 0.71
| t-score |
Human Di | 0.51 | 0.76 | -0.69
d | 0.15 | 0.31 | 0.26
p | 0.60 | 0.60 | 0.63
Micro. Di |  | 0.25 | -1.20
s |  | 0.09 | 0.45
p |  | 0.55 | 0.80
DeepL Di |  |  | -1.44
d |  |  | 0.72
p |  |  | 0.76
| Ratio |
Human Di | 0.42 | 0.52 | 0.84
d | 0.39 | 0.50 | 0.77
p | 0.69 | 0.70 | 0.81
Micro. Di |  | 0.10 | 0.42
d |  | 0.14 | 0.47
p |  | 0.56 | 0.71
DeepL Di |  |  | 0.31
d |  |  | 0.37
p |  |  | 0.66
Table 1: Differences (column translator minus row translator) and effect sizes
for the two indices and the ratio in the four translation types. Di =
Difference, d = Cohen’s d, p = proportion of texts in which the mean effect is
observed.

## 3\. Results

### 3.1. Parliamentary Corpus

The mean percentages of highly collocational bigrams for the MI and t-score
and the mean ratio for the four translation type of the two genres of text are
shown in Figures 2 to 4. The differences observed on the parliamentary corpus
are very similar to those obtained with the news corpus. This section is
focused on the analysis of the Parliamentary corpus while the comparison with
the news corpus is presented in the next section.

Table 1 presents the differences between the mean scores for every pairs of
translators for the parliamentary corpus. The Student’s t-test for non-
independent measures was used to determine whether these mean differences were
statistically significant. Due to the large number of tests performed (18),
the Bonferroni procedure was used to compensate for the inflated Type I error
rates, with the threshold for an alpha of 0.05 (two-tailed) set at 0.0027
(two-tailed). These tests indicate that all differences are significant,
except for those between Microsoft Translator and DeepL for the three indices
and the difference for the t-score between the human and Microsoft
translations.

Table 1 also gives two effect sizes. Cohen’s $d$ informs about the size of the
difference between the means as a function of its variability. It is usual to
consider that a $d$ of 0.20 indicates a small effect size, a $d$ of 0.50 a
medium effect and a $d$ of 0.80 a large effect [Cohen, 1988]. The second
effect size is the proportion of texts for which the difference between the
two translations has the same sign as the mean difference. The maximum value
of 1.0 means that texts produced by a translator always have larger scores
than those translated by the other translator while the minimum value of 0.50
indicates no difference for this measure between the two translators.

As these results show, the three hypotheses about the differences between
human and machine translations are all confirmed by statistically significant
differences, except for the difference in t-score between human and Microsoft
translations, which is nevertheless in the right direction.

In these analyses, Cohen’s $d$ for MI and for the ratio are often medium and
sometimes even large and the differences are present in a large proportion of
texts. For the t-score on the other hand, all effect sizes are small. This
could be explained by the fact that the collocations highlighted by this
lexical association measure are mostly very frequent in the language and thus
more easily learned by automatic systems [Koehn and Knowles, 2017, Li et al.,
2020].

The comparison of the texts translated by Microsoft Translator and by DeepL
does not show, as indicated above, any statistically significant difference
and the effect sizes are very small. The outputs of Google Translate on the
other hand contain fewer highly collocational bigrams for MI and for t-score
than these two other machine translators, potentially suggesting less
efficiency of this translator for collocation processing.

### 3.2. Comparison between the Two Genres

As shown in Figures 2 to 4, all the observed trends are very similar in the
two corpora, indicating that the two genres of text lead to the same
conclusions. However, there is a strong contrast in the mean values. The MI
scores are lower in the parliamentary corpus while the t-scores are higher.
This is the case for both human and machine translations. This observation is
most probably explained by a difference between the text genres, a difference
that should already be present in the original French texts.

The comparison of the effect sizes between the two types of translation (Table
2 in ?)) clearly indicates that the differences are much stronger in the news
corpus. This observation is consistent with the hypothesis of a greater
literalness of the human translations in the parliamentary corpus.

## 4\. Conclusion

The analyses carried out on the parliamentary corpus have made it possible to
replicate the conclusions obtained with a news corpus. The observed trends are
very similar, but the differences are less strong in the parliamentary corpus.
This observation seems to confirm the usefulness of the parliamentary genre
for the comparison of human and machine translation. Indeed, one can think
that the less literal nature of the translations in news [Ponomarenko, 2019,
Sosoni, 2011] favors the identification of differences between the two types
of translations. The differences observed in the parliamentary corpus thus
seem to be more directly related to the translators effectiveness rather than
to other factors.

Among the directions for future research, there is certainly the analysis of
translations from English to French, but also between other languages. Here
again, the Europarl corpus, as well as parliamentary debates in multilingual
countries, allows for a great deal of experimentation. A potential difficulty
is that the approach used requires a reference corpus in the target language.
This problem does not seem too serious since it has been shown that freely
available Wacky corpora [Baroni et al., 2009] can be used without altering the
results of the CollGram technique [Bestgen, 2016]. Confirming these results in
other languages, but also in other genres of texts, would allow to take
advantage of them to try to improve machine translation systems.

A unanswered question is whether identical results would be obtained on the
basis of a genre-specific reference corpus, which is very easy to obtain for
European parliamentary debates. This corpus would be composed of documents
originally produced in English. It would also be interesting to use other
approaches to phraseology, especially more qualitative ones, to confirm the
conclusions. Finally, the difference in mean values between the two text
genres justifies an analysis of the original texts with the same technique.

## 5\. Acknowledgements

The author is a Research Associate of the Fonds de la Recherche Scientifique
(F.R.S-FNRS).

## 6\. Bibliographical References

## References

  * Baldwin and Kim, 2010 Baldwin, T. and Kim, S. N.  (2010).  Multiword expressions.  In Nitin Indurkhya et al., editors, Handbook of Natural Language Processing, pages 267–292. CRC Press.
  * Baroni et al., 2009 Baroni, M., Bernardini, S., Ferraresi, A., and Zanchetta, E.  (2009).  The WaCky wide web: A collection of very large linguistically processed web-crawled corpora.  Language Resources and Evaluation, 43:209–226.
  * Bernardini, 2007 Bernardini, S.  (2007).  Collocations in translated language. combining parallel, comparable and reference corpora.  In Proceedings of the Corpus Linguistics Conference, pages 1–16. Lancaster University.
  * Bestgen and Granger, 2014 Bestgen, Y. and Granger, S.  (2014).  Quantifying the development of phraseological competence in L2 English writing: An automated approach.  Journal of Second Language Writing, 26:28–41.
  * Bestgen, 2016 Bestgen, Y.  (2016).  Evaluation automatique de textes. Validation interne et externe d’indices phraséologiques pour l’évaluation automatique de textes rédigés en anglais langue étrangère.  Traitement automatique des langues, 57(3):91–115.
  * Bestgen, 2018 Bestgen, Y.  (2018).  Normalisation en traduction : analyse automatique des collocations dans des corpus.  Des mots aux actes, 7:459–469.
  * Bestgen, 2019 Bestgen, Y.  (2019).  Evaluation de textes en anglais langue ètrangère et séries phraséologiques : comparaison de deux procédures automatiques librement accessibles.  Revue française de linguistique appliquée, 24:81–94.
  * Bestgen, 2021 Bestgen, Y.  (2021).  Using CollGram to compare formulaic language in human and machine translation.  In Proceedings of the Translation and Interpreting Technology Online Conference, pages 174–180, Held Online, July. INCOMA Ltd.
  * Bielsa and Bassnett, 2009 Bielsa, E. and Bassnett, S.  (2009).  Translation in Global News.  Routledge.
  * Cartoni and Meyer, 2012 Cartoni, B. and Meyer, T.  (2012).  Extracting directional and comparable corpora from a multilingual corpus for translation studies.  In Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC’12), pages 2132–2137, Istanbul, Turkey, May. European Language Resources Association (ELRA).
  * Cohen, 1988 Cohen, J.  (1988).  Statistical power analysis for the behavioral sciences.  Erlbaum.
  * De Clercq et al., 2021 De Clercq, O., De Sutter, G., Loock, R., Cappelle, B., and Plevoets, K.  (2021).  Uncovering Machine Translationese Using Corpus Analysis Techniques to Distinguish between Original and Machine-Translated French.  Translation Quarterly, 101:21–45.
  * Durrant and Schmitt, 2009 Durrant, P. and Schmitt, N.  (2009).  To what extent do native and non-native writers make use of collocations?  International Review of Applied Linguistics in Language Teaching, 47:157–177.
  * Islam and Mehler, 2012 Islam, Z. and Mehler, A.  (2012).  Customization of the Europarl corpus for translation studies.  In Nicoletta Calzolari, et al., editors, Proceedings of the Eighth International Conference on Language Resources and Evaluation, LREC 2012, Istanbul, Turkey, May 23-25, 2012, pages 2505–2510. European Language Resources Association (ELRA).
  * Koehn and Knowles, 2017 Koehn, P. and Knowles, R.  (2017).  Six challenges for neural machine translation.
  * Koehn, 2005 Koehn, P.  (2005).  Europarl: A Parallel Corpus for Statistical Machine Translation.  In Conference Proceedings: the tenth Machine Translation Summit, pages 79–86, Phuket, Thailand. AAMT, AAMT.
  * Läubli et al., 2018 Läubli, S., Sennrich, R., and Volk, M.  (2018).  Has machine translation achieved human parity? a case for document-level evaluation.  In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4791–4796, Brussels, Belgium, October-November. Association for Computational Linguistics.
  * Laufer and Waldman, 2011 Laufer, B. and Waldman, T.  (2011).  Verb-noun collocations in second language writing: A corpus analysis of learners’ English.  Language Learning, 61:647–672.
  * Li et al., 2020 Li, M., Roller, S., Kulikov, I., Welleck, S., Boureau, Y.-L., Cho, K., and Weston, J.  (2020).  Don’t say that! making inconsistent dialogue unlikely with unlikelihood training.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4715–4728. Association for Computational Linguistics.
  * Ponomarenko, 2019 Ponomarenko, L.  (2019).  Translating identities in multilingual news.  Ph.D. thesis, Universitat Autonoma de Barcelona.
  * Popel et al., 2020 Popel, M., Tomkova, M., Tomek, J., Kaiser, L., Uszkoreit, J., Bojar, O., and Zabokrtsky, Z.  (2020).  Transforming machine translation: A deep learning system reaches news translation quality comparable to human professionals.  Nature Communications, 11:1–15.
  * Porte, 2013 Porte, G.  (2013).  Who needs replication?  CALICO Journal, 30:10–15.
  * Rayson, 1991 Rayson, P.  (1991).  Matrix: A statistical method and software tool for linguistic analysis through corpus comparison. Ph.D. thesis, Lancaster University.
  * Sosoni, 2011 Sosoni, V.  (2011).  Training translators to work for the EU institutions: luxury or necessity?  The Journal of Specialised Translation, 16:77–108.
  * Ustaszewski, 2019 Ustaszewski, M.  (2019).  Optimising the Europarl corpus for translation studies with the Europarl Extract toolkit.  Perspectives, 27:107–123.
  * Vanmassenhove et al., 2019 Vanmassenhove, E., Shterionov, D., and Way, A.  (2019).  Lost in translation: Loss and decay of linguistic richness in machine translation.  In Proceedings of Machine Translation Summit XVII: Research Track, pages 222–232, Dublin, Ireland, August. European Association for Machine Translation.
  * Wu et al., 2016 Wu, Y., Schuster, M., Chen, Z., Le, Q. V., Norouzi, M., Macherey, W., Krikun, M., Cao, Y., Gao, Q., Macherey, K., Klingner, J., Shah, A., Johnson, M., Liu, X., Łukasz Kaiser, Gouws, S., Kato, Y., Kudo, T., Kazawa, H., Stevens, K., Kurian, G., Patil, N., Wang, W., Young, C., Smith, J., Riesa, J., Rudnick, A., Vinyals, O., Corrado, G., Hughes, M., and Dean, J.  (2016).  Google’s neural machine translation system: Bridging the gap between human and machine translation.