Facilitator notes: not student-facing. These notes are for planning and running classes. Student resources are at vknight.org/gt/.

Moran Processes

Activity (approximately 60 minutes)

Goal. Reproduce a Moran process by hand so the birth-death dynamics and fixation are felt before they are formalised. This activity is deliberately longer than the usual 20 minutes.

The deck. There is a write-on deck at /decks/moran-process/main.pdf: the Hawk-Dove payoffs printed, the birth-death chain with its transition probabilities blank, tables for the fitnesses and the selection probabilities, and a table turning those probabilities into ranges on a D12. There is no separate form: everything the pairs need is on the deck.

Every slide of the deck names the numbered section of the notes it is reading, and the last slide gathers them into one table, marks what is examinable and sets the reading for the next class. A "While you play" slide carries the rules and the D12 ranges: leave it up while the room plays. Each pair only needs scrap paper to keep a tally of how each run ended.

Requires one D12 (12-sided die) per pair. Twelve is divisible by both four and six, so a single die reproduces every selection probability. Without a D12, a d6 and a d4 also work, using the mapping in the code below.

Virtual modification: use breakout rooms of 4. For dice, show how to use the Python random library.

Explain that we will aim to reproduce a Moran process with \(n=3\).

We will do this with the Hawk–Dove game:

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

Recall, this corresponds to sharing of 4 resources:

Give students 5 minutes to write out the fitnesses of each type in each possible situation.

Confirm:

\(f(\text{hawk})\) \(f(\text{dove})\)
1 hawk, 2 doves \(0\times0 + 2\times3 = 6\) \(1\times1 + 1\times2 = 3\)
2 hawks, 1 dove \(1\times0 + 1\times3 = 3\) \(2\times1 + 0\times2 = 2\)

Give students 5 minutes to write out the probabilities of selection of each type in each possible situation.

Confirm:

Select Selection: birth Selection: death
1 hawk, 2 doves hawk \(\frac{6}{6 + 2\times3}\) \(\frac{1}{3}\)
1 hawk, 2 doves dove \(\frac{2\times3}{6 + 2\times3}\) \(\frac{2}{3}\)
2 hawks, 1 dove hawk \(\frac{2\times3}{2\times3 + 2}\) \(\frac{2}{3}\)
2 hawks, 1 dove dove \(\frac{2}{2\times3 + 2}\) \(\frac{1}{3}\)

Let students simulate.

Count from groups to obtain mean fixation rate of a hawk.

Show the following code that allows us to simulate the simulation undertaken by the students (this is not the same code as in the notes):

import collections
import matplotlib.pyplot as plt
import numpy as np
import tqdm

def roll_n_sided_dice(n=6):
    """Roll a dice with n sides."""
    return np.random.randint(1, n + 1)

class MoranProcess:
    """
    A class for a Moran process with a population of size n=3 using the
    standard hawk-dove game:

        A = [[0, 3],
             [1, 2]]

    Note that this is a simulation corresponding to an in-class activity
    where students roll dice.
    """
    def __init__(self, number_of_hawks=1, seed=None):
        if seed is not None:
            np.random.seed(seed)

        self.number_of_hawks = number_of_hawks
        self.number_of_doves = 3 - number_of_hawks

        self.dice_and_values_for_hawk_birth = {1: (6, {1, 2, 3}), 2: (4, {1, 2, 3})}
        self.dice_and_values_for_hawk_death = {1: (6, {1, 2}), 2: (6, {1, 2, 3, 4})}

        self.history = [(self.number_of_hawks, self.number_of_doves)]

    def step(self):
        """Select a hawk or a dove for birth and death, then update."""
        birth_dice, birth_values = self.dice_and_values_for_hawk_birth[self.number_of_hawks]
        death_dice, death_values = self.dice_and_values_for_hawk_death[self.number_of_hawks]

        select_hawk_for_birth = self.roll_dice_for_selection(dice=birth_dice, values=birth_values)
        select_hawk_for_death = self.roll_dice_for_selection(dice=death_dice, values=death_values)

        if select_hawk_for_birth:
            self.number_of_hawks += 1
        else:
            self.number_of_doves += 1

        if select_hawk_for_death:
            self.number_of_hawks -= 1
        else:
            self.number_of_doves -= 1

        self.history.append((self.number_of_hawks, self.number_of_doves))

    def roll_dice_for_selection(self, dice, values):
        """Return True if the roll is in the target set."""
        return roll_n_sided_dice(n=dice) in values

    def simulate(self):
        """Run the simulation until the number of hawks is 0 or 3."""
        while self.number_of_hawks in [1, 2]:
            self.step()
        return self.number_of_hawks

    def __len__(self):
        return len(self.history)

This carries out the simulations:

repetitions = 10 ** 5
end_states = []
path_lengths = []

for seed in range(repetitions):
    mp = MoranProcess(seed=seed)
    end_states.append(mp.simulate())
    path_lengths.append(len(mp))

counts = collections.Counter(end_states)
counts[3] / repetitions
# ≈ 0.54666

Discuss obtaining theoretic probabilities of changing state:

\[ p_{10}=\frac{6}{12}\frac{1}{3}=\frac{1}{6}\qquad p_{12}=\frac{6}{12}\frac{2}{3}=\frac{1}{3}\qquad p_{21}=\frac{2}{8}\frac{2}{3}=\frac{1}{6}\qquad p_{23}=\frac{6}{8}\frac{1}{3}=\frac{1}{4} \]

Now work through the notes, culminating in the proof of the theorem for the absorption probabilities of a birth–death process.

Discuss and use code from the chapter to show the fixation with the hawk–dove game:

a = np.array([[0, 3], [1, 2]])

Calculate theoretic value using the formula from the theorem:

\[ \begin{align*} f_{1i} &= \frac{3(n-i)}{n - 1} = 3\frac{n-i}{n-1} \\ f_{2i} &= \frac{i + 2(n - i -1)}{n - 1} = \frac{2n - 2 - i}{n - 1} \end{align*} \]

This gives (for \(n=3\)):

\(i=1\) \(i=2\)
\(f_{1i}\) 3 3/2
\(f_{2i}\) 3/2 1
\(\gamma_i\) 1/2 2/3

Thus:

\[ x_1 = \frac{1}{1 + 1/2 + 1/2\times2/3} = \frac{1}{11/6} \approx 0.545455 \]

Discussion

Work through the Moran Process chapter.

Discussion Point: After the definition of the moran process, ask how this differs from our example?

Discussion Point: After the definition of fixation probability, ask what the fixation probability of a hawk is based on our simulation?

Discussion Point: After the theoretic fixation in two types ask how this could be used for our example? Leave this as an exercise.

Close on the last slide. It names what the class was reading and sets the reading for next time. Then run the quick quiz from the Moran Process topic page: five questions on the screen, answered by a show of hands. It takes five minutes and tells us both what landed.

Answers for the deck

Everything below is already derived in the activity above; this is the same material in the order the deck asks for it.

Fitnesses. With one hawk and two doves, \(f(\text{hawk}) = 6\) and \(f(\text{dove}) = 3\). With two hawks and one dove, \(f(\text{hawk}) = 3\) and \(f(\text{dove}) = 2\). So the hawk is fitter when hawks are rare and when they are common, but by a much smaller margin once they are common.

Selection. Birth is proportional to the total fitness of each type; death is uniform, so it is proportional to how many of that type there are.

State Born a hawk Dies a hawk
1 hawk, 2 doves \(6/12 = 1/2\) \(1/3\)
2 hawks, 1 dove \(6/8 = 3/4\) \(2/3\)

The D12. With one hawk, a hawk is born on 1 to 6 and dies on 1 to 4. With two hawks, a hawk is born on 1 to 9 and dies on 1 to 8. Any higher roll chooses a dove.

Transitions. The count only changes when the type born differs from the type that dies:

\[ p_{10} = \tfrac{1}{2}\cdot\tfrac{1}{3} = \tfrac{1}{6}, \qquad p_{12} = \tfrac{1}{2}\cdot\tfrac{2}{3} = \tfrac{1}{3}, \qquad p_{21} = \tfrac{1}{4}\cdot\tfrac{2}{3} = \tfrac{1}{6}, \qquad p_{23} = \tfrac{3}{4}\cdot\tfrac{1}{3} = \tfrac{1}{4}. \]

The remaining probability in each state is the chance of drawing the same type for birth and death, which leaves the state unchanged.

Fixation. With \(\gamma_i = p_{i,i-1}/p_{i,i+1}\) we get \(\gamma_1 = 1/2\) and \(\gamma_2 = 2/3\), so

\[ x_1 = \frac{1}{1 + \gamma_1 + \gamma_1\gamma_2} = \frac{1}{1 + \tfrac{1}{2} + \tfrac{1}{3}} = \frac{6}{11} \approx 0.545. \]

Simulating the students' dice gives about \(0.547\), so a class of twenty pairs should land somewhere near eleven hawk fixations out of twenty. That spread is worth naming: with twenty runs the standard error is about \(0.11\), so anything from roughly 8 to 14 is consistent with the theory.

From the activity to the exam answer

The activity above is written up as a marked exam question: Question 1 (the in-class activity) on the Moran Process page, with a full worked solution. Closing the loop here is the step that helps students who find exams hard: work through that question together, or set it as the immediate follow-up, so they see the game they just played turned into a full-mark answer.

The deck, filled in

Every page of the deck with its boxes completed, built from the same source as the blank deck we project. Click a page to see it full size.

Page 1 of the deck, with the answers written in
Page 1
Page 2 of the deck, with the answers written in
Page 2
Page 3 of the deck, with the answers written in
Page 3
Page 4 of the deck, with the answers written in
Page 4
Page 5 of the deck, with the answers written in
Page 5
Page 6 of the deck, with the answers written in
Page 6
Page 7 of the deck, with the answers written in
Page 7
Page 8 of the deck, with the answers written in
Page 8
Page 9 of the deck, with the answers written in
Page 9
Page 10 of the deck, with the answers written in
Page 10
Page 11 of the deck, with the answers written in
Page 11

Communications

General email templates to send before and after this class. Fill in the bracketed placeholders before sending.

Before class

Hi all,

A reminder that our next Game Theory class covers Moran Processes.

All of the course materials, including the relevant chapter, are available
at https://vknight.org/gt/. It is worth skimming the chapter beforehand.

See you in class,
Vince

After class

Dear all,

Thanks for your work in today's class on Moran Processes.

A recording is available here [RECORDING LINK] and on Learning Central.

All class resources are available at https://vknight.org/gt/.

Thanks,
Vince