- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
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.
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\).
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\).
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\).
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.
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.
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.
The weights of (parent, offspring position) pairs are nonnegative and sum to one.
On a connected graph, the probability that neither type has taken over tends to zero.
On a regular graph, \((1/r)^{\# \text{mutants}}\) is preserved in expectation by one step; when \(r=1\), so is the number of mutants.
On a connected regular graph with \(r\neq 1\), the fixation probability from \(k\) mutants is \((1-r^{-k})/(1-r^{-n})\).
For \(n\ge 2\), both chains fix from \(k\) mutants with probability \(k/n\).
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\).
Under the Birth–death kernel with fitness \(r\) on the complete graph, the number of mutants is the chain without self-loops.
On a connected regular graph with \(r=1\), the fixation probability is \(k/n\).
On a connected graph, the probability that the pull process has not reached a constant configuration after \(t\) steps tends to \(0\).
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.
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.
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.
On every finite graph, \(\Phi _{\mathrm{push}}\) is invariant in expectation under neutral push and \(\Phi _{\mathrm{pull}}\) is invariant in expectation under pull.
For \(r\neq 1\) and \(n\ge 1\), both chains fix the mutants from \(k\) copies with probability \((1-r^{-k})/(1-r^{-n})\).
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)\).
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 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\).
For every \(r{\gt}0\), \(\Phi \) is invariant in expectation under one Birth–death step on the star.
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 \).
For every \(r{\gt}0\), a single mutant at a uniformly random vertex fixes with probability