The Moran Process and the Isothermal Theorem

We formalize the Birth–death Moran process on a finite graph and the “if” direction of the isothermal theorem of Lieberman, Hauert and Nowak (2005): on a connected regular graph, a mutant population of size \(k\) with fitness \(r\neq 1\) takes over the whole population with probability \((1-r^{-k})/(1-r^{-n})\), and with probability \(k/n\) when \(r=1\). The complete graph gives Moran’s formula (Moran, The survival of a mutant gene under selection, J. Austral. Math. Soc. 1, 1959). As in the voter project, eventual probabilities are suprema of increasing finite-time probabilities; no path-space measure is used.

1 The model

This section and the three following ones formalize the “if” direction of the isothermal theorem of Lieberman, Hauert and Nowak, Evolutionary dynamics on graphs (Nature 2005), with Moran’s formula (1959) on the complete graph; the main theorem is in the section on fixation probabilities.

Definition 1 Birth–death Moran kernel
✓

Mutants have fitness \(r{\gt}0\) and residents fitness \(1\). A step chooses a parent \(u\) with probability proportional to its fitness and an offspring position \(w\) uniformly among the neighbours of \(u\) (or \(w=u\) if \(u\) is isolated); the individual at \(w\) is replaced by a copy of the parent.

The weights of (parent, offspring position) pairs are nonnegative and sum to one.

Proof ▶

Sum over the offspring position first: each parent’s placement weights sum to one. The remaining sum of fitnesses over the total fitness is one.

2 Invariance on regular graphs

Lemma 3 Birth mass is \(r\) times death mass
✓

On a \(d\)-regular graph, the probability that a step adds a mutant equals \(r\) times the probability that it removes one: both are proportional to the number of edges between the two types, counted from either side.

Proof ▶

For \(d{\gt}0\) both masses are the oriented cut divided by \(Fd\), weighted by the parent’s fitness; the cut is symmetric under swapping endpoints. For \(d=0\) both masses vanish.

Theorem 4 Invariant potentials
✓

On a regular graph, \((1/r)^{\# \text{mutants}}\) is preserved in expectation by one step; when \(r=1\), so is the number of mutants.

Proof ▶

A step changes the number of mutants by \(\pm 1\) or not at all, so its expectation is affine in the birth and death masses, and these cancel by the previous lemma.

3 Absorption on connected graphs

Theorem 5 Fixation or extinction
✓

On a connected graph, the probability that neither type has taken over tends to zero.

Proof ▶

Constant configurations are absorbing. From a mixed configuration, a mutant adjacent to a resident (which exists by connectivity) reproduces onto it with positive probability; by induction on the number of residents, fixation is reachable. Apply the shared finite-chain absorption theorem.

4 Fixation probabilities

Let an observable be invariant in expectation, equal to \(1\) on the all-mutant and to \(0\) on the all-resident configuration. If the all-mutant configuration is absorbing and the probability that neither type has taken over tends to zero, the observable is the fixation probability.

Proof ▶

This is the finite-horizon optional stopping theorem of the shared dynamics package (Dynamics.Kernel.iSup_event_of_invariant, roadmap FND-4) with the two constant configurations as targets: the fixation and unfixed indicators are the corresponding events.

On a connected regular graph with \(r\neq 1\), the fixation probability from \(k\) mutants is \((1-r^{-k})/(1-r^{-n})\).

Proof ▶

Apply the previous lemma to \(\psi =(1-(1/r)^{\# \text{mutants}})/(1-(1/r)^n)\), invariant by the invariance theorem and equal to \(1\) and \(0\) on the two constant configurations; the absorption theorem gives the vanishing survival probability.

On a connected regular graph with \(r=1\), the fixation probability is \(k/n\).

Proof ▶

The same argument with \(\psi =\# \text{mutants}/n\).

Theorem 9 Moran’s formula
✓
#

On the complete graph, the fixation probability from \(k\) mutants is \((1-r^{-k})/(1-r^{-n})\).

Proof ▶

The complete graph is connected and \((n-1)\)-regular.

The converse of the isothermal theorem does not hold in general (Galanis, Göbel, Goldberg, Lapinskas and Richerby, Proposition 12), so only this direction is formalized.

5 Push versus pull on arbitrary graphs

On the complete graph the neutral push and pull voter processes coincide; on an irregular graph they fix a mutant set with different probabilities, weighted by \(1/\deg \) and by \(\deg \) respectively. In population genetics this is the difference between Birth–death and death–Birth updating. Antal, Redner and Sood, Evolutionary dynamics on degree-heterogeneous graphs (Phys. Rev. Lett. 96, 2006), obtain these weights from quantities conserved by the neutral dynamics (their results with selection use a mean-field approximation); here they are proved formally, on every connected graph.

Definition 10 Death–Birth kernel
✓

In one pull (death–Birth) step, a uniformly random vertex \(u\) adopts the type of a uniformly random neighbour \(w\) (an isolated vertex keeps its type), so the pair \((u,w)\) has weight \(\frac1n\cdot \frac1{\deg u}\) for \(w\sim u\). The neutral push (Birth–death) process is the Moran kernel with \(r=1\).

Definition 11 Reproductive values
✓
#

For a configuration with mutant set \(S\), \(\Phi _{\mathrm{push}}(S)=\sum _{v\in S}1/\deg v\) and \(\Phi _{\mathrm{pull}}(S)=\sum _{v\in S}\deg v\).

On every finite graph, \(\Phi _{\mathrm{push}}\) is invariant in expectation under neutral push and \(\Phi _{\mathrm{pull}}\) is invariant in expectation under pull.

Proof ▶

Write \(x_v\in \{ 0,1\} \) for the type of \(v\). Under push, the pair (parent \(u\), target \(w\sim u\)) has weight \(\frac1n\frac1{\deg u}\) and changes \(\Phi _{\mathrm{push}}\) by \((x_u-x_w)/\deg w\), so the expected change is \(\frac1n\sum _{u\sim w}(x_u-x_w)/(\deg u\deg w)\). Under pull, \(u\) copies \(w\sim u\) with weight \(\frac1n\frac1{\deg u}\) and changes \(\Phi _{\mathrm{pull}}\) by \((x_w-x_u)\deg u\), so the expected change is \(\frac1n\sum _{u\sim w}(x_w-x_u)\). Both sums are over ordered adjacent pairs of an antisymmetric function, hence vanish.

On a connected graph, the probability that the pull process has not reached a constant configuration after \(t\) steps tends to \(0\).

Proof ▶

As for push: constant configurations are absorbing, and from any other configuration a resident adjacent to a mutant copies it with positive probability, so the number of mutants reaches \(n\) with positive probability; the shared absorption theorem concludes.

On a connected graph with at least two vertices, the fixation probability of a mutant set \(S\) is \(\sum _{v\in S}\frac1{\deg v}\big/\sum _{v\in V}\frac1{\deg v}\) under neutral push and \(\sum _{v\in S}\deg v/(2|E|)\) under pull.

Proof ▶

Apply the fixation-limit lemma to the normalized reproductive values, which are invariant and equal to \(1\) and \(0\) on the two constant configurations; the denominators are positive because every degree is at least \(1\).

6 Moran chains on counts

Population genetics follows the number \(k\) of mutants. In Moran’s model (1958) the reproducing and the dying individual are drawn independently and uniformly, possibly the same one; on the complete graph \(K_n\) the death–Birth kernel draws two distinct vertices, since a simple graph has no self-loops. A lumping (the same chain on counts) and the same jump chain are defined in the shared library (Dynamics.Kernel.Lumps, Dynamics.Kernel.SameJumpChain).

A symmetric birth–death chain on \(\{ 0,\dots ,n\} \) moves from \(k\) to \(k-1\) and to \(k+1\) with probability \(q(k)\) each. Moran’s chain has \(q(k)=k(n-k)/n^2\), the chain without self-loops \(q(k)=k(n-k)/(n(n-1))\), and the absorbed walk \(q(k)=1/2\) for \(0{\lt}k{\lt}n\) and \(q(0)=q(n)=0\).

Theorem 16 Death–Birth on \(K_n\) is a Moran chain on counts
✓

Under the death–Birth kernel on the complete graph, the number of mutants is the chain without self-loops: from every configuration with \(k\) mutants, one step leads to \(k+1\) and to \(k-1\) mutants with probability \(k(n-k)/(n(n-1))\) each.

Proof ▶

The updating vertex \(u\) and the copied vertex \(w\) form a uniformly random ordered pair of distinct vertices. The number of mutants increases iff \(u\) is a resident and \(w\) a mutant, \((n-k)k\) of the \(n(n-1)\) pairs, decreases iff \(u\) is a mutant and \(w\) a resident, and stays otherwise.

Moran’s chain and the chain without self-loops have the same jump chain: the walk that moves up or down by one with probability \(1/2\) each until it is absorbed at \(0\) or \(n\).

Proof ▶

Off the diagonal, the rows of Moran’s chain are \((n-1)/n\) times those of the chain without self-loops, and from \(0{\lt}k{\lt}n\) the latter moves to \(k-1\) and \(k+1\) with equal probabilities.

For \(n\ge 2\), both chains fix from \(k\) mutants with probability \(k/n\).

Proof ▶

On the complete graph pull fixation is \((n-1)k/((n-1)n)\); it transfers to the chain without self-loops through the lumping, applied to a configuration with \(k\) mutants. Kernels with the same jump chain have the same absorption probabilities (shared library), which gives Moran’s chain.

7 Moran’s chain with selection on counts

With mutants of fitness \(r{\gt}0\) and residents of fitness \(1\), Moran’s model with selection by fecundity (1959) draws the reproducing individual with probability proportional to its fitness and the dying individual uniformly from the whole population, possibly the same one. On the complete graph the Birth–death kernel draws the parent in the same way, but its offspring replaces a uniformly random neighbour, that is another vertex.

A birth–death chain on \(\{ 0,\dots ,n\} \) moves from \(k\) to \(k-1\) with probability \(d(k)\) and to \(k+1\) with probability \(u(k)\); the symmetric chains are the case \(d=u\). With \(F_k=rk+n-k\) the total fitness, the chain without self-loops has \(u(k)=rk(n-k)/(F_k(n-1))\) and \(d(k)=k(n-k)/(F_k(n-1))\), Moran’s chain has \(u(k)=rk(n-k)/(F_kn)\) and \(d(k)=k(n-k)/(F_kn)\), and the biased walk has \(u(k)=r/(1+r)\) and \(d(k)=1/(1+r)\) for \(0{\lt}k{\lt}n\), and \(u=d=0\) at \(0\) and \(n\).

Theorem 20 Birth–death on \(K_n\) is a chain on counts
✓

Under the Birth–death kernel with fitness \(r\) on the complete graph, the number of mutants is the chain without self-loops.

Proof ▶

The parent \(u\) is drawn with probability \(f(u)/F_k\) and the replaced vertex \(w\neq u\) with probability \(1/(n-1)\). The number of mutants increases iff \(u\) is a mutant and \(w\) a resident, with probability \(rk(n-k)/(F_k(n-1))\), decreases iff \(u\) is a resident and \(w\) a mutant, with probability \((n-k)k/(F_k(n-1))\), and stays otherwise.

Moran’s chain and the chain without self-loops have the same jump chain, the biased walk: until it is absorbed at \(0\) or \(n\), the count moves up with probability \(r/(1+r)\) and down with probability \(1/(1+r)\).

Proof ▶

Off the diagonal the rows of Moran’s chain are \((n-1)/n\) times those of the chain without self-loops, and from \(0{\lt}k{\lt}n\) the latter moves up and down with probabilities in the ratio \(r:1\).

For \(r\neq 1\) and \(n\ge 1\), both chains fix the mutants from \(k\) copies with probability \((1-r^{-k})/(1-r^{-n})\).

Proof ▶

Moran’s formula on the complete graph transfers to the chain without self-loops through the lumping, applied to a configuration with \(k\) mutants, and to Moran’s chain through the jump chain.

For \(r=1\) the two chains are the neutral chains of Definition 15, so under neutral push on \(K_n\) the number of mutants is the neutral chain without self-loops, as under pull. On every regular graph, neutral push and pull are the same kernel on configurations.

Proof ▶

With \(r=1\) the total fitness is \(n\). On a regular graph a vertex places its offspring on a given neighbour with the same probability as that neighbour places its offspring on it, so exchanging the two vertices of each pair turns push into pull.

8 Exact fixation on the star

The star with \(n\) leaves is Mathlib’s starGraph \(c\) on \(n+1\) vertices: the centre \(c\) is adjacent to every leaf and leaves only to \(c\). It is not regular, and it amplifies selection (Lieberman, Hauert and Nowak 2005); its exact fixation probability is due to Broom and Rychtář (2008, §5). Write

\[ q=\frac{n+r}{r(nr+1)},\qquad \kappa =\frac{nr+1}{r(n+r)}=\frac1{r^2q}. \]
Definition 24 Star potential
✓

For a configuration with \(i\) mutant leaves, \(\Phi =q^i\) if the centre is a resident and \(\Phi =\kappa q^i\) if it is a mutant.

Theorem 25 The star potential is invariant
✓

For every \(r{\gt}0\), \(\Phi \) is invariant in expectation under one Birth–death step on the star.

Proof ▶

Only the ordered pairs \((c,\ell )\) and \((\ell ,c)\) for a leaf \(\ell \) carry weight, namely \(\mathrm{fit}(c)/(nF)\) and \(\mathrm{fit}(\ell )/F\). Along each edge the two contributions cancel: if \(\ell \) is a mutant and \(c\) a resident they give \(\frac{q^{i-1}}F\big(\frac{1-q}n+rq(\kappa -1)\big)=0\), and if \(c\) is a mutant and \(\ell \) a resident they give \(\frac{q^i}F\big(1-\kappa +\frac{r\kappa (q-1)}n\big)=0\); equal types change nothing.

For \(r\ne 1\), the fixation probability from \(s\) is \((1-\Phi (s))/(1-\kappa q^n)\). A single mutant fixes with probability \((1-q)/(1-\kappa q^n)\) from a leaf, \((1-\kappa )/(1-\kappa q^n)\) from the centre, and \((n(1-q)+(1-\kappa ))/((n+1)(1-\kappa q^n))\) from a uniformly random vertex.

Proof ▶

For \(r{\gt}1\) we have \(q\le 1\) and \(\kappa {\lt}1\), so \(\kappa q^n\le \Phi \le 1\); for \(r{\lt}1\) all inequalities reverse. Hence the normalized potential is \(1\) at fixation, \(0\) at extinction and in \([0,1]\) otherwise, and the fixation-limit lemma applies.

Theorem 27 The formula of Broom and Rychtář
✓

For every \(r{\gt}0\), a single mutant at a uniformly random vertex fixes with probability

\[ \frac{n\cdot \frac{nr}{nr+1}+\frac r{r+n}}{(n+1)\big(1+\frac n{n+r}\sum _{j=1}^{n-1}q^j\big)}. \]
Proof ▶

For \(r\ne 1\) and \(n\ge 1\), sum the geometric series: \(1+\frac n{n+r}\sum _{j=1}^{n-1}q^j= r^2(1-\kappa q^n)/(r^2-1)\). For \(r=1\) both sides are \(1/(n+1)\), by push–pull fixation; for \(n=0\) both are \(1\).

For every \(n\ge 2\), the fixation probability from a uniformly random vertex is larger than Moran’s \((1-1/r)/(1-r^{-(n+1)})\) for \(r{\gt}1\) and smaller for \(0{\lt}r{\lt}1\).

Proof ▶

Put \(s=1/r\) and \(t=(1+ns)/(n+s)\), so that \(q=st\) and \(\kappa =s/t\). The difference has the sign of \((1-s)\big(E(1-s^{n+1})-s^{n+1}(1-t^{n-1})\big)\) with \(E=s^2(n-1)^2/((n+s)(1+ns))\). By Bernoulli, \(1-t^{n-1}\le (n-1)(1-t)=(n-1)^2(1-s)/(n+s)\), which reduces the claim to \(s^{n-1}(1-s)(1+ns){\lt}1-s^{n+1}\). Its slack is \(\sum _{k=0}^{n-2}(1-s)(s^k-s^n)\), a nonempty sum of positive terms on both sides of \(s=1\).

Theorem 29 Large stars amplify \(r\) to \(r^2\)
✓

For \(r{\gt}1\), the fixation probability from a uniformly random vertex of the star with \(n\) leaves tends to \(1-1/r^2\) as \(n\to \infty \).

Proof ▶

\(n(1-q)/(n+1)=\frac n{n+1}\cdot \frac n{n+1/r}\cdot (1-r^{-2})\to 1-r^{-2}\), \((1-\kappa )/(n+1)\to 0\), and \(0\le \kappa q^n\le r^{-n}\to 0\) because \(q\le 1/r\) for \(n\ge 1\).