## ON MULTI-TYPE CANNINGS MODELS AND MULTI-TYPE EXCHANGEABLE COALESCENTS

Martin Möhle111Mathematisches Institut, Eberhard Karls Universität Tübingen,
Auf der Morgenstelle 10, 72076 Tübingen, Germany, E-mail address:
<EMAIL_ADDRESS>
Date:

###### Abstract

A multi-type neutral Cannings population model with mutation and fixed
subpopulation sizes is analyzed. Under appropriate conditions, as all
subpopulation sizes tend to infinity, the ancestral process, properly time-
scaled, converges to a multi-type exchangeable coalescent with mutation
sharing the exchangeability and consistency property. The proof gains from
coalescent theory for single-type Cannings models and from decompositions into
reproductive and mutational parts. The second part deals with a different but
closely related multi-type Cannings model with mutation and fixed total
population size but stochastically varying subpopulation sizes. The latter
model is analyzed forward and backward in time with an emphasis on its
behaviour as the total population size tends to infinity. Forward in time,
multitype limiting branching processes arise for large population size. Its
backward structure and related open problems are briefly discussed.

Keywords: Consistency; exchangeability; mutation; multi-type branching
process; multi-type Cannings model; multi-type coalescent

2020 Mathematics Subject Classification: Primary 60J90; 60J10 Secondary 92D15;
92D25

##  1 Introduction

Multi-type models play an important role in mathematical population genetics
and evolutionary game theory. Many of the early multi-type population models
belong to the class of multi-type branching processes (Athreya and Ney [2],
Harris [23]) but also different multi-type population models have been studied
in the early literature, for example based on Poissonian or renewal inputs
(Port [38]). In all these models, each individual has a certain type which
determines (the distribution of) the number of offspring of that individual of
any type. In applications, individuals might be objects like genes in biology,
particles in physics or balls in combinatorial urn models. More recent and
more advanced models even allow for genetic forces like selection and
recombination. The reader is referred to the book of Ewens [15] for an
overview on models in mathematical population genetics. We also refer
exemplary to the works of Etheridge [11], Etheridge and Griffiths [12],
Etheridge, Griffiths and Taylor [13] and Griffiths [21] to point to (multi-
type) models including biological forces such as selection and recombination.
We are however interested in the neutral case where neither selection nor
recombination acts in the population. To avoid technical difficulties it is
assumed that the space $E$ of possible types is finite or countable infinite.
Our intension is to study some neutral multi-type population models with non-
overlapping generations and mutation in the spirit of Cannings [8, 9, 10]. In
the first model studied in Section 2, all subpopulation sizes are constant,
whereas in the second model studied in Section 3, the total population size is
constant.

Before we turn to these multi-type models let us mention some fundamental and
well-known results concerning single-type Cannings models. Cannings studied a
population model with non-overlapping generations and a fixed number
$N\in\mathbb{N}:=\\{1,2,\ldots\\}$ of individuals in each generation
$r\in\mathbb{Z}:=\\{\ldots,-1,0,1,\ldots\\}$. Each individual
$i\in[N]:=\\{1,\ldots,N\\}$ alive in generation $r\in\mathbb{Z}$ produces a
random number $\nu_{i,N}^{(r)}$ of offspring and these offspring form the next
generation. It is assumed that, for each generation $r$, the offspring sizes
$\nu_{i,N}^{(r)}$, $i\in[N]$, are exchangeable and that the offspring vectors
$\nu_{N}^{(r)}:=(\nu_{1,N}^{(r)},\ldots,\nu_{N,N}^{(r)})$, $r\in\mathbb{Z}$,
are independent and identically distributed (iid) over the generations. Since
the total population size is assumed to be constant equal to $N$, the relation
$\nu_{1,N}^{(r)}+\cdots+\nu_{N,N}^{(r)}=N$ holds for all generations $r$. We
define $\nu_{i,N}:=\nu_{i,N}^{(0)}$ for convenience for all $N\in\mathbb{N}$
and $i\in[N]$.

We are mainly interested in the ancestral structure of these models. For
$n\in\mathbb{N}$ let ${\cal P}_{n}$ denote the set of partitions of
$[n]:=\\{1,\ldots,n\\}$. Take a sample of $n\in[N]$ individuals from
generation $0$. For each $r\in\mathbb{N}_{0}:=\\{0,1,\ldots\\}$ define a
random partition $\Pi_{r}:=\Pi_{r}^{(n,N)}$ by the property that $i,j\in[n]$
belong to the same block of $\Pi_{r}$ if and only if the individuals $i$ and
$j$ share a common ancestor $r$ generations backward in time. It is well known
that $(\Pi_{r})_{r\in\mathbb{N}_{0}}$ is a time-homogeneous Markov chain with
state space ${\cal P}_{n}$ and initial state $\\{\\{1\\},\ldots,\\{n\\}\\}$.
For $x\in\mathbb{R}$ define $(x)_{0}:=1$ and $(x)_{j}:=x(x-1)\cdots(x-j+1)$
for all $j\in\mathbb{N}$. Transitions from $\pi\in{\cal P}_{n}$ to
$\pi^{\prime}\in{\cal P}_{n}$ are only possible with positive probability if
each block of $\pi^{\prime}$ is a union of some blocks of $\pi$. In this case
the transition probability
$p_{\pi\pi^{\prime}}:=\mathbb{P}(\Pi_{r}=\pi^{\prime}\,|\,\Pi_{r-1}=\pi)$ is
given by (see [35, Eq. (3)])

$p_{\pi\pi^{\prime}}\ =\
\frac{(N)_{j}}{(N)_{i}}\mathbb{E}((\nu_{1,N})_{i_{1}}\cdots(\nu_{j,N})_{i_{j}}),$
(1)

where $i$ and $j$ denote the number of blocks of $\pi$ and $\pi^{\prime}$
respectively and $i_{1},\ldots,i_{j}$ are the group sizes of merging blocks of
$\pi$. Note that $i_{1}+\cdots+i_{j}=i$. The functions
$\Phi_{j}^{(N)}:\\{(k_{1},\ldots,k_{j})\in\mathbb{N}^{j}:k_{1}+\cdots+k_{j}\leq
N\\}\to[0,1]$, $N\in\mathbb{N}$, $j\in[N]$, defined via

$\Phi_{j}^{(N)}(k_{1},\ldots,k_{j})\ :=\
\frac{(N)_{j}}{(N)_{k}}\mathbb{E}((\nu_{1,N})_{k_{1}}\cdots(\nu_{j,N})_{k_{j}})$
(2)

for all $k_{1},\ldots,k_{j}\in\mathbb{N}$ with $k:=k_{1}+\cdots+k_{j}\leq N$,
therefore play a key role in the analysis of the ancestral structure of
Cannings population models. In particular, for
$N\in\mathbb{N}\setminus\\{1\\}$,

$c_{N}\ :=\ \Phi_{1}^{(N)}(2)\ =\ \frac{\mathbb{E}((\nu_{1,N})_{2})}{N-1}\ =\
\frac{{\rm Var}(\nu_{1,N})}{N-1}$ (3)

is the probability that two individuals, randomly sampled from some
generation, share a common ancestor one generation backward in time. This
probability, called the _coalescence probability_ , is of fundamental interest
in coalescent theory, since $1/c_{N}$ is the time-scale in order to obtain
convergence of the ancestral process as the total population size $N$ tends to
infinity. The quantity $N_{e}:=1/c_{N}$ is called the _effective population
size_ of the Cannings model. The transition functions $\Phi_{j}^{(N)}$,
$j\in\mathbb{N}$, satisfy the consistency relation (see [33, Eqs. (3) and
(4)])

$\displaystyle\Phi_{j}^{(N)}(k_{1},\ldots,k_{j})\ =\
\Phi_{j+1}^{(N)}(k_{1},\ldots,k_{j},1)$
$\displaystyle+\sum_{i=1}^{j}\Phi_{j}^{(N)}(k_{1},\ldots,k_{i-1},k_{i}+1,k_{i+1},\ldots,k_{j}),$
(4)

$k_{1},\ldots,k_{j}\in\mathbb{N}$ with $k_{1}+\cdots+k_{j}<N$, and these
functions are monotone in the sense that

$\Phi_{j}^{(N)}(k_{1},\ldots,k_{j})\ \leq\
\Phi_{\ell}^{(N)}(m_{1},\ldots,m_{\ell})$ (5)

for all $1\leq\ell\leq j\leq N$ and
$k_{1},\ldots,k_{j},m_{1},\ldots,m_{\ell}\in\mathbb{N}$ with $k_{1}\geq
m_{1},\ldots,k_{\ell}\geq m_{\ell}$ and $k_{1}+\cdots+k_{j}\leq N$. Note that
(5) follows from (4) by induction on the difference $j-\ell$. The consistency
(4) and the monotonicity (5) play a key role (see, for example, [35]) in the
analysis of the ancestral structure of Cannings models as $N\to\infty$, which
is the main reason why we mention these two properties already in the
introduction.

The paper is organized as follows. In Section 2, a multi-type Cannings model
with fixed subpopulation sizes is introduced and its ancestral structure is
analyzed in detail. The main convergence result (Theorem 1) is provided and
verified in Subsection 2.1. Multi-type exchangeable coalescents with mutation
and their block counting processes are considered in Subsections 2.2 and 2.3
respectively.

A closely related multi-type Cannings model with fixed total population size
but variable subpopulation sizes is studied in Section 3. Subsection 3.1
studies its structure forward in time. A limiting multi-type branching process
is provided in Subsection 3.2. Some backward results on this model are
discussed in Subsection 3.3. Details on the particular multi-type Kimura model
are deferred to Subsection 3.4. The paper finishes with a summary and
discussion of some open problems in Section 4.

##  2 A multi-type Cannings population model with fixed subpopulation sizes

It is assumed that the type space $E$ is finite or countable infinite and that
the number of individuals of type $k\in E$ does not change over the
generations and is hence equal to some given constant $N_{k}\in\mathbb{N}$.
Reproduction within each subpopulation of type $k\in E$ is assumed to take
place according to a neutral Cannings population model (as described in the
introduction) with population size $N_{k}$ and offspring sizes
$\nu_{i,N_{k},k}$, $i\in\\{1,\ldots,N_{k}\\}$. The additional index $k$
indicates that (the distribution of) the number $\nu_{i,N_{k},k}$ of offspring
of the $i$-th individual in subpopulation $k$ is allowed to explicitly depend
on $k$. Offspring sizes in different subpopulations or in different
generations are assumed to be independent.

In each generation, a mutation step follows the reproduction step. A given
number $N_{k\ell}$ of the $N_{k}$ children born in subpopulation $k\in E$
mutate to type $\ell\in E$ with $\ell\neq k$. Note that $\sum_{\ell\neq
k}N_{k\ell}\in\\{0,\ldots,N_{k}\\}$ and that $N_{kk}:=N_{k}-\sum_{\ell\neq
k}N_{k\ell}$ of the children born in subpopulation $k$ do not mutate and,
hence, keep their type $k$. Since the size of each subpopulation is assumed to
be constant, the conservation equalities

$\sum_{\ell\neq k}N_{k\ell}\ =\ \sum_{\ell\neq k}N_{\ell k},\qquad k\in E,$
(6)

are required. Particular models of this form with subpopulation sizes
$N_{k}=2c_{k}N$ for some $c_{k},N\in\mathbb{N}$, and Wright–Fisher
reproduction in each subpopulation have been studied by Notohara [36] and
(Wilkinson–)Herbots [24, 25, 41]. In these works types are interpreted as
colonies and mutation as migration between these colonies.

Each children born in subpopulation $k\in E$ has probability $N_{k\ell}/N_{k}$
to mutate to type $\ell\in E$ with $\ell\neq k$. However, since the
subpopulation sizes are constant, the individuals do not mutate independently.
For any given sample of $n_{k}$ ($\in[N_{k}]$) children taken from the $N_{k}$
children born in subpopulation $k\in E$, and for given integers
$n_{k\ell}\in\mathbb{N}_{0}$, $\ell\neq k$, with $\sum_{\ell\neq
k}n_{k\ell}\leq n_{k}$, the probability that, for all $\ell\in E$ with
$\ell\neq k$, $n_{k\ell}$ of these $n_{k}$ children mutate to type $\ell$, is
given by the multi-hypergeometric expression

$\frac{\prod_{\ell\in E}\binom{N_{k\ell}}{n_{k\ell}}}{\binom{N_{k}}{n_{k}}},$
(7)

where $N_{kk}:=N_{k}-\sum_{\ell\neq k}N_{k\ell}$ and
$n_{kk}:=n_{k}-\sum_{\ell\neq k}n_{k\ell}$ is the number of children in the
sample which do not mutate.

Before the ancestral structure of this model is described, the notion of typed
(or labelled) partitions is introduced. Let $n\in\mathbb{N}$. Each partition
of $[n]$ can be written as $\\{B_{1},\ldots,B_{j}\\}$, where
$B_{1},\ldots,B_{j}$ are the (non-empty) blocks of the partition. Note that
$\bigcup_{i=1}^{j}B_{i}=[n]$. We additionally equip each block $B_{i}$,
$i\in[j]$, with a type $k_{i}\in E$ and call the set ${\cal P}_{n,E}$
consisting of all $\pi:=\\{(B_{1},k_{1}),\ldots,(B_{j},k_{j})\\}$ satisfying
$\\{B_{1},\ldots,B_{j}\\}\in{\cal P}_{n}$ and $k_{1},\ldots,k_{j}\in E$ the
space of typed (or labelled) partitions of $[n]$. Each typed partition of
$[n]$ can be viewed as a usual partition of $[n]$ with the additional property
that each block of the partition is painted with some ‘color’ taken from the
space $E$ of possible ‘colors’. We also call $B_{i}$ a $k_{i}$-block of $\pi$,
$i\in[j]$.

Take a sample of $n\in[N]$ individuals from generation $0$, label them (in
some arbitrary order) from $1$ to $n$, and let $k_{1},\ldots,k_{n}\in E$
denote the types of these individuals. The ancestry of the individuals in the
sample can be traced back as follows. For $r\in\mathbb{N}_{0}$ define a random
typed partition $\Pi_{r}=\Pi_{r}^{(n,(N_{k})_{k\in E})}$ of $[n]$ by the
property that $i,j\in[n]$ belong to the same $k$-block of $\Pi_{r}$ if and
only if the individuals $i$ and $j$ share a common ancestor $r$ generations
backward in time and this ancestor has type $k$. The process
$(\Pi_{r})_{r\in\mathbb{N}_{0}}$ is called a multi-type ancestral process,
sometimes also a multi-type backward process or a multi-type discrete
coalescent process. It is readily checked that
$(\Pi_{r})_{r\in\mathbb{N}_{0}}$ is a time-homogeneous Markov chain with state
space ${\cal P}_{n,E}$ and initial state
$\\{(\\{1\\},k_{1}),\ldots,(\\{n\\},k_{n})\\}$, where $k_{i}\in E$ denotes the
type of individual $i\in[n]$. Let
$p_{\pi\pi^{\prime}}:=\mathbb{P}(\Pi_{r}=\pi^{\prime}\,|\,\Pi_{r-1}=\pi)$,
$\pi,\pi^{\prime}\in{\cal P}_{n,E}$, denote the transition probabilities. From
the two-step definition of the model it follows that the transition matrix
$P:=(p_{\pi\pi^{\prime}})_{\pi,\pi^{\prime}\in{\cal P}_{n,E}}$ has the product
form

$P\ =\ P^{\rm mut}P^{\rm rep},$ (8)

where $P^{\rm mut}$ denotes the transition matrix of the ancestral process for
the model without reproduction, i.e. for the model with $\nu_{i,N_{k},k}=1$
almost surely for all $k\in E$ and all $i\in\\{1,\ldots,N_{k}\\}$, and $P^{\rm
rep}$ denotes the transition matrix of the ancestral process for the model
without mutation, i.e. for the model with $N_{k\ell}=0$ for all $k,\ell\in E$
with $k\neq\ell$.

For the model without mutation, transitions from $\pi\in{\cal P}_{n,E}$ to
$\pi^{\prime}\in{\cal P}_{n,E}$ are only possible with positive probability if
each $k$-block of $\pi^{\prime}$ is a union of some $k$-blocks of $\pi$. In
this case, since offspring numbers in different subpopulations are
independent, it follows that

$p_{\pi\pi^{\prime}}^{\rm rep}\ =\ \prod_{k\in
E}\Phi_{j_{k}}^{(k,N_{k})}(i_{k,1},\ldots,i_{k,j_{k}}),$ (9)

where $i_{k}$ and $j_{k}$ are the number of $k$-blocks of $\pi$ and
$\pi^{\prime}$ respectively, $i_{k,1},\ldots,i_{k,j_{k}}$ are the group sizes
of merging $k$-blocks of $\pi$, and

$\displaystyle\Phi_{j_{k}}^{(k,N_{k})}(i_{k,1},\ldots,i_{k,j_{k}})$ (10)
$\displaystyle:=$
$\displaystyle\frac{(N_{k})_{j_{k}}}{(N_{k})_{i_{k}}}\mathbb{E}\big{(}(\nu_{1,N_{k},k})_{i_{k,1}}\cdots(\nu_{j_{k},N_{k},k})_{i_{k,j_{k}}}\big{)}.$

Note that $i_{k,1}+\cdots+i_{k,j_{k}}=i_{k}$.

For $k,\ell\in E$, the backward mutation probability $m_{k\ell}$, which is by
definition the proportion of the individuals in subpopulation $k$ after the
mutation step, who where born in subpopulation $\ell$, is

$m_{k\ell}\ :=\ \frac{N_{\ell k}}{N_{k}}\qquad k,\ell\in E.$ (11)

where $N_{kk}:=N_{k}-\sum_{\ell\neq k}N_{\ell k}$. Note that $m_{kk}$ is the
proportion of the individuals in subpopulation $k$, who did not undergo a
mutation during the mutation step.

For the model without reproduction, the entries of the matrix $P^{\rm mut}$
are obtained as follows. Let $\pi,\pi^{\prime}\in{\cal P}_{n,E}$. A mutational
transition from $\pi$ to $\pi^{\prime}$ backward in time is only possible with
positive probability if $\pi^{\prime}$ has the same blocks as $\pi$. For
$k,\ell\in E$ let $n_{k\ell}$ denote the number of blocks being a $k$-block of
$\pi$ and a $\ell$-block of $\pi^{\prime}$. Then,

$p_{\pi\pi^{\prime}}^{\rm mut}\ =\ \prod_{k\in E}\frac{\prod_{\ell\in
E}(N_{\ell k})_{n_{k\ell}}}{(N_{k})_{n_{k}}},$ (12)

where $n_{k}:=\sum_{\ell\in E}n_{k\ell}$ denotes the number of $k$-blocks of
$\pi$. For example, if $\pi=\\{([n],k)\\}$ and $\pi^{\prime}=\\{([n],\ell)\\}$
for some $k,\ell\in E$, then (12) reduces to the backward mutation rate
$m_{k\ell}$ defined in (11). If all the $N_{k\ell}$ are sufficiently large,
then there is essentially no difference between sampling without replacement
and sampling with replacement, leading to the approximation

$p_{\pi\pi^{\prime}}^{\rm mut}\ \approx\ \prod_{k,\ell\in
E}\bigg{(}\frac{N_{\ell k}}{N_{k}}\bigg{)}^{n_{k\ell}}\ =\ \prod_{k,\ell\in
E}m_{k\ell}^{n_{k\ell}}.$ (13)

###  2.1 A limiting multi-type coalescent

To avoid technical difficulties it is in this section mainly assumed that the
number of types is finite, i.e. $|E|<\infty$. The case of countable infinite
type space $E$ is briefly discussed in Remark 3 at the end of this section.

We are interested in the behavior of the ancestral process
$(\Pi_{r}^{(n,(N_{k})_{k\in E})})_{r\in\mathbb{N}_{0}}$ as all subpopulation
sizes $N_{k}$, $k\in E$, become large, that is, as

$N\ :=\ \min_{k\in E}N_{k}\ \to\ \infty.$ (14)

In order to state a convergence result, a couple of assumptions are imposed,
which are described in the following. Let us start with the assumptions
concerning the Cannings reproduction models acting in each subpopulation. For
$k\in E$ let

$c_{k}(N_{k})\ :=\ \frac{{\rm Var}(\nu_{1,N_{k},k})}{N_{k}-1}$ (15)

denote the coalescence probability of the Cannings model acting in
subpopulation $k$ with population size $N_{k}>1$. It is assumed that
$c_{k}(N_{k})>0$ for all sufficiently large $N_{k}$. Note that
$c_{k}(N_{k})=0$ if and only if $\nu_{1,N_{k},k}=1$ almost surely. For every
subpopulation $k\in E$, it is assumed that all the limits

$\phi_{j}^{(k)}(i_{1},\ldots,i_{j})\ :=\
\lim_{N_{k}\to\infty}\frac{\Phi_{j}^{(k,N_{k})}(i_{1},\ldots,i_{j})}{c_{k}(N_{k})},$
(16)

$j,i_{1},\ldots,i_{j}\in\mathbb{N}$ with $i_{1},\ldots,i_{j}\geq 2$, exist,
where

$\Phi_{j}^{(k,N_{k})}(i_{1},\ldots,i_{j})\ :=\
\frac{(N_{k})_{j}}{(N_{k})_{i}}\mathbb{E}((\nu_{1,N_{k},k})_{i_{1}}\cdots(\nu_{j,N_{k},k})_{i_{j}}).$

for all $j\in[N_{k}]$ and $i_{1},\ldots,i_{j}\in\mathbb{N}$ with
$i:=i_{1}+\cdots+i_{j}\leq N_{k}$. The existence of the limits (16) is a
relatively mild condition, since, by the monotonicity property,
$\Phi_{j}^{(k,N_{k})}(i_{1},\ldots,i_{j})\leq\Phi_{1}^{(k,N_{k})}(2)=c_{k}(N_{k})$
for all $i_{1},\ldots,i_{j}\geq 2$ which shows that the fraction on the right-
hand side of (16) is bounded between $0$ and $1$. Moreover, if the limits (16)
exist for all $j,i_{1},\ldots,i_{j}\in\mathbb{N}$ with $i_{1},\ldots,i_{j}\geq
2$, then these limits exist for the wider range of parameters
$j,i_{1},\ldots,i_{j}\in\mathbb{N}$ satisfying $i_{1}+\cdots+i_{j}>j$, which
follows readily from the consistency relation of the functions
$\Phi_{j}^{(k,N_{k})}$, $j\in[N_{k}]$, by induction on the number of $1$’s
among the $i_{1},\ldots,i_{j}$. In this case also the limits

$\phi_{j}^{(k)}(1,\ldots,1)\ :=\
\lim_{N_{k}\to\infty}\frac{\Phi_{j}^{(k,N_{k})}(1,\ldots,1)-1}{c_{k}(N_{k})},$
(17)

$j\in\mathbb{N}$, exist. For each $k\in E$, the consistency relations and the
monotonicity property of the functions $\Phi_{j}^{(k,N_{k})}$, $j\in[N_{k}]$,
carry over to the limits $\phi_{j}^{(k)}$, $j\in\mathbb{N}$. More precisely,
for all $k\in E$ and $j,i_{1},\ldots,i_{j}\in\mathbb{N}$,

$\displaystyle\phi_{j}^{(k)}(i_{1},\ldots,i_{j})\ =\
\phi_{j+1}^{(k)}(i_{1},\ldots,i_{j},1)$
$\displaystyle+\sum_{m=1}^{j}\phi_{j}^{(k)}(i_{1},\ldots,i_{m-1},i_{m},i_{m+1},\ldots,i_{j})$

and

$\phi_{j}^{(k)}(i_{1},\ldots,i_{j})\ \leq\
\phi_{\ell}^{(k)}(m_{1},\ldots,m_{\ell})$

for all $\ell,j\in\mathbb{N}$ with $\ell\leq j$ and
$i_{1},\ldots,i_{j},m_{1},\ldots,m_{\ell}\in\mathbb{N}$ with $i_{1}\geq
m_{1},\ldots,i_{\ell}\geq m_{\ell}$.

A more delicate calibration assumption on the coalescence probabilities
$c_{k}(N_{k})$, $k\in E$, is needed. Recall that $N:=\min_{k\in
E}N_{k}\in\mathbb{N}$. It is assumed that there exists a sequence
$(c_{N})_{N\in\mathbb{N}}$ of positive real numbers such that, for all $k\in
E$,

$\frac{c_{k}(N_{k})}{c_{N}}\ \to\ d_{k},\qquad N\to\infty,$ (18)

for some constant $d_{k}\geq 0$.

The assumptions on the mutation parameters are standard. It is assumed that,
for all types $k,\ell\in E$ with $k\neq\ell$, the backward mutation rate
$m_{k\ell}=m_{k\ell}(N)$ depends on $N$ in such a way that

$\frac{m_{k\ell}(N)}{c_{N}}\ \to\ \rho_{k\ell},\qquad N\to\infty,$ (19)

for some constant $\rho_{k\ell}\geq 0$.

Under these assumptions, for a given sample size $n\in\mathbb{N}$, two
generator matrices $Q^{\rm rep}$ and $Q^{\rm mut}$ can be defined as follows.
Let

$Q^{\rm rep}\ :=\ (q_{\pi\pi^{\prime}}^{\rm rep})_{\pi,\pi^{\prime}\in{\cal
P}_{n,E}}$ (20)

denote the generator matrix with the following entries. Let
$\pi,\pi^{\prime}\in{\cal P}_{n,E}$ with $\pi\neq\pi^{\prime}$ and such that
each $k$-block of $\pi^{\prime}$ is a union of some $k$-blocks of $\pi$. Let
$i_{k}$ and $j_{k}$ denote the number of $k$-blocks of $\pi$ and
$\pi^{\prime}$ respectively, and let $i_{k,1},\ldots,i_{k,j_{k}}$ denote the
group sizes of merging $k$-blocks of $\pi$. Note that
$i_{k,1}+\cdots+i_{k,j_{k}}=i_{k}$. If there exists exactly one $k\in E$ with
$i_{k}>j_{k}$, then

$q_{\pi\pi^{\prime}}^{\rm rep}\ :=\
d_{k}\phi_{j_{k}}^{(k)}(i_{k,1},\ldots,i_{k,j_{k}}).$ (21)

All other non-diagonal entries of $Q^{\rm rep}$ are (by definition) equal to
$0$.

The second generator matrix

$Q^{\rm mut}\ :=\ (q_{\pi\pi^{\prime}}^{\rm mut})_{\pi,\pi^{\prime}\in{\cal
P}_{n,E}}$ (22)

is defined as follows. Let
$\pi=\\{(B_{1},k_{1}),\ldots,(B_{j},k_{j})\\}\in{\cal P}_{n,E}$. If
$\pi^{\prime}$ is identical to $\pi$, except for the fact that only one single
block of $\pi^{\prime}$, say $B_{i}$, has a type $\ell_{i}$ different from
$k_{i}$, then

$q_{\pi\pi^{\prime}}^{\rm mut}\ :=\ \rho_{k_{i}\ell_{i}}.$ (23)

All other non-diagonal entries of $Q^{\rm mut}$ are (by definition) equal to
$0$. Note that $q_{\pi\pi}^{\rm mut}=-\sum_{i=1}^{j}\rho_{k_{i}\ell_{i}}$.

We now state the main convergence result. Recall that the type space $E$ is
assumed to be finite and that $N:=\min_{k\in E}N_{k}$.

######  Theorem 1 (Convergence to multi-type coalescents).

Assume that the following three assumptions hold.

  1. (i)

Reproduction assumption: For every $k\in E$ the limits (16) exist for all
$j,i_{1},\ldots,i_{j}\in\mathbb{N}$ with $i_{1},\ldots,i_{j}\geq 2$.

  2. (ii)

Calibration assumption: There exist positive real numbers $c_{1},c_{2},\ldots$
such that, for every $k\in E$, (18) holds for some constant $d_{k}\geq 0$.

  3. (iii)

Mutation assumption: For any two types $k,\ell\in E$ with $k\neq\ell$, the
backward mutation rate $m_{k\ell}=m_{k\ell}(N)$ depends on $N:=\min_{k\in
E}N_{k}$ in such a way that (19) holds for some constant $\rho_{k\ell}\geq 0$
as $N\to\infty$.

Sample $n\in\mathbb{N}$ individuals from generation $0$, label them randomly
from $1$ to $n$, and let $k_{1},\ldots,k_{n}\in E$ denote the types of these
individuals. Then, the following statement holds.

If $c_{N}\to 0$, then the time-scaled multi-type ancestral process
$(\Pi_{\lfloor t/c_{N}\rfloor}^{(n,(N_{k})_{k\in E})})_{t\geq 0}$ converges in
$D_{{\cal P}_{n,E}}([0,\infty))$ as $N\to\infty$ to a continuous-time limiting
Markov process $(\Pi_{t}^{(n)})_{t\geq 0}$ with state space ${\cal P}_{n,E}$,
initial state $\\{(\\{1\\},k_{1}),\ldots,(\\{n\\},k_{n})\\}$ and infinitesimal
generator

$Q\ =\ Q^{\rm rep}+Q^{\rm mut},$

where $Q^{\rm rep}$ and $Q^{\rm mut}$ are the matrices (20) and (22)
respectively.

######  Remark 1.

Due to the structure of the entries (21) of the generator $Q^{\rm rep}$, the
continuous-time limiting process $\Pi^{(n)}:=(\Pi_{t}^{(n)})_{t\geq 0}$
arising in Theorem 1 allows for simultaneous multiple mergers of ancestral
lineages in one arbitrary subpopulation but not at the same time in more than
one subpopulation. During each mutational transition, the process $\Pi^{(n)}$
only allows for a change of the type of one single block. For $|E|=1$, Theorem
1 essentially reduces to Theorem 2.1 of [35]. A convergence result for the
situation when $c_{N}\to c>0$ is provided in Theorem 2 below.

###### Proof.

Let $\pi,\pi^{\prime}\in{\cal P}_{n,E}$ with $\pi\neq\pi^{\prime}$ and such
that each $k$-block of $\pi^{\prime}$ is a union of some $k$-blocks of $\pi$.
Then, by (9),

$\frac{p_{\pi\pi^{\prime}}^{\rm rep}}{c_{N}}\ =\ \frac{1}{c_{N}}\prod_{k\in
E}\Phi_{j_{k}}^{(k,N_{k})}(i_{k,1},\ldots,i_{k,j_{k}}).$

If there exists exactly one $k\in E$ with $i_{k,1}+\cdots+i_{k,j_{k}}>j_{k}$,
then

$\displaystyle\frac{p_{\pi\pi^{\prime}}^{\rm rep}}{c_{N}}$ $\displaystyle=$
$\displaystyle\frac{\Phi_{j_{k}}^{(k,N_{k})}(i_{k,1},\ldots,i_{k,j_{k}})}{c_{N}}\prod_{\ell\neq
k}\Phi_{j_{\ell}}^{(\ell,N_{\ell})}(1,\ldots,1)$ $\displaystyle\to$
$\displaystyle d_{k}\phi_{j_{k}}^{(k)}(i_{k,1},\ldots,i_{k,j_{k}})\ =\
q_{\pi\pi^{\prime}}^{\rm rep}$

by (16) and the comments thereafter. If $\pi^{\prime}$ is such that in at
least two different subpopulations a true merger event takes place, then
$p_{\pi\pi^{\prime}}^{\rm rep}/c_{N}\to 0=q_{\pi\pi^{\prime}}^{\rm rep}$ as
$N\to\infty$. Moreover,

$\frac{1-p_{\pi\pi}^{\rm rep}}{c_{N}}\ =\
\sum_{\pi^{\prime}\neq\pi}\frac{p_{\pi\pi^{\prime}}^{\rm rep}}{c_{N}}\ \to\
\sum_{\pi^{\prime}\neq\pi}q_{\pi\pi^{\prime}}^{\rm rep}\ =\ -q_{\pi\pi}^{\rm
rep}$

as $N\to\infty$. Thus,

$P^{\rm rep}\ =\ I+c_{N}Q^{\rm rep}+o(c_{N}),\qquad N\to\infty.$

Let us now turn to $P^{\rm mut}$. Let
$\pi=\\{(B_{1},k_{1}),\ldots,(B_{j},k_{j})\\}\in{\cal P}_{n,E}$. If
$\pi^{\prime}$ is identical to $\pi$, except for the fact that there exists
exactly one single block of $\pi^{\prime}$, say $B_{i}$, which has a type
$\ell_{i}$ different from $k_{i}$, then it follows from (12) and the
assumption that all the limits (19) exist, that

$\displaystyle\frac{p_{\pi\pi^{\prime}}^{\rm mut}}{c_{N}}$ $\displaystyle\sim$
$\displaystyle\frac{1}{c_{N}}\prod_{k,\ell\in E}(m_{k\ell}(N))^{n_{k\ell}}\ =\
\frac{m_{k_{i}\ell_{i}}(N)}{c_{N}}$ $\displaystyle\to$
$\displaystyle\rho_{k_{i}\ell_{i}}\ =\ q_{\pi\pi^{\prime}}^{\rm mut},\qquad
N\to\infty.$

Thus, $P^{\rm mut}=I+c_{N}Q^{\rm mut}+o(c_{N})$ as $N\to\infty$. The
transition matrix (8) of the ancestral process therefore has the asymptotic
expansion

$\displaystyle P$ $\displaystyle=$ $\displaystyle P^{\rm mut}P^{\rm rep}$
$\displaystyle=$ $\displaystyle(I+c_{N}Q^{\rm mut}+o(c_{N}))(I+c_{N}Q^{\rm
rep}+o(c_{N}))$ $\displaystyle=$ $\displaystyle I+c_{N}Q+o(c_{N}),\qquad
N\to\infty,$

where $Q:=Q^{\rm rep}+Q^{\rm mut}$. Let $\|.\|$ denote the matrix norm defined
via $\|A\|:=\sup_{\pi}\sum_{\pi^{\prime}}|a_{\pi\pi^{\prime}}|$ for all
$A=(a_{\pi\pi^{\prime}})_{\pi,\pi^{\prime}\in{\cal P}_{n,E}}$. It follows for
all $t\geq 0$ that $\|P^{\lfloor t/c_{N}\rfloor}-(I+c_{N}Q)^{\lfloor
t/c_{N}\rfloor}\|\leq\lfloor t/c_{N}\rfloor\|P-(I+c_{N}Q)\|\to 0$ as
$N\to\infty$, which shows that $P^{\lfloor
t/c_{N}\rfloor}\sim(I+c_{N}Q)^{\lfloor t/c_{N}\rfloor}\to e^{tQ}$ as
$N\to\infty$. Thus, the convergence of the one-dimensional distributions is
established. The convergence of the finite-dimensional distributions follows
by exploiting the Markov property of the involved processes.

It remains to verify the convergence in $D_{{\cal P}_{n,E}}([0,\infty))$. For
$t\geq 0$, $f:{\cal P}_{n,E}\to\mathbb{R}$ and $\pi\in{\cal P}_{n,E}$ define

$\displaystyle Sf(\pi)$ $\displaystyle:=$
$\displaystyle\mathbb{E}(f(\Pi_{r}^{(n,(N_{k})_{k\in
E})})\,|\,\Pi_{r-1}^{(n,(N_{k})_{k\in E})}=\pi)$ $\displaystyle=$
$\displaystyle\sum_{\pi^{\prime}\in{\cal
P}_{n,E}}f(\pi^{\prime})p_{\pi\pi^{\prime}}$

and $T_{t}f(\pi):=\sum_{\pi^{\prime}\in{\cal
P}_{n,E}}f(\pi^{\prime})(e^{tQ})_{\pi\pi^{\prime}}$. Note that the operator
$S$ depends on $n$ and $(N_{k})_{k\in E}$ and that
$S^{m}f(\pi)=\sum_{\pi^{\prime}\in{\cal
P}_{n,E}}f(\pi^{\prime})(P^{m})_{\pi\pi^{\prime}}$ for $m\in\mathbb{N}_{0}$
and that $\\{T_{t}\\}_{t\geq 0}$ is a (Feller) semigroup on the space $L$ of
all functions $f:{\cal P}_{n,E}\to\mathbb{R}$ with (conservative) generator
$Af(\pi):=\sum_{\pi^{\prime}\in{\cal
P}_{n,E}}f(\pi^{\prime})q_{\pi\pi^{\prime}}$. Since $|{\cal P}_{n,E}|<\infty$,
it follows for all $t\geq 0$ and $f\in L$ that

$\displaystyle\|S^{\lfloor t/c_{N}\rfloor}f-T_{t}f\|\ :=\ \sup_{\pi\in{\cal
P}_{n,E}}|S^{\lfloor t/c_{N}\rfloor}f(\pi)-T_{t}f(\pi)|$ $\displaystyle\leq$
$\displaystyle\sup_{\pi\in{\cal P}_{n,E}}\sum_{\pi^{\prime}\in{\cal
P}_{n,E}}|f(\pi^{\prime})||(S^{\lfloor
t/c_{N}\rfloor})_{\pi\pi^{\prime}}-(e^{tQ})_{\pi\pi^{\prime}}|$
$\displaystyle\leq$ $\displaystyle\|f\|\sup_{\pi\in{\cal
P}_{n,E}}\sum_{\pi^{\prime}\in{\cal P}_{n,E}}|(P^{\lfloor
t/c_{N}\rfloor})_{\pi\pi^{\prime}}-(e^{tQ})_{\pi\pi^{\prime}}|$
$\displaystyle=$ $\displaystyle\|f\|\,\|P^{\lfloor t/c_{N}\rfloor}-e^{tQ}\|\
\to\ 0,\qquad N\to\infty.$

The convergence in $D_{{\cal P}_{n,E}}([0,\infty))$ to a Markov process
$(\Pi_{t}^{(n)})_{t\geq 0}$ with initial state
$\\{(\\{1\\},k_{1}),\ldots,(\\{n\\},k_{n})\\}$ and corresponding (Feller)
semigroup $\\{T_{t}\\}_{t\geq 0}$ thus follows from Ethier and Kurtz [14, p.
168, Theorem 2.6], applied with $E$ there replaced by ${\cal P}_{n,E}$,
$\varepsilon_{N}:=c_{N}$ and $Y_{N}(r)$ there replaced by
$\Pi_{r}^{{(n,(N_{k})_{k\in E})}}$, $r\in\mathbb{N}_{0}$. ∎

  * Example. (Multi-type Kingman $n$-coalescent) Assume that Wright–Fisher reproduction acts in each subpopulation. Then, the coalescence probability in subpopulation $k\in E$ is given by $c_{k}(N_{k})=1/N_{k}$. For simplicity it is assumed that the population sizes are all equal to $N_{k}=N\in\mathbb{N}$. Then the calibration assumption (ii) of Theorem 1 obviously holds with $c_{N}:=1/N>0$ and $d_{k}:=1$. Clearly, $c_{N}\to 0$ as $N\to\infty$. From $\Phi_{j}^{(k)}(i_{1},\ldots,i_{j})=(N_{k})_{j}/N_{k}^{i}$ for all $j,i_{1},\ldots,i_{j}\in\mathbb{N}$, where $i:=i_{1}+\cdots+i_{j}$, it follows that the reproduction assumption (i) holds with $\phi_{1}^{(k)}(2)=1$. All other limits in (16) are equal to $0$. Thus, Theorem 1 is applicable. The limiting process in Theorem 1 is a multi-type Kingman $n$-coalescent in the sense that single binary mergers of two ancestral lineages of the same type occur with rate $1$. Note that binary mergers at the same time in more than one subpopulation are impossible.

In some cases the sequence $(c_{N})_{N\in\mathbb{N}}$ does not converge to $0$
(as assumed in Theorem 1) but to a positive constant $c>0$. In this situation
the following time-discrete variant of Theorem 1 holds.

######  Theorem 2.

Suppose that the assumptions (i), (ii) and (iii) of Theorem 1 hold. Take a
sample of $n\in\mathbb{N}$ individuals from generation $0$ and let
$k_{1},\ldots,k_{n}\in E$ denote their types. Then the following statement
holds.

If $c_{N}\to c>0$ as $N\to\infty$, then the multi-type ancestral process
$(\Pi_{r}^{(n,(N_{k})_{k\in E})})_{r\in\mathbb{N}_{0}}$ converges in $D_{{\cal
P}_{n,E}}(\mathbb{N}_{0})$ as $N\to\infty$ to a discrete-time limiting Markov
process $(\Pi_{r}^{(n)})_{r\in\mathbb{N}_{0}}$ with state space ${\cal
P}_{n,E}$, initial state $\\{(\\{1\\},k_{1}),\ldots,(\\{n\\},k_{n})\\}$ and
transition matrix

$A\ :=\ A^{\rm mut}A^{\rm rep},$

where the two stochastic matrices $A^{\rm mut}=(a_{\pi\pi^{\prime}}^{\rm
mut})_{\pi,\pi^{\prime}\in{\cal P}_{n,E}}$ and $A^{\rm
rep}=(a_{\pi\pi^{\prime}}^{\rm rep})_{\pi,\pi^{\prime}\in{\cal P}_{n,E}}$ are
defined as follows.

If $\pi^{\prime}$ has the same blocks as $\pi$, then

$a_{\pi\pi^{\prime}}^{\rm mut}\ :=\ \prod_{k,\ell\in
E}(c\rho_{k\ell})^{n_{k\ell}},$

where $n_{k\ell}$ denotes the number of blocks being a $k$-block of $\pi$ and
an $\ell$-block of $\pi^{\prime}$. All other entries of $A^{\rm mut}$ are (by
definition) equal to $0$.

Let $\pi,\pi^{\prime}\in{\cal P}_{n,E}$ with $\pi\neq\pi^{\prime}$ and such
that each $k$-block of $\pi^{\prime}$ is a union of some $k$-blocks of $\pi$.
Let $i_{k}$ and $j_{k}$ denote the number of $k$-blocks of $\pi$ and
$\pi^{\prime}$ respectively, and let $i_{k,1},\ldots,i_{k,j_{k}}$ denote the
group sizes of merging $k$-blocks of $\pi$. Then,

$a_{\pi\pi^{\prime}}^{\rm rep}\ :=\ \prod_{k\in
E}\big{(}cd_{k}\phi_{j_{k}}^{(k)}(i_{k,1},\ldots,i_{k,j_{k}})\big{)}.$

All other non-diagonal entries of $A^{\rm rep}$ are (by definition) equal to
$0$.

######  Remark 2.

In contrast to the continuous-time limiting process in Theorem 1, the
discrete-time limiting process
$\Pi^{(n)}:=(\Pi_{r}^{(n)})_{r\in\mathbb{N}_{0}}$ arising in Theorem 2 allows
for simultaneous multiple mergers of ancestral lineages at the same time in
more than one subpopulation. During each transition, the process $\Pi^{(n)}$
also allows for a change of the type of more than one single block.

###### Proof.

If $\pi^{\prime}$ has the same blocks as $\pi$, then, by (12),

$\displaystyle p_{\pi\pi^{\prime}}^{\rm mut}$ $\displaystyle=$
$\displaystyle\prod_{k\in E}\frac{\prod_{\ell\in E}(N_{\ell
k})_{n_{k\ell}}}{(N_{k})_{n_{k}}}\ \sim\ \prod_{k,\ell\in
E}(m_{k\ell}(N))^{n_{k\ell}}$ $\displaystyle\to$
$\displaystyle\prod_{k,\ell\in E}(c\rho_{k\ell})^{n_{k\ell}}\ =\
a_{\pi\pi^{\prime}}^{\rm mut}$

as $N\to\infty$. This shows that $P^{\rm mut}\to A^{\rm mut}$ as $N\to\infty$.
Similarly, if $\pi\neq\pi^{\prime}$ are such that each $k$-block of
$\pi^{\prime}$ is a union of some $k$-blocks of $\pi$, then, by (9),

$\displaystyle p_{\pi\pi^{\prime}}^{\rm rep}$ $\displaystyle=$
$\displaystyle\prod_{k\in
E}\Phi_{j_{k}}^{(k,N_{k})}(i_{k,1},\ldots,i_{k,j_{k}})$ $\displaystyle\to$
$\displaystyle\prod_{k\in
E}\big{(}cd_{k}\phi_{j_{k}}^{(k)}(i_{k,1},\ldots,i_{k,j_{k}})\big{)}\ =\
a_{\pi\pi^{\prime}}^{\rm rep}$

as $N\to\infty$, showing that $P^{\rm rep}\to A^{\rm rep}$ as $N\to\infty$. It
follows that $P=P^{\rm mut}P^{\rm rep}\to A^{\rm mut}A^{\rm rep}=A$ as
$N\to\infty$. Due to the Markov property of the involved processes, the
convergence of the finite-dimensional distributions follows immediately. For
processes with discrete time set $\mathbb{N}_{0}$, the convergence of the
finite-dimensional distributions is equivalent (see, for example, Billingsley
[3, p. 19]) to the convergence in $D_{{\cal P}_{n,E}}(\mathbb{N}_{0})$. ∎

######  Remark 3 (Countable type space).

Assume that the type space $E$ is countable infinite. Then we conjecture that
Theorem 1 remains valid under the additional assumption that
$\rho_{k}:=\sum_{\ell\in E,\ell\neq k}\rho_{k\ell}<\infty$ for all $k\in E$.
Since the state space ${\cal P}_{n,E}$ is not finite anymore, one can however
not simply follow the proof for the finite type space case. Instead one may
verify the relative compactness of the processes $(\Pi_{\lfloor
t/c_{N}\rfloor}^{(n,(N_{k})_{k\in E})})_{t\geq 0}$, $(N_{k})_{k\in E}$, via
similar techniques as in the proof of Theorem 2.1 of Herbots [24]. The
convergence in $D_{{\cal P}_{n,E}}([0,\infty))$ then follows from Ethier and
Kurtz [14, p. 131, Theorem 7.8].

###  2.2 Multi-type coalescent with mutation

It is not hard to check that the limiting process
$\Pi^{(n)}=(\Pi_{t}^{(n)})_{t\geq 0}$ arising in Theorem 1 is exchangeable in
the sense that the distribution of $\Pi^{(n)}$ is invariant under relabelling
of the $n$ individuals. We call $\Pi^{(n)}$ a _continuous-time multi-type
exchangeable $n$-coalescent with mutation_.

From the consistency relation it follows that the family of processes
$\\{\Pi^{(n)}:n\in\mathbb{N}\\}$ is consistent, that is, for all
$n,m\in\mathbb{N}$ with $m\leq n$, the projected process
$(\varrho_{nm}\circ\Pi_{t}^{(n)})_{t\geq 0}$ has the same distribution as
$(\Pi_{t}^{(m)})_{t\geq 0}$, where $\varrho_{nm}:{\cal P}_{n,E}\to{\cal
P}_{m,E}$ denotes the natural projection from ${\cal P}_{n,E}$ to ${\cal
P}_{m,E}$ defined via $\varrho_{nm}(\pi):=\\{(B_{i}\cap[m],k_{i}):1\leq i\leq
j,B_{i}\cap[m]\neq\emptyset\\}$ for all
$\pi=\\{(B_{1},k_{1}),\ldots,(B_{j},k_{j})\\}\in{\cal P}_{n,E}$. Exploiting
Kolmogorov’s extension theorem it can be shown that there exists a process
$\Pi=(\Pi_{t})_{t\geq 0}$ (the projective limit of the sequence
$(\Pi^{(n)})_{n\in\mathbb{N}}$) with state space ${\cal P}_{\infty,E}$, the
space of labelled partitions of $\mathbb{N}$, such that for every
$n\in\mathbb{N}$, $(\varrho_{n}\circ\Pi_{t})_{t\geq 0}$ is a multi-type
exchangeable $n$-coalescent with mutation and the same infinitesimal rates,
where $\varrho_{n}:{\cal P}_{\infty,E}\to{\cal P}_{n,E}$ denotes the natural
projection from ${\cal P}_{\infty,E}$ to ${\cal P}_{n,E}$ defined via
$\varrho_{n}(\pi):=\\{(B\cap[n],k):(B,k)\in\pi,B\cap[n]\neq\emptyset\\}$ for
all $\pi\in{\cal P}_{\infty,E}$. We call the process $\Pi$ a _multi-type
exchangeable coalescent with mutation_.

From the work of Schweinsberg [39] it follows that for every $k\in E$ there
exists a unique finite measure $\Xi_{k}$ on the infinite simplex
$\Delta:=\\{x=(x_{i})_{i\in\mathbb{N}}:x_{1}\geq x_{2}\geq\cdots\geq
0,\sum_{i\in\mathbb{N}}x_{i}\leq 1\\}$ such that the infinitesimal rate limits
in (16) have the integral representation

$\displaystyle\phi_{j}^{(k)}(i_{1},\ldots,i_{j})\ =\
a_{k}1_{\\{j=1,i_{1}=2\\}}$
$\displaystyle+\int_{\Delta\setminus\\{0\\}}\sum_{m_{1}\neq\cdots\neq
m_{j}}x_{m_{1}}^{i_{1}}\cdots x_{m_{j}}^{i_{j}}\frac{\Xi_{k}({\rm
d}x)}{(x,x)},$

$i_{1},\ldots,i_{j}\geq 2$, where $a_{k}:=\Xi_{k}(\\{0\\})$ denotes the mass
of $\Xi_{k}$ at $0\in\Delta$ and $(x,x):=\sum_{i\in\mathbb{N}}x_{i}^{2}$ for
$x=(x_{i})_{i\in\mathbb{N}}\in\Delta$. The distribution of $\Pi$ is hence
fully described by the sequence of measures $\Xi=(\Xi_{k})_{k\in E}$, the
calibration constants $d_{k}\geq 0$, $k\in E$, and the mutation parameters
$\rho_{k\ell}$, $k\neq\ell$. We therefore call the process $\Pi$ also a
(multi-type) $\Xi$-coalescent (with mutation). The process $\Pi$ is the
natural generalization of (single-type) exchangeable (and consistent)
coalescents to the multi-type case. If all the measures $\Xi_{k}$, $k\in E$,
are concentrated on the subset $[0,1]\times\\{0\\}\times\\{0\\}\times\cdots$
of $\Delta$, then we speak of a _multi-type $\Lambda$-coalescent with
mutation_, where $\Lambda:=(\Lambda_{k})_{k\in E}$ and the finite measure
$\Lambda_{k}$ on $[0,1]$ is defined via
$\Lambda_{k}(B):=\Xi_{k}(B\times\\{0\\}\times\\{0\\}\times\cdots)$ for all
Borel sets $B\subseteq[0,1]$.

For a recent paper dealing with multi-type $\Lambda$-coalescents of this form
(and as well non-consistent multi-type $\Lambda$-coalescents) we refer the
reader to Johnston, Kyprianou and Rogers [27]. If $d_{k}\Xi_{k}=0$ is the zero
measure, then there is no reproductive activity in subpopulation $k$, which
may be interpreted as a sleeping seed bank. The ancestral structure of seed
bank models has gained some interest in the literature (see, for example,
Blath et al. [5, 6] or González Casanova et al. [17]). At this point we also
would like to refer the reader to the work of Griffiths [22], where the notion
of a ‘multi-type $\Lambda$-coalescent’ seems to appear for the first time. In
different mathematical context, the notion of a ‘multi-type coalescent point
process’ also appears in the work of Popovic and Rivas [37], which is
mentioned for completeness here. We would also like to draw the attention of
the reader to the recent preprint of Allen and McAvoy [1] for a coalescent
with a general spatial and genetic structure and to the work of Liu and Zhou
[30] for a forward stepping stone model with $\Xi$-resampling mechanism.

All what have been said in this subsection applies also to the discrete-time
limiting processes $(\Pi_{r}^{(n)})_{r\in\mathbb{N}_{0}}$, $n\in\mathbb{N}$,
arising in Theorem 2. Thus there exists a process
$(\Pi_{r})_{r\in\mathbb{N}_{0}}$ with state-space ${\cal P}_{\infty,E}$ such
that for every $n\in\mathbb{N}$ the projected process
$(\varrho_{n}\circ\Pi_{r})_{r\in\mathbb{N}_{0}}$ is a discrete-time multi-type
exchangeable $n$-coalescent with mutation and the same infinitesimal rates.
Again, this process can be fully described by a sequence $\Xi=(\Xi_{k})_{k\in
E}$ of finite measures $\Xi_{k}$ on the infinite simplex $\Delta$, the
calibration constants $d_{k}\geq 0$, $k\in E$, and the mutation parameters
$\rho_{k\ell}\geq 0$, $k\neq\ell$.

###  2.3 Multi-type block counting process

For $t\geq 0$ and $k\in E$ let $N_{t}^{(k)}$ denote the number of $k$-blocks
of $\Pi_{t}$. Define $N_{t}:=(N_{t}^{(k)})_{k\in E}$. Due to a classical
criterion of Burke and Rosenblatt [7, Theorem 1], adapted to the continuous-
time setting, the process $(N_{t})_{t\geq 0}$, called the _block counting
process_ of $\Pi$, is Markovian with state space $\mathbb{N}^{E}$ and
generator $G=G^{\rm rep}+G^{\rm mut}$, where $G^{\rm rep}=(g_{ij}^{\rm
rep})_{i,j\in\mathbb{N}^{E}}$ and $G^{\rm mut}=(g_{ij}^{\rm
mut})_{i,j\in\mathbb{N}^{E}}$ have the following entries. Let $i=(i_{k})_{k\in
E},j=(j_{k})_{k\in E}\in\mathbb{N}^{E}$ with $i\geq j$. If there exists
exactly one $k\in E$ with $i_{k}>j_{k}$, then

$\displaystyle g_{ij}^{\rm rep}$ $\displaystyle=$ $\displaystyle
d_{k}\frac{i_{k}!}{j_{k}!}\sum_{i_{k,1},\ldots,i_{k,j_{k}}}\frac{\phi_{j_{k}}^{(k)}(i_{k,1},\ldots,i_{k,j_{k}})}{i_{k,1}!\cdots
i_{k,j_{k}}!},$

where the sum extends over all $i_{k,1},\ldots,i_{k,j_{k}}\in\mathbb{N}$
satisfying $i_{k,1}+\cdots+i_{k,j_{k}}=i_{k}$. All other non-diagonal entries
of $G^{\rm rep}$ are equal to $0$. The diagonal entries are given by

$g_{ii}^{\rm rep}\ =\ \sum_{k\in E}d_{k}\phi_{i_{k}}^{(k)}(1,\ldots,1),$

where $\phi_{i_{k}}^{(k)}(1,\ldots,1)$ ($\leq 0$) is defined via (17) for all
$k\in E$ and $i_{k}\in\mathbb{N}$. The matrix $G^{\rm mut}$ has entries
$g_{ij}^{\rm mut}=i_{k}\rho_{k\ell}$, if $j=i-e_{k}+e_{\ell}$ for some
$k,\ell\in E$ with $k\neq\ell$, where $e_{k}$ denotes the $k$-th unit vector
in $\mathbb{R}^{E}$. For example, if each $\Xi_{k}$ is the Dirac measure at
$0\in\Delta$, then the generator $G$ has entries

$g_{ij}\ =\ \left\\{\begin{array}[]{cl}-\sum_{k\in
E}\big{(}i_{k}\rho_{k}+d_{k}\binom{i_{k}}{2}\big{)}&\mbox{if $j=i$,}\\\
\displaystyle i_{k}\rho_{k\ell}&\mbox{if $j=i-e_{k}+e_{\ell}$}\\\ &\hskip
8.53581pt\mbox{for some $k\neq\ell$,}\\\ d_{k}\binom{i_{k}}{2}&\mbox{if
$j=i-e_{k}$}\\\ &\hskip 8.53581pt\mbox{for some $k\in E$,}\\\
0&\mbox{otherwise,}\end{array}\right.$

$i=(i_{k})_{k\in E},j=(j_{k})_{k\in E}\in\mathbb{N}_{0}^{E}$. In this case
$(N_{t})_{t\geq 0}$ coincides with the structured coalescent studied by
Notohara [36] and Wilkinson–Herbots [41, Eq. (3)], where $\rho_{k\ell}\geq 0$
is the mutation rate from type $k$ to type $\ell$ (backward in time),
$\rho_{k}:=\sum_{\ell\neq k}\rho_{k\ell}$ and $d_{k}\geq 0$ is the coalescence
rate of any pair of lineages in subpopulation $k\in E$. In the notation of
Johnston, Kyprianou and Rogers [27, Example 2.2], this structured coalescent
is the block counting process of a multi-type Kingman coalescent with binary
merging rate $\rho_{kk\to k}:=d_{k}$ and type changing rate
$\rho_{k\to\ell}:=\rho_{k\ell}$.

##  3 A multi-type Cannings population model with variable subpopulation sizes

We now study a different but closely related multi-type population model with
constant total population size. We consider a population with a fixed number
$N\in\mathbb{N}$ of individuals in each generation $r\in\mathbb{Z}$. As for
the model described in the introduction, each individual $i\in[N]$ alive in
generation $r\in\mathbb{Z}$ produces a random number $\nu_{i,N}^{(r)}$ of
offspring and each offspring a-priori inherits the type of its parent.

In each generation, independently of the offspring sizes, a mutation step
follows the reproduction step. Each offspring of type $k\in E$ mutates to type
$\ell\in E$ with a given probability $u_{k\ell}\geq 0$. These offspring form
the next generation, so our model has non-overlapping generations.

As for the standard (single-type) Cannings model, it is assumed that the
offspring sizes are exchangeable within each generation and independent and
identically distributed (iid) over different generations. Since the population
size is assumed to be constant equal to $N$, the relation
$\sum_{i\in[N]}\nu_{i,N}^{(r)}=N$ holds for each generation $r\in\mathbb{Z}$.

As before, the type space $E$ is assumed to be finite or countable infinite.
Without loss of generality $E=\\{1,\ldots,K\\}$ for some $K\in\mathbb{N}$ or
$E=\mathbb{N}$. Clearly, $U:=(u_{k\ell})_{k,\ell\in E}$ is a stochastic
matrix, called the mutation matrix. The model is neutral with no selection,
since the number of offspring produced by each individual does not dependent
of the type of this individual. We call this model the neutral multi-type
Cannings model with mutation. For $|E|=1$ the model reduces to the classical
neutral exchangeable population model of Cannings [8, 9, 10] as described in
the introduction. We use the notation $\nu_{i,N}:=\nu_{i,N}^{(0)}$, $C_{0}:=0$
and $C_{i}:=\nu_{1,N}+\cdots+\nu_{i,N}$ for $i\in[N]$.

###  3.1 Forward structure

Let $X_{k}(r)$ denote the number of individuals of type $k\in E$ in generation
$r\in\mathbb{N}_{0}$, and set $X(r):=(X_{k}(r))_{k\in E}$. It is readily seen
that $X:=(X(r))_{r\in\mathbb{N}_{0}}$ is a time-homogeneous Markov chain with
state space $\Delta_{N}(E):=\\{i=(i_{k})_{k\in
E}\in\mathbb{N}_{0}^{E}:\sum_{k\in E}i_{k}=N\\}$. Note that
$|\Delta_{N}(E)|=\binom{N+|E|-1}{N}$ if $|E|<\infty$.

Let $\Pi:=(\pi_{ij})_{i,j\in\Delta_{N}(E)}$ denote the transition matrix of
$X$ having entries $\pi_{ij}:=\mathbb{P}(X(r+1)=j\,|\,X(r)=i)$. Clearly
$\Pi=\Pi(U)$ depends on the mutation matrix $U=(u_{k\ell})_{k,\ell\in E}$. For
the multi-allelic Cannings model without mutation (when $U=I$ is the identity
matrix) it is known (see, for example, Gladstien [16] or [34, Eq. (1)]) that
$\Pi^{\rm rep}:=\Pi(I)$ has entries

$\pi_{ij}^{\rm rep}\ =\ \pi_{ij}(I)\ =\ \mathbb{P}(D(i)=j),\qquad
i,j\in\Delta_{N}(E),$ (24)

where $D(i):=(D_{k}(i))_{k\in E}$ is defined via

$D_{k}(i)\ :=\ \sum_{s=s_{k-1}+1}^{s_{k}}\nu_{s,N},\qquad k\in E,$

with $s_{0}:=0$ and $s_{k}:=i_{1}+\cdots+i_{k}$ for $k\in E$. Note that
$\sum_{k\in E}D_{k}(i)=\nu_{1,N}+\cdots+\nu_{N,N}=N$. In particular,
$\pi_{ii}(I)=1$ for all states $i$ of the form $i=Ne_{k}$ with $k\in E$, where
$e_{k}$ denotes the $k$-th unit vector in $\mathbb{R}^{E}$. Thus all the
states $Ne_{k}$, $k\in E$, are absorbing.

In order to describe the structure of the transition matrix $\Pi=\Pi(U)$ for
general mutation matrix $U$ it turns out to be convenient to introduce a
matrix $\Pi^{\rm mut}$ as follows. Fix $i=(i_{k})_{k\in E}\in\Delta_{N}(E)$
and let $M_{k}$, $k\in E$, be independent random variables, where
$M_{k}=(M_{k\ell})_{\ell\in E}$ has a multinomial distribution with parameters
$i_{k}$ and $(u_{k\ell})_{\ell\in E}$, i.e.
$\mathbb{P}(M_{k}=j)=i_{k}!\prod_{\ell\in E}u_{k\ell}^{j_{\ell}}/j_{\ell}!$
for all $j=(j_{\ell})_{\ell\in E}\in\mathbb{N}_{0}^{E}$ with $\sum_{\ell\in
E}j_{\ell}=i_{k}$. Let $\Pi^{\rm mut}=(\pi_{ij}^{\rm
mut})_{i,j\in\Delta_{N}(E)}$ denote the matrix with entries

$\pi_{ij}^{\rm mut}\ :=\ \mathbb{P}(M_{\bullet}=j),\qquad
i,j\in\Delta_{N}(E),$ (25)

where we use the dot subscript summation notation $M_{\bullet}:=\sum_{k\in
E}M_{k}$. It is readily checked that

$\displaystyle\pi_{ij}^{\rm mut}$ $\displaystyle=$
$\displaystyle\sum_{M}\prod_{k\in E}\mathbb{P}(M_{k}=(m_{k\ell})_{\ell\in E})$
(26) $\displaystyle=$ $\displaystyle\sum_{M}\prod_{k\in
E}\bigg{(}i_{k}!\prod_{\ell\in
E}\frac{u_{k\ell}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)}$

for all $i,j\in\Delta_{N}(E)$, where the sum extends over all matrices
$M=(m_{k\ell})_{k,\ell\in E}\in\mathbb{N}_{0}^{E\times E}$ having row sums
$m_{k\bullet}:=\sum_{\ell\in E}m_{k\ell}=i_{k}$, $k\in E$, and column sums
$m_{\bullet\ell}:=\sum_{k\in E}m_{k\ell}=j_{\ell}$, $\ell\in E$. Clearly, the
matrix $\Pi^{\rm mut}$ depends on the mutation matrix
$U=(u_{k\ell})_{k,\ell\in E}$. For example, for $E=\\{1,2\\}$ (two types) it
follows that

$\displaystyle\pi_{ij}^{\rm mut}$ $\displaystyle=$
$\displaystyle\mathbb{P}(M_{11}+M_{21}=j_{1},M_{12}+M_{22}=j_{2})$
$\displaystyle=$ $\displaystyle\mathbb{P}(M_{11}+M_{21}=j_{1}),$

for all $i=(i_{1},i_{2})\in\mathbb{N}_{0}^{2}$ and
$j=(j_{1},j_{2})\in\mathbb{N}_{0}^{2}$ with $i_{1}+i_{2}=N$ and
$j_{1}+j_{2}=N$, where $M_{11}$ and $M_{21}$ are independent, $M_{11}$ has a
binomial distribution with parameters $i_{1}$ and $u_{11}$ and $M_{21}$ has a
binomial distribution with parameters $i_{2}=N-i_{1}$ and $u_{21}$.

The following result clarifies the structure of the transition matrix
$\Pi=\Pi(U)$ for general mutation matrix $U$.

######  Lemma 1.

The chain $X$ (of the model with general mutation matrix $U$) has transition
matrix

$\Pi\ =\ \Pi^{\rm rep}\Pi^{\rm mut},$ (27)

where $\Pi^{\rm rep}:=\Pi(I)$ is the transition matrix of the chain $X$ for
the multi-type Cannings model without mutation having entries (24) and
$\Pi^{\rm mut}$ is the matrix with entries (26).

######  Remark 4.

The transition matrix $\Pi$ thus factorizes into the reproductive part
$\Pi^{\rm rep}$ (involving the offspring sizes $\nu_{1,N},\ldots,\nu_{N,N}$)
and the mutational part $\Pi^{\rm mut}$ (involving the mutation matrix $U$).

###### Proof of Lemma 1.

Let $i=(i_{k})_{k\in E},j=(j_{k})_{k\in E}\in\Delta_{N}(E)$. By the
independence of $\nu_{N}^{(r)}:=(\nu_{1,N}^{(r)},\ldots,\nu_{N,N}^{(r)})$ and
$X(r)$,

$\pi_{ij}\ =\
\sum_{m}\mathbb{P}(X(r+1)=j\,|\,X(r)=i,\nu_{N}^{(r)}=m)\mathbb{P}(\nu_{N}^{(r)}=m),$

where the sum extends over all $m=(m_{1},\ldots,m_{N})\in\mathbb{N}_{0}^{N}$
satisfying $\mathbb{P}(\nu_{N}^{(r)}=m)>0$. Let
$I_{k}:=\\{s\in[N]:\mbox{individual $s$ in generation $r$ has type $k$}\\}$,
$k\in E$. Then,

$\displaystyle\mathbb{P}(X(r+1)=j\,|\,X(r)=i,\nu_{N}^{(r)}=m)$
$\displaystyle=$ $\displaystyle\sum_{M}\prod_{k\in E}\bigg{(}\Big{(}\sum_{s\in
I_{k}}m_{s}\Big{)}!\prod_{\ell\in
E}\frac{u_{k\ell}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)},$

where $m_{k\ell}$ corresponds to the number of children of parents of type $k$
which mutate to type $\ell$. Note that $\sum_{k\in E}m_{k\ell}=j_{\ell}$,
$\ell\in E$, and $\sum_{\ell\in E}m_{k\ell}=\sum_{s\in I_{k}}m_{s}$, $k\in E$.
The offspring variables $\nu_{1,N},\ldots,\nu_{N,N}$ are exchangeable and the
sets $I_{k}$, $k\in E$, are pairwise disjoint with $\bigcup_{k\in E}I_{k}=[N]$
and $|I_{k}|=i_{k}$, $k\in E$. Therefore,

$\pi_{ij}\ =\ \mathbb{E}\bigg{(}\sum_{M}\prod_{k\in
E}\bigg{(}D_{k}(i)!\prod_{\ell\in
E}\frac{u_{kl}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)}\bigg{)},$ (28)

where the sum extends over all matrices $M=(m_{k\ell})_{k,\ell\in
E}\in\mathbb{N}_{0}^{E\times E}$ having column sums $\sum_{k\in
E}m_{k\ell}=j_{\ell}$, $\ell\in E$, and row sums $\sum_{\ell\in
E}m_{k\ell}=D_{k}(i)$, $k\in E$. Alternatively,

$\pi_{ij}\ =\ \sum_{M}\mathbb{P}(D(i)=d)\,\prod_{k\in
E}\bigg{(}d_{k}!\prod_{\ell\in
E}\frac{u_{k\ell}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)},$ (29)

where the sum extends over all matrices $M=(m_{k\ell})_{k,\ell\in
E}\in\mathbb{N}_{0}^{E\times E}$ having column sums $\sum_{k\in
E}m_{k\ell}=j_{\ell}$, $\ell\in E$, and $d:=(d_{k})_{k\in E}$ is defined via
$d_{k}:=\sum_{\ell\in E}m_{k\ell}$, $k\in E$. It remains to note that the
right-hand side of Eq. (29) is equal to $\sum_{d\in\Delta_{N}(E)}\pi_{id}^{\rm
rep}\pi_{dj}^{\rm mut}=(\Pi^{\rm rep}\Pi^{\rm mut})_{ij}$. Thus, $\Pi=\Pi^{\rm
rep}\Pi^{\rm mut}$. ∎

The transition probability $\pi_{ij}$ simplifies considerably in particular
situations, as the following examples demonstrate.

  * Example. (parent independent mutation) If the mutation probabilities $u_{k\ell}=u_{\ell}$ do not depend on the type $k\in E$ of the parent, then (29) reduces to the multinomial expression

$\pi_{ij}\ =\ N!\prod_{k\in E}\frac{u_{k}^{j_{k}}}{j_{k}!},$ (30)

$i=(i_{k})_{k\in E},j=(j_{k})_{k\in E}\in\Delta_{N}(E)$. Eq. (30) is obvious
from the model and can be also derived from (27) as follows. By the
convolution property for multinomial distributions ${\rm Mn}(i_{k},u)$, $k\in
E$, with the same probability vector $u:=(u_{\ell})_{\ell\in E}$,
$M_{\bullet}=\sum_{k\in E}M_{k}$ has a multinomial distribution with
parameters $\sum_{k\in E}i_{k}=N$ and $u$. Thus, by (25), $\pi_{ij}^{\rm
mut}=\mathbb{P}(M_{\bullet}=j)={\rm Mn}(N,u)(j)$ does not depend on $i$ and
(30) follows from (27). Note that the transition probability $\pi_{ij}$ in
(30) neither depends on $i$ nor on the offspring sizes
$\nu_{1,N},\ldots,\nu_{N,N}$. If $K:=|E|\in\mathbb{N}$ and $u_{k\ell}:=1/K$
for all $k,\ell\in E$ then $\pi_{ij}=N!K^{-N}/(j_{1}!\cdots j_{K}!)$.

  * Example. (absence of mutation) If $U=I$ (identity matrix), which corresponds to the multi-allelic Cannings model without mutation, then the matrix $\Pi^{\rm mut}$ with entries (25) is the identity matrix and the transition matrix $\Pi=\Pi^{\rm rep}\Pi^{\rm mut}=\Pi^{\rm rep}$ has entries (24).

  * Example. (multi-allelic Wright–Fisher model with mutation) If the family size vector $\nu_{N}:=(\nu_{1,N},\ldots,\nu_{N,N})$ has a symmetric multinomial distribution ${\rm Mn}(N,(1/N)_{i\in[N]})$, then $D(i)=(D_{k}(i))_{k\in E}\stackrel{{\scriptstyle d}}{{=}}{\rm Mn}(N,(i_{k}/N)_{k\in E})$. Plugging $\mathbb{P}(D(i)=d)=N!N^{-N}\prod_{k\in E}i_{k}^{d_{k}}/d_{k}!$ into (29), the factorials $d_{k}!$ cancel, and from $\sum_{l\in E}m_{kl}=d_{k}$ it follows that

$\pi_{ij}\ =\ \frac{N!}{N^{N}}\sum_{M}\prod_{k\in E}\prod_{\ell\in
E}\frac{(u_{k\ell}i_{k})^{m_{k\ell}}}{m_{k\ell}!},$

where the sum extends over all matrices $M=(m_{k\ell})_{k,\ell\in E}$ with
$\sum_{k\in E}m_{k\ell}=j_{\ell}$, $\ell\in E$. Applying the binomial
expansion $n!\sum_{(n_{k})_{k\in E}\in\Delta_{n}(E)}\prod_{k\in
E}(x_{k}^{n_{k}}/n_{k}!)=(\sum_{k\in E}x_{k})^{n}$, $n\in\mathbb{N}_{0}$,
$x_{k}\in\mathbb{R}$, $k\in E$, for each $\ell\in E$ with $n:=j_{\ell}$,
$n_{k}:=m_{k\ell}$ and $x_{k}:=u_{k\ell}i_{k}$ shows that (29) simplifies to

$\pi_{ij}\ =\ N!\prod_{\ell\in
E}\frac{\pi_{\ell}^{j_{\ell}}}{j_{\ell}!},\qquad i,j\in\Delta_{N}(E),$ (31)

with $\pi_{\ell}:=N^{-1}\sum_{k\in E}u_{k\ell}i_{k}$ for $\ell\in E$. In
particular, conditional on $X(r)=i$, for every $\ell\in E$ the random variable
$X_{\ell}(r+1)$ has a binomial distribution with parameters $N$ and
$\pi_{\ell}$, converging as $N\to\infty$ in distribution to a Poisson
distribution with parameter $N\pi_{\ell}=\sum_{k\in E}u_{k\ell}i_{k}$. For
$|E|<\infty$ the chain $X$ and its diffusion limit as $N\to\infty$ of this
multi-allele Wright–Fisher model with mutation has been studied extensively in
the (classical) literature on mathematical population genetics. We refer the
reader exemplary to Etheridge [11], Ewens [15] and Griffiths [18, 19, 20].

A further example, the multitype Kimura model, is deferred to Subsection 3.4.

The forward structure is often alternatively described by the process
$\widetilde{X}:=(\widetilde{X}(r))_{r\in\mathbb{N}_{0}}$ having state space
$E^{N}$, where $\widetilde{X}(r):=(\widetilde{X}_{i}(r))_{i\in[N]}$ and
$\widetilde{X}_{i}(r)$ denotes the type of the $i$-th individual alive in
generation $r\in\mathbb{N}_{0}$. Processes of this form are extensively used,
for example in Birkner et al. [4] even for more general type spaces $E$. Let
$f:E^{N}\to\Delta_{N}(E)$ denote the function which maps $x\in E^{N}$ to
$f(x):=i:=(i_{k})_{k\in E}$ with $i_{k}:=|\\{i\in[N]:x_{i}=k\\}|$, $k\in E$.
The process $X$ is easily pathwise recovered from $\widetilde{X}$ via
$X(r)=f(\widetilde{X}(r))$, $r\in\mathbb{N}_{0}$. Strictly speaking, the
process $\widetilde{X}$ contains (pathwise) slightly more information than
$X$, since the type of each individual is known. However, due to the
exchangeability of the model arising from the random assignment condition,
from the distributional point of view the processes $X$ and $\widetilde{X}$
contain the same information. More precisely, the transition probabilities
$\widetilde{\pi}_{xy}:=\mathbb{P}(\widetilde{X}(r+1)=y\,|\,\widetilde{X}(r)=x)$,
$x,y\in E^{N}$, of the process $\widetilde{X}$ are related to those of $X$ via

$\widetilde{\pi}_{xy}\ =\ \frac{\pi_{ij}}{|f^{-1}(\\{j\\})|}\ =\
\frac{\prod_{k\in E}j_{k}!}{N!}\pi_{ij},$ (32)

where $i:=(i_{k})_{k\in E}:=f(x)$ and $j:=(j_{k})_{k\in E}:=f(y)$.
Alternatively,

$\widetilde{\pi}_{xy}\ =\ \frac{1}{N!}\sum_{\sigma\in
S_{N}}\mathbb{E}\bigg{(}\prod_{i=1}^{N}\prod_{j=C_{i-1}+1}^{C_{i}}u_{x_{i}y_{\sigma
j}}\bigg{)},$ (33)

where $S_{N}$ denotes the set of all permutations of $[N]$, $C_{0}:=0$ and
$C_{i}:=\nu_{1,N}+\cdots+\nu_{i,N}$ for all $i\in[N]$. For $N=1$ we recover
the mutation probabilities $\widetilde{\pi}_{xy}=u_{xy}$, $x,y\in E$.

For parent independent mutation, that is, $u_{k\ell}=u_{\ell}$ for all
$k,\ell\in E$, Eq. (33) reduces to

$\widetilde{\pi}_{xy}\ =\ \frac{1}{N!}\sum_{\sigma\in
S_{N}}\mathbb{E}\bigg{(}\prod_{j=1}^{N}u_{y_{\sigma j}}\bigg{)}\ =\
u_{y_{1}}\cdots u_{y_{N}},$

which neither depends on $i$ nor on $(\nu_{1,N},\ldots,\nu_{N,N})$.

In absence of mutation ($u_{kk}=1$ for all $k\in E$),

$\widetilde{\pi}_{xy}\ =\ \frac{\prod_{k\in
E}j_{k}!}{N!}\mathbb{P}(D(i)=j),\qquad x,y\in E^{N},$

where $i:=(i_{k})_{k\in E}:=f(x)$ and $j:=(j_{k})_{k\in E}:=f(y)$ and
$D(i):=(D_{k}(i))_{k\in E}$ with
$D_{k}(i):=\sum_{s=s_{k-1}+1}^{s_{k}}\nu_{s,N}$, $s_{0}:=0$ and
$s_{k}:=i_{1}+\cdots+i_{k}$ for $k\in E$.

For the multi-type Wright–Fisher model with mutation, each child $j\in[N]$
chooses randomly and independently its parent. Thus,

$\displaystyle\widetilde{\pi}_{xy}$ $\displaystyle=$
$\displaystyle\prod_{j\in[N]}\sum_{i\in[N]}\mathbb{P}(\mbox{child $j$ chooses
parent $i$})u_{x_{i}y_{j}}$ (34) $\displaystyle=$
$\displaystyle\frac{1}{N^{N}}\prod_{j\in[N]}\sum_{i\in[N]}u_{x_{i}y_{j}}\qquad
x,y\in E^{N}.$

Fix $x\in E^{N}$ and $j\in\Delta_{N}(E)$. Define $i:=f(x)$. Then,

$\displaystyle\sum_{y\in f^{-1}(\\{j\\})}\widetilde{\pi}_{xy}$ (35)
$\displaystyle=$ $\displaystyle\frac{1}{N^{N}}\sum_{y\in
f^{-1}(\\{j\\})}\prod_{n\in[N]}(u_{x_{1}y_{n}}+\cdots+u_{x_{N}y_{n}})$
$\displaystyle=$ $\displaystyle\frac{1}{N^{N}}\sum_{y\in
f^{-1}(\\{j\\})}\prod_{n\in[N]}\bigg{(}\sum_{k\in E}i_{k}u_{ky_{n}}\bigg{)}$
$\displaystyle=$ $\displaystyle\frac{1}{N^{N}}\sum_{y\in
f^{-1}(\\{j\\})}\prod_{\ell\in E}\bigg{(}\sum_{k\in
E}i_{k}u_{k\ell}\bigg{)}^{j_{\ell}}$ $\displaystyle=$ $\displaystyle\sum_{y\in
f^{-1}(\\{j\\})}\prod_{\ell\in E}\pi_{\ell}^{j_{\ell}}$ $\displaystyle=$
$\displaystyle|f^{-1}(\\{j\\})|\prod_{\ell\in E}\pi_{\ell}^{j_{\ell}}\ =\
N!\prod_{\ell\in E}\frac{\pi_{\ell}^{j_{\ell}}}{j_{\ell}!}.$

This expression depends only via $i=f(x)$ on $x$. Thus, by Rosenblatt’s
criterion for functions of Markov processes, with $\tilde{X}$ also the process
$X=(X(r))_{r\in\mathbb{N}_{0}}=(f(\widetilde{X}(r)))_{r\in\mathbb{N}_{0}}$ is
Markovian and (35) is the transition probability $\pi_{ij}$ of the chain $X$
to move from $i$ to $j$, in agreement with (31).

###  3.2 A limiting multi-type branching process

Assume that the number of type is finite but not equal to $1$; without loss of
generality, $E=[K]$ with $K\in\mathbb{N}\setminus\\{1\\}$. Define
$L:=K-1\in\mathbb{N}$. In the following the space
$S_{N,L}:=S_{N}([L])=\\{i=(i_{\ell})_{\ell\in[L]}\in\mathbb{N}_{0}^{L}\,:\,\sum_{\ell\in[L]}i_{\ell}\leq
N\\}$ plays a crucial role. So far, the model was described forward in time by
the process $X=(X(r))_{r\in\mathbb{N}_{0}}$ having state space
$\Delta_{N,K}:=\Delta_{N}([K])=\\{i=(i_{k})_{k\in
E}\in\mathbb{N}_{0}^{K}:\sum_{k\in[K]}i_{k}=N\\}$. Note that
$|S_{N,L}|=\sum_{n=0}^{N}|\Delta_{n,L}|=\sum_{n=0}^{N}\binom{n+L-1}{n}=\binom{N+L}{N}=\binom{N+K-1}{N}=|\Delta_{N,K}|$.
Since the last component $X_{K}(r)=N-\sum_{\ell=1}^{L}X_{\ell}(r)$ is
determined by the other components $X_{1}(r),\ldots,X_{L}(r)$, we can
disregard the last component $X_{K}(r)$ and view the forward process
$X=(X(r))_{r\in\mathbb{N}_{0}}$ as a process with state space $S_{N,L}$ by
writing $X(r)$ equivalently in the form

$X_{r}\ :=\ (X_{\ell}(r))_{\ell\in[L]},\qquad r\in\mathbb{N}_{0}.$ (36)

The following definition is useful to understand the behavior of $X_{r}$ as
the total population $N$ tends to infinity.

######  Definition 1.

The offspring sizes $\nu_{1,N},\ldots,\nu_{N,N}$ are said to be asymptotically
independent, if there exist independent random variables
$\xi_{1},\xi_{2},\ldots$ such that

$\lim_{N\to\infty}\mathbb{P}(\nu_{1,N}=m_{1},\ldots,\nu_{j,N}=m_{j})\ =\
\prod_{i=1}^{j}\mathbb{P}(\xi_{i}=m_{i})$ (37)

for all $j\in\mathbb{N}$ and $m_{1},\ldots,m_{j}\in\mathbb{N}_{0}$.

The exchangeability of $\nu_{1,N},\ldots,\nu_{N,N}$ implies that the random
variables $\xi_{1},\xi_{2},\ldots$ are identically distributed. As in [28, p.
491] or [32, Lemma 2.1] it follows that $\nu_{1,N},\ldots,\nu_{N,N}$ are
asymptotically independent if and only if there exists a random variable $\xi$
such that, for all $m\in\mathbb{N}_{0}$,
$\mathbb{P}(\nu_{1,N}=m)\to\mathbb{P}(\xi=m)$ and
$\mathbb{P}(\nu_{1,N}=\nu_{2,N}=m)\to(\mathbb{P}(\xi=m))^{2}$ as $N\to\infty$.
We call $\xi$ the limiting variable. Note that $\mathbb{E}(\xi)\leq 1$. There
exist examples with $\mathbb{E}(\xi)<1$. For example, if
$(\nu_{1,N},\ldots,\nu_{N,N})$ is a random permutation of $(N,0,\ldots,0)$,
then $\nu_{1,N},\ldots,\nu_{N,N}$ are asymptotically independent with limiting
variable $\xi=0$.

We shall see soon that the asymptotic independence of the offspring sizes
alone will not be sufficient to ensure convergence of the forward process to a
limiting process as $N\to\infty$. An additional assumption on the mutation
probabilities is needed, which turns out to be of the form

$u_{KK}\ =\ 1,$ (38)

that is, mutations from the ‘last’ type $K$ back to any other type $k<K$ are
impossible. Clearly, (38) wipes out several important models. The remark at
the end of this section shows that the following results fail if (38) does not
hold. The convergence results presented later (Theorem 3) are based on the
following lemma.

######  Lemma 2.

Suppose that the offspring sizes $\nu_{1,N},\ldots,\nu_{N,N}$ are
asymptotically independent with limiting variable $\xi$. Let
$K\in\mathbb{N}\setminus\\{1\\}$ and set $L:=K-1\in\mathbb{N}$. If $u_{KK}=1$,
that is, mutations from type $K$ to any type $\ell\in[L]$ are not possible,
then

$\mathbb{P}(X_{1}=j\,|\,X_{0}=i)\ \to\
\mathbb{P}\bigg{(}\bigcap_{\ell\in[L]}\bigg{\\{}\sum_{k\in[L]}Y_{k\ell}^{*i_{k}}=j_{\ell}\bigg{\\}}\bigg{)}$
(39)

as $N\to\infty$ for all
$i=(i_{\ell})_{\ell\in[L]},j=(j_{\ell})_{\ell\in[L]}\in\mathbb{N}_{0}^{L}$,
where $Y_{k\ell}^{*i_{k}}$ denotes the $i_{k}$-th convolution of $Y_{k\ell}$
and $Y_{k}=(Y_{k\ell})_{\ell\in[L]}$, $k\in[L]$, are independent
$\mathbb{N}_{0}^{L}$-valued random variables having distribution

$\mathbb{P}(Y_{k}=j)\ =\
\mathbb{E}\big{(}(\xi)_{|j|}u_{kK}^{\xi-|j|}\big{)}\prod_{\ell\in[L]}\frac{u_{k\ell}^{j_{\ell}}}{j_{\ell}!},$
(40)

$j=(j_{\ell})_{\ell\in[L]}\in\mathbb{N}_{0}^{L}$, with
$|j|:=\sum_{\ell\in[L]}j_{\ell}$. In (40), the notation $(x)_{0}:=1$ and
$(x)_{n}:=x(x-1)\cdots(x-n+1)$ for $x\in\mathbb{R}$ and $n\in\mathbb{N}$ is
used.

######  Remark 5.

Fix $k\in[L]$. Eq. (40) essentially states that, conditional on $\xi$,
$(Y_{k1},\ldots,Y_{kL},\xi-\sum_{\ell\in[L]}Y_{k\ell})$ has a multinomial
distribution with parameters $\xi$ and $(u_{k\ell})_{\ell\in E}$. By the
convolution property for multinomial distributions with the same probability
vector, conditional on $\xi$, for any $n\in\mathbb{N}_{0}$, the $n$-th
convolution
$(Y_{k1}^{*n},\ldots,Y_{kL}^{*n},(\xi-\sum_{\ell\in[L]}Y_{k\ell})^{*n})$ has a
multinomial distribution with parameters $\xi^{*n}$ and $(u_{k\ell})_{\ell\in
E}$. In particular, for all $n\in\mathbb{N}_{0}$ and
$(j_{\ell})_{\ell\in[L]}\in\mathbb{N}_{0}^{L}$,

$\mathbb{P}\bigg{(}\bigcap_{\ell\in[L]}\\{Y_{k\ell}^{*n}=j_{\ell}\\}\bigg{)}\
=\
\mathbb{E}((\xi^{*n})_{|j|}u_{kK}^{\xi^{*n}-|j|})\prod_{\ell\in[L]}\frac{u_{k\ell}^{j_{\ell}}}{j_{\ell}!},$

where $|j|:=\sum_{\ell\in[L]}j_{\ell}$. This convolution property turns out to
be crucial for the proof of Lemma 2 and ensures the branching property of the
limiting process arising in Theorem 3 below.

######  Remark 6.

For $K=2$, (39) reduces to
$\mathbb{P}(X_{1}(1)=j\,|\,X_{1}(0)=i)\to\mathbb{P}(Y^{*i}=j)$ as $N\to\infty$
for all $i,j\in\mathbb{N}_{0}$, where $Y:=Y_{11}$ has distribution
$\mathbb{P}(Y=j)=\mathbb{E}\big{(}\binom{\xi}{j}u_{11}^{j}u_{12}^{\xi-j}\big{)}$,
$j\in\mathbb{N}_{0}$. Conditional on $\xi$, $Y$ has a binomial distribution
with parameters $\xi$ and $u_{11}$.

###### Proof of Lemma 2.

Fix $(i_{\ell})_{\ell\in[L]},(j_{\ell})_{\ell\in[L]}\in\mathbb{N}_{0}^{L}$ and
let $N$ be sufficiently large such that
$i_{K}:=N-\sum_{\ell\in[L]}i_{\ell}\in\mathbb{N}_{0}$ and
$j_{K}:=N-\sum_{\ell\in[L]}j_{\ell}\in\mathbb{N}_{0}$. Define
$i:=(i_{k})_{k\in E}$ and $j:=(j_{k})_{k\in E}$. We have to verify that
$\pi_{ij}$ converges to the right-hand side of (39) as $N\to\infty$. Since
$u_{KK}=1$ and, hence, $u_{K\ell}=0$ for all $\ell\in[L]$, it follows that
only matrices $M=(m_{k\ell})_{k,\ell\in E}$ with last row
$(m_{K\ell})_{\ell\in[K]}$ equal to $(0,\ldots,0,D_{k})$ contribute to the sum
in (28). Thus, (28) reduces to

$\pi_{ij}\ =\
\mathbb{E}\bigg{(}\sum_{M}\prod_{k\in[L]}\bigg{(}(D_{k})_{m_{k}}u_{kK}^{D_{k}-m_{k}}\prod_{\ell\in[L]}\frac{u_{k\ell}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)}\bigg{)},$

where $m_{k}:=\sum_{\ell\in[L]}m_{k\ell}$ and the sum extends over all
‘reduced’ matrices $M=(m_{k\ell})_{k,\ell\in[L]}\in\mathbb{N}_{0}^{L\times L}$
having column sums $\sum_{k\in E}m_{k\ell}=j_{\ell}$, $\ell\in[L]$. From the
asymptotic independence of $\nu_{1,N},\ldots,\nu_{N,N}$ it follows that
$D=(D_{k})_{k\in[L]}\to(\xi_{k}^{*i_{k}})_{k\in[L]}$ in distribution as
$N\to\infty$, where $\xi_{1},\xi_{2},\ldots$ are iid copies of a random
variable $\xi$ satisfying $\nu_{1}\to\xi$ in distribution as $N\to\infty$.
Thus, as $N\to\infty$, $\pi_{ij}$ converges to

$\displaystyle\sum_{M}\prod_{k\in[L]}\bigg{(}\mathbb{E}\big{(}(\xi_{k}^{*i_{k}})_{m_{k}}u_{kK}^{\xi_{k}^{*i_{k}}-m_{k}}\big{)}\prod_{\ell\in[L]}\frac{u_{k\ell}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)}$
$\displaystyle=$
$\displaystyle\sum_{M}\prod_{k\in[L]}\mathbb{P}\bigg{(}\bigcap_{l\in[L]}\\{Y_{k\ell}^{*i_{k}}=m_{k\ell}\\}\bigg{)}$
$\displaystyle=$
$\displaystyle\sum_{M}\mathbb{P}\bigg{(}\bigcap_{k,\ell\in[L]}\\{Y_{k\ell}^{*i_{k}}=m_{k\ell}\\}\bigg{)}$
$\displaystyle=$
$\displaystyle\mathbb{P}\bigg{(}\bigcap_{\ell\in[L]}\bigg{\\{}\sum_{k\in[L]}Y_{k\ell}^{*i_{k}}=j_{\ell}\bigg{\\}}\bigg{)}.$

The proof is complete. ∎

Before we come to the main convergence result, we provide some more
information on $Y_{k}$.

######  Lemma 3 (Descending factorial moments of $Y_{k}$).

The joint descending factorial moments
$\mu(m):=\mathbb{E}(\prod_{\ell\in[L]}(Y_{k\ell})_{m_{\ell}})$,
$m=(m_{\ell})_{\ell\in[L]}\in\mathbb{N}_{0}^{L}$, of
$Y_{k}=(Y_{k\ell})_{\ell\in[L]}$ are given by

$\mu(m)\ =\
\mathbb{E}\big{(}(\xi)_{|m|}\big{)}\prod_{\ell\in[L]}u_{k\ell}^{m_{\ell}},$
(41)

where $|m|:=\sum_{\ell\in[L]}m_{\ell}$.

###### Proof of Lemma 3.

Let $k\in[L]$ and $m=(m_{\ell})_{\ell\in[L]}\in\mathbb{N}_{0}^{L}$. By (40),

$\displaystyle\mu(m)\ =\
\sum_{j_{1},\ldots,j_{L}\in\mathbb{N}_{0}}\mathbb{P}(Y_{k}=(j_{1},\ldots,j_{L}))\prod_{\ell\in[L]}(j_{\ell})_{m_{\ell}}$
$\displaystyle=$
$\displaystyle\sum_{j\in\mathbb{N}_{0}}\mathbb{E}\big{(}(\xi)_{j}u_{kK}^{\xi-j}\big{)}\sum_{\begin{subarray}{c}j_{1},\ldots,j_{L}\in\mathbb{N}_{0}\\\
j_{1}+\cdots+j_{L}=j\end{subarray}}\prod_{\ell\in[L]}\frac{(j_{\ell})_{m_{\ell}}u_{k\ell}^{j_{\ell}}}{j_{\ell}!}$
$\displaystyle=$
$\displaystyle\sum_{j\geq|m|}\mathbb{E}\big{(}(\xi)_{j}u_{kK}^{\xi-j}\big{)}\sum_{\begin{subarray}{c}j_{1}\geq
m_{1},\ldots,j_{L}\geq m_{L}\\\
j_{1}+\cdots+j_{L}=j\end{subarray}}\prod_{\ell\in[L]}\frac{u_{k\ell}^{j_{\ell}}}{(j_{\ell}-m_{\ell})!}.$

By the multinomial formula, the last sum reduces to
$u_{k}^{j-|m|}/(j-|m|)!\prod_{\ell\in[L]}u_{k\ell}^{j_{\ell}}$, where
$u_{k}:=\sum_{\ell\in[L]}u_{k\ell}$. Thus,

$\displaystyle\mu(m)$ $\displaystyle=$
$\displaystyle\sum_{j\geq|m|}\mathbb{E}\big{(}(\xi)_{j}u_{kK}^{\xi-j}\big{)}\frac{u_{k}^{j-|m|}}{(j-|m|)!}\prod_{\ell\in[L]}u_{k\ell}^{m_{\ell}}$
$\displaystyle=$
$\displaystyle\mathbb{E}\bigg{(}(\xi)_{|m|}\sum_{j\geq|m|}\binom{\xi-|m|}{j-|m|}u_{kK}^{\xi-j}u_{k}^{j-|m|}\bigg{)}\prod_{\ell\in[L]}u_{k\ell}^{m_{\ell}}.$

The result follows from
$\sum_{j\geq|m|}\binom{\xi-|m|}{j-|m|}u_{kK}^{\xi-j}u_{k}^{j-|m|}=(u_{kK}+u_{k})^{\xi-|m|}=1^{\xi-|m|}=1$.
∎

######  Remark 7.

Note that $Y_{k\ell}$ has descending factorial moments
$\mathbb{E}((Y_{k\ell})_{m})=\mathbb{E}((\xi)_{m})u_{k\ell}^{m}$,
$m\in\mathbb{N}_{0}$, in agreement with the fact that, conditional on $\xi$,
$Y_{k\ell}$ has a binomial distribution with parameters $\xi$ and $u_{k\ell}$.
Moreover, for $\ell_{1},\ell_{2}\in[L]$ with $\ell_{1}\neq\ell_{2}$,

${\rm Cov}(Y_{k\ell_{1}},Y_{k\ell_{2}})\ =\
\big{(}\mathbb{E}((\xi)_{2})-(\mathbb{E}(\xi))^{2}\big{)}u_{k\ell_{1}}u_{k\ell_{2}}.$
(42)

Thus, in general, the random variables $Y_{k\ell}$, $\ell\in[L]$, are not
pairwise uncorrelated. A nice exception occurs when $\xi$ is Poisson
distributed, since $\mathbb{E}((\xi)_{2})=(\mathbb{E}(\xi))^{2}$ in this case.
A concrete such exception is the Wright–Fisher model.

The following result (Theorem 3) shows that, under the assumptions of Lemma 2,
the forward structure can be approximated for large $N$ by a multi-type
Galton–Watson branching process. For general information on multi-type
branching processes we refer the reader to Athreya and Ney [2, Chapter V],
Harris [23, Chapter II] and Mode [31].

######  Theorem 3 (Multi-type branching process limit).

Suppose that the assumptions of Lemma 2 are satisfied. If $X_{0}\to Z_{0}$ in
distribution as $N\to\infty$ for some $\mathbb{N}_{0}^{L}$-valued random
variable $Z_{0}$, then, as $N\to\infty$, the forward process
$X:=(X_{r})_{r\in\mathbb{N}_{0}}$, defined via (36), converges in
$D_{\mathbb{N}_{0}^{L}}(\mathbb{N}_{0})$ to an $L$-type Galton–Watson
branching process $Z:=(Z_{r})_{r\in\mathbb{N}_{0}}$, whose distribution is
characterized as follows. For every $k\in[L]$ and
$j=(j_{\ell})_{\ell\in[L]}\in\mathbb{N}_{0}^{L}$, the probability that a
parent of type $k\in[L]$ produces for each $\ell\in[L]$ exactly $j_{\ell}$
children of type $\ell$ is given by (40).

######  Remark 8.

Analogous results for bisexual population models with $K=2$ types are stated
in [28, Theorem 1] and [32, Theorem 2.2 and Corollary 2.4].

###### Proof of Theorem 3.

Let $n\in\mathbb{N}_{0}$ and $j(0),\ldots,j(n)\in\mathbb{N}_{0}^{L}$. For all
sufficiently large $N$, by the Markov property and the time-homogeneity of the
process $X$,

$\displaystyle\mathbb{P}(X_{0}=j(0),\ldots,X_{n}=j(n))$ $\displaystyle=$
$\displaystyle\mathbb{P}(X_{0}=j(0))\prod_{r=0}^{n-1}\mathbb{P}(X_{r+1}=j(r+1)\,|\,X_{r}=j(r))$
$\displaystyle=$
$\displaystyle\mathbb{P}(X_{0}=j(0))\prod_{r=0}^{n-1}\mathbb{P}(X_{1}=j(r+1)\,|\,X_{0}=j(r)).$

By the assumptions and Lemma 2, this expression converges as $N\to\infty$ to

$\displaystyle\mathbb{P}(Z_{0}=j(0))\prod_{r=0}^{n-1}\mathbb{P}\bigg{(}\bigcap_{\ell\in[L]}\bigg{\\{}\sum_{k\in[L]}Y_{k\ell}^{*j_{k}(r)}=j_{\ell}(r+1)\bigg{\\}}\bigg{)}$
$\displaystyle=$
$\displaystyle\mathbb{P}(Z_{0}=j(0))\prod_{r=0}^{n-1}\mathbb{P}(Z_{r+1}=j(r+1)\,|\,Z_{r}=j(r))$
$\displaystyle=$ $\displaystyle\mathbb{P}(Z_{0}=j(0),\ldots,Z_{n}=j(n)).$

The convergence of the finite-dimensional distributions is established. For
processes with discrete time set $\mathbb{N}_{0}$, the convergence of the
finite-dimensional distributions is equivalent (see, for example, Billingsley
[3, p. 19]) to the convergence in $D_{\mathbb{N}_{0}^{L}}(\mathbb{N}_{0})$,
i.e. to the weak convergence $Q_{N}\to Q$ as $N\to\infty$, where $Q_{N}$ and
$Q$ denote the image measures of $X$ and $Z$ respectively. Note that $Q_{N}$
and $Q$ are probability measures on $(\mathbb{R}^{L})^{\mathbb{N}_{0}}$
equipped with the Borel $\sigma$-field generated by the product topology (of
pointwise convergence). ∎

  * Example. Suppose that $\nu_{1,N},\ldots,\nu_{N,N}$ are asymptotically independent (with iid limiting variables $\xi_{1},\xi_{2},\ldots$) and that $u_{kk}=1$ for all $k\in E$ (absence of mutation). If $L:=K-1\in\mathbb{N}$ then the assumptions of Lemma 2 are obviously satisfied and Theorem 3 is applicable. From (40) it follows that (39) holds with $Y_{k\ell}:=\xi_{\ell}$ for $k=\ell$ and $Y_{k\ell}:=0$ for $k\neq\ell$.

  * Example. For the Wright–Fisher model, the offspring sizes $\nu_{1,N},\ldots,\nu_{N,N}$ are asymptotically independent, where the limiting variables $\xi_{1},\xi_{2},\ldots$ are iid copies of a random variable $\xi$ having a Poisson distribution with parameter $1$. From (40) and $\mathbb{E}\big{(}(\xi)_{|j|}u_{kK}^{\xi-|j|}\big{)}=\sum_{n\geq|j|}(n)_{|j|}u_{kK}^{n-|j|}e^{-1}/n!=e^{-1}\sum_{n\geq 0}u_{kK}^{n}/n!=e^{-\sum_{\ell\in[L]}u_{k\ell}}$ it follows that the random variables $Y_{k\ell}$ are independent with $Y_{k\ell}$ Poisson distributed with parameter $u_{k\ell}$, $k,\ell\in[L]$. Theorem 3 is applicable provided that $u_{KK}=1$. In this case, for the limiting $L$-type branching process the probability that a parent of type $k\in[L]$ produces for each $\ell\in[L]$ exactly $j_{\ell}$ children of type $\ell$ is given by $\prod_{\ell\in[L]}\mathbb{P}(Y_{k\ell}=j_{\ell})=\prod_{\ell\in[L]}u_{k\ell}^{j_{\ell}}e^{-u_{k\ell}}/j_{\ell}!$.

######  Remark 9.

Without the condition $u_{KK}=1$, Lemma 2 and, hence, Theorem 3 in general
fail. Consider for example the Wright–Fisher model with $K=2$ types. Fix
$i\in\mathbb{N}_{0}$. For all $N\geq i$, conditional on $X_{1}(0)=i$, the
random variable $X_{1}(1)$ has a binomial distribution with parameter $N$ and
$\pi_{1}:=(u_{11}i+u_{21}(N-i))/N$. This binomial distribution does not weakly
converge as $N\to\infty$ as long as $u_{21}>0$, since
$N\pi_{1}=u_{11}i+u_{21}(N-i)\to\infty$ in this case. Thus, (39) does not hold
if $u_{22}<1$, so Lemma 2 and Theorem 3 are not applicable.

###  3.3 Some backward results

For $N\in\mathbb{N}$ define $S_{N}(E):=\\{i=(i_{k})_{k\in
E}\in\mathbb{N}_{0}^{E}:\sum_{k\in E}i_{k}\leq N\\}$. Fix $i=(i_{k})_{k\in
E}\in S_{N}(E)$. Suppose that one has taken in some generation
$r\in\mathbb{Z}$ a sample of $|i|:=\sum_{k\in E}i_{k}$ individuals, where
$i_{k}$ of these individuals are of type $k$, $k\in E$. For $j=(j_{k})_{k\in
E}\in S_{N}(E)$ let $A_{ij}$ denote the event that, for each $k\in E$, the
$i_{k}$ individuals of type $k$ have exactly $j_{k}$ parents. Define
$p_{ij}:=\mathbb{P}(A_{ij})$ and $P:=(p_{ij})_{i,j\in S_{N}(E)}$. Clearly, all
quantities $A_{ij}=A_{ij}(U)$, $p_{ij}=p_{ij}(U)$ and $P=P(U)$ depend on the
mutation matrix $U$. For the model without mutation, that is, for $U=I$
(identity matrix), it is known (see, for example, [34, Proposition 1]) that
$P^{\rm rep}:=P(I)$ has entries

$\displaystyle p_{ij}^{\rm rep}$ $\displaystyle=$
$\displaystyle\frac{(N-|i|)!\prod_{k\in E}i_{k}!}{(N-|j|)!\prod_{k\in
E}j_{k}!}\sum_{m}\mathbb{E}\bigg{(}\prod_{s=1}^{|j|}\binom{\nu_{s,N}}{m_{s}}\bigg{)}$
(43) $\displaystyle=$ $\displaystyle\frac{\prod_{k\in E}i_{k}!}{\prod_{k\in
E}j_{k}!}\sum_{m}\frac{\Phi_{|j|}(m_{1},\ldots,m_{|j|})}{m_{1}!\cdots
m_{|j|}!},$

where $|i|:=\sum_{k\in E}i_{k}$, $|j|:=\sum_{k\in E}j_{k}$ and the sum extends
over all $m=(m_{1},\ldots,m_{|j|})\in\mathbb{N}^{|j|}$ satisfying
$m_{1}+\cdots+m_{j_{1}}=i_{1}$,
$m_{j_{1}+1}+\cdots+m_{j_{1}+j_{2}}=i_{2},\ldots,m_{j_{1}+\cdots+j_{K-1}+1}+\cdots+m_{|j|}=i_{K}$.

For $k\in E$ let $e_{k}$ denote the $k$-th unit vector in $\mathbb{R}^{E}$.
From (43) it follows that, for all $N\in\mathbb{N}\setminus\\{1\\}$,
$p_{2e_{k},e_{k}}(I)=\Phi_{1}(2)=c_{N}$ does not depend on $k\in E$ and
coincides with the coalescence probability (3).

In order to obtain formulas for $p_{ij}=p_{ij}(U)$ for general mutation matrix
$U$ we proceed as follows. Let $P^{\rm mut}:=(p_{ij}^{\rm mut})_{i,j\in
S_{N}(E)}$ denote the matrix with entries

$p_{ij}^{\rm mut}\ :=\ \sum_{M}\prod_{k\in E}\bigg{(}i_{k}!\prod_{\ell\in
E}\frac{u_{\ell k}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)},\quad i,j\in S_{N}(E),$
(44)

where the sum extends over all matrices $M=(m_{k\ell})_{k,\ell\in
E}\in\mathbb{N}_{0}^{E\times E}$ having row sums $\sum_{\ell\in
E}m_{k\ell}=i_{k}$, $k\in E$, and column sums $\sum_{k\in
E}m_{k\ell}=j_{\ell}$, $\ell\in E$. The matrix $P^{\rm mut}$ has a similar
structure as the matrix $\Pi^{\rm mut}$ with entries (26), but note that
$u_{k\ell}$ is replaced by its transpose $u_{\ell k}$ and that $i$ and $j$
belong to $S_{N}(E)$ instead of $\Delta_{N}(E)$. For general mutation matrix
$U$ the backward probabilities $p_{ij}=p_{ij}(U)$ can be calculated using the
following result.

######  Lemma 4.

The backward matrix $P=(p_{ij})_{i,j\in S_{N}(E)}$ (for the model with general
mutation matrix $U$) is given by

$P\ =\ P^{\rm mut}P^{\rm rep},$

where $P^{\rm mut}=(p_{ij}^{\rm mut})_{i,j\in S_{N}(E)}$ is the matrix with
entries (44) and $P^{\rm rep}=P(I)$ is the backward matrix for the multi-type
Cannings without mutation having entries (43).

###### Proof.

Fix $i=(i_{k})_{k\in E},j=(j_{k})_{k\in E}\in S_{N}(E)$. Recall that the model
is defined forward in time by a reproductive step (involving the offspring
sizes $\nu_{1},\ldots,\nu_{N}$) followed by a mutational step (involving the
mutation matrix $U$). Backward in time we therefore first have to take into
account the mutational step and then the reproductive step. Having this
factorization in mind it follows that

$p_{ij}(U)\ =\ \sum_{M}\bigg{(}\prod_{k\in E}\bigg{(}i_{k}!\prod_{\ell\in
E}\frac{u_{\ell k}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)}\bigg{)}p_{dj}(I),$ (45)

where the sum extends over all matrices $M=(m_{k\ell})_{k,\ell\in E}$ having
row sums $\sum_{\ell\in E}m_{k\ell}=i_{k}$ for all $k\in E$ and
$d:=(d_{\ell})_{\ell\in E}$ is defined via $d_{\ell}:=\sum_{k\in E}m_{k\ell}$
for all $\ell\in E$. Note that $|d|:=\sum_{\ell\in E}d_{\ell}=\sum_{k,\ell\in
E}m_{k\ell}=\sum_{k\in E}i_{k}=:|i|$. In particular, $d\in S_{N}(E)$. Now
split the sum in (45) into

$p_{ij}(U)\ =\ \sum_{d\in S_{N}(E)}\bigg{(}\sum_{M}\prod_{k\in
E}\bigg{(}i_{k}!\prod_{\ell\in E}\frac{u_{\ell
k}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)}\bigg{)}p_{dj}(I),$ (46)

where $\sum_{M}$ extends over all matrices $M=(m_{k\ell})_{k,\ell\in E}$
satisfying $\sum_{\ell\in E}m_{k\ell}=i_{k}$ for all $k\in E$ and $\sum_{k\in
E}m_{k\ell}=d_{\ell}$ for all $\ell\in E$. Note that the sum $\sum_{M}$ in
(46) is empty if $|d|\neq|i|$. The right-hand side in (46) is equal to
$\sum_{d\in S_{N}(E)}p_{id}^{\rm mut}p_{dj}^{\rm rep}=(P^{\rm mut}P^{\rm
rep})_{ij}$. Thus, $P=P^{\rm mut}P^{\rm rep}$. ∎

######  Remark 10.

The matrix $P$ is in general not stochastic, as already mentioned in the
remarks on page 715 of [34]. It is hence not straightforward to define a
proper ancestral process in the same way as for the model studied in Section
2.

###  3.4 Multi-type Kimura model

Let $c\in\mathbb{N}$. The Cannings population model, where the vector
$\nu_{N}:=(\nu_{1,N},\ldots,\nu_{N,N})$ of offspring sizes has the symmetric
multi-hypergeometric distribution

$\mathbb{P}(\nu=j)\ =\ \frac{1}{\binom{cN}{N}}\prod_{i\in[N]}\binom{c}{j_{i}}$

for $j=(j_{i})_{i\in[N]}\in\mathbb{N}_{0}^{N}$ with $\sum_{i\in[N]}j_{i}=N$,
is called the Kimura model with parameter $c$; see [16, p. 636] or [29]. Since
$D=(D_{k})_{k\in E}$ has a multi-hypergeometric distribution with parameters
$N$, $cN$ and $ci_{k}$, $k\in E$, i.e.,
$\mathbb{P}(D=j)=\binom{cN}{N}^{-1}\prod_{k\in E}\binom{ci_{k}}{j_{k}}$,
$i,j\in\Delta_{N}(E)$, it follows from (29) that the forward process has
transition probabilities

$\pi_{ij}\ =\ \frac{1}{\binom{cN}{N}}\sum_{M}\prod_{k\in
E}\bigg{(}\binom{ci_{k}}{j_{k}}d_{k}!\prod_{\ell\in
E}\frac{u_{k\ell}^{m_{k\ell}}}{m_{k\ell}!}\bigg{)},$ (47)

$i=(i_{k})_{k\in E},j=(j_{k})_{k\in E}\in\Delta_{N}(E)$, where the sum extends
over all matrices $M=(m_{k\ell})_{k,\ell\in E}$ having column sums $\sum_{k\in
E}m_{k\ell}=j_{\ell}$, $\ell\in E$, and $d_{k}:=\sum_{\ell\in E}m_{k\ell}$,
$k\in E$. Eq. (47) does not seem to simplify much further.

It is easily checked that the offspring sizes $\nu_{1},\ldots,\nu_{N}$ are
asymptotically independent with $\nu_{1}\to\xi$ in distribution as
$N\to\infty$, where $\xi$ has a binomial distribution with parameters $c$ and
$1/c$.

If $L:=K-1\in\mathbb{N}$ and $u_{KK}=1$, then Theorem 3 is applicable. For
$n\in\mathbb{N}_{0}$ and $x\in\mathbb{R}$,

$\displaystyle\mathbb{E}\big{(}(\xi)_{n}x^{\xi-n}\big{)}\ =\
\sum_{m=n}^{c}(m)_{n}x^{m-n}\binom{c}{m}\bigg{(}\frac{1}{c}\bigg{)}^{m}\bigg{(}1-\frac{1}{c}\bigg{)}^{c-m}$
$\displaystyle=$
$\displaystyle(c)_{n}\bigg{(}\frac{1}{c}\bigg{)}^{n}\sum_{k=0}^{c-n}\binom{c-n}{k}\bigg{(}\frac{x}{c}\bigg{)}^{k}\bigg{(}1-\frac{1}{c}\bigg{)}^{c-n-k}$
$\displaystyle=$
$\displaystyle(c)_{n}\bigg{(}\frac{1}{c}\bigg{)}^{n}\bigg{(}1-\frac{1-x}{c}\bigg{)}^{c-n}.$

Thus, for the limiting $L$-type Galton–Watson branching process the
probability (40) that an individual of type $k\in[L]$ produces for each
$\ell\in[L]$ exactly $j_{\ell}$ children of type $\ell$ is

$\mathbb{P}(Y_{k}=j)\ =\
(c)_{|j|}\bigg{(}\frac{1}{c}\bigg{)}^{|j|}\bigg{(}1-\frac{u_{k}}{c}\bigg{)}^{c-|j|}\prod_{l\in[L]}\frac{u_{k\ell}^{j_{\ell}}}{j_{\ell}!},$

$j=(j_{\ell})_{\ell\in[L]}\in\mathbb{N}_{0}^{L}$, where
$|j|:=\sum_{\ell\in[L]}j_{\ell}$ and $u_{k}:=\sum_{\ell\in[L]}u_{k\ell}$. From
Lemma 3 it follows that $Y_{k}$ has joint descending factorial moments

$\mathbb{E}\bigg{(}\prod_{\ell\in[L]}(Y_{k\ell})_{m_{\ell}}\bigg{)}\ =\
(c)_{|m|}\bigg{(}\frac{1}{c}\bigg{)}^{|m|}\prod_{\ell\in[L]}u_{k\ell}^{m_{\ell}},\quad(m_{\ell})\in\mathbb{N}_{0}^{L},$

where $|m|:=\sum_{\ell\in[L]}m_{\ell}$. Note that $\mathbb{E}(\xi)=1$ and
$\mathbb{E}((\xi)_{2})=(c)_{2}(1/c)^{2}=1-1/c$. For $\ell_{1},\ell_{2}\in[L]$
with $\ell_{1}\neq\ell_{2}$ it follows from (42) that ${\rm
Cov}(Y_{k\ell_{1}},Y_{k\ell_{2}})=-u_{k\ell_{1}}u_{k\ell_{2}}/c\leq 0$. If the
mutation probabilities are strictly positive, then $Y_{k\ell_{1}}$ and
$Y_{k\ell_{2}}$ are negatively correlated.

##  4 Discussion and open problems

In Section 2 we have analyzed the ancestry of a multi-type Cannings model with
fixed subpopulation sizes and mutation leading to limiting coalescent
processes with mutation (see Theorem 1) enjoying the exchangeability and
consistency property.

We have also studied (see Section 3) a different but closely related Cannings
model with constant total population size but variable subpopulation sizes
with an emphasis on its forward structure. Under certain conditions its
forward structure can be approximated by a limiting multi-type branching
process (Theorem 3). However, questions concerning its ancestral structure
(see Remark 10) and duality results linking its forward and backward
structure, including algebraic approaches to duality, remain open.

Particular classes of multi-type Cannings models have not been discussed in
this paper. Schweinsberg [40] studies the ancestry of a class of single-type
Cannings model obtained via sampling without replacement from a supercritical
branching process. Huillet et al. [26] study analog single-type models based
on a sampling with replacement strategy. We leave the study of multi-type
versions of the models of [40] and [26] for future work.

## References

  * [1] Allen, B. and McAvoy, A. (2022) The coalescent with arbitrary spatial and genetic structure. Preprint.
  * [2] Athreya, K. B. and Ney, P. E. (1972) _Branching Processes_. Die Grundlehren der Mathematischen Wissenschaften 196. Springer, New York. MR0373040
  * [3] Billingsley, P. (1999) _Convergence of Probability Measures_. Second Edition. Wiley, New York. MR1700749
  * [4] Birkner, M., Blath, J., Möhle, M., Steinrücken, M. and Tams, J. (2009) A modified lookdown construction for the Xi-Fleming-Viot process with mutation and populations with recurrent bottlenecks. ALEA Lat. Am. J. Probab. Math. Stat. 6, 25–61. MR2485878
  * [5] Blath, J., González Casanova, A., Kurt, N., and Spanò, D. (2013) The ancestral process of long term seed bank models. J. Appl. Probab. 50(3), 741–759. MR3102512
  * [6] Blath, J., González Casanova, A., Kurt, N. and Wilke-Berenguer, M. (2016) A new coalescent for seed-bank models. Ann. Appl. Probab. 26(2), 857–891. MR3476627
  * [7] Burke, C. J. and Rosenblatt, M. (1958) A Markovian function of a Markov chain. Ann. Math. Statist. 29, 1112–1122. MR0101557
  * [8] Cannings, C. (1974) The latent roots of certain Markov chains arising in genetics: A new approach, I. Haploid models. Advances in Appl. Probability 6(2), 260–290. MR0343949
  * [9] Cannings, C. (1975) The latent roots of certain Markov chains arising in genetics: A new approach, II. Further haploid models. Advances in Appl. Probability 7(2), 260–290. MR0371430
  * [10] Cannings, C. (1976) Multitype drift models. Advances in Appl. Probability 8(1), 1–2.
  * [11] Etheridge, A. (2011) _Some Mathematical Models from Population Genetics_. Lecture Notes in Mathematics 2012, Springer. MR2759587
  * [12] Etheridge, A. M. and Griffiths, R. C. (2009) A coalescent dual process in a Moran model with genic selection. Theoret. Population Biol. 75(4), 320–330. MR number not available
  * [13] Etheridge, A. M., Griffiths, R. C. and Taylor, J. E. (2010) A coalescent dual process in a Moran model with genic selection, and the lambda coalescent limit. Theoret. Population Biol. 78(2), 77–92. MR number not available
  * [14] Ethier, S. N. and Kurtz, T. G. (1986) _Markov Processes, Characterization and Convergence_. Wiley, New York. MR0838085
  * [15] Ewens, W. J. (2004) _Mathematical Population Genetics. I. Theoretical Introduction._ Second Edition, Springer, New York. MR2026891
  * [16] Gladstien, K. (1978) The characteristic values and vectors for a class of stochastic matrices arising in genetics. SIAM J. Appl. Math. 34(4), 630–642. MR0475977
  * [17] González Casanova, A., Peñaloza, L. and Siri-Jégousse, A. (2022) Seed bank Cannings models: how dormancy smoothes random genetic drift. arXiv preprint 2210.05819, 11 Oct 2022
  * [18] Griffiths, R. C. (1979) A transition density expansion for a multi-allele diffusion model. Advances in Appl. Probability 11(2), 310–325. MR0526415
  * [19] Griffiths, R. C. (1980a) Lines of descent in the diffusion approximation of neutral Wright-Fisher models. Theoret. Population Biol. 17(1), 37–50. MR0568666
  * [20] Griffiths, R. C. (1980b) Allele frequencies in multidimensional Wright–Fisher models with a general symmetric mutation structure. Theoret. Population Biol. 17(1), 51–70. MR0568667
  * [21] Griffiths, R. C. (1981) Neutral two-locus multiple allele models with recombination. Theoret. Population Biol. 19(2), 169–186. MR0630871
  * [22] Griffiths, R. C. (2016) A multi-type $\Lambda$-coalescent. Branching Processes and Their Applications. (Inés M. del Puerto, Miguel González, Cristina Gutiérrez, Rodrigo Martínez, Carmen Minuesa, Manuel Molina, Manuel Mona, and Alfonso Ramos, eds.), Lecture Notes in Statistics, Springer International Publishing, Cham, pp. 23–37. MR3587979
  * [23] Harris, T. E. (1963) _The Theory of Branching Processes_. Die Grundlehren der Mathematischen Wissenschaften 119, Springer, Berlin. MR0163361
  * [24] Herbots, H. M. (1994) Stochastic models in population genetics: genealogy and genetic differentiation in structured populations. PhD thesis, Queen Mary and Westfield College, University of London. MR number not available
  * [25] Herbots, H. M. (1997) The structured coalescent. In: Donnelly, P. and Tavaré, S. (Eds.), Progress in population genetics and human evolution. IMA Vol. Math. Appl. 87, 231–255, Springer, New York. MR1493030
  * [26] Huillet, T. and Möhle, M. (2022) Asymptotic genealogies for a class of generalized Wright–Fisher models. Mod. Stoch. Theory Appl. 9(1), 17–43. MR4388708
  * [27] Johnston, S. G. G., Kyprianou, A. and Rogers, T. (2022) Multitype $\Lambda$-coalescents. Ann. Appl. Probab., to appear.
  * [28] Kämmerle, K. (1991) The extinction probability of descendants in bisexual models of fixed population size. J. Appl. Probab. 28(3), 489–502. MR1123823
  * [29] Kimura, M. (1957) Some problems of stochastic processes in genetics. Ann. Math. Statist. 28, 882–901. MR0094267
  * [30] Liu, H. L. and Zhou, X. W. (2022) Generalized stepping stone model with $\Xi$-resampling mechanism. Acta Math. Sin. (Engl. Ser.) 38(11), 1998–2018. MR4515130
  * [31] Mode, C. J. (1971) _Multitype Branching Processes. Theory and Applications._ Modern Analytic and Computational Methods in Science and Mathematics 34, American Elsevier Publishing Co., Inc., New York. MR0279901
  * [32] Möhle, M. (1994) Forward and backward processes in bisexual models with fixed population size. J. Appl. Probab. 31(2), 309–332. MR1274789
  * [33] Möhle, M. (2002) The coalescent in population models with time-inhomogeneous environment. Stochastic Process. Appl. 97(2), 199–227. MR1875333
  * [34] Möhle, M. (2010) Looking forwards and backwards in the multi-allelic neutral Cannings population model. J. Appl. Probab. 47(3), 713–731. MR2731344
  * [35] Möhle, M. and Sagitov, S. (2001) A classification of coalescent processes for haploid exchangeable population models. Ann. Probab. 29(4), 1547–1562. MR1880231
  * [36] Notohara, M. (1990) The coalescent and the genealogical process in geographically structured population. J. Math. Biol. 29(1), 59–75. MR1083665
  * [37] Popovic, L. and Rivas, M. (2014) The coalescent point process of multi-type branching trees. Stochastic Process. Appl. 124(12), 4120–4148. MR3264441
  * [38] Port, S. C. (1968) A multitype stochastic population model: an extended version. The RAND Corp., RM-5659-PR. MR number not available
  * [39] Schweinsberg, J. (2000) Coalescents with simultaneous multiple collisions. Electron. J. Probab. 5, 1–50. MR1781024
  * [40] Schweinsberg, J. (2003) Coalescent processes obtained from supercritical Galton–Watson processes. Stochastic Process. Appl. 106(1), 107–139. MR1983046
  * [41] Wilkinson–Herbots, H. M. (1998) Genealogy and subpopulation differentiation under various models of population structure. J. Math. Biol. 37(6), 535–585. MR1664797