Moran Processes

Motivating example: The Hawk Dove Game

Consider a finite population of \(N\) animals. Similarly to the motivating example for replicator dynamics, these animals when they interact will always share their food. Due to a genetic mutation, some of these animals may act in an aggressive manner and not share their food. If two aggressive animals meet they both compete and end up with no food. If an aggressive animal meets a sharing one, the aggressive one will take most of the food.

The difference with a replicator dynamics model is that it will be assumed that the size of the population is finite and stays constant.

These interactions can be represented using the matrix \(A\):

\[\begin{split}A = \begin{pmatrix} 2 & 1\\ 3 & 0 \end{pmatrix}\end{split}\]

In this scenario: what is the probability that the mutation takes over the entire population?

To answer this question we will assume a vector \(v\) represents the population. In this case:

  • \(v_1\) represents the number of individuals of the population that share.

  • \(v_2\) represents the number of individuals of the population that act aggressively.

Note that as the size of the population is assumed to be constant this implies that:

\[\sum_i x_i = N\]

Where \(N\) is the number of individuals in the population.

The overall fitness of an individual of a given type in a population \(v\) is then given by the expected utility (as given by \(A\)) of individuals of that type as they interact with the population:

\[\begin{split}\begin{align*} f_1 = & \frac{2 (v_1 - 1) + 1 v_2}{N - 1}\\ f_2 = & \frac{3 v_1 + 1 (v_2 - 1)}{N - 1} \end{align*}\end{split}\]

Note that \(f_i\) is dependent on \(v\).

The evolutionary process defined in this chapter will assume an individual will be selected for copy proportional to their fitness. The probability of picking an individual of a given type \(i\) is thus given by:

\[\frac{v_i f_i}{v_1 f_1 + v_2 f_2}\]

To ensure the population stays constant this requires that an individual is chosen to be removed. This is done uniformly randomly. The probability of picking an individual of a given type \(i\) for removal is then given by:

\[\frac{v_i}{v_1 + v_2}\]

These probabilities allow us to define a Markov process that describes the evolution of the system. Here is a diagram showing the different states in the process for \(N=5\).

stateDiagram-v2 direction LR s1: (1, 4) s2: (2, 3) s3: (3, 2) s4: (4, 1) s1 --> s2 s2 --> s1 s2 --> s3 s3 --> s2 s3 --> s4 s4 --> s3 note left of s1 (0, 5) end note note right of s4 (5, 0) end note

The answer to our question corresponds to the probability that starting in state \(v=(4, 1)\), we arrive at state \(v=(0, 5)\).

The following plot shows 4 possible outcomes. In 2 of them the sharing animals resist the invasion of the aggressive one.

(Source code, png, hires.png, pdf)

../_images/moran-process-1.png

The Moran process

First defined in [Moran1958] the Moran process assumes a constant population of \(N\) individuals which can be of \(m\) different types. There exists a fitness function \(f:[1, \dots, m] \times [1, \dots, m] ^ N \to \mathbb{R}\) that maps each individual to a numeric fitness value which is dependent on the types of the individuals in the population.

The process is defined as follows, at each step:

  1. Every individual \(k\) has their fitness \(f_k\) calculated.

  2. An individual is randomly selected for copying. This selection is done proportional to their fitness: \(f_k(v)\). Thus, the probability of selecting individual \(k\) for copying is given by:

    \[\frac{f_k(v)}{\sum_{h=1^N}f_h(v)}\]
  3. An individual is selected for removal. This selection is done uniformly randomly. Thus, the probability of selecting individual \(i\) for removal is given by:

    \[1 / N\]
  4. An individual of the same type as the individual selected for copying is introduced to the population.

  5. The individual selected for removal is removed.

The process is repeated until there is only one type of individual left in the population.

Fitness function on a game

A common representation of the fitness function \(f\) is to use a game.

As an example consider a population with \(N=10\) and \(m=3\) types of individuals. The fitness of a given individual is calculated by considering the utilities received by each individual when they interact with all other individuals. These interactions are given by the \(3\times 3\) matrix \(A\):

\[\begin{split}A = \begin{pmatrix} 3 & 2 & 1\\ 1 & 3 & 2\\ 2 & 1 & 3 \end{pmatrix}\end{split}\]

\(A_{ij}\) represents the utility of an individual of type \(i\) interacting with an individual of type \(j\).

In this setting, the fitness of an individual of type \(i\) is:

\[f_i(v) = (v_{i} - 1)A_{ii} + \sum_{j\ne i, j=1}^{N}v_jA_{ij}\]

For example, if \(v=(4, 5, 1)\) then the fitness of individuals of each type are given by:

  1. Individuals of the first type:

    \[3 \times 3 + 5 \times 2 + 1 \times 1 = 20\]
  2. Individuals of the second type:

    \[4 \times 3 + 4 \times 1 + 1 \times 2 = 18\]
  3. Individuals of the third type:

    \[0 \times 3 + 4 \times 2 + 5 \times 1 = 13\]

Selection probabilities on a game

The probability of selecting an individual of type \(i\) for copying is given by:

\[\frac{v_{i}\times\left((v_{i} - 1)A_{ii} + \sum_{j\ne i, j=1}^{N}v_jA_{ij}\right)} {\sum_{i=1}^mv_{i}\times\left((v_{i} - 1)A_{ii} + \sum_{j\ne i, j=1}^{N}v_jA_{ij}\right)}\]

So for this \(3\times 3\) example, the probability of selecting an individual of each type for copying is given by:

  1. Individuals of the first type:

    \[\frac{4 \times 20}{4 \times 20 + 5 \times 18 + 1 \times 13} = \frac{80}{183}\]
  2. Individuals of the second type:

    \[\frac{5 \times 18}{4 \times 20 + 5 \times 18 + 1 \times 13} = \frac{90}{183}\]
  3. Individuals of the third type:

    \[\frac{1 \times 13}{4 \times 20 + 5 \times 18 + 1 \times 13} = \frac{13}{183}\]

Question

For the hawk dove game what are the probabilities of selecting an individual for copying and for removal for the following populations:

  1. \(v=(4, 5)\)

  2. \(v=(3, 0)\)

  3. \(v=(6, 6)\)

The Moran process with mutation

The Moran process can be modified to allow for mutation. When a new individual is selected for copying, there is a \(p\) probability that they mutate to a another type from the original population (even if they are no longer present in the population.

The following plot shows 4 possible outcomes of the Moran process of the Hawk Dove game with a probability of mutation of \(p=.2\). Note that as opposed to the numerical simulations without mutation, the process does not terminate as new types of individuals can always enter the population.

(Source code, png, hires.png, pdf)

../_images/moran-process-2.png

The Moran process with 2 types of individuals

When considering a Moran process on 2 types of individuals the fitness function is defined by \(A\) which is, in this case is a 2 by 2 matrix.

In the case of a only two types of individuals, the population vector \(v\) can be replaced by an integer \(n\) which represents the number of individuals of the first type. The number of individuals of the second type is then given by \(N - n\).

In this case the random process is a specific type of process called a birth death process:

  • A set of possible states: \(S = \{0, 1, \dots, N\}\)

  • Two absorbing states: \(0\) and N.

  • Probabilities \(p_{ij}\) of going from state \(i\) to \(j\) defined by:

    • \(p_{i, i + 1} + p_{i, i - 1} \leq 1\) for \(1\leq i \leq N - 1\).

    • \(p_{ii} = 1 - p_{i, i + 1} - p_{i, i - 1}\) for \(1\leq i \leq N - 1\).

    • \(p_{00} = p_{NN} = 1\).

Fixation probability

The probability of starting in state \(i\) and the process ending in state \(N\) is denoted by \(x_i\).

The probability of a single individual of the first type being able to take over the population is denoted by \(\rho\) and \(\rho=x_1\).

Given a birth death process, the probability \(x_i\) is given by:

\[x_i=\frac{1+\sum_{j=1}^{i-1}\prod_{k=1}^j\gamma_k}{1+\sum_{j=1}^{N-1}\prod_{k=1}^j\gamma_k}\]

where:

\[\gamma_k = \frac{p_{k,k-1}}{p_{k,k+1}}\]

The proof of this result is omitted here but it allows for the specific case of the Moran process to be obtained:

The transition probabilities are then given by:

\[\begin{split}\begin{align*} p_{i,i+1}&=\frac{if_{1}(i)}{if_{1}(i) + (N-i)f_{2}(i)}\frac{N-i}{N}\\ p_{i,i-1}&=\frac{(N-i)f_{2}(i)}{if_{1}(i) + (N-i)f_{2}(i)}\frac{i}{N} \end{align*}\end{split}\]

which gives:

\[\begin{split}\begin{align*} \gamma_i&=\frac{p_{i, i - 1}}{p_{i, i +1}}\\ &=\frac{\frac{(N-i)f_{2}(i)}{if_{1}(i) + (N-i)f_{2}(i)}\frac{i}{N}} {\frac{if_{1}(i)}{if_{1}(i) + (N-i)f_{2}(i)}\frac{N-i}{N}}\\ &=\frac{(N-i)f_{2}(i)\frac{i}{N}} {if_{1}(i)\frac{N-i}{N}}\\ &=\frac{f_{2}(i)}{f_{1}(i)} \end{align*}\end{split}\]

Thus, the formula for \(x_i\) in the general birth death process can be used to obtain the fixation probability \(\rho=x_1\).

Question

For the hawk dove game obtain \(\rho\) for the following population sizes:

  1. \(N=2\)

  2. \(N=3\)

  3. \(N=4\)

Exercises

  1. For the following games, obtain the fixation probability \(x_1\) for \(N=4\):

    1. \(A=\begin{pmatrix}1 & 1 \\ 1 & 1\end{pmatrix}\)

    2. \(A=\begin{pmatrix}1 & 2 \\ 3 & 1\end{pmatrix}\)

  2. Consider the game \(A=\begin{pmatrix}r & 1 \\ 1 & 1\end{pmatrix}\) for \(r>1\) and \(N\), and obtain \(x_1\) as a function of \(r\). How does \(r\) effect the chance of fixation?

  3. Prove the theorem for fixation probabilities in a birth death process (a Moran process with 2 types).

Using Nashpy

See Use Moran processes for guidance of how to use Nashpy to obtain numerical simulations of the Moran process. See Obtain fixation probabilities for guidance of how to use Nashpy to obtain approximations of the fixation probabilities. This is what is used to obtain all the plots above.