Evolutionary amplifiers: Difference between revisions

From EvoLudo
No edit summary
 
Line 60: Line 60:
== Fixation probabilities on superstars ==
== Fixation probabilities on superstars ==
The intriguing dynamical features of evolutionary amplifiers have first been reported by [[#Publications|Lieberman et al. (2005)]]. However, the formula for the fixation probabilities reported therein has resulted in a controversy that took time and effort to resolve. Lieberman et al. (2005) originally derived the fixation probability of a single mutant with fitness \(r\) on a superstar graph as
The intriguing dynamical features of evolutionary amplifiers have first been reported by [[#Publications|Lieberman et al. (2005)]]. However, the formula for the fixation probabilities reported therein has resulted in a controversy that took time and effort to resolve. Lieberman et al. (2005) originally derived the fixation probability of a single mutant with fitness \(r\) on a superstar graph as
\begin{align}\label{eq:nature05}
\begin{equation}
\rho_k = \dfrac{1-\dfrac1{r^k}}{1-\dfrac1{r^{kN}}}.  
\rho_k = \dfrac{1-\dfrac1{r^k}}{1-\dfrac1{r^{kN}}}. \tag{1}
\end{align}
\label{eq:nature05}
\end{equation}


For \(k=2\) this approximates the fixation probability for the star graph, \(\rho_2\). Note that it is only an approximation because of (i) a small chance that the hub vertex is selected to reproduce several times in a row and (ii) because the fixation probability of a mutant that arises in the hub is very close to zero. The formula becomes exact in the limit \(N\to\infty\) because then the finite size corrections vanish. The exact formula for the star graph is derived in [[#References|Broom & Rychtář (2008)]]. Similarly, Eq. \ref{eq:nature05} has been confirmed for the superstar with \(k=3\) ([[#References|Houchmandzadeh & Vallade, 2011]]). However, for \(k=5\) [[#References|Díaz et al. (2013)]] have reported an upper bound for the fixation probability \(\rho_5\):
For \(k=2\) this approximates the fixation probability for the star graph, \(\rho_2\). Note that it is only an approximation because of (i) a small chance that the hub vertex is selected to reproduce several times in a row and (ii) because the fixation probability of a mutant that arises in the hub is very close to zero. The formula becomes exact in the limit \(N\to\infty\) because then the finite size corrections vanish. The exact formula for the star graph is derived in [[#References|Broom & Rychtář (2008)]]. Similarly, Eq. \ref{eq:nature05} has been confirmed for the superstar with \(k=3\) ([[#References|Houchmandzadeh & Vallade, 2011]]). However, for \(k=5\) [[#References|Díaz et al. (2013)]] have reported an upper bound for the fixation probability \(\rho_5\):
\[\rho_5 \leq 1-\frac{r+1}{2r^5 + r + 1}\]
\begin{equation}
\rho_5 \leq 1-\frac{r+1}{2r^5 + r + 1}
\end{equation}
in the limit \(N\to\infty\). For beneficial mutants with \(r\geq 1.42\) this results in a contradiction when compared to Eq. \ref{eq:nature05} in the same limit:
in the limit \(N\to\infty\). For beneficial mutants with \(r\geq 1.42\) this results in a contradiction when compared to Eq. \ref{eq:nature05} in the same limit:
\[\rho_k = 1-\frac1{r^k}.\]
\begin{equation}
\rho_k = 1-\frac1{r^k}.
\end{equation}


Upon closer inspection it turns out that the original formula, Eq. \ref{eq:nature05}, was far too optimistic in terms of the strength of amplification for \(k\geq5\). The reasons for this overestimation, however, are rather subtle and relate to the fact that the states of neighbouring vertices along each directed chain feeding into the hub are highly correlated ([[#Publications|Jamieson-Lane & Hauert, 2015]]). In essence, this reduces the amplification from exponential in \(k\) to just a linear factor. Although an exact formula for the fixation probability on superstars is inaccessible, rather tight upper and lower bounds on \(\rho_k\) can be derived. In the limit \(N\to\infty\) the formula becomes significantly simpler and reduces to  
Upon closer inspection it turns out that the original formula, Eq. \ref{eq:nature05}, was far too optimistic in terms of the strength of amplification for \(k\geq5\). The reasons for this overestimation, however, are rather subtle and relate to the fact that the states of neighbouring vertices along each directed chain feeding into the hub are highly correlated ([[#Publications|Jamieson-Lane & Hauert, 2015]]). In essence, this reduces the amplification from exponential in \(k\) to just a linear factor. Although an exact formula for the fixation probability on superstars is inaccessible, rather tight upper and lower bounds on \(\rho_k\) can be derived. In the limit \(N\to\infty\) the formula becomes significantly simpler and reduces to  
\begin{align}
\begin{equation}
\label{eq:jtb05}
1-\dfrac1{r^4(k-1)\left(1-\frac1r\right)^2} \leq \rho_k \leq 1-\dfrac1{1+r^4(k-1)} \tag{2}
1-\dfrac1{r^4(k-1)\left(1-\frac1r\right)^2} \leq \rho_k \leq 1-\dfrac1{1+r^4(k-1)}
\label{eq:jtb13}
\end{align}
\end{equation}
although the bounds are not as tight anymore. At the same time, the lower bound in this idealized limit is consistently too high. Quite surprisingly, this indicates that even for \(B=M=200\), which translates to a population size of \(N\approx40'000\), finite size effects remain significant. Although, the primary cause for the finite size effects is easily accounted for because it simply relates to the chance that a randomly placed mutant ends up in one of the chains (or the hub) and hence almost certainly goes extinct.
although the bounds are not as tight anymore. At the same time, the lower bound in this idealized limit is consistently too high. Quite surprisingly, this indicates that even for \(B=M=200\), which translates to a population size of \(N\approx40'000\), finite size effects remain significant. Although, the primary cause for the finite size effects is easily accounted for because it simply relates to the chance that a randomly placed mutant ends up in one of the chains (or the hub) and hence almost certainly goes extinct.


Eq. \ref{eq:jtb05} resolves the controversy around fixation probabilities on superstars while confirming the original claim that it is possible, in principle, to construct a perfect amplifier - even though much larger graphs are required than previously thought to achieve the same amplification effect.
Eq. \ref{eq:jtb13} resolves the controversy around fixation probabilities on superstars while confirming the original claim that it is possible, in principle, to construct a perfect amplifier - even though much larger graphs are required than previously thought to achieve the same amplification effect.


==Publications==
==Publications==
Retrieved from "https://wiki.evoludo.org/index.php?title=Evolutionary_amplifiers"