The Moran Process and the Isothermal Theorem
1 The model
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.
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
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.
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.
On a regular graph, \((1/r)^{\# \text{mutants}}\) is preserved in expectation by one step; when \(r=1\), so is the number of mutants.
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
On a connected graph, the probability that neither type has taken over tends to zero.
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.
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})\).
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\).
The same argument with \(\psi =\# \text{mutants}/n\).
On the complete graph, the fixation probability from \(k\) mutants is \((1-r^{-k})/(1-r^{-n})\).
The complete graph is connected and \((n-1)\)-regular.
The converse of the isothermal theorem is false (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.
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\).
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.
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\).
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.
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 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
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.
For every \(r{\gt}0\), \(\Phi \) is invariant in expectation under one Birth–death step on the star.
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.
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.
For every \(r{\gt}0\), a single mutant at a uniformly random vertex fixes with probability
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\).
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\).
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 \).
\(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\).