|Home | About | Journals | Submit | Contact Us | Français|
In this paper, we show that for evolutionary dynamics between two types that can be described by a Moran process, the conditional fixation time of either type is the same irrespective of the selective scenario. With frequency dependent selection between two strategies A and B of an evolutionary game, regardless of whether A dominates B, A and B are best replies to themselves, or A and B are best replies to each other, the conditional fixation times of a single A and a single B mutant are identical. This does not hold for Wright-Fisher models, nor when the mutants start from multiple copies.
A key aspect of evolutionary dynamics concerns the process where a new mutant is introduced in a population. Through selection and random drift, the frequency of the mutant changes, and sometimes the mutant can reach fixation in the population (Fisher, 1922; Haldane, 1927; Fisher, 1930; Wright, 1931, 1942; Kimura, 1957; Robertson, 1960; Kimura, 1994; Bürger, 2000). The probability of fixation and the mean time to fixation of a single mutant are important quantities. There is an extensive literature on this topic using diffusion theory to calculate both the fixation probability and the conditional mean time to fixation (Kimura, 1994; Ewens, 2004).
In particular, the conditional fixation time of a single mutant is often a more relevant measure of the evolutionary success of a mutant. Since the loss of a mutant gene is much more frequent, the conditional fixation time is much longer than the unconditional absorption time until either fixation or loss. (Nei & Roychoudhury, 1973; Maruyama, 1974, 1977) noted, using diffusion theory, that under weak constant selection the mean fixation time for a favorable mutant is the same as that for the corresponding deleterious mutant in a Wright-Fisher process. Diffusion methods can similarly show that in the setting of weak frequency dependent selection involving two phenotypes engaged in a game, the mean fixation time of a single mutant of either phenotype is the same.
However, we show in this paper that, even under strong frequency dependent (including constant) selection, the conditional fixation time of a single mutant of either phenotype has the same distribution, hence same mean, variance, etc, for a Moran process, though not for a Wright-Fisher process. Our method is much simpler algebraically than the diffusion calculations of (Nei & Roychoudhury, 1973; Maruyama, 1974, 1977; Ewens, 2004); furthermore, it requires no limiting assumption on population size or selection factor.
In Section 2, we focus on the the frequency dependent game dynamics of a Moran process for finite populations proposed in (Nowak et al., 2004; Nowak & Sigmund, 2004; Taylor et al., 2004). We state the surprising result that the time to fixation of a single mutant, under weak and strong selection, in a finite population, is independent of the strategies of the mutant and the resident population. In other words, a single A mutant fixates in a population of B players as quickly as a single B mutant in a population of A players, regardless of the strength of selection, or the fact that a single A mutant might be more likely to fixate than a single B mutant, or vice versa. Surprisingly this symmetry holds not only for the mean but also for variance and all higher moments. We have learned that (Antal & Scheuring, 2006) independently obtained the result that the two conditonal mean fixation times are the same in a particular game model of Moran process. The symmetry does not hold when the initial number of mutants is greater than 1.
In Section 3, we note that this symmetry does not hold for models based on the Wright-Fisher process.
In Section 4, we generalize the symmetry of conditional fixation times to a class of Markov processes, where only states 1 and N − 1 can transition into absorbing states 0 and N respectively. If the transition matrix further satisfies the detailed balance condition, then the conditional fixation time from state 1 to state N has the same distribution as that from state N − 1 to state 0. In particular, the two conditional fixation times have the same mean and the same variance and also all the moments.
Our result holds for games on cycles (Nakamaru et al., 1997, 1998; Nakamaru & Iwasa, 2005). Furthermore, our result also applies to a wide range of imitation processes of interest to economists (Ellison, 1993; Binmore & Samuelson, 1997; Maruta, 2002), when the detailed balance condition holds.
To illustrate the idea, we start with a frequency dependent Moran process as described in (Nowak et al., 2004; Taylor et al., 2004). The payoff matrix for a game with two strategies A and B is given by Table 1.
We have a population of N individuals, each individual uses strategy either A or B. The number of individuals using strategy A is given by i, and the fitness of individuals using strategy A and B are respectively fi and gi, where
w measures the strength of selection. The bigger w is, the stronger the selection.
The selection dynamics of this two strategy game with N players can be formulated as a Moran process (Moran, 1962) with frequency dependent fitness. At each time step, an individual is chosen for reproduction proportional to its fitness. One identical offspring is being produced which replaces another randomly chosen individual. Thus the population size, N, is strictly constant. The probability of adding an A-offspring is ifi/(ifi +(N −i)gi). At each time step, the number of A individuals can either increase by one, stay the same, or fall by one. Therefore, the transition matrix of the Markov process is tri-diagonal and defines a birth-death process. The transition matrix is given by
for 0 ≤ i ≤ N. All other entries of the transition matrix are 0.
The probabilities, ρA, of a single A player to reach fixation in a population of B players, and ρB, of a single B player to reach fixation in a population of A players are given respectively by (Karlin & Taylor, 1975)
In general, we have ρA ≠ ρB. However, we have
The conditional mean fixation time of a single A mutant, tA, is the same as that of a single B mutant, tB, for all levels of selection and for all games.
In other words, even if an A player is more likely to fixate in a population of B players, than a B player in a population of A players, the conditional mean time for a single A player to take over the whole population is the same as that for a single B player. The conditional mean time to fixation for a single mutant is the same irrespective of the direction of flow or the strength of selection, w.
In Figure 1(a), the x-axis measures w which ranges from 0 to 1, and the y-axis measures the conditional mean fixation time of a single mutant. We see that the conditional mean fixation times for a single A mutant and and a single B mutant are identical for all w and for four different games: a neutral game, a constant fitness game where A is dominant, a bi-stable game, and a Hawk-Dove game.
In fact, we shall show in Appendix A that the probability distributions of the conditional time to fixation for a single mutant of either type A or B are the same. Therefore, the mean, variance, and all other moments of the two conditional fixation times are the same.
On the other hand, simulation shows that in general the conditional fixation time of i A mutants is not the same as that of i B mutants for weak or strong selection when i > 1 as explained later.
We calculate in Appendix B tA = tB for a Moran process under weak constant and frequency dependent selection.
In a Wright-Fisher process, at each time step, the entire population is replaced by a new generation of the same size, its composition is determined by sampling with replacement from the previous generation. If there are i A players before reprodution, the number of A players after reproduction is a binomial random variable with index N and parameter ifi/(ifi +(N − i)gi). The probability of having jA players afte reproduction is
Under strong selection, the conditional fixation time of a single A mutant is not the same as that of a single B mutant. Figure 1(b) plots the conditional mean fixation time of a single mutant using strategy A or B for the same four games as in Figure 1(a). Again, the x-axis measure the strength of selection w, and the y-axis measures the conditional mean fixation time. The solid lines plot the times for A mutant, and dashed lines for B mutant. For each of the three non-neutral games, as w increases, the two conditional fixation times for A and B, and the corresponding solid and dashed lines, diverge further apart.
Under weak and constant selection, using diffusion theory (Nei & Roychoudhury, 1973; Maruyama, 1974, 1977; Ewens, 2004) showed that a selectively disadvantageous mutant, if destined for fixation, spends as much time, on average, in any frequency range as a correspondingly advantageous mutant destined for fixation. In particular, the conditional mean fixation time of a single advantageous mutant is the same as that of a corresponding deleterious mutant. We can even generalize this symmetry result under weak selection to frequency depedent selection for Wright-Fisher model. Figure 1(b) shows that when w is small, the conditional mean fixation times of a single A mutant and a single B mutant are approximately identical for four different games.
Moran and Wright-Fisher processes are two examples of a general Markov process on states 0, 1, 2,…,N, with 0 and N being absorbing states. We have seen in Sections 2 and 3 that a single A mutant can reach fixation equally fast as a single B mutant in a Moran process irrespective of selection strength and game, while in a Wright-Fisher process, this only holds when selection is weak.
We prove in Appendix A that
For a Markov process P on 0, 1, 2,…,N state, where 0 and N are absorbing states, suppose Pi0 = 0 for all i ≥ 2, and PjN = 0 for all j ≤ N − 2; furthermore P satisfies the detailed balanced condition, i.e. there exist a vector , where all entries are positive, such that
for 1 ≤ i, j ≤ N − 1, then the distribution functions of the conditional fixation time from state 1 to N and from state N − 1 to 0 are the same. In particular, the conditional fixation time from state 1 to N and from state N − 1 to 0 have the same mean and variance.
It shall be clear from the proof in Appendix A that there is only one state that can lead to each of the absorbing states.
The principle of detailed balance is important in describing equilibrium properties. When the detailed balance condition is satisfied, the equilibrium can be achieved in the sense that around any closed circuit, the netflow is zero. In terms of the transition probabilities of a Markov process, the detailed balance condition dictates that around any circulation, the product of all the transition probabilities along the loop is the same and non-zero going counterclockwise and clockwise. The detailed balance condition is also known as Kolmogorov cycle condition, or Kolomogorov consistency condition.
Obviously, if P is symmetric, it satisfies the detailed balance condition.
An important class of Markov processes which satisfy detailed balance condition is the birth-death process, whose transition matrix P is a continuant, satisfying the condition that Pij = 0 if |i − j| > 1. In particular, for a Moran process discussed in Section 2, Proposition 1 follows immediately.
The principle of detailed balance is equivalent to the time reversal property for Markov processes. For a Markov process M admitting a stationary distribution , where the ψi's are positive, M is reversible if and only if it satisfies the detailed balance condition ψiMij = ψjMji for all i, j.
The Moran process, with selection as well as mutation is reversible, since there exists a stationary distribution and it satisfies the detailed balance condition. In contrast, the Wright-Fisher process with selection and mutation is not reversible, because it does not satisfy the detailed balance condition. However, in diffusion approximation for a Wright-Fisher process, Proposition 2 holds. Diffusion approximation is in effect assuming weak selection and a large population size. Proposition 2 does not hold for Wright-Fisher process in general because it does not satisfy the detailed balance condition, nor does it satisfy the property that only one state can transition into each of the two absorbing states.
It is important to note that for a Markov process satisfying the conditions of Propositoin 2, when i ≠ 1, N − 1, the distribution of conditional time to absorption from state i to N is in general different from the corresponding distribution from state N − i to state 0. This will be illustrated by the proof of Proposition 2 in Appendix A.
We have shown in this paper that in a Moran process describing evolutionary dynamics of two types, the conditional time to absorption for a single mutant of either type has the same probability distribution, hence the same mean, variance and all other moments. This is a consequence of the fact that the Moran process satisfies the detailed balance condition on the intermediate states, whereby equilibrium is achieved. Our symmetry result does not hold for a Wright-Fisher process, except in the diffusion limit of weak selection and large population.
Under the setting of a generalized Moran process, a single deleterious mutant succeeds in taking over the population of more favorable wild-type individiduals as fast as a single corresponding favorable mutant can take over a population of weaker wild-type individuals.
A deleterious mutant goes into extinction most of the time, but if it does succeed in replacing the population, it spreads as fast as the corresponding single favorable mutant. In contrast, while a single favorable mutant rarely goes to extinction, under strong selection, it does not succeed any faster.
Our symmetry result of conditional mean fixation time does not hold if the mutant starts from multiple copies in both Moran and Wright-Fisher models. If a group of mutants is introduced, then it is in general faster for the favorable mutants to succeed than for the corresponding deleterious mutants to succeed. Figure 2(a) shows the conditional mean fixation times of 2 A mutants and 2 B mutants for four different games in a Moran process. The two times are different. The solid lines plot the time for A, and dashed lines for B. We see that upon fixation, the advantageous mutants fixate faster than corresponding deleterious mutants; both fixate faster than 2 neutral mutants, except when the game is Hawk-Dove. Figure 2(b) shows the conditional mean fixation times of 2 A mutants and 2 B mutants for four different games in a Wright-Fisher process. Again the two fixation times are different, and for very weak selection, the two fixation times are close.
In fact, our results can also be applied to the study of evolutionary game dynamics on graphs, of which there is a great deal of current interest (Nakamaru et al., 1997, 1998; Nakamaru & Iwasa, 2005; Lieberman et al., 2005; Ohtsuki et al., 2006). In the case of a cycle graph with N nodes, the game dynamics starting from a single mutant can be described by the Moran process. State 0 is all B, and state N is all A; while state 1 corresponds to the set of configurations where exactly one node plays A and the rest play B; and similarly for state N − 1. Since the number of mutants can increase or decrease by at most 1 at each time step, the corresponding Markov process is a birth-death process satisfying the detailed balance condition. Hence, our result that the fixation time of a single mutant of either strategy is the same holds for games on a cycle. For higher dimesional torus type graphs or lattices, where symmetric conditions guarantee that there is only a single state that can transition into either of the two absorption states, we still need to make sure that the detailed balance condition satifies, in order to apply our result.
Since our results on the equality of fixation time apply to the class of Markov processes where the transition probabilities on the immediate states satisfy the detailed balance condition, it would be interesting to find examples of such Markov processes, other than the Moran process, (e.g. lattices and higher dimensional torus with approproriate transition matrix,) which satisfy this equilibrium condition.
The Program for Evolutionary Dynamics is supported by Jeffrey Epstein.
Consider a general Markov process on states 0, 1, 2,…, N, where 0 and N are absorbing states, and P is its transition matrix. Further, we add the constraint that Pi0 = 0 for all i ≥ 2, and PjN = 0 for all j ≤ N − 2. Hence, there is only one way in to the absorbing states 0 and N.
Let Tr denote transposition, define
From now on, we will work with the (N − 1) × (N − 1) submatrix of the original Markov matrix P with its first and last rows and columns removed, i.e. P is just the transition matrix on states 1 through N − 1.
First, we find that
where I is the (N − 1) × (N − 1) identity matrix.
It is important that P0i = 0 for i > 1 and PN,j = 0 for j < N − 1 here and in the proof of Proposition 2.
The matrix is called the fundamental matrix of the matrix P. The mean waiting time, tij, in state j before absoprtion into state 0 or N starting from state i is given by and .
The conditional waiting time in state j before absorption into state N starting from state i, , is given by tijπj/πi.
Let Ψ be the diagonal matrix whose diagonal entries are given by Ψ1, Ψ2,…, ΨN−1. The detailed balanced condition is just
we can similarly show that
for all 1 ≤ j ≤ N − 1, namely, the conditional mean sojourn time at state j starting from state 1 and starting from state N − 1 are the same.
Since the distributions of conditional fixation time are the same, i.e. , we have that the conditional mean times to absorption from state 1 to N and from state N − 1 to 0 are the same:
For a continuant matrix P, where Pij = 0 if |i − j| > 1. Let Pi,i+1 = λi, and Pi,i−1 = μi, λ0 = μN = 0. We can write down the expressions for , , , and explicitly [Karlin & Taylor, 1975; Ewens, 2004]. Let
Using these formulae, we can calculate tA,tB in Appendix B.
It is important to note that for transition matrices satisfying the detailed balance condition,
in general. In particular, since
the conditional mean fixation times
In the special case of constant selection, where A has constant fitness r =1+ w > 1, and B has constant fitness 1, we have ρA > ρB. For weak selection (w << 1/N), we calculate that
In particular, for large N,we have
Therefore, the fixation time of a single mutant of either strategy is reduced by (N+3)(N − 2)w2/72 compared to the fixation time of a neutral mutant. For r > 1, one A player is more likely to fixate among B players than vice versa. We certainly expect that it would take shorter time for A to fixate than a neutral mutant. Moreover, a single B player also takes the same shorter time span than a neutral mutant to fixate in a population of A players, although the relative fitness of B is smaller than that of A.
Under weak frequency dependent selection, we find that
where γ = b + c − a − d and δ = a − d + (d − b)N. For large N,we have
Hence even when strategy A dominates B, B fixates in a population of A players equally fast as A fixates among B players. For bi-stable games, a > c and b < d, the fixation time for a single A or B player is shorter than that of a neutral mutant. For Hawk-Dove games, a < c and b > d, the fixation time is longer than that of a neutral mutant.