# Trees within trees: Simple nested coalescents

###### Abstract

We consider the compact space of pairs of nested partitions of $\mathbb{N}$,
where by analogy with models used in molecular evolution, we call “gene
partition” the finer partition and “species partition” the coarser one. We
introduce the class of nondecreasing processes valued in nested partitions,
assumed Markovian and with exchangeable semigroup. These processes are said
simple when each partition only undergoes one coalescence event at a time (but
possibly the same time). Simple nested exchangeable coalescent (SNEC)
processes can be seen as the extension of $\Lambda$-coalescents to nested
partitions. We characterize the law of SNEC processes as follows. In the
absence of gene coalescences, species blocks undergo $\Lambda$-coalescent type
events and in the absence of species coalescences, gene blocks lying in the
same species block undergo i.i.d. $\Lambda$-coalescents. Simultaneous
coalescence of the gene and species partitions are governed by an intensity
measure $\nu_{s}$ on $(0,1]\times{\mathcal{M}}_{1}([0,1])$ providing the
frequency of species merging and the law in which are drawn (independently)
the frequencies of genes merging in each coalescing species block. As an
application, we also study the conditions under which a SNEC process comes
down from infinity.

Airam Blancas1, Jean-Jil Duchamps2,3, Amaury Lambert2,3, Arno Siri-Jégousse4

1 Institut für Mathematik, Goethe-Universität, Frankfurt, Germany;
2 Laboratoire de Probabilités, Statistique et Modélisation (LPSM), Sorbonne
Université, CNRS UMR 8001, Paris, France;
3 Center for Interdisciplinary Research in Biology (CIRB), Collège de France,
CNRS UMR 7241, INSERM U1050, PSL Research University, Paris, France;
4 Instituto de Investigaciones en Matemáticas Aplicadas y Sistemas (IIMAS),
Universidad Nacional Autónoma de México (UNAM), Mexico City, Mexico.

#### Keywords and phrases:

Lambda-coalescent; exchangeable; partition; coming down from infinity; random
tree; gene tree; population genetics; species tree; phylogenetics; evolution.

#### MSC 2000 Classification.

60G09, 60G57, 60J35, 60J75, 92D10, 92D15.

##  1 Introduction

In the framework of population biology, one can see asexual organisms, but
also DNA sequences or even species, as replicating particles. The genealogical
ascendance of co-existing replicating particles can always be represented by a
tree whose tips are labelled by the names of these particles [25, 27, 42].
Even if species are not strictly speaking replicating particles, ancestral
relationships between species are also usually represented by a tree whose
nodes are interpreted as _speciation_ events, i.e., the emergence of two or
more species from one single species. The inference of the so-called _gene
tree_ of contemporary DNA sequences from their comparison has a decade-long
history. It is considered as a field in its own right, called _molecular
phylogenetics_ [19, 32], which relies heavily on the theory of Markov
processes. (This can be misleading, but the _species tree_ , much more often
than the gene tree, is called a _phylogeny_.)

When one type of replicating particle is physically embedded in another type
of particle, like a virus in its host, their common history can be depicted as
a _tree within a tree_ [14, 29, 34]: tree of dividing parasites inside the
tree of dividing hosts, tree of paralogous genes (i.e. distinct DNA segments
resulting from gene duplication and coding for similar functions) inside the
gene family tree, gene tree inside the species tree. In many such cases,
biologists are more interested in the coarser tree rather than in the finer
tree. Typically, the finer tree is a gene tree and is inferred thanks to
methods developed in molecular phylogenetics. One of the current
methodological challenges in quantitative biology is to devise fast
statistical algorithms able to also infer the coarser tree. When the genes are
sampled from infecting pathogens of the same species (Influenza, HIV…), the
coarser tree is the epidemic transmission process [21, 45]. When the genes are
sampled from (any kind of) different species, the coarser tree is the _species
tree_ [33, 22, 43]. It is often required to use several gene trees nested in
the same species tree to infer the latter.

In terms of stochastic modeling, the standard strategy is to define the two
nested trees in a hierarchical model referred to as the _multispecies
coalescent model_ [36, 12] (see also [18, 3] for recent surveys on general
coalescent theory and applications to population genetics). First, the species
tree is fixed or drawn from some classic probability distribution (e.g., pure-
birth process stopped at some fixed time, viewed as present time). Second,
each gene sequence is assigned to the contemporary species it is (supposed to
be) sampled from. Recall that each contemporary species is in correspondence
with a tip of the species tree. Third, conditional on the species tree, each
gene lineage can then be traced backwards in time inside the species tree,
starting from the tip species harboring it and traveling through its ancestral
species successively. In addition, gene lineages are assumed to coalesce
according to the _censored Kingman coalescent_ [24], i.e., each pair of
lineages _lying in the same species_ independently coalesces at constant rate.

In the case when the species tree is also distributed as a Kingman coalescent,
the former two-type coalescent process is a Markov process as time runs
backward, that we call the _nested Kingman coalescent_ (or ‘Kingman-in-
Kingman’) [28, 8, 11]. Our goal here is to display a much richer class of
Markov models for trees within trees, called _simple nested exchangeable
coalescent_ (SNEC) processes, where multiple species lineages can merge into
one single species lineage, and where simultaneously, within those merging
species, multiple gene lineages can merge into one single gene lineage. To
make this more precise, we show in the next display some valid and invalid
coalescence events from an initial state where six genes, labeled from 1 to 6,
are grouped by pairs in three species lineages. We represent this situation in
the next display by a pair of partitions $\binom{\pi^{s}}{\pi^{g}}$, as in the
left-hand side of the display. Event (A) is valid because the first two
species merge and simultaneously, _within_ these species, genes labeled 1, 2
and 3 coalesce. On the contrary, event (B) is not a valid transition because
there are two distinct gene coalescences (1 with 2, and 3 with 4), which is
proscribed, and event (C) is not valid because the gene coalescence (5 with 6)
is outside the species coalescence.

$\displaystyle\Bigg{(}\\!\\!\\!\mbox{
\begin{tabular}[]{l@{~}l@{~}l@{~}l@{~}l@{~}l}\\{ 1,\hfil~{}&2
\\}\\{\hfil~{}&3,\hfil~{}&4 \\}\\{\hfil~{}&5,\hfil~{}&6 \\}\\\ \\{ 1
\\}\\{\hfil~{}&2 \\}\\{\hfil~{}&3 \\}\\{\hfil~{}&4 \\}\\{\hfil~{}&5
\\}\\{\hfil~{}&6 \\}\end{tabular} }\\!\\!\\!\Bigg{)}$
$\displaystyle\rightarrow\Bigg{(}\\!\\!\\!\mbox{
\begin{tabular}[]{l@{~}l@{~}l@{~}l@{~}l@{~}l}\\{
1,\hfil~{}&2,\hfil~{}&3,\hfil~{}&4 \\}\\{\hfil~{}&5,\hfil~{}&6 \\}\\\ \\{
1,\phantom{\\}\\{}\hfil~{}&2,\phantom{\\}\\{}\hfil~{}&3 \\}\\{\hfil~{}&4
\\}\\{\hfil~{}&5 \\}\\{\hfil~{}&6 \\}\end{tabular} }\\!\\!\\!\Bigg{)}$ (A)
$\displaystyle\not\rightarrow\Bigg{(}\\!\\!\\!\mbox{
\begin{tabular}[]{l@{~}l@{~}l@{~}l@{~}l@{~}l}\\{
1,\hfil~{}&2,\hfil~{}&3,\hfil~{}&4 \\}\\{\hfil~{}&5,\hfil~{}&6 \\}\\\ \\{
1,\phantom{\\}\\{}\hfil~{}&2 \\}\\{\hfil~{}&3,\phantom{\\}\\{}\hfil~{}&4
\\}\\{\hfil~{}&5 \\}\\{\hfil~{}&6 \\}\end{tabular} }\\!\\!\\!\Bigg{)}$ (B)
$\displaystyle\not\rightarrow\Bigg{(}\\!\\!\\!\mbox{
\begin{tabular}[]{l@{~}l@{~}l@{~}l@{~}l@{~}l}\\{
1,\hfil~{}&2,\hfil~{}&3,\hfil~{}&4 \\}\\{\hfil~{}&5,\hfil~{}&6 \\}\\\ \\{ 1
\\}\\{\hfil~{}&2 \\}\\{\hfil~{}&3 \\}\\{\hfil~{}&4
\\}\\{\hfil~{}&5,\phantom{\\}\\{}\hfil~{}&6 \\}\end{tabular}
}\\!\\!\\!\Bigg{)}$ (C)

In brief, SNEC processes are the generalization of _$\Lambda$ -coalescents_ to
processes valued, not in partitions of $\mathbb{N}$, but in pairs of nested
partitions of $\mathbb{N}$. The class of $\Lambda$-coalescents [37, 35], for
which only one coalescence event can occur at a time, is a subclass of Markov,
exchangeable processes with possibly non-binary nodes, called _$\Xi$
-coalescents_, where several coalescence events can be simultaneous [4, 38].

Non-binary nodes in species trees can be interpreted as _unresolved nodes_ (a
sequence of binary nodes following each other too closely in time for their
order to be inferred correctly) or _radiation_ events (periods of frequent
speciations due to the opening of new ecological opportunities that can be
exploited by different, new species). In gene trees, non-binary nodes are
increasingly recognized as a conspicuous sign of natural selection both by
biologists [44, 30] and by mathematicians and physicists [1, 16, 10, 31, 13,
41] ; it is also well understood that non-binary nodes could be consequences
of bottlenecks as well as large variance in offspring distributions [17, 40].
The class of SNEC processes includes all these features. They can distinguish
unresolved nodes (sequence of stochastically close, binary coalescences) from
radiations (multiple merger in the species tree). Under the interpretation of
non-binary nodes as a result of natural selection, SNEC processes can model
the appearance of alleles responsible for positive selection (multiple merger
in the gene tree) or for divergent adaptation (multiple merger simultaneously
in the gene tree and in the species tree).

From a mathematical point of view as well, SNEC processes open up the door to
many possible new investigations. For example some of us are currently
studying the speed of coming down from infinity of SNEC processes [28, 8] as
well as similar extensions [15] to fragmentation processes [4]. It will be
interesting to investigate how the nested trees generated by SNEC processes
can be cast in the frameworks of multilevel measure-valued processes [7, 11]
and flows of bridges [5, 6] as well as of exchangeable combs [20, 26]. It
would also be natural to study the extension of $\Xi$-coalescents to nested
partitions.

#### Organization of the article.

In Section 2, we introduce some notation, and give examples of nested
coalescent processes whose distributions are characterized by four parameters.
Section 3 formally defines our object of study, the SNEC processes. We prove
our main result in Section 4, and show in Section 5 how SNEC processes can be
constructed from a collection of Poisson point processes. Finally, Section 6
gives a necessary and sufficient condition under which SNEC processes come
down from infinity.

##  2 Statement of results and notation

###  2.1 Statement of results and examples

An exchangeable partition is a random partition of $\mathbb{N}$ whose law is
invariant by permutations of $\mathbb{N}$ (with finite support). A
$\Lambda$-coalescent is a Markov process valued in the exchangeable partitions
of $\mathbb{N}$ typically starting from the partition $\mathbf{0}_{\infty}$ of
$\mathbb{N}$ into singletons, and such that only one coalescence event can
occur at a time. The generator of a $\Lambda$-coalescent
$\mathcal{R}=(\mathcal{R}(t),t\geq 0)$ is characterized by a $\sigma$-finite
measure $\nu$ on $(0,1]$ called the coagulation measure and a non-negative
real number $a$ called the Kingman coefficient. Then $\mathcal{R}$ can be
constructed from a Poisson point process as follows.

For $x\in(0,1]$, let $P_{x}$ denote the law of a sequence of i.i.d.
Bernoulli$(x)$ r.v.’s and define

$P:=\int_{(0,1]}\nu(dx)P_{x}$

Also define ${\tt K}_{i,i^{\prime}}$ the (Dirac) law of the sequence with only
zero entries except a 1 at positions $i$ and $i^{\prime}$ and set

${\tt K}:=\sum_{1\leq i<i^{\prime}}{\tt K}_{i,i^{\prime}}$

Finally, let $M$ be a Poisson point process with intensity measure
$dt\otimes(P+a{\tt K})$. Roughly speaking, at each atom $(t,(X_{i},i\geq 1))$
of $M$, $\mathcal{R}(t)$ is obtained from $\mathcal{R}(t-)$ by merging exactly
the $i$-th block of $\mathcal{R}(t-)$ together, for all $i$ such that
$X_{i}=1$. The rigorous description is given through restrictions of
$\mathcal{R}$ to $[n]:=\\{1,\ldots,n\\}$ and by applying Kolmogorov extension
theorem. See [4] for details. Note that for this description to apply (i.e.,
for restrictions of $\mathcal{R}$ to $[n]$ to have positive holding times),
one needs the coagulation measure to satisfy

$\int_{(0,1]}x^{2}\,\nu(dx)<\infty.$ (2.9)

The finite measure $x^{2}\,\nu(dx)$ is usually denoted $\Lambda(dx)$, hence
the name $\Lambda$-coalescent.

We can now draw the parallel with the results obtained in this paper. We want
to define a Markov process
$\mathcal{R}=\left((\mathcal{R}^{s}(t),\mathcal{R}^{g}(t)),\;t\geq 0\right)$
valued in exchangeable bivariate, nested partitions of $\mathbb{N}$, in the
sense that the _gene partition_ $\mathcal{R}^{g}(t)$ is finer than the
_species partition_ $\mathcal{R}^{s}(t)$ for all $t$ a.s.

We now have to allow for coalescences in both the gene partition and the
species partition. To this aim, we will consider a doubly indexed array of 0’s
and 1’s $\mathbf{Z}={(\mathbf{X},(\mathbf{Y}_{i},\,i\geq
1))}=(X_{i},Y_{ij},\,i,j\geq 1)$. The goal is to give a characterization and a
Poissonian construction of $\mathcal{R}$ under the assumptions that the
semigroup of $\mathcal{R}$ is exchangeable and that both $\mathcal{R}^{s}$ and
$\mathcal{R}^{g}$ undergo only one coalescence at a time (but possibly the
same time), as detailed in forthcoming Definition 2. Roughly speaking, and
similarly as previously, $X_{i}$ will determine whether the $i$-th species
block participates in the coalescence in the species partition
$\mathcal{R}^{s}$, and $Y_{ij}$ whether the $j$-th gene block of the $i$-th
species block participates in the coalescence in the gene partition
$\mathcal{R}^{g}$.

Let us start with the Kingman-type coalescences. Let ${\tt
K}^{s}_{i,i^{\prime}}$ be the (Dirac) law of the array $\mathbf{Z}$ with only
zero entries except $X_{i}=X_{i^{\prime}}=1$ and let ${\tt
K}^{g}_{i;j,j^{\prime}}$ be the (Dirac) law of the array $\mathbf{Z}$ with
only zero entries except $X_{i}=Y_{ij}=Y_{ij^{\prime}}=1$. Finally, define

${\tt K}^{s}=\sum_{1\leq i<i^{\prime}}{\tt K}^{s}_{i,i^{\prime}}\quad\mbox{
and }\quad{\tt K}^{g}=\sum_{1\leq i}\sum_{1\leq j<j^{\prime}}{\tt
K}^{g}_{i;j,j^{\prime}}$

Let us carry on with multiple gene mergers without simultaneous species
coalescences. Let $x\in(0,1]$ and $i\in\mathbb{N}$. Let $P^{g}_{i,x}$ be the
distribution of the array $\mathbf{Z}$ with only zero entries except at row
$i$, where $X_{i}=1$ and the $(Y_{ij},\,j\geq 1)$ are i.i.d. Bernoulli$(x)$
r.v.’s. Let us define

$P^{g}_{x}:=\sum_{i\geq 1}P^{g}_{i,x}$

Finally, let us consider multiple species mergers, with possible simultaneous
gene mergers. Let $x\in(0,1]$ and $\mu\in\mathcal{M}_{1}([0,1])$. Let
$(X_{i},\,i\geq 1)$ be a sequence of i.i.d. Bernoulli$(x)$ r.v.’s and let
$(Q_{i},\,i\geq 1)$ be an independent sequence of i.i.d. r.v.’s of $[0,1]$
with distribution $\mu$. Then for each $i\geq 1$, conditional on $X_{i}$ and
$Q_{i}$, let $(Y_{ij},\,j\geq 1)$ be an independent sequence of i.i.d.
Bernoulli$(Q_{i})$ r.v.’s. if $X_{i}=1$ and the null array otherwise. Let us
write $P^{s}_{x,\mu}$ for the distribution of the array $\mathbf{Z}$ thus
defined.

Our main result is that for any simple nested exchangeable coalescent (SNEC)
process $\mathcal{R}$, there are

  * •

two non-negative real numbers $a_{s}$ and $a_{g}$;

  * •

a $\sigma$-finite measure $\nu_{g}$ on $(0,1]$;

  * •

a $\sigma$-finite measure $\nu_{s}$ on $(0,1]\times\mathcal{M}_{1}([0,1])$,

such that $\mathcal{R}$ can be constructed from a Poisson point process $M$
with intensity $dt\otimes\nu(d\mathbf{Z})$ where

$\nu:=a_{s}{\tt K}_{s}+a_{g}{\tt
K}_{g}+\int_{(0,1]}\nu_{g}(dx)\,P^{g}_{x}+\int_{(0,1]\times\mathcal{M}_{1}([0,1])}\nu_{s}(dx,d\mu)\,P^{s}_{x,\mu}.$

Similarly as explained previously, at each atom $(t,\mathbf{Z})$ of $M$, the
double array $\mathbf{Z}$ prescribes which blocks have to merge at time $t$.
For the finite restrictions of $\mathcal{R}$ to have positive holding times,
the measures $\nu_{s}$ and $\nu_{g}$ are required to satisfy the forthcoming
conditions (3.15) and (3.16) respectively, which are the analogs to (2.9).

Note that coagulations of the Kingman type cannot occur simultaneously in the
species partition and in the gene partition.

We now give a couple of examples of SNEC processes.

If $\nu_{s}(dp,d\mu)=\nu_{s}^{\prime}(dp)\,\delta_{\delta_{0}}(d\mu)$, species
and genes never coalesce simultaneously and the nested coalescent is a
multispecies coalescent (see Introduction), where the species tree is given by
the $\Lambda$-coalescent with coagulation measure $\nu_{s}^{\prime}$ and
Kingman coefficient $a_{s}$, while the genes in the same species block undergo
independent $\Lambda$-coalescents with coagulation measure $\nu_{g}$ and
Kingman coefficient $a_{g}$. In particular, when $\nu_{s}^{\prime}$ and
$\nu_{g}$ are zero, the SNEC process is a nested Kingman coalescent (Kingman-
in-Kingman).

Whenever $\nu_{s}$ is not under the form
$\nu_{s}(dp,d\mu)=\nu_{s}^{\prime}(dp)\,\delta_{\delta_{0}}(d\mu)$, species
blocks and gene blocks can coalesce simultaneously. For example if
$\nu_{s}(dp,d\mu)=\nu_{s}^{\prime}(dp)\,\delta_{\delta_{x}}(d\mu)$ for
$x\in(0,1]$, at each species coalescence event, a proportion $x$ of gene
blocks contained in the species blocks participating in the coalescence event,
are simultaneously merged together. In particular, if $x=1$, the gene tree
coincides with the species tree on lineages situated after a species
coalescence event. Recall that there are conditions (see (3.15)) for $\nu_{s}$
to be a correct SNEC measure, which in this case translate to

$\displaystyle\int_{(0,1]}\nu_{s}^{\prime}(dp)\,p^{2}<\infty\quad\text{ and
}\quad\int_{(0,1]}\nu_{s}^{\prime}(dp)\,p\,x^{2}<\infty,$

which is simply equivalent to

$\int_{(0,1]}\nu_{s}^{\prime}(dp)\,p<\infty.$

Otherwise the simplest sort of measure $\nu_{s}$ can be obtained by
parameterizing its second component $\mu$, for example if $\mu$ is a Beta
distribution $\mu_{a,b}(dq)=c_{a,b}\,q^{a-1}(1-q)^{b-1}\,dq$, where $a,b>0$
and $c_{a,b}=\frac{\Gamma(a+b)}{\Gamma(a)\,\Gamma(b)}$, we can consider
$\nu_{s}$ under the form

$\nu_{s}(dp,d\mu)=\nu_{s}^{\prime}(dp,da,db)\,\delta_{\mu_{a,b}}(d\mu).$

In this case, the condition (3.15a) reads

$\int_{(0,1]\times(0,\infty)\times(0,\infty)}\nu_{s}^{\prime}(dp,da,db)\,p^{2}<\infty,$

and (3.15b) becomes

$\int_{(0,1]\times(0,\infty)\times(0,\infty)}\nu_{s}^{\prime}(dp,da,db)\,p\int_{[0,1]}c_{a,b}\,q^{a+1}(1-q)^{b-1}\,dq<\infty,$

which can be rewritten

$\int_{(0,1]\times(0,\infty)\times(0,\infty)}\nu_{s}^{\prime}(dp,da,db)\,\frac{pa(a+1)}{(a+b)(a+b+1)}<\infty.$

Note that the idea to use a Beta distribution here is inspired by the
$\Lambda$-coalescent setting [35], where Beta distributions appear as natural
candidates for the parametrization of the measure $\Lambda$, as the
coalescence rate of each $k$-tuple of blocks among a total number of $b$
blocks is expressed in the form

$\int_{0}^{1}x^{k-2}(1-x)^{b-k}\Lambda(dx).$

###  2.2 Notation

For any $n\in\bar{\mathbb{N}}:=\mathbb{N}\cup\\{+\infty\\}$, let
$\mathcal{P}_{n}$ be the set of partitions of $[n]$ . A partition $\pi$ is
called _simple_ if at most one of its non-empty blocks is not a singleton. We
denote the set of simple partitions of $[n]$ by $\mathcal{P}_{n}^{\prime}$,
that is,

$\mathcal{P}_{n}^{\prime}=\\{\pi\in\mathcal{P}_{n},\;\text{Card}\\{i,\;|\pi_{i}|>1\\}\leq
1\\}$

where $\pi_{1},\pi_{2},\dots$ denote the blocks of $\pi$ ordered by their
least element and $|\pi_{i}|$ stands for the number of elements in the block
$\pi_{i}$. Recall that a partition $\pi$ can be viewed as an equivalence
relation, in the sense that $i\overset{\pi}{\thicksim}j$ if and only if $i$
and $j$ belong to the same block of the partition $\pi$. If $\pi^{g}$ and
$\pi^{s}$ belong to $\mathcal{P}_{n}$, we will say that the bivariate
partition $\pi=(\pi^{s},\pi^{g})$ is _nested_ (or equivalently that $\pi^{g}$
is finer than $\pi^{s}$) when

$i\overset{\pi^{g}}{\thicksim}j\ \Longrightarrow\
i\overset{\pi^{s}}{\thicksim}j.$

Note that this is defines a natural partial order on $\mathcal{P}_{n}$, and we
can write $\pi^{g}\preceq\pi^{s}$ if $(\pi^{g},\pi^{s})$ is nested. The set of
nested partitions of $[n]$ is denoted in the sequel by $\mathcal{N}_{n}$. We
will sometimes use the notation $\mathbf{1}_{n}:=\\{[n]\\}$ for the coarsest
partition of $[n]$, and $\mathbf{0}_{n}:=\\{\\{1\\},\\{2\\},\ldots\\}$ for the
finest partition of $[n]$.

######  Example 1.

An example of nested partition of $\\{1,2,\ldots,10\\}$ is given by

$\displaystyle\pi^{s}$
$\displaystyle=\big{\\{}\\{1,5,7\\},\;\\{2,4,8,10\\},\;\\{3,6,9\\}\big{\\}}$
$\displaystyle\pi^{g}$
$\displaystyle=\big{\\{}\\{1\\},\;\\{2,4\\},\;\\{3\\},\;\\{5,7\\},\;\\{6,9\\},\;\\{8\\},\;\\{10\\}\big{\\}}.$

The notation $(\pi^{s},\pi^{g})$ owes to our modeling inspiration (see
Introduction) where gene lineages are enclosed into species lineages.

Notation related to and properties of $\mathcal{P}_{n}$ can naturally be
extended to the framework of bivariate partitions. For the sake of
completeness we specify here the ones we will use repeatedly. The number of
non-empty blocks of a bivariate partition
$\pi=(\pi_{1},\pi_{2})\in\mathcal{P}_{n_{1}}\times\mathcal{P}_{n_{2}}$ is
merely $|\pi|:=(|\pi_{1}|,|\pi_{2}|)$. If $m_{1}<n_{1}$ and $m_{2}<n_{2}$, we
write $\pi_{|m_{1}\times m_{2}}$ for the restriction of $\pi$ to
$\mathcal{P}_{m_{1}}\times\mathcal{P}_{m_{2}}$, that is, $\pi_{|m_{1}\times
m_{2}}=(\pi_{1\,|m_{1}},\pi_{2\,|m_{2}})$. If $m\leq\min(n_{1},n_{2})$, we
will write $\pi_{|m}:=\pi_{|m\times m}$ for its restriction to
$\mathcal{P}^{2}_{m}:=\mathcal{P}_{m}\times\mathcal{P}_{m}$. A sequence
$\pi^{(1)},\pi^{(2)},...$ of elements of
$\mathcal{P}_{1}^{2},\mathcal{P}_{2}^{2},...$ is called _consistent_ if for
all integers $k^{\prime}\leq k$, $\pi^{(k^{\prime})}$ coincides with the
restriction of $\pi^{(k)}$ to $[k^{\prime}]^{2}$. Moreover, a sequence of
partitions $(\pi^{(n)}:n\in\mathbb{N})$ is consistent if and only if there
exists $\pi\in\mathcal{P}^{2}_{\infty}$ such that $\pi_{|{n}}=\pi^{(n)}$ for
every $n\in\mathbb{N}$.

Given a nested partition we can use the coagulation operator Coag (more
details in Chapter 3 in Bertoin [4]) to write the species partition in terms
of the labels of the gene partition. Recall that if $\pi\in\mathcal{P}_{n}$
and $\tilde{\pi}\in\mathcal{P}_{m}$ with $m\geq|\pi|$, then define
$\pi^{\prime}=\text{Coag}(\pi,\tilde{\pi})$ as the partition of
$\mathcal{P}_{n}$ such that

$\pi^{\prime}_{j}=\bigcup_{i\in\tilde{\pi}_{j}}\pi_{i}.$

For every $n\in\bar{\mathbb{N}}$, let $\pi=(\pi^{s},\pi^{g})$ be an element of
$\mathcal{N}_{n}$ and write $m=|\pi^{g}|$. The unique partition
$\bar{\pi}\in\mathcal{P}_{m}$ such that
$\pi^{s}=\text{Coag}(\pi^{g},\bar{\pi})$ is called the _link_ partition of
$\pi$. We sometimes say that $\pi$ is linked by $\bar{\pi}$. To illustrate the
previous definition, observe that the nested partition defined in Example 1
has link partition $\bar{\pi}=\\{\\{1,4\\},\\{2,6,7\\},\\{3,5\\}\\}$.

We can next get a partition of $\mathcal{P}_{n_{1}}\times\mathcal{P}_{n_{2}}$
through the coagulation of two pairs of partitions. More precisely, if
$(\pi^{1},\tilde{\pi}^{1})\in\mathcal{P}_{n_{1}}\times\mathcal{P}_{n_{1}^{\prime}}$
and
$(\pi^{2},\tilde{\pi}^{2})\in\mathcal{P}_{n_{2}}\times\mathcal{P}_{n_{2}^{\prime}}$
with $n_{1}^{\prime}\geq|\pi^{1}|$ and $n_{2}^{\prime}\geq|\pi^{2}|$, then
$(\text{Coag}(\pi^{1},\tilde{\pi}^{1}),\text{Coag}(\pi^{2},\tilde{\pi}^{2}))$
is well defined and it is an element of
$\mathcal{P}_{n_{1}}\times\mathcal{P}_{n_{2}}$. If we denote
$\pi=(\pi^{1},\pi^{2})$ and $\tilde{\pi}=(\tilde{\pi}^{1},\tilde{\pi}^{2})$ we
will say that the pair $(\pi,\tilde{\pi})$ is _admissible_ and denote the
latter operation by $\text{Coag}_{2}(\pi,\tilde{\pi})$. In the following we
will sometimes call the partition $\tilde{\pi}$ as the _recipe_ partition.

In the sequel, we are interested in the coagulation of a nested partition, say
$\pi=(\pi^{s},\pi^{g})$, with a pair of simple partitions
$\tilde{\pi}=(\tilde{\pi}^{s},\tilde{\pi}^{g})$. Nevertheless, we should
observe that the resulting partition, $\text{Coag}_{2}(\pi,\tilde{\pi})$ is
not necessarily nested. For instance, if we coagulate the partition $\pi$ of
Example 1, with $\tilde{\pi}^{s}=\\{\\{1,2\\},\\{3\\}\\}$, and
$\tilde{\pi}^{g}=\\{\\{1,3\\},\\{2\\},\\{4\\},\\{5\\},\\{6\\},\\{7\\}\\}$ then
$\text{Coag}(\pi^{g},\tilde{\pi}^{g})$ is not nested in
$\text{Coag}(\pi^{s},\tilde{\pi}^{s})$. In order to maintain the nested
property while coagulating a nested partition we need to watch out the way the
gene blocks do merge together and if they respect the species structure. To
this end, for any $n\in\bar{\mathbb{N}}$ and $\pi\in\mathcal{N}_{n}$, we can
define the set
$\widetilde{\mathcal{P}}(\pi)\subset(\mathcal{P}^{\prime}_{n})^{2}$ of simple
recipe partitions permitting a consistent merger of species and genes, i.e.

$\widetilde{\mathcal{P}}(\pi)=\Big{\\{}\tilde{\pi}=(\tilde{\pi}^{s},\tilde{\pi}^{g})\in(\mathcal{P}_{n}^{\prime})^{2},\;i\overset{\widetilde{\pi}^{g}}{\sim}j\implies
i\overset{\bar{\pi}}{\sim}j,\text{ or
}k\overset{\widetilde{\pi}^{s}}{\sim}l,\text{ where
}\pi^{g}_{i}\subset\pi^{s}_{k}\text{ and
}\pi^{g}_{l}\subset\pi^{s}_{l}\Big{\\}},$

where $\bar{\pi}$ denotes as usual the link partition of $\pi$. Simply put,
$\widetilde{\mathcal{P}}(\pi)$ is the subset of
$(\mathcal{P}_{n}^{\prime})^{2}$ such that

$\tilde{\pi}\in\widetilde{\mathcal{P}}(\pi)\iff\text{Coag}_{2}(\pi,\tilde{\pi})\in\mathcal{N}_{n}.$

Finally the natural partial order on partitions can be extended to bivariate
partitions by defining
$(\pi^{1,s},\pi^{1,g})\preceq(\pi^{2,s},\pi^{2,g})\iff\pi^{1,s}\preceq\pi^{2,s}$
and $\pi^{1,g}\preceq\pi^{2,g}$. This partial order allows us to see
coalescent processes as nondecreasing processes in the space of nested
partitions.

##  3 Simple nested exchangeable coalescents

In the aim to describe the joint dynamics of the species and gene partitions,
we will now define a nondecreasing process with values in the nested
partitions, called _nested coalescent process_. In this work we are only
interested in _simple_ nested coalescents in the sense that at any jump event,
called coalescence event, all blocks undergoing a modification merge into one
single block. Simple exchangeable coalescent processes were first introduced
independently by Pitman [35] and Sagitov [37], and are usually called in the
literature $\Lambda$-coalescents (see Introduction). Here we use the term
_simple_ as in [4], to denote the analog of a $\Lambda$-coalescent process in
the case of (nested) bivariate partitions.

Note that for any partition $\pi\in\mathcal{P}_{\infty}$ and any _injection_
$\sigma:\mathbb{N}\to\mathbb{N}$, there is a partition $\sigma(\pi)$ defined
by

$i\overset{\sigma(\pi)}{\thicksim}j\iff\sigma(i)\overset{\pi}{\thicksim}\sigma(j).$

For bivariate partitions we define in the same way
$\sigma(\pi^{s},\pi^{g}):=(\sigma(\pi^{s}),\sigma(\pi^{g}))$. For random
partitions, exchangeability is usually defined as invariance under the action
of permutations $\sigma:\mathbb{N}\to\mathbb{N}$. Here, to avoid degenerate
processes we will define our processes as being invariant under the action of
all injections $\sigma:\mathbb{N}\to\mathbb{N}$. Indeed, by making this
assumption we avoid dependence on, for instance, the total number of blocks of
the partition. An example of what we consider here a degenerate process with
values in $\mathcal{P}_{\infty}$ would be a modified Kingman coalescent where
any pair of blocks merge at rate $a=a(n)$, a function of $n$ the total number
of blocks. While this process would be invariant under permutations of
$\mathbb{N}$, it is in general not invariant under injections, as their action
can change the total number of blocks in a partition of $\mathbb{N}$.
Furthermore, given $(\Pi(t),\,t\geq 0)$ such a process and $n$ an integer, the
restriction $(\Pi(t)_{|n},\,t\geq 0)$ would not be a Markov process, as the
jump rates of $\Pi(t)_{|n}$ depend on the whole partition $\Pi(t)$. Invariance
under injections ensures us that processes can be consistently defined, i.e.
that $(\Pi(t)_{|n},\,t\geq 0)$ will always be a Markov process. It will also
be useful in forthcoming proofs to consider invariance under injections rather
than only permutations.

Since we consider processes with values in the space $\mathcal{P}_{\infty}$,
let us endow it with the natural topology generated by the sets of the form
$\\{\pi^{\prime}\in\mathcal{P}_{\infty},\,\pi^{\prime}_{|n}=\pi\\}$ for
$n\in\mathbb{N}$ and $\pi\in\mathcal{P}_{n}$. It is readily checked that this
topology is metrizable and makes $\mathcal{P}_{\infty}$ compact. Also, note
that the product topology on $\mathcal{P}_{\infty}^{2}$, and that induced on
$\mathcal{N}_{\infty}$ also makes them compact.

######  Definition 2.

Let $\mathcal{R}:=\left((\mathcal{R}^{s}(t),\mathcal{R}^{g}(t)),\;t\geq
0\right)$ be a càdlàg Markov process with values in
$\mathcal{P}^{2}_{\infty}$. This process is called a _simple nested
exchangeable coalescent_ , SNEC for short, if

  1. i)

For any $t\geq 0$, $\mathcal{R}(t)$ is nested;

  2. ii)

The process $(\mathcal{R}(t),\;t\geq 0)$ evolves with simple coalescence
events, that is for any time $t\geq 0$ such that
$\mathcal{R}(t-)\neq\mathcal{R}(t)$, there is a random bivariate partition
$\widetilde{\mathcal{R}}(t)=(\widetilde{\mathcal{R}}^{s}(t),\widetilde{\mathcal{R}}^{g}(t))$
taking values in $\widetilde{\mathcal{P}}(\mathcal{R}(t-))$ such that

${\mathcal{R}(t)=\text{Coag}_{2}(\mathcal{R}(t-),\widetilde{\mathcal{R}}(t));}$

  3. iii)

The semigroup of the process $(\mathcal{R}(t),\;t\geq 0)$ is exchangeable, in
the sense that for any $t,t^{\prime}\geq 0$ and any _injection_
$\sigma:\mathbb{N}\to\mathbb{N}$,

$\left(\sigma(\mathcal{R}(t+t^{\prime}))\mid\mathcal{R}(t)=\pi\right)\stackrel{{\scriptstyle(d)}}{{=}}\left(\mathcal{R}(t+t^{\prime})\mid\mathcal{R}(t)=\sigma(\pi)\right).$
(3.10)

To start the analysis of SNEC processes we would like to make some
observations related to Definition 2. First note that $\mathcal{R}$ is a
$\mathcal{N}_{\infty}$-valued process such that for every $t,t^{\prime}\geq
0$, the conditional distribution of $\mathcal{R}(t+t^{\prime})$ given
$\mathcal{R}(t)=\pi$ is the law of $\text{Coag}_{2}(\pi,\tilde{\pi})$, where
$\tilde{\pi}\in\widetilde{\mathcal{P}}(\pi)$, hence the law of $\tilde{\pi}$
depends on $t^{\prime}$ but also on $\pi$. Also, it will be clear from our
main result (see Theorem 5) that $(\mathcal{R}^{s}(t),\;t\geq 0)$ is an
exchangeable coalescent, however $(\mathcal{R}^{g}(t),\;t\geq 0)$ is not a
Markov process in general, because the distribution of
$\mathcal{R}^{g}(t+t^{\prime})$ may depend on $\mathcal{R}^{s}(t)$.

We now turn to investigate the transitions of the restrictions of a SNEC to
finite partitions, which relies on the following lemma.

######  Lemma 3 (Projective Markov property).

Let $\mathcal{R}=(\mathcal{R}(t),\;t\geq 0)$ be a process with values in
$\mathcal{N}_{\infty}$ and for every integer $n$, write
$\mathcal{R}_{|{n}}=(\mathcal{R}_{|{n}}(t),\;t\geq 0)$ for its restriction to
$\mathcal{N}_{n}$. Then $\mathcal{R}$ is a SNEC in $\mathcal{N}_{\infty}$ if
and only if for all $n\in\mathbb{N}$, $\mathcal{R}_{|{n}}$ is a continuous-
time Markov chain on the space $\mathcal{N}_{n}$ satisfying the analog of
statements i) – iii) of Definition 2, namely:

  1. i)

For all $t\geq 0$, $\mathcal{R}_{|{n}}$ is nested;

  2. ii)

For $\varrho,\pi\in\mathcal{N}_{n}$, the rate from $\varrho$ to $\pi$ is zero
if $\pi$ can not be obtained from a simple coalescence event;

  3. iii)

The Markov chain $(\mathcal{R}_{|n}(t),\;t\geq 0)$ is exchangeable, in the
sense that for any $t,t^{\prime}\geq 0$, $\varrho,\pi\in\mathcal{N}_{n}$ and
$\sigma$ _permutation_ of $n$, the rate from $\varrho$ to $\pi$ is equal to
that from $\sigma(\varrho)$ to $\sigma(\pi)$.

###### Proof.

Let $\mathcal{R}$ be a SNEC in $\mathcal{N}_{\infty}$ and let
$n\in\mathbb{N}$. Let us prove that $\mathcal{R}_{|{n}}$ satisfies the claimed
properties. Let $\varrho\in\mathcal{N}_{n}$. Pick
$\varrho^{\star}\in\mathcal{N}_{\infty}$ such that
$\varrho^{\star}_{|n}=\varrho$, and which contains an infinite number of
species blocks, each of which containing an infinite number of gene blocks,
each of them being an infinite subset of $\mathbb{N}$. Now for any
$\varrho^{\prime}\in\mathcal{N}_{\infty}$ such that
$\varrho^{\prime}_{|n}=\varrho$, there is an injection
$\sigma:\mathbb{N}\to\mathbb{N}$ such that
$\sigma(\varrho^{\star})=\varrho^{\prime}$ and such that
$\sigma_{|[n]}=\text{id}_{[n]}$, so for any $t,t^{\prime}\geq 0$,

$\displaystyle(\mathcal{R}_{|n}(t+t^{\prime})\,\mid\,\mathcal{R}(t)=\varrho^{\prime})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}(\mathcal{R}_{|n}(t+t^{\prime})\,\mid\,\mathcal{R}(t)=\sigma(\varrho^{\star}))$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}(\sigma(\mathcal{R})_{|n}(t+t^{\prime})\,\mid\,\mathcal{R}(t)=\varrho^{\star})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}(\mathcal{R}_{|n}(t+t^{\prime})\,\mid\,\mathcal{R}(t)=\varrho^{\star}).$

Since this is valid for any $\varrho^{\prime}$ such that
$\varrho^{\prime}_{|n}=\varrho$, this conditional distribution depends only on
$\\{\mathcal{R}_{|n}(t)=\varrho\\}$, which proves that $\mathcal{R}_{|n}$ is a
Markov process. Now the assumption that $\mathcal{R}$ has càdlàg paths ensures
us that the process $\mathcal{R}_{|n}$ stays some positive time in each
visited state a.s. Therefore $\mathcal{R}_{|n}$ is a continuous-time Markov
chain. Now statements i) – iii) are easily deduced from Definition 2.

Conversely, let $\mathcal{R}=(\mathcal{R}(t),\,t\geq 0)$ be a process with
values in $\mathcal{N}_{\infty}$ such that for all $n\in\mathbb{N}$,
$\mathcal{R}_{|n}$ is a Markov chain satisfying i) – iii) of the lemma. Then
i) and ii) of Definition 2 follow immediately, and it remains to check that
for any injection $\sigma:\mathbb{N}\to\mathbb{N}$, the equality in
distribution (3.10) holds.

Let $\sigma:\mathbb{N}\to\mathbb{N}$ be an injection and fix $n\in\mathbb{N}$.
Define $N=\max\\{\sigma(1),\sigma(2),\ldots,\sigma(n)\\}$, and consider
$\widetilde{\sigma}:[N]\to[N]$ a permutation such that for all $1\leq i\leq
n$, $\widetilde{\sigma}(i)=\sigma(i)$. For instance, one can define
inductively for $n+1\leq i\leq N$,

$\widetilde{\sigma}(i):=\min([N]\setminus\\{\sigma(1),\sigma(2),\ldots,\sigma(i-1)\\}).$

Now notice that for any $t\geq 0$ and any $\pi\in\mathcal{N}_{\infty}$,

$\sigma(\pi)_{|n}=\widetilde{\sigma}(\pi_{|N})_{|n},$

which enables us to write, for any $t,t^{\prime}\geq 0$,

$\displaystyle(\sigma(\mathcal{R})_{|n}(t+t^{\prime})\mid\mathcal{R}(t)=\pi)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}(\widetilde{\sigma}(\mathcal{R}_{|N}(t+t^{\prime}))_{|n}\mid\mathcal{R}(t)=\pi)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}(\mathcal{R}_{|N}(t+t^{\prime})_{|n}\mid\mathcal{R}_{|N}(t)=\widetilde{\sigma}(\pi_{|N}))$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}(\mathcal{R}_{|n}(t+t^{\prime})\mid\mathcal{R}_{|n}(t)=\widetilde{\sigma}(\pi_{|N})_{|n})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}(\mathcal{R}_{|n}(t+t^{\prime})\mid\mathcal{R}_{|n}(t)=\sigma(\pi)_{|n})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}(\mathcal{R}_{|n}(t+t^{\prime})\mid\mathcal{R}(t)=\sigma(\pi)).$

The passage to the second line in the last display is a consequence of iii) of
the lemma, and we used the fact that restrictions are Markov chains, i.e.
${(\mathcal{R}_{|n}(t+t^{\prime})\mid\mathcal{R}_{|n}(t)=\pi_{|n})}\stackrel{{\scriptstyle(d)}}{{=}}{(\mathcal{R}_{|n}(t+t^{\prime})\mid\mathcal{R}(t)=\pi)}$.
Since $n$ is arbitrary in

$(\sigma(\mathcal{R})_{|n}(t+t^{\prime})\mid\mathcal{R}(t)=\pi)\stackrel{{\scriptstyle(d)}}{{=}}{(\mathcal{R}_{|n}(t+t^{\prime})\mid\mathcal{R}(t)=\sigma(\pi))},$

we have shown (3.10), concluding the proof. ∎

This key lemma enables us to give the following first properties of SNEC
processes.

######  Proposition 4.

Let $\mathcal{R}$ be a SNEC.

  * •

If the process $\mathcal{R}$ starts from an exchangeable nested partition
$\mathcal{R}(0)$, then for any $t\geq 0$, $\mathcal{R}^{g}(t)$ and
$\mathcal{R}^{s}(t)$ are exchangeable partitions.

  * •

The process $\mathcal{R}$ is a Feller process, so in particular it satisfies
the strong Markov property.

  * •

Conditional on $\mathcal{R}(t)$, if $\bar{\mathcal{R}}(t)$ denotes the link
partition of $\mathcal{R}(t)$ then for any $t,t^{\prime}\geq 0$, the
distribution of $\mathcal{R}^{g}(t+t^{\prime})$ is the law of
$\text{Coag}(\mathcal{R}^{g}(t),\tilde{\pi}^{g})$, where $\tilde{\pi}^{g}$ is
a random partition such that
$\sigma(\tilde{\pi}^{g})\overset{d}{=}\tilde{\pi}^{g}$ for any permutation
$\sigma$ preserving $\bar{\mathcal{R}}(t)$ i.e., such that

$i\overset{\bar{\mathcal{R}}(t)}{\thicksim}j\Rightarrow\sigma(i)\overset{\bar{\mathcal{R}}(t)}{\thicksim}\sigma(j).$
(3.11)

Another property is that the process $(\mathcal{R}^{s}(t),\;t\geq 0)$ is a
simple exchangeable coalescent process, but we do not prove it at this point
as it will be clear from Theorem 5.

###### Proof.

The first point of the proposition is immediate considering iii) of Definition
2.

As for the second point, recall that $\mathcal{N}_{\infty}$ is endowed with
the topology generated by the sets of the form
$\\{\pi\in\mathcal{N}_{\infty},\,\pi_{|n}=\widehat{\pi}\\}$, for
$n\in\mathbb{N},\,\widehat{\pi}\in\mathcal{N}_{n}$. It is easy to see that
this topology is metrized by
$d(\pi,\pi^{\prime}):=(\sup\\{n\in\mathbb{N},\,\pi_{|n}=\pi^{\prime}_{|n}\\})^{-1}$
(with $(\sup\mathbb{N})^{-1}=0$) and that $(\mathcal{N}_{\infty},d)$ is
compact.

We need to show that for any continuous (then bounded) function
$f:\mathcal{N}_{\infty}\to\mathbb{R}$, the function
$P_{t}f:\pi\mapsto\mathbb{E}_{\pi}f(\mathcal{R}(t))$ (where
$\mathbb{E}_{\pi}(\cdot)=\mathbb{E}(\cdot\,|\,\mathcal{R}(0)=\pi)$) is
continuous, and that $P_{t}f(\pi)\to f(\pi)$ as $t\to 0$. By definition the
process is càdlàg so we have almost surely $f(\mathcal{R}(t))\to
f(\mathcal{R}(0))$ so clearly by taking expectations $P_{t}f(\pi)\to f(\pi)$
as $t\to 0$. Now to show that $P_{t}f$ is continuous, consider
$n\in\mathbb{N}$ and let $\\{\widehat{\pi}^{1},\ldots,\widehat{\pi}^{k}\\}$ be
an enumeration of $\mathcal{N}_{n}$. We pick
$\pi^{1},\ldots,{\pi}^{k}\in\mathcal{N}_{\infty}$ such that
$\pi^{i}_{|n}=\widehat{\pi}^{i}$, and define
$\widehat{f}_{n}:\mathcal{N}_{\infty}\to\mathbb{R}$ by

$\widehat{f}_{n}(\pi)=f(\pi^{i})\quad\text{ if }\pi_{|n}=\widehat{\pi}^{i}.$

Now since $f$ is continuous on $(\mathcal{N}_{\infty},d)$ which is compact,
$f$ is uniformly continuous, which means that

$\omega_{n}:=\sup_{\pi\in\mathcal{N}_{\infty}}\lvert
f(\pi)-\widehat{f}_{n}(\pi)\rvert\to 0\quad\text{as }n\to\infty.$

For $t>0$ and $\pi,\pi^{\prime}\in\mathcal{N}_{\infty}$, we have

$\lvert
P_{t}f(\pi)-P_{t}f(\pi^{\prime})\rvert\leq\left\lvert\mathbb{E}_{\pi}\widehat{f}_{n}(\mathcal{R}(t))-\mathbb{E}_{\pi^{\prime}}\widehat{f}_{n}(\mathcal{R}(t))\right\rvert+2\omega_{n}.$
(3.12)

Now suppose $\pi_{|n}=\pi^{\prime}_{|n}$. Since $\widehat{f}_{n}$ depends only
on $\pi_{|n}$ and by Lemma 3 the process $\mathcal{R}_{|n}$ has the same
distribution under $\mathbb{P}_{\pi}$ or $\mathbb{P}_{\pi^{\prime}}$, we have
the equality
$\mathbb{E}_{\pi}\widehat{f}_{n}(\mathcal{R}(t))=\mathbb{E}_{\pi^{\prime}}\widehat{f}_{n}(\mathcal{R}(t))$,
and plugging that into (3.12), we get

$\sup\\{\lvert
P_{t}f(\pi)-P_{t}f(\pi^{\prime})\rvert,\;\pi,\pi^{\prime}\in\mathcal{N}_{\infty},\,\pi_{|n}=\pi^{\prime}_{|n}\\}\leq
2\omega_{n}\to 0\quad\text{as }n\to\infty,$

showing that $P_{t}f$ is continuous.

For the third point of the proposition, $\mathcal{R}^{g}(t+t^{\prime})$ is
clearly of the form $\text{Coag}(\mathcal{R}^{g}(t),\tilde{\pi}^{g})$, where
$\tilde{\pi}=(\tilde{\pi}^{s},\tilde{\pi}^{g})$ is a random recipe partition
whose distribution depends on $\mathcal{R}(t)$ and $t^{\prime}$. Let us show
that the conditional distribution of $\tilde{\pi}$ given $\mathcal{R}(t)$ is
invariant under the action of permutations preserving $\bar{\mathcal{R}}(t)$.

Without loss of generality, we can work under the conditioning
$\\{\mathcal{R}(t)=(\varrho,\mathbf{0}_{\infty})\\}$, where $\varrho$ is any
partition and $\mathbf{0}_{\infty}$ is the partition into singletons, so that
for all $\pi$, we have $\text{Coag}(\mathcal{R}^{g}(t),\pi)=\pi$. In
particular, note that in this case we have
$\mathcal{R}^{g}(t+t^{\prime})=\tilde{\pi}^{g}$, and
$\bar{\mathcal{R}}(t)=\varrho$. Let $\sigma$ be a permutation such that
$\sigma(\varrho)=\varrho$. The problem then reduces to showing that

$\left(\sigma(\mathcal{R}^{g}(t+t^{\prime}))\mid\mathcal{R}(t)=(\varrho,\mathbf{0}_{\infty})\right)\stackrel{{\scriptstyle(d)}}{{=}}\left(\mathcal{R}^{g}(t+t^{\prime})\mid\mathcal{R}(t)=(\varrho,\mathbf{0}_{\infty})\right),$

which is now an immediate consequence of iii) in Definition 2. ∎

Let us now investigate the transition rates of the Markov chains
$\mathcal{R}_{|{n}}$ appearing in Lemma 3, for every $n\in\mathbb{N}$. In this
direction fix $n\in\mathbb{N}$, let $\varrho\in\mathcal{N}_{\infty}$ and
$\pi\in\mathcal{N}_{n}$ and denote the jump rate of $\mathcal{R}_{|n}$ from
$\varrho_{|n}$ to $\pi$ by

$q_{n}({\varrho,{\pi}}):=\lim_{t\rightarrow
0+}\frac{1}{t}\mathbb{P}_{\varrho}(\mathcal{R}_{|n}(t)={\pi})$ (3.13)

where
$\mathbb{P}_{\varrho}(\cdot)=\mathbb{P}(\cdot\,|\,\mathcal{R}(0)=\varrho)$.
The index $n$ is not necessary in the notation as it can be read in the
partition $\pi$. However we keep it as it will ease reading. Remind that
$q_{n}({\varrho,{\pi}})$ only depends on $\varrho$ through $\varrho_{|n}$. As
is remarked in Lemma 3, $q_{n}({\varrho,\pi})$ equals zero if $\pi$ is not
obtained from $\varrho_{|n}$ by coagulating blocks according to a partition in
$\widetilde{\mathcal{P}}(\varrho_{|n})$, that is by merging some species
blocks of $\varrho^{s}_{|n}$ into one and some gene blocks of the new species
into one. Also observe that the rates do not depend on the sizes of the gene
blocks in the starting configuration so there is no loss of generality if we
consider that $\varrho^{g}=\mathbf{0}_{\infty}$, the trivial partition made of
singletons. Of course changing the starting partition $\varrho$ has some
effect on the arrival partition $\pi$. This is why we will need to write
transition rates in another way, giving more emphasis on the dependence of the
coagulation mechanism upon the starting partition.

Fix $n\in\bar{\mathbb{N}}$ and suppose that $\mathcal{R}_{|n}$ starts from $n$
singleton gene blocks allocated into $b$ species. Since labels of genes do not
affect the transition rates, we will keep the data of the number of genes in
each species in a vector $\mathbf{g}=(g_{1},\dots,g_{b})$. This vector
suffices to describe the starting position. Indeed $|\mathbf{g}|=b$ gives the
number of species and $\sum_{i=1}^{b}g_{i}=n$ gives the number of genes.

Now the coagulation mechanism will be described by two terms. We will say that
a gene block _participates in the coalescence event_ if it merges with other
gene blocks. We will say that a species block _participates in the coalescence
event_ if it merges with other species blocks or if it contains gene blocks
that participate in the coalescence event.

The behaviour of the species blocks will be encoded in a vector
$\mathbf{s}=(s_{1},\dots,s_{b})$ with coordinates taking values in
$\\{0,1\\}$. Namely, $s_{i}=1$ if the $i$-th species participates in the
coalescence event and $s_{i}=0$ otherwise. The total number of species
involved in the event is $k=\sum_{i=1}^{b}s_{i}$.

The behaviour of the gene blocks will be encoded by an array
$\mathbf{c}=(\mathbf{c}_{1},\dots,\mathbf{c}_{b})$ where $\mathbf{c}_{i}$ is a
vector describing which gene blocks in the $i$-th species participate in the
coalescence event. If $s_{i}=1$ ($i$-th species block participating in the
coalescence event), then $\mathbf{c}_{i}=(c_{i1},\dots,c_{ig_{i}})$ is such
that $c_{ij}=1$ if $j$-th gene block inside $i$-th species block participates
in the coalescence event and $c_{ij}=0$ otherwise. If $s_{i}=0$, the $i$-th
species block is not participating in the event and so neither will the gene
blocks within it. In this case we set
$\mathbf{c}_{i}=(0,0,\ldots,0)=\mathbf{0}$ and nothing happens at the gene
level. Note that the number of gene blocks participating in the coalescence
event is $\sum_{i,j}c_{ij}$.

Note that all such arrays $(\mathbf{g},\mathbf{s},\mathbf{c})$ do not
necessarily code for observable coalescence events, so we will define a
restricted set of arrays of interest for our study. First, note that one needs
to have $\sum_{i}s_{i}\geq 2$ in order to observe a species merger. If
$\sum_{i}s_{i}=1$, then there is a gene coalescence if and only if
$\sum_{i,j}c_{ij}\geq 2$. Also, we will restrict ourselves to the arrays
$(\mathbf{g},\mathbf{s},\mathbf{c})$ such that $\sum_{i,j}c_{ij}\neq 1$,
because a sole gene coalescing is not distinguishable from no gene coalescing.

Formally, we consider finite arrays $(\mathbf{g},\mathbf{s},\mathbf{c})$
satisfying the assumptions

$\displaystyle\begin{aligned} &\text{If }|\mathbf{g}|=b,\text{ then
}\mathbf{s}\in\\{0,1\\}^{b}\text{ and
}\mathbf{c}=(\mathbf{c}_{1},\ldots,\mathbf{c}_{b}),\;\mathbf{c}_{i}\in\\{0,1\\}^{g_{i}},\\\
&\text{ with }s_{i}=0\implies\forall j,c_{ij}=0\end{aligned}$ (H1)
$\displaystyle{\sum_{i,j}c_{ij}<2\implies\sum_{i}s_{i}\geq 2,}$ (H2) and
$\displaystyle\sum_{i,j}c_{ij}\neq 1.$ (H3)

We denote by $\mathcal{C}$ the set of arrays
$(\mathbf{g},\mathbf{s},\mathbf{c})$ satisfying (H1), (H2) and (H3).

We then denote the transition rate of $\mathcal{R}_{|n}$ from a partition
described by $\mathbf{g}$ (such that $\sum g_{i}=n$) to a new partition
obtained by merging species and genes according to $\mathbf{s}$ and
$\mathbf{c}$ by

$q_{b,k}(\mathbf{g},\mathbf{s},\mathbf{c}).$

Here again indices $b$ and $k$ are not necessary but permit to read easily the
coalescence event at the species level ($k=\sum s_{i}$ species merging among
$b=|\mathbf{g}|$). We insist on the fact that we consider only arrays
$(\mathbf{g},\mathbf{s},\mathbf{c})\in\mathcal{C}$ when we study the rates
$q_{b,k}(\mathbf{g},\mathbf{s},\mathbf{c})$, and that these quantities
determine uniquely the law of a SNEC $\mathcal{R}$, since they describe
completely the rates associated to each finite-space continuous-time Markov
chain $\mathcal{R}_{|n}$.

We introduce a notation that we will use in the next result for ease of
writing. For $\mu$ a probability on $[0,1]$, consider any probability space
where $Z_{1},Z_{2},\ldots$ are i.i.d. with distribution $\mu$ and denote the
expectation $\mathbb{E}_{\mu}$. Now take a vector $(g_{i},\,i\in S)$ of
integers, where $S$ is a finite subset of $\mathbb{N}$. We define

$\displaystyle\mathcal{U}(\mu,(g_{i},i\in S))$
$\displaystyle=\mathbb{E}_{\mu}\Big{[}\sum_{i\in
S}g_{i}Z_{i}(1-Z_{i})^{g_{i}-1}\\!\\!\\!\prod_{j\in S\,:\,j\neq
i}(1-Z_{j})^{g_{j}}\Big{]}$ (3.14) $\displaystyle=\sum_{i\in
S}g_{i}\int_{[0,1]}\mu(dq)q(1-q)^{g_{i}-1}\\!\\!\\!\prod_{j\in S\,:\,j\neq
i}\int_{[0,1]}\mu(dq)(1-q)^{g_{j}}.$

This can be thought of as the probability that a random array $(c_{ij},\,i\in
S,1\leq j\leq g_{i})$ does not satisfy (H3), where conditional on
$(Z_{i},\,i\in S)$ the variables $(c_{ij})$ are independent, and for all
$i,j$, $c_{ij}=1$ with probability $Z_{i}$. We can now state our main result.

######  Theorem 5.

There exist two non-negative real numbers $a_{s},a_{g}\geq 0$ and two
measures:

  * •

$\nu_{s}$ on $E=(0,1]\times\mathcal{M}_{1}([0,1])$;

  * •

$\nu_{g}$ on $(0,1]$;

such that

$\displaystyle\int_{E}\nu_{s}(dp,d\mu)p^{2}<\infty,$ (3.15a)
$\displaystyle\int_{E}\nu_{s}(dp,d\mu)p\int_{[0,1]}\mu(dq)q^{2}<\infty,$
(3.15b) $\text{ and }\int_{(0,1]}\nu_{g}(dq)q^{2}<\infty,$ (3.16)

and such that for any array $(\mathbf{g},\mathbf{s},\mathbf{c})\in\mathcal{C}$
such that $|\mathbf{g}|=b$, $\sum_{i}s_{i}=k$ and $\sum_{j}c_{ij}=l_{i}$,

$\displaystyle q_{b,k}(\mathbf{g},\mathbf{s},\mathbf{c})=$
$\displaystyle\int_{E}\nu_{s}(dp,d\mu)p^{k}(1-p)^{b-k}\Biggl{(}\prod_{i\,:\,{s_{i}}=1}\int_{[0,1]}\mu(dq)q^{l_{i}}(1-q)^{g_{i}-l_{i}}$
(3.17)
$\displaystyle\qquad\qquad\qquad\qquad+\mathbb{1}{\\{\mathbf{c}=\mathbf{0}\\}}\,\mathcal{U}(\mu,(g_{i},\,1\leq
i\leq b\text{ with }s_{i}=1))\Biggr{)}$
$\displaystyle+a_{s}\mathbb{1}{\left\\{k=2,\mathbf{c}=\mathbf{0}\right\\}}$
$\displaystyle+\mathbb{1}{\\{k=1\\}}\left(a_{g}\mathbb{1}{\\{l_{I}=2\\}}+\int_{(0,1]}\nu_{g}(dq)q^{l_{I}}(1-q)^{g_{I}-l_{I}}\right),$

where the functional $\mathcal{U}$ is defined in (3.14) and
$I=I(\mathbf{g},\mathbf{s},\mathbf{c})$, in the case $k=1$, is the unique
index in $\\{1,2,\ldots,b\\}$ such that $s_{I}=1$.

Furthermore, this correspondence between laws of SNEC processes and
quadruplets $(a_{s},a_{g},\nu_{s},\nu_{g})$ satisfying (3.15) and (3.16) is
bijective.

######  Remark 6.

We will show the _surjective_ part of the theorem’s last statement in Section
5, using an explicit Poissonian construction. For now we prove the existence
and uniqueness of the characteristics $(a_{s},a_{g},\nu_{s},\nu_{g})$.

##  4 Proof of Theorem 5

Consider a SNEC process
$\mathcal{R}=((\mathcal{R}^{s}(t),\mathcal{R}^{g}(t)),\;t\geq 0)$ with values
in $\mathcal{N}_{\infty}$ and recall its jump rates $q_{n}(\varrho,\pi)$
defined in (3.13). Also recall the alternative notation
$q_{b,k}(\mathbf{g},\mathbf{s},\mathbf{c})$. Here, $\mathbf{g}$ is a vector of
size $b$ such that $\sum g_{i}=n$, $\mathbf{s}$ is a vector having the same
size as $\mathbf{g}$ with coordinates in $\\{0,1\\}$ such that $\sum s_{i}=k$,
and $\mathbf{c}$ is a family of $|\mathbf{g}|$ elements denoted by
$\mathbf{c}_{1},\mathbf{c}_{2}\dots$ where $\mathbf{c}_{i}$ is a vector of
$\\{0,1\\}^{g_{i}}$ if $s_{i}=1$ and $\mathbf{c}_{i}=\mathbf{0}$ if $s_{i}=0$.

######  Lemma 7.

For any initial value
$\varrho=(\varrho_{s},\varrho_{g})\in\mathcal{N}_{\infty}$, there exists a
unique measure $\mu_{\varrho}$ on $\mathcal{N}_{\infty}$ such that

$\mu_{\varrho}(\\{\varrho\\})=0\quad\text{and}\quad\forall n\geq
1,\;\mu_{\varrho}(\Pi_{|n}\neq\varrho_{|n})<\infty$ (4.18)

and such that the transition rate of the Markov chain $\mathcal{R}_{|n}$ from
$\varrho_{|n}$ to $\pi\in\mathcal{N}_{n}$ is given by

$q_{n}(\varrho,\pi)=\mu_{\varrho}(\Pi_{|n}=\pi).$ (4.19)

Furthermore, for any permutation $\sigma:\mathbb{N}\to\mathbb{N}$,

$\mu_{\varrho}(\sigma(\Pi)\in\cdot)=\mu_{\sigma(\varrho)}(\Pi\in\cdot).$
(4.20)

Note that we write $\mu_{\varrho}(\Pi\in A)$ instead of $\mu_{\varrho}(A)$
because we implicitly work on the canonical space $\mathcal{N}_{\infty}$ and
we denote by $\Pi$ the generic element of $\mathcal{N}_{\infty}$.

###### Proof.

Let $n<m$. We first note that since $\mathcal{R}_{|m}$ and
$\mathcal{R}_{|n}=(\mathcal{R}_{|m})_{|n}$ are Markov chains, the transition
rates can be expressed, for any
$\pi\in\mathcal{N}_{n}\setminus\\{\varrho_{|n}\\}$,

$q_{n}(\varrho,\pi)=\sum_{\pi^{\prime}\in\mathcal{N}_{m}\,:\;\pi^{\prime}_{|n}=\pi}q_{m}(\varrho,\pi^{\prime}).$
(4.21)

Let us now check that this consistency property along with Carathéodory’s
extension theorem ensures us that there exists a measure $\mu_{\varrho}$ on
$\mathcal{N}_{\infty}\setminus\\{\varrho\\}$ satisfying (4.19).

Here the family
$\mathcal{A}:=\big{\\{}\\{\Pi_{|n}=\pi\\},\;n\in\mathbb{N},\pi\in\mathcal{N}_{n}\setminus\\{\varrho_{|n}\\}\big{\\}}\cup\\{\emptyset\\}$
clearly forms a semi-ring of subsets of $\mathcal{N}_{\infty}$, and it remains
to check that the functional $\widetilde{\mu}:\mathcal{A}\to[0,+\infty]$,
defined by

$\widetilde{\mu}(\emptyset):=0\quad\text{and}\quad\widetilde{\mu}(\\{\Pi_{|n}=\pi\\}):=q_{n}(\varrho,\pi),$

is a pre-measure. Equation (4.21) shows that $\widetilde{\mu}$ is finitely
additive, and the only difficulty lies in understanding that $\widetilde{\mu}$
is countably additive. Now observe that the topology of
$\mathcal{N}_{\infty}\setminus\\{\varrho\\}$ is generated by $\mathcal{A}$,
and that each of the non-empty sets in $\mathcal{A}$ is both open and closed
(thus compact), because

$\mathcal{N}_{\infty}\setminus\\{\Pi_{|n}=\pi\\}=\bigcup_{\varrho\in\mathcal{N}_{n}\setminus\\{\pi\\}}\\{\Pi_{|n}=\varrho\\}.$

This implies that if $(A_{n})_{n\geq 1}$ is a family of pairwise disjoint
elements of $\mathcal{A}$ such that $\bigcup_{n}A_{n}\in\mathcal{A}$, then at
most a finite number of the $A_{n}$ are non-empty (because since
$\bigcup_{n}A_{n}$ is compact, there is a finite subcover), so countable
additivity reduces to finite additivity. Therefore Carathéodory’s extension
theorem applies, hence the existence of a measure $\mu_{\varrho}$ on
$\mathcal{N}_{\infty}\setminus\\{\varrho\\}$ satisfying (4.19).

Considering $\mu_{\varrho}$ as a measure on $\mathcal{N}_{\infty}$ such that
$\mu_{\varrho}(\\{\varrho\\})=0$, we check easily (4.18) by noticing that

$\mu_{\varrho}(\Pi_{|n}\neq\varrho_{|n})=\sum_{\pi\in\mathcal{N}_{n}\setminus\\{\varrho_{|n}\\}}q_{n}(\varrho,\pi)<\infty.$

Furthermore, for any $n$, $\pi\in\mathcal{N}_{n}\setminus\\{\varrho_{|n}\\}$
and $\sigma:\mathbb{N}\to\mathbb{N}$ permutation, we have by the
exchangeability property (3.10) of a SNEC, that

$\mu_{\varrho}(\sigma(\Pi)_{|n}=\pi)=\lim_{t\to
0}\frac{1}{t}\mathbb{P}_{\varrho}(\sigma(\mathcal{R}(t))_{|n}=\pi)=\lim_{t\to
0}\frac{1}{t}\mathbb{P}_{\sigma(\varrho)}(\mathcal{R}_{|n}(t)=\pi)=\mu_{\sigma(\varrho)}(\Pi_{|n}=\pi),$

which proves that (4.20) holds on $\mathcal{A}$. Since the topology of
$\mathcal{N}_{\infty}$ is generated by $\mathcal{A}$, the proof is complete. ∎

The latter lemma implies that there exists a family of exchangeable measures
on $\mathcal{N}_{\infty}$ characterizing (i.e. acting as an analog of a Markov
kernel for continuous-space pure-jump Markov chains) the SNEC process
$\mathcal{R}$. Furthermore, since we are dealing with a simple coalescent, it
is clear from the characterization (4.19) that $\mu_{\varrho}$ is simple in
the sense that it is supported by all the possible bivariate partitions
obtained from a simple coalescence from $\varrho$. To put it simply,

$\mu_{\varrho}\left(\mathcal{N}_{\infty}\setminus\\{\text{Coag}_{2}(\varrho,\tilde{\pi}),\;\tilde{\pi}\in\widetilde{\mathcal{P}}(\varrho)\\}\right)=0.$

The measure $\mu_{\varrho}$ can be translated as a measure on arrays of random
variables in $\\{0,1\\}$. Informally, we can associate to each species in
$\varrho$ a 1 entry if it participates in the coalescence and a 0 entry
otherwise. Inside the species participating to the coalescence event, we can
also associate a 1 entry to the genes participating in the coalescence event
and a 0 entry otherwise. To tally with the definition of the SNEC we will need
a certain partial exchangeability structure for this array. This picture can
be formalized as follows. Let
$((X_{i},(Y_{ij},\;j\in\mathbb{N})),\;i\in\mathbb{N})$ be an array of
Bernoulli random variables and denote by $Z_{i}$ the $i$-th line vector
$(X_{i},(Y_{ij},\;j\in\mathbb{N}))$. We say that this array is _hierarchically
exchangeable_ if

  1. (A1)

the family $(Z_{i},\;i\in\mathbb{N})$ is exchangeable;

  2. (A2)

for any $i\in\mathbb{N}$, the family $(X_{i},(Y_{ij},\;j\in\mathbb{N}))$ is
invariant under any permutation over the $j$’s.

We also naturally extend this definition to measures on the space
$(\\{0,1\\}\times\\{0,1\\}^{\mathbb{N}})^{\mathbb{N}}$. We say that such a
measure $\mu$ is hierarchically exchangeable if it is invariant both under the
permutations of the rows, and the permutations within a row.

For an initial state
$\varrho=(\varrho^{s},\varrho^{g})\in\mathcal{N}_{\infty}$ and an arrival
state $\pi=\text{Coag}_{2}(\varrho,\tilde{\pi})\in\mathcal{N}_{\infty}$, with
$\tilde{\pi}$ a simple bivariate partition
$\tilde{\pi}=(\tilde{\pi}^{s},\tilde{\pi}^{g})\in(\mathcal{P}^{\prime}_{\infty})^{2}$,
define the array
$\mathbf{Z}(\varrho,\pi)=(\mathbf{X},\mathbf{Y}_{1},\mathbf{Y}_{2},\ldots)$ by

$\displaystyle X_{i}=1\text{ if the $i$-th block in $\varrho^{s}$ has
coalesced in $\pi$},$ (4.22) $\displaystyle Y_{ij}=1\text{ if the $I(i,j)$-th
block in $\varrho^{g}$ has coalesced in $\pi$},$

where $I(i,j):=k$ if the $k$-th block of $\varrho^{g}$ is the $j$-th gene
block of the $i$-th species block.

Now choose a state $\varrho$ with an infinite number of species blocks, each
containing an infinite number of gene blocks. Let $\nu$ be the push-forward of
$\mu_{\varrho}$ by the application

$\pi\longmapsto\mathbf{Z}(\varrho,\pi).$

Then the exchangeability property of $\mu_{\varrho}$ (4.20) implies that $\nu$
is a hierarchically exchangeable measure on
$(\\{0,1\\}\times\\{0,1\\}^{\mathbb{N}})^{\mathbb{N}}$, and (4.18) implies
that

$\nu(\mathbf{Z}=\mathbf{0})=0,\quad\text{ and
}\quad\nu\left(\sum_{i=1}^{n}X_{i}\geq 2\text{ or }\exists i\leq
n,\,\sum_{j=1}^{n}Y_{ij}\geq 2\right)<\infty,$ (4.23)

where $\mathbf{0}$ denotes the null array on
$(\\{0,1\\}\times\\{0,1\\}^{\mathbb{N}})^{\mathbb{N}}$. Also, note that the
application $(\mu_{\varrho},\,\varrho\in\mathcal{N}_{\infty})\mapsto\nu$ is
one-to-one. Indeed, we can conversely define for any $\mathbf{Z}$ and any
nested partition $\varrho\in\mathcal{N}_{\infty}$, the nested partition
$C(\varrho,\mathbf{Z})\in\mathcal{N}_{\infty}$ obtained from $\varrho$ by
merging exactly the blocks that _participate in the coalescence_ where

  * •

The $i$-th block of $\varrho^{s}$ participates iff $X_{i}=1$;

  * •

The $j$-th block in $\varrho^{g}$ of the $i$-th block of $\varrho^{s}$
participates iff $X_{i}=1$ and $Y_{ij}=1$.

With this definition, $\mu_{\varrho}$ is obtained as the push-forward of $\nu$
by the map $\mathbf{Z}\mapsto C(\varrho,\mathbf{Z})$.

Now recall the alternative notation
$q_{b,k}(\mathbf{g},\mathbf{s},\mathbf{c})$ for the transition rate of
$\mathcal{R}_{|n}$ (where $n=\sum_{i}g_{i}$) from a nested partition with $b$
species blocks and $g_{1},\dots,g_{b}$ gene blocks inside them, to a nested
partition obtained by merging $k$ species blocks according to the vector
$\mathbf{s}$ and gene blocks inside those species according to the array
$\mathbf{c}$. For any array
$(\mathbf{g},\mathbf{s},\mathbf{c})\in\mathcal{C}$, note that (4.19)
translates in terms of our push-forward $\nu$ in the following way:

$\displaystyle q_{b,k}(\mathbf{g},\mathbf{s},\mathbf{c})$
$\displaystyle=\nu\bigl{(}\forall 1\leq i\leq b,\,X_{i}=s_{i},\text{ and
}\forall 1\leq j\leq g_{i},Y_{ij}=c_{ij}\bigr{)}$ (4.24)
$\displaystyle+\mathbb{1}_{\\{\mathbf{c}=\mathbf{0}\\}}\nu\left(\forall 1\leq
i\leq b,\,X_{i}=s_{i},\text{ and
}\sum_{i=1}^{b}\sum_{j=1}^{g_{i}}Y_{ij}=1\right).$

Indeed, the first line is quite straightforward and comes from our
representation of coalescence events by those arrays
$(\mathbf{g},\mathbf{s},\mathbf{c})\in\mathcal{C}$ (see Section 3) which
basically means that blocks participating in a coalescence event are those
associated with a $1$. However in the case when $\mathbf{c}=\mathbf{0}$, there
is an additional probability to observe the coalescence of species blocks
associated to $\mathbf{s}$ with no coalescence of gene blocks (the case when
all the $Y_{ij}$’s are 0 is included in the first term), which is when exactly
one of the $Y_{ij}$’s is equal to $1$. This gives rise to the second line of
(4.24).

We now have to establish a de Finetti representation of hierarchically
exchangeable arrays to express the measure of an event of the form $\\{\forall
1\leq i\leq b,\,X_{i}=s_{i},\text{ and }\forall 1\leq j\leq
g_{i},Y_{ij}=c_{ij}\\}$. Note that we consider random measures in the
following, but only on Borel spaces $(S,\mathcal{S})$ (i.e. spaces isomorphic
to a Borel subset of $\mathbb{R}$ endowed with the Borel $\sigma$-algebra),
which will enable us to use de Finetti’s theorem [23]. For this we write
$\mathcal{M}_{1}(S)$ for the space of probability measures on $S$, which is
endowed with the $\sigma$-algebra generated by the maps $\mu\mapsto\mu(B)$ for
all $B\in\mathcal{S}$. The spaces $(S,\mathcal{S})$ that we consider will be
for instance $[0,1]$ with its Borel sets or $\\{0,1\\}^{\mathbb{N}}$ equipped
with the product $\sigma$-algebra, which are clearly Borel spaces.

######  Proposition 8.

Let
$\mathbf{Z}=(Z_{i},\;i\in\mathbb{N})=((X_{i},(Y_{ij},\;j\in\mathbb{N})),\;i\in\mathbb{N})$
be a hierarchically exchangeable array (with variables in $\\{0,1\\}$). Then
there exists a unique probability measure $\Lambda$ on
$E^{\prime}=[0,1]\times\mathcal{M}_{1}([0,1])\times\mathcal{M}_{1}([0,1])$
(and we will write any element $\mu$ of $E^{\prime}$ as $(p,\mu_{0},\mu_{1})$)
such that for all $n\geq 1$

$\displaystyle\mathbb{P}(X_{i}=x_{i},Y_{ij}=y_{ij},\;i,j\in[n])$
$\displaystyle\begin{aligned}
&=\int_{E^{\prime}}\Lambda(d\mu)\prod_{i=1}^{n}\Bigg{[}(p\mathbb{1}_{\\{x_{i}=1\\}}+(1-p)\mathbb{1}_{\\{x_{i}=0\\}})\\\
&\hskip
100.00015pt\int_{[0,1]}\mu_{x_{i}}(dq_{i})\prod_{j=1}^{n}(q_{i}\mathbb{1}_{\\{y_{ij}=1\\}}+(1-q_{i})\mathbb{1}_{\\{y_{ij}=0\\}})\Bigg{]}.\end{aligned}$
(4.25)

###### Proof.

Let us first observe that if a sequence $(X,(Y_{j},\;j\in\mathbb{N}))$
satisfies Hypothesis (A2), then, conditional on $X=x\in\\{0,1\\}$, the
sequence $(Y_{j},\;j\in\mathbb{N})$ is exchangeable. We can thus apply de
Finetti’s theorem: conditional on $X=x$ there is a unique probability measure
$\mu_{x}$ giving the distribution of the asymptotic frequency $q$ of the
variables ${(Y_{j},\;j\in\mathbb{N})}$, and conditional on $q$ they are i.i.d.
Bernoulli with parameter $q$. This implies that, for any $\\{0,1\\}$-valued
finite sequence $(x,y_{1},y_{2},\dots,y_{k})$,

$\displaystyle\mathbb{P}(X=x,Y_{1}=y_{1},\dots,Y_{k}=y_{k})$
$\displaystyle=\mathbb{P}(X=x)\int_{[0,1]}\mu_{x}(dq)\prod_{j=1}^{k}(q\mathbb{1}_{\\{y_{j}=1\\}}+(1-q)\mathbb{1}_{\\{y_{j}=0\\}}).$
(4.26)

Also observe that since $X$ is binary, there exists $p\in[0,1]$ such that
$\mathbb{P}(X=x)=p\mathbb{1}_{\\{x=1\\}}+(1-p)\mathbb{1}_{\\{x=0\\}}$.

As a consequence of Hypothesis (A1), we can apply once again de Finetti’s
theorem: there exists a unique law $\tilde{\Lambda}$ on
$\mathcal{M}_{1}(\\{0,1\\}^{\mathbb{N}})$ such that the law of
$(Z_{i},\;i\in\mathbb{N})$ equals
$\int_{\mathcal{M}_{1}(\\{0,1\\}^{\mathbb{N}})}\tilde{\Lambda}(d\tilde{\mu})\bigotimes_{i\geq
1}\tilde{\mu}$. Furthermore it has been seen that $\tilde{\mu}$ can be
expressed as in (4).

Now let $F$ stand for the measurable mapping such that
$F(\tilde{\mu})=(p,\mu_{0},\mu_{1})\in E^{\prime}$ and let $\Lambda$ be the
push-forward of $\tilde{\Lambda}$ by the mapping $F$. We obtain that if $A$
and $(B_{i},\;i\in A)$ are finite subsets of $\mathbb{N}$, then

$\displaystyle\mathbb{P}(X_{i}=x_{i},Y_{ij_{i}}=y_{ij_{i}},\;i\in A,j_{i}\in
B_{i})$ $\displaystyle=\int_{E^{\prime}}\Lambda(d\mu)\prod_{i\in
A}\Bigg{[}(p\mathbb{1}_{\\{x_{i}=1\\}}+(1-p)\mathbb{1}_{\\{x_{i}=0\\}})$
$\displaystyle\hskip 100.00015pt\int_{[0,1]}\mu_{x_{i}}(dq_{i})\prod_{j_{i}\in
B_{i}}(q_{i}\mathbb{1}_{\\{y_{ij_{i}}=1\\}}+(1-q_{i})\mathbb{1}_{\\{y_{ij_{i}}=0\\}})\Bigg{]}.$

This ends the proof. ∎

This result is almost enough to express (4.24) but one has to be careful
because the measure $\nu$ might not be finite. However, it is $\sigma$-finite
because by (4.23),

$\nu=\lim_{n\to\infty}\uparrow\nu\left(\left\\{\sum_{i=1}^{n}X_{i}\geq 2\text{
or }\exists i\leq n,\,\sum_{j=1}^{n}Y_{ij}\geq
2\right\\}\cap\;\cdot\;\right),$

and those events have finite measure. The idea behind the following lemma is
to make use of those events and hierarchical exchangeability to express $\nu$
as a limit of finite measures which, thanks to an application of Proposition
8, have a representation under the form $\eqref{eq:deFinetti}$.

Let us introduce some notation that will enable us to make this argument
formal. For a fixed vector $(\mathbf{g},\mathbf{s},\mathbf{c})\in\mathcal{C}$,
such that $|\mathbf{g}|=b$, let us examine the event

$A=A(\mathbf{g},\mathbf{s},\mathbf{c}):=\\{\forall 1\leq i\leq
b,\,X_{i}=s_{i},\text{ and }\forall 1\leq j\leq g_{i},Y_{ij}=c_{ij}\\}$

and its measure $\nu(A)$. Let us define, for all $n\geq 1$ the shifted random
array

$\mathbf{Z}_{n}:=(X_{i+n},Y_{(i+n)j},\;i,j\in\mathbb{N}).$ (4.27)

We decompose naturally
$A=(A\cap\\{\mathbf{Z}_{b}\neq\mathbf{0}\\})\cup(A\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\})$,
where $b=|\mathbf{g}|$.

Recall that the array $\mathbf{Z}$ encodes which species blocks and which gene
blocks are participating in a coalescence. Therefore the event
$A\cap\\{\mathbf{Z}_{b}\neq 0\\}$ indicates that there are merging species
blocks outside of the first $b$ blocks. In fact we will see that this implies
that such merging blocks are infinitely many (a random proportion $p$ of
them), and within each of these blocks, a random proportion $q$ of gene blocks
are also participating in the coalescence event. The following technical lemma
makes this statement rigorous.

######  Lemma 9.

For an array $(\mathbf{g},\mathbf{s},\mathbf{c})$ satisfying assumptions (H1)
and (H2), there exists a unique measure $\nu_{s}$ on
$E=(0,1]\times\mathcal{M}([0,1])$ such that

$\nu(A\cap\\{\mathbf{Z}_{b}\neq\mathbf{0}\\})=\int_{E}\nu_{s}(dp,d\mu)p^{k}(1-p)^{b-k}\prod_{i\,:\,s_{i}=1}\int_{[0,1]}\mu(dq)q^{l_{i}}(1-q)^{g_{i}-l_{i}},$
(4.28)

where $b:=|\mathbf{g}|$, $k:=\sum_{i}s_{i}$ and $l_{i}:=\sum_{j}c_{ij}$.
Moreover, $\nu_{s}$ satisfies (3.15).

###### Proof.

We define some events that will be used to express
$\nu(A\cap\\{\mathbf{Z}_{b}\neq\mathbf{0}\\})$.

$\displaystyle A_{n}=A_{n}(\mathbf{g},\mathbf{s},\mathbf{c}):=\\{\forall 1\leq
i\leq b,\,X_{i+n}=s_{i},\text{ and }\forall 1\leq j\leq
g_{i},Y_{(i+n)j}=c_{ij}\\}$
$\displaystyle{B_{n}:=\left\\{\sum_{i=1}^{n}X_{i}\geq 2\right\\}}$
$\displaystyle{B^{\prime}_{n}=B^{\prime}_{n}(\mathbf{g},\mathbf{s},\mathbf{c}):=\left\\{\sum_{i=b+1}^{b+n}X_{i}\geq
2\right\\}.}$

Note that $(\mathbf{g},\mathbf{s},\mathbf{c})$ satisfies (H1) and (H2), so we
have ${A\subset\\{\sum_{i=1}^{m}X_{i}\geq 2\text{ or
}\sum_{i,j=1}^{m}Y_{ij}\geq 2\\}}$ for $m=\max(b,g_{1},\ldots g_{b})$. Now
because $\nu$ satisfies (4.23), necessarily $\nu(A)<\infty$, which implies
that

$\nu(A\cap\\{\mathbf{Z}_{b}\in\cdot\\})$

is a finite hierarchically exchangeable measure on
$(\\{0,1\\}\times\\{0,1\\}^{\mathbb{N}})^{\mathbb{N}}$. The de Finetti
representation (Proposition 8) implies that on the event $A$, $\mathbf{Z}_{b}$
is either $\mathbf{0}$, or has an infinite number of entries with value $1$.
In particular,

$A\cap\\{\mathbf{Z}_{b}\neq\mathbf{0}\\}=A\cap\\{\mathbf{Z}_{b}\text{ has at
least two entries at }1\\},$

therefore, there is the equality

$A\cap\\{\mathbf{Z}_{b}\neq\mathbf{0}\\}=\bigcup_{n\geq 1}A\cap
B^{\prime}_{n},$

where the union is increasing. Therefore,

$\displaystyle\nu(A\cap\\{\mathbf{Z}_{b}\neq\mathbf{0}\\})$
$\displaystyle=\lim_{n\to\infty}\nu(A\cap B^{\prime}_{n}).$
$\displaystyle=\lim_{n\to\infty}\nu(B_{n}\cap A_{n}),$

where we used the hierarchical exchangeability of $\nu$ to get the second
equality. Now we know from (4.23) and because $\nu$ is exchangeable that the
measure

$\nu(B_{n}\cap\\{\mathbf{Z}_{n}\in\cdot\\})$

is a finite hierarchically exchangeable measure on
$(\\{0,1\\}\times\\{0,1\\}^{\mathbb{N}})^{\mathbb{N}}$. Because it is finite
we can apply Proposition 8 to deduce that there exists a finite measure
$\Lambda_{n}$ on $E^{\prime}=(0,1]\times\mathcal{M}([0,1])^{2}$ such that

$\displaystyle\nu(B_{n}\cap A_{n})$
$\displaystyle=\int_{E^{\prime}}\Lambda_{n}(dp,d\mu_{0},d\mu_{1})\prod_{i=1}^{b}\Bigg{[}(p\mathbb{1}_{\\{s_{i}=1\\}}+(1-p)\mathbb{1}_{\\{s_{i}=0\\}})$
$\displaystyle\hskip
125.00018pt\int_{[0,1]}\mu_{s_{i}}(dq_{i})\prod_{j=1}^{g_{i}}(q_{i}\mathbb{1}_{\\{c_{ij}=1\\}}+(1-q_{i})\mathbb{1}_{\\{c_{ij}=0\\}})\Bigg{]}.$

We can simplify this expression since $\nu$ is supported by the set
$\\{\forall i\in\mathbb{N},\,X_{i}=0\Rightarrow\forall
j\in\mathbb{N},Y_{ij}=0\\}.$ This implies that $\Lambda_{n}$-a.e. the measure
$\mu_{0}$ is $\delta_{0}$ the Dirac measure at $0$. Therefore we write
$\widetilde{\Lambda}_{n}$ for the push forward measure on
$E:=(0,1]\times\mathcal{M}([0,1])$ of $\Lambda_{n}$ by the application
$(p,\mu_{0},\mu_{1})\mapsto(p,\mu_{1})$. We now have

$\nu(B_{n}\cap
A_{n})=\int_{E}\widetilde{\Lambda}_{n}(dp,d\mu)p^{k}(1-p)^{b-k}\prod_{i\,:\,s_{i}=1}\int_{[0,1]}\mu(dq)q^{l_{i}}(1-q)^{g_{i}-l_{i}}.$
(4.29)

To be able to pass to the limit, let us check that the sequence of measures
$(\widetilde{\Lambda}_{n})$ is increasing. Indeed, recall that $\Lambda_{n}$
is obtained from two applications of de Finetti’s theorem to the exchangeable
array $\mathbf{Z}_{n}$, so the asymptotic parameters $p$ and $\mu$ appearing
in (4.29) are a deterministic, measurable functional of $\mathbf{Z}_{n}$. Let
us write this functional $F(\mathbf{Z}_{n})=(p,\mu)$, so now
$\widetilde{\Lambda}_{n}$ is simply the measure

$\nu(B_{n}\cap\\{F(\mathbf{Z}_{n})\in\cdot\\}).$

But $p$ and $\mu$ are asymptotic quantities of the array $\mathbf{Z}_{n}$,
which do not depend on the first row of $\mathbf{Z}_{n}$, so
$F(\mathbf{Z}_{n+1})=F(\mathbf{Z}_{n})$ and we have

$\displaystyle\widetilde{\Lambda}_{n}$
$\displaystyle=\nu(B_{n}\cap\\{F(\mathbf{Z}_{n})\in\cdot\\})$
$\displaystyle=\nu(B_{n}\cap\\{F(\mathbf{Z}_{n+1})\in\cdot\\})$
$\displaystyle\leq\nu(B_{n+1}\cap\\{F(\mathbf{Z}_{n+1})\in\cdot\\})$
$\displaystyle=\widetilde{\Lambda}_{n+1},$

where the passage from the second to the third line is simply because
$B_{n}\subset B_{n+1}$. Therefore there is a limiting measure $\nu_{s}$ on $E$
such that

$\nu(A\cap\\{\mathbf{Z}_{b}\neq\mathbf{0}\\})=\lim_{n\to\infty}\nu(B_{n}\cap
A_{n})=\int_{E}\nu_{s}(dp,d\mu)p^{k}(1-p)^{b-k}\\!\\!\\!\prod_{i\,:\,s_{i}=1}\int_{[0,1]}\mu(dq)q^{l_{i}}(1-q)^{g_{i}-l_{i}},$

so we recover (4.28). To prove the uniqueness of this measure, consider any
measure $\nu^{\prime}_{s}$ on $E$ such that (4.28) holds. Then we have simply

$\tilde{\Lambda}_{n}(dp,d\mu)=\nu(B_{n}\cap\\{F(\mathbf{Z}_{n})\in(dp,d\mu)\\})=(1-(1-p)^{n}-np(1-p)^{n-1})\nu^{\prime}_{s}(dp,d\mu),$

where the first equality is by definition and the second because we assumed
that (4.28) holds for $\nu^{\prime}_{s}$. Taking limits on both sides yields

$\nu_{s}(dp,d\mu)=\nu^{\prime}_{s}(dp,d\mu).$

It remains to prove (3.15). Note that the condition (4.23) implies that

$\nu(X_{1}=X_{2}=1)<\infty\quad\text{ and
}\quad\nu(X_{1}=1,Y_{1,1}=Y_{1,2}=1)<\infty.$

Translating these conditions with the formula (4.28), we recover exactly
(3.15). ∎

Let us now examine $\nu(A\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\})$. Recall that
the event $A\cap\\{\mathbf{Z}_{b}=0\\}$ indicates that there are no other
merging species blocks than those within the first $b$ blocks. The next lemma
shows that this implies that we are either in a Kingman-type coalescence (a
pair of species blocks are merging, occurring at rate $a_{s}$, or a pair of
gene blocks within one species are merging, occurring at rate $a_{g}$), or in
a multiple gene coalescence within a single species block (in which case a
random proportion $q$ of gene blocks are merging).

The key idea is to use exchangeability and the $\sigma$-finiteness property
(4.23) of the measure $\nu$ to show by contradiction that
$\nu(A\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\})$ is zero in certain cases.

######  Lemma 10.

For an array $(\mathbf{g},\mathbf{s},\mathbf{c})$ satisfying assumptions (H1)
and (H2), there exist unique real numbers $a_{s},a_{g}\geq 0$ and a unique
measure $\nu_{g}$ on $(0,1]$ satisfying (3.16) such that

$\displaystyle\nu(A\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\})$
$\displaystyle=a_{s}\mathbb{1}{\left\\{k=2,\mathbf{c}=\mathbf{0}\right\\}}$
(4.30)
$\displaystyle+\mathbb{1}{\\{k=1\\}}\left(a_{g}\mathbb{1}{\\{l_{I}=2\\}}+\int_{(0,1]}\nu_{g}(dq)q^{l_{I}}(1-q)^{g_{I}-l_{I}}\right),$

where $b:=|\mathbf{g}|$, $k:=\sum_{i}s_{i}$, $l_{i}:=\sum_{j}c_{ij}$ and in
the case $k=1$, $I$ is the unique index in $\\{1,2,\ldots,b\\}$ such that
$s_{I}=1$.

###### Proof.

The measure $\nu(\mathbf{X}\in\cdot)$ is an exchangeable measure on
$\\{0,1\\}^{\mathbb{N}}$ such that, because of (4.23),
$\nu(X_{1}=X_{2}=X_{3}=1)<\infty$. Note that exchangeability implies that for
any $n,i\geq 3$,

$\nu(\\{X_{1}=X_{2}=X_{3}=1\\}\cap\\{\mathbf{Z}_{n}=\mathbf{0}\\})=\nu(\\{X_{1}=X_{2}=X_{i}=1\\}\cap\\{\mathbf{Z}_{i}=\mathbf{0}\\}),$
(4.31)

But the events
$(\\{X_{1}=X_{2}=X_{i}=1\\}\cap\\{\mathbf{Z}_{i}=\mathbf{0}\\},\,i\geq 3)$ are
disjoint and all included in $\\{X_{1}=X_{2}=1\\}$, so that

$\sum_{i\geq
3}\nu(\\{X_{1}=X_{2}=X_{i}=1\\}\cap\\{\mathbf{Z}_{i}=\mathbf{0}\\})\leq\nu(\\{X_{1}=X_{2}=1\\})<\infty.$

From (4.31) we deduce
$\nu(\\{X_{1}=X_{2}=X_{3}=1\\}\cap\\{\mathbf{Z}_{n}=\mathbf{0}\\})=0$. This
implies immediately that for a finite array
$(\mathbf{g},\mathbf{s},\mathbf{c})$ such that $k=\sum_{i}s_{i}>2$, we have
$\nu(A\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\})=0$.

  * •

In the case $k=2$ (suppose $s_{1}=s_{2}=1$), one must examine several cases.

    * –

Suppose first $c_{1,1}=c_{1,2}=1$. This means that the first two gene blocks
of the first species block coalesce while the first two species blocks
coalesce. Then we note that for any $n,i\geq 2$,

$\displaystyle\nu(\\{X_{1}=X_{2}=1,\,Y_{1,1}=Y_{1,2}=1\\}\cap\\{\mathbf{Z}_{n}=\mathbf{0}\\})$
$\displaystyle=\nu(\\{X_{1}=X_{i}=1,\,Y_{1,1}=Y_{1,2}=1\\}\cap\\{\mathbf{Z}_{i}=\mathbf{0}\\}).$

However,

$\sum_{i\geq
2}\nu(\\{X_{1}=X_{i}=1,\,Y_{1,1}=Y_{1,2}=1\\}\cap\\{\mathbf{Z}_{i}=\mathbf{0}\\})\leq\nu(\\{Y_{1,1}=Y_{1,2}=1\\})<\infty,$

so that necessarily
$\nu(\\{X_{1}=X_{2}=1,\,Y_{1,1}=Y_{1,2}=1\\}\cap\\{\mathbf{Z}_{n}=\mathbf{0}\\})=0$.
So in the case $c_{1,1}=c_{1,2}=1$, we have
$\nu(A\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\})=0$.

    * –

Now suppose $c_{1,1}=c_{2,1}=1$, and all the other $c_{ij}$ are zero. From our
previous point, note that

$\nu(\\{X_{1}=X_{2}=1,\,Y_{1,1}=Y_{2,1}=1,\text{ and }\exists j\geq
2,Y_{1,j}=1\\}\cap\\{\mathbf{Z}_{n}=\mathbf{0}\\})=0,$

which implies that the events
$(\\{X_{1}=X_{2}=1,\,Y_{1,j}=Y_{2,1}=1\\}\cap{\\{\mathbf{Z}_{n}=\mathbf{0}\\}},\,{j\geq
1})$ are $\nu$-a.e. disjoint. Therefore for any $n\geq 2$,

$\sum_{j\geq
1}\nu(\\{X_{1}=X_{2}=1,\,Y_{1,j}=Y_{2,1}=1\\}\cap\\{\mathbf{Z}_{n}=\mathbf{0}\\})\leq\nu(\\{X_{1}=X_{2}=1\\})<\infty,$

So necessarily
$\nu(\\{X_{1}=X_{2}=1,\,Y_{1,j}=Y_{2,1}=1\\}\cap\\{\mathbf{Z}_{n}=\mathbf{0}\\})=0$.
This implies that in the case $c_{1,1}=c_{2,1}=1$, we have
$\nu(A\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\})=0$.

    * –

The previous two points show that in the case $k=2$, the only way to have
$\nu(A\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\})>0$ is if $\mathbf{c}=\mathbf{0}$.
In that case, define

$\displaystyle a_{s}$
$\displaystyle:=\nu(\\{X_{1}=X_{2}=1\\}\cap\\{\mathbf{Z}_{2}=\mathbf{0}\\})$
$\displaystyle=\nu(\\{X_{1}=X_{2}=1\\}\cap\\{\mathbf{Y}=\mathbf{0}\text{ and
}\forall k\notin\\{1,2\\},\,X_{k}=0\\}).$

Then by exchangeability, for all $i,j\in\mathbb{N}$ with $i\neq j$, we have

$a_{s}=\nu(\\{X_{i}=X_{j}=1\\}\cap\\{\mathbf{Y}=\mathbf{0}\text{ and }\forall
k\notin\\{i,j\\},\,X_{k}=0\\}),$

and in conclusion, for any array $(\mathbf{g},\mathbf{s},\mathbf{c})$ such
that $k=2$, we have

$\nu(A\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\})=\mathbb{1}_{\\{\mathbf{c}=\mathbf{0}\\}}a_{s}.$

  * •

In the case $k=1$, suppose that $s_{1}=1$. On the event

$\\{X_{1}=1,\,X_{2}=X_{3}=\cdots=X_{b}=0\\}\cap\\{\mathbf{Z}_{b}=\mathbf{0}\\},$

we have simply $\mathbf{Z}_{1}=\mathbf{0}$, and then the measure

$\nu^{\prime}:=\nu\bigl{(}\\{(Y_{1,j})_{j\in\mathbb{N}}\in\cdot\\}\cap\\{X_{1}=1,\,\mathbf{Z}_{1}=\mathbf{0}\\}\bigr{)}$

is an exchangeable measure on $\\{0,1\\}^{\mathbb{N}}$ such that for all
$n\in\mathbb{N}$, ${\nu^{\prime}\left(\sum_{j=1}^{n}Y_{j}\geq
2\right)<\infty}$. Therefore (see for instance Bertoin [4]) there exist a
unique constant $a_{g}\geq 0$ and $\nu_{g}$ a unique measure on $(0,1]$
satisfying (3.16) such that $\nu^{\prime}$ can be written

$\nu^{\prime}(Y_{1}=y_{1},Y_{2}=y_{2},\ldots,Y_{n}=y_{n})=a_{g}\mathbb{1}_{l=2}+\int_{(0,1]}\nu_{g}(dq)q^{l}(1-q)^{n-l},$

for any vector
$(y_{1},y_{2},\ldots,y_{n})\in\\{0,1\\}^{n}\setminus\\{\mathbf{0}\\}$ such
that $l:=\sum_{i}y_{i}\geq 2$.

Putting all the previous considerations together yields (4.30). ∎

Now it remains to put together Lemma 9 and Lemma 10. Recall that we restricted
the rate function $q$ to arrays in $\mathcal{C}$, i.e. satisfying (H1) to
(H3). The reason for assuming (H3) is that then we can always write
$q_{b,k}(\mathbf{g},\mathbf{s},\mathbf{c})$ as in (4.24), that is

$\displaystyle q_{b,k}(\mathbf{g},\mathbf{s},\mathbf{c})$
$\displaystyle=\nu\bigl{(}\forall 1\leq i\leq b,\,X_{i}=s_{i},\text{ and
}\forall 1\leq j\leq g_{i},Y_{ij}=c_{ij}\bigr{)}$
$\displaystyle+\mathbb{1}_{\\{\mathbf{c}=\mathbf{0}\\}}\nu\left(\forall 1\leq
i\leq b,\,X_{i}=s_{i},\text{ and
}\sum_{i=1}^{b}\sum_{j=1}^{g_{i}}Y_{ij}=1\right).$

Using the previous two lemmas to decompose the two lines on the events
$\\{\mathbf{Z}_{b}\neq\mathbf{0}\\}$ and $\\{\mathbf{Z}_{b}=\mathbf{0}\\}$, we
obtain the formula (3.17), concluding the proof of Theorem 5.

##  5 Poissonian construction

The goal of the present section is to show how any simple nested exchangeable
coalescent can be constructed from a Poisson point process. Consider two real
coefficients $a_{s},a_{g}\geq 0$ and two measures: $\nu_{s}$ on
$E=(0,1]\times\mathcal{M}_{1}([0,1])$ satisfying (3.15), and $\nu_{g}$ on
$(0,1]$, satisfying (3.16). Recall the measures
$\mathtt{K}_{s},\mathtt{K}_{g},P^{g}_{x}$ and $P^{s}_{x,\mu}$ introduced in
Section 2, and the measure $\nu(d\mathbf{Z})$ defined on the space
$\widehat{E}$ of doubly indexed arrays of 0’s and 1’s
$\mathbf{Z}=(\mathbf{X},(\mathbf{Y}_{i},\,i\geq 1))=(X_{i},Y_{ij},\,i,j\geq
1)$

$\nu:=a_{s}{\tt K}_{s}+a_{g}{\tt
K}_{g}+\int_{(0,1]}\nu_{g}(dx)\,P^{g}_{x}+\int_{(0,1]\times\mathcal{M}_{1}([0,1])}\nu_{s}(dx,d\mu)\,P^{s}_{x,\mu}.$

Note that $\nu$ characterizes the distribution of the SNEC through the
relation (4.24). The key idea of the construction is that $\nu$ necessarily
satisfies (4.23), which is easily shown using exchangeability and conditions
(3.15) and (3.16). First, note that $\nu(\mathbf{Z}=\mathbf{0})=0$ is trivial
from our definitions, and that a straightforward union bound yields

$\displaystyle\nu\Big{(}\textstyle\sum_{i=1}^{n}$ $\displaystyle X_{i}\geq
2\text{ or }\exists i\leq n,\textstyle\sum_{j=1}^{n}Y_{ij}\geq 2\Big{)}$
$\displaystyle\leq\sum_{1\leq i<i^{\prime}\leq
n}\nu(X_{i}=X_{i^{\prime}}=1)+\sum_{i=1}^{n}\sum_{1\leq j<j^{\prime}\leq
n}\nu(X_{i}=Y_{ij}=Y_{ij^{\prime}}=1)$
$\displaystyle=\frac{n(n-1)}{2}\nu(X_{1}=X_{2}=1)+\frac{n^{2}(n-1)}{2}\nu(X_{1}=Y_{1,1}=Y_{1,2}=1),$

therefore we need only check that these two quantities are finite. Now by
definition, we have

$\displaystyle\mathtt{K}_{s}(X_{1}=X_{2}=1)=1,$
$\displaystyle\quad\mathtt{K}_{s}(X_{1}=Y_{1,1}=Y_{1,2}=1)=0,$
$\displaystyle\mathtt{K}_{g}(X_{1}=X_{2}=1)=0,$
$\displaystyle\quad\mathtt{K}_{g}(X_{1}=Y_{1,1}=Y_{1,2}=1)=1,$ $\displaystyle
P^{g}_{x}(X_{1}=X_{2}=1)=0,$ $\displaystyle\quad
P^{g}_{x}(X_{1}=Y_{1,1}=Y_{1,2}=1)=x^{2},$ $\displaystyle
P^{s}_{x,\mu}(X_{1}=X_{2}=1)=x^{2},$ $\displaystyle\quad
P^{s}_{x,\mu}(X_{1}=Y_{1,1}=Y_{1,2}=1)=x\int_{[0,1]}\mu(dq)q^{2}.$

Integrating the last two lines with respect to $\nu_{g}$ and $\nu_{s}$ and
summing, we see that (3.15) and (3.16) imply that both $\nu(X_{1}=X_{2}=1)$
and $\nu(X_{1}=Y_{1,1}=Y_{1,2}=1)$ are finite, proving (4.23).

Now to start the construction of our process, consider an initial partition
$\pi_{0}\in\mathcal{N}_{\infty}$. Let $M$ be a Poisson point process on
$(0,\infty)\times\widehat{E}$ with intensity $dt\otimes\nu(d\mathbf{Z})$. We
will construct on the same probability space the processes
$\mathcal{R}^{n}=(\mathcal{R}^{n}(t),\,t\geq 0)$, for $n\in\mathbb{N}$ thanks
to $M$.

Recall that for any $\mathbf{Z}=(\mathbf{X},(\mathbf{Y}_{i},\,i\geq
1))=(X_{i},Y_{ij},\,i,j\geq 1)$ and any nested partition
$\pi\in\mathcal{N}_{n}$, we denote by $C(\pi,\mathbf{Z})$ the nested partition
of $\mathcal{N}_{n}$ obtained from $\pi$ by merging exactly the blocks that
_participate in the coalescence_ where

  * •

The $i$-th block of $\pi^{s}$ participates iff $X_{i}=1$;

  * •

The $j$-th block in $\pi^{g}$ of the $i$-th block of $\pi^{s}$ participates
iff $X_{i}=1$ and $Y_{ij}=1$.

Fix $n\in\mathbb{N}$, and let $M_{n}$ denote the subset of $M$ consisting of
points $(t,\mathbf{Z})$ such that $\sum_{i=1}^{n}X_{i}\geq 2$ or $\exists
i\leq n,\,X_{i}\sum_{j=1}^{n}Y_{ij}\geq 2$. Because of (4.23), there are only
a finite number of such points with $t$ in a compact set of $[0,+\infty)$.
Therefore one can label the atoms of the set
$M_{n}:=\\{(t_{k},\mathbf{Z}^{(k)}),k\in\mathbb{N}\\}$ in increasing order,
i.e. such that $0\leq t_{1}\leq t_{2}\ldots$

We set $\mathcal{R}^{n}(t)=(\pi_{0})_{|n}$ for $t\in[0,t_{1})$. Then define
recursively

$\mathcal{R}^{n}(t)=C(\mathcal{R}^{n}(t_{i}-),\mathbf{Z}^{(i)}),\quad\text{for
every }t\in[t_{i},t_{i+1}).$

These processes are consistent in $n$ as we show in the following result.

######  Proposition 11.

For every $t\geq 0$, the sequence of random bivariate partitions
$(\mathcal{R}^{n}(t),n\in\mathbb{N})$ is consistent. If we denote by
$\mathcal{R}(t)$ the unique partition of $\mathcal{N}_{\infty}$ such that
$\mathcal{R}_{|n}(t)=\mathcal{R}^{n}(t)$ for every $n\in\mathbb{N}$, then the
process $\mathcal{R}=(\mathcal{R}(t),t\geq 0)$ is a SNEC started from
$\pi_{0}$, with rates given as in Theorem 5.

The proof uses similar arguments as in the proof of consistency of
exchangeable coalescents given in Proposition 4.5 of [4].

###### Proof.

The key idea (basically (4.4) in [4]) is that by definition, the coagulation
operator satisfies

$\text{Coag}_{2}(\pi,\tilde{\pi})_{|n}=\text{Coag}_{2}(\pi_{|n},\tilde{\pi})=\text{Coag}_{2}(\pi_{|n},\tilde{\pi}_{|n})$
(5.32)

for any $\pi,\tilde{\pi}$ and $n$ for which this is well defined.

Recall that we defined $M_{n}$ as the subset of $M$ consisting of points
$(t,\mathbf{Z})$ such that $\sum_{i=1}^{n}X_{i}\geq 2$ or $\exists i\leq
n,\,X_{i}\sum_{j=1}^{n}Y_{ij}\geq 2$. Fix $n\geq 2$ and write
$(t_{1},\mathbf{Z}^{(1)})$ for the first atom of $M_{n}$ on
$(0,\infty)\times\widehat{E}$. Plainly,
$\mathcal{R}^{n-1}(t)=\mathcal{R}^{n}_{|n-1}(t)=(\pi_{0})_{|n-1}$ for every
$t\in[0,t_{1})$.

Consider first the case when $\sum_{i=1}^{n-1}X^{(1)}_{i}\geq 2$ or $\exists
i\leq n-1,\,X^{(1)}_{i}\sum_{j=1}^{n-1}Y^{(1)}_{ij}\geq 2$. Then
$(t_{1},\mathbf{Z}^{(1)})$ is also the first atom of $M_{n-1}$ and by
definition and using (5.32),
$\mathcal{R}^{n-1}(t_{1})=\mathcal{R}^{n}_{|n-1}(t)$.

Now suppose $\sum_{i=1}^{n-1}X^{(1)}_{i}\leq 1$ and $\forall i\leq
n-1,\,X^{(1)}_{i}\sum_{j=1}^{n-1}Y^{(1)}_{ij}\leq 1$. This implies that at
time $t_{1}$, there is no species (resp. genes) coalescence between the $n-1$
first species (resp. genes) of $\mathcal{R}^{n}(t_{1}-)$. Therefore the
coalescence event in $\mathcal{R}^{n}$ at time $t_{1}$ leaves the first $n-1$
blocks of $\mathcal{R}^{n}(t_{1}-)^{s}$ or $\mathcal{R}^{n}(t_{1}-)^{g}$
unchanged, though there may be a coalescence involving the $n$-th block (in
that case, necessarily a singleton $\\{n\\}$) and one of the $n-1$ first
blocks. So finally
$\mathcal{R}^{n}(t_{1})_{|n-1}=\mathcal{R}^{n}(t_{1}-)_{|n-1}=\mathcal{R}^{n-1}(t_{1})$.

In both cases we have
$\mathcal{R}^{n}(t_{1})_{|n-1}=\mathcal{R}^{n-1}(t_{1})$, and by an obvious
induction this is true for any further jump of the process $\mathcal{R}^{n}$,
so that for all $t\geq 0$,

$\mathcal{R}^{n}(t)_{|n-1}=\mathcal{R}^{n-1}(t).$

This shows the existence of $\mathcal{R}$ such that for all $n$,
$\mathcal{R}_{|n}=\mathcal{R}^{n}$.

From this Poissonian construction $\mathcal{R}^{n}$ is a Markov process, and
by definition the arrays $\mathbf{Z}^{(i)}_{|[n]^{2}}$ are hierarchically
exchangeable, which implies that $\mathcal{R}^{n}$ is an exchangeable process.
Clearly by construction $\mathcal{R}^{n}(t)$ is nested for all $t$, and the
only jumps of the process $\mathcal{R}^{n}$ are coalescence events. According
to Lemma 3, the process $\mathcal{R}$ is a SNEC process. Because the arrays
$\mathbf{Z}$, where $(t,\mathbf{Z})\in M$, are the same arrays that appear in
the proof of Theorem 5, it is clear that the jump rates of $\mathcal{R}^{n}$
are those given in Theorem 5. ∎

##  6 Marginal coalescents – Coming down from infinity

Consider a SNEC process $\mathcal{R}=(\mathcal{R}^{s},\mathcal{R}^{g})$, with
rates given as in Theorem 5 by two coefficients $a_{s},a_{g}\geq 0$ and two
measures, $\nu_{s}$ on $E=(0,1]\times\mathcal{M}_{1}([0,1])$ and $\nu_{g}$ on
$(0,1]$ satisfying (3.15) and (3.16).

It is obvious from Proposition 11 that $(\mathcal{R}^{s}(t),\;t\geq 0)$ is a
simple coalescent process, with Kingman coefficient $a_{s}$ and coagulation
measure $\widehat{\nu}_{s}$ satisfying (2.9) which is the push-forward of
$\nu_{s}(dp,d\mu)$ by the application $(p,\mu)\mapsto p$. Let us call this
univariate coalescent the _(marginal) species coalescent_ of the SNEC process
$\mathcal{R}$.

Now, notice that under an initial condition with a unique species block (i.e.,
$\mathcal{R}^{s}$ is constant to the coarsest partition
$\mathbf{1}_{\infty}$), the process $(\mathcal{R}^{g}(t),\;t\geq 0)$ also
behaves as a simple coalescent process, with Kingman coefficient $a_{g}$ and
coagulation measure $\widehat{\nu}_{g}$ defined by

$\forall B\text{ Borel set of
}(0,1],\quad\widehat{\nu}_{g}(B):=\nu_{g}(B)+\int_{(0,1]\times\mathcal{M}_{1}([0,1])}\nu_{s}(dp,d\mu)p\,\mu(B).$

We call the simple coalescent thus defined the _(marginal) gene coalescent_ of
the SNEC process $\mathcal{R}$.

Equivalently, in terms of $\Lambda$-coalescents, the marginal species
coalescent is a $\Lambda_{s}$-coalescent with $\Lambda_{s}$ defined by

$\forall B\text{ Borel set of
}[0,1],\quad\Lambda_{s}(B)=a_{s}\delta_{0}(B)+\int_{B\times\mathcal{M}_{1}([0,1])}\nu_{s}(dp,d\mu)p^{2},$
(6.33)

and the marginal gene coalescent is a $\Lambda_{g}$-coalescent with
$\Lambda_{g}$ defined for all $B$ Borel set of $[0,1]$ by

$\Lambda_{g}(B)=a_{g}\delta_{0}(B)+\int_{B}\nu_{g}(dq)q^{2}+\int_{(0,1]\times\mathcal{M}_{1}([0,1])}\nu_{s}(dp,d\mu)p\int_{B}\mu(dq)q^{2}.$
(6.34)

These two marginal processes allow us to express properties of the initial
bivariate SNEC process. Consider an initial state
$\varrho_{0}\in\mathcal{N}_{\infty}$ with infinitely many species blocks, each
containing infinitely many gene blocks. In a way analogous to the one-
dimensional case, recalling that
$\lvert\mathcal{R}^{g}(t)\rvert\geq\lvert\mathcal{R}^{s}(t)\rvert$ for all
$t\geq 0$, we will say that a SNEC _comes down from infinity_ (CDI) if for all
$t>0$

$\lvert\mathcal{R}^{g}(t)\rvert<\infty\qquad\mathbb{P}_{\varrho_{0}}\text{-a.s.}$

In the univariate case, characterizing which coalescent processes come down
from infinity has been solved [39] for $\Lambda$-coalescents, with the
following necessary and sufficient condition for coming down from infinity:

$\sum_{n\geq
2}\left(\sum_{k=2}^{n}(k-1)\binom{n}{k}\int_{[0,1]}\Lambda(dp)p^{k-2}(1-p)^{n-k}\right)^{-1}<\infty.$

Note that the previous condition is true as soon as $\Lambda$ has an atom at
$0$ ($\Lambda(\\{0\\})$ is the Kingman coefficient of the process). An
equivalent criterion (see [6], and [2] for a probabilistic proof) is the
integrability of $1/\psi$ near $+\infty$, where

$\psi(q):=\int_{[0,1]}\left(e^{-qx}-1+qx\right)x^{-2}\,\Lambda(dx).$ (6.35)

We will now see that in the case of simple nested coalescents, we can give a
general characterization of the different CDI properties of a SNEC process,
depending only on the properties of the marginal species and marginal gene
coalescents.

First notice that if the marginal gene coalescent does not CDI, then any
species block with infinitely many gene blocks at some time $t$ clearly keeps
infinitely many gene blocks for any $t^{\prime}\geq t$. Also in any case the
process $\mathcal{R}^{s}$ has the distribution of the marginal species
coalescent, so determining whether the number of species comes down from
infinity is trivial.

######  Proposition 12.

We assume here that $\widehat{\nu}_{s}(\\{1\\})=\widehat{\nu}_{g}(\\{1\\})=0$
and that the marginal gene coalescent comes down from infinity (CDI). Then we
have the following three cases.

  1. i)

If the marginal species coalescent CDI as well, then $\mathcal{R}$ CDI.

  2. ii)

If the marginal species coalescent does not CDI but
$\displaystyle\int_{[0,1]}\widehat{\nu}_{s}(dx)\,x=\infty$, then for any
initial condition with infinitely many species blocks and for each time $t>0$,
the number of gene blocks in each species block of $\mathcal{R}(t)$ is
infinite a.s.

  3. iii)

If the marginal species coalescent does not CDI and
$\displaystyle\int_{[0,1]}\widehat{\nu}_{s}(dx)\,x<\infty$, then for any
initial condition and for each time $t>0$, the number of gene blocks in each
species block of $\mathcal{R}(t)$ is finite a.s.

As a consequence of this proposition, it is clear that $\mathcal{R}$ comes
down from infinity if and only if both the marginal species coalescent and the
marginal gene coalescent come down from infinity.

A simple example of a SNEC process coming down from infinity is the nested
Kingman coalescent (‘Kingman in Kingman’), given by its marginal rates
$a_{s},a_{g}>0$, defined so that each pair of species coalesces at rate
$a_{s}$ independently of the others, and each pair of genes within the same
species coalesces at rate $a_{g}$ independently of the rest. Since the
marginal coalescents are precisely two Kingman coalescents, they both come
down from infinity.

Note that the Bolthausen-Sznitman coalescent [9] (denoted $U$-coalescent in
[35] because the measure $\Lambda$ is uniform on $[0,1]$) satisfies the
conditions of the peculiar case ii). So for a SNEC $\mathcal{R}$ defined by a
Kingman gene coalescent evolving within a species $U$-coalescent, at each
positive time the number of gene blocks within a species block is infinite (if
the initial state $\varrho_{0}$ has an infinite number of species blocks).

Case iii) can easily be obtained by considering a “slow” species coalescent,
such as a $\delta_{x}$-coalescent for $x\in(0,1)$, or any
$\beta(a,b)$-coalescent with $a>1,b>0$ (that is a $\Lambda$-coalescent with
$\Lambda(dx)=c_{a,b}x^{a-1}(1-x)^{b-1}dx$).

###### Proof.

i) Suppose both marginal coalescents come down from infinity, and consider an
initial state $\varrho\in\mathcal{N}_{\infty}$ with infinitely many species
blocks, each containing infinitely many gene blocks.

Choose $t>0$. Since $\mathcal{R}^{s}$ comes down from infinity, we have
$\mathbb{P}_{\varrho}(\lvert\mathcal{R}^{s}(t/2)\rvert<\infty)=1$, and
necessarily, $\mathcal{R}^{s}$ stays constant on an interval $[t/2,T[$, where
$T$ is its next jump time. Now on the interval $[t/2,\min(T,t)[$, within each
of the $\lvert\mathcal{R}^{s}(t/2)\rvert$ species block, the gene blocks
undergo independent coalescent processes which CDI, therefore there are
finitely many gene blocks in each species at time $\min(T,t)$, which implies

$\mathbb{P}_{\varrho}(\lvert\mathcal{R}^{g}(t)\rvert<\infty)=1.$

Let us say a few words before proving ii) and iii). Pick $t>0$ and focus on
the species containing $1$ (the first species). To this aim, write $M(t)$ for
the number of genes within the first species, at time $t$. By exchangeability,
to show ii) it is sufficient to show $\mathbb{P}_{\varrho}(M(t)=\infty)=1$,
for any initial condition $\varrho$ with infinitely many species blocks, and
to show iii) it is sufficient to show $\mathbb{P}_{\varrho}(M(t)<\infty)=1$,
for any initial condition $\varrho$.

ii) Suppose $\int_{[0,1]}\widehat{\nu}_{s}(dx)\,x=\infty$. First, note that
since the species coalescent does not CDI and $\widehat{\nu}_{s}(\\{1\\})=0$,
there are at all times $t\geq 0$ infinitely many species blocks (see for
instance [35, Proposition 23]). Now let us fix $\delta\in(0,t]$ and
$\varepsilon\in(0,1]$, and investigate the random number of coalescence events
in the time interval $[t-\delta,t]$ involving the first species and at least a
proportion $\varepsilon$ of all other species. More precisely, we consider the
number of atoms $(s,\mathbf{Z})$ in the Poissonian construction such that
$s\in[t-\delta,t]$, $X_{1}=1$ and
$\lim_{n\to\infty}\sum_{i=1}^{n}X_{i}/n\geq\varepsilon$. From the Poissonian
construction, it is easy to see that this number is a Poisson random variable
with mean

$\delta\int_{[\varepsilon,1]}\widehat{\nu}_{s}(dx)\,x.$

Pick any $A\in\mathbb{N}$ and $\eta>0$. We will show
$\mathbb{P}_{\varrho}(M(t)\leq A)<2\eta$, which is sufficient to conclude that
$M(t)=\infty$ a.s. Note that we assumed that the marginal gene coalescent CDI,
so for $\Pi=(\Pi(t),\,t\geq 0)$ a version of this univariate coalescent
started from $\mathbf{0}_{\infty}$, we have
$\mathbb{P}(\lvert\Pi(\delta)\rvert<\infty)=1$ for all $\delta>0$. In
addition, $\Pi$ is right-continuous, so
$\lvert\Pi(\delta)\rvert\uparrow\infty$ as $\delta\to 0$. Therefore, one can
choose $\delta>0$ small enough, and then $\varepsilon>0$ such that

$\mathbb{P}(\lvert\Pi(\delta)\rvert\leq A)<\eta\quad\text{ and }\quad
e(\varepsilon):=\int_{[\varepsilon,1]}\widehat{\nu}_{s}(dx)\,x\geq\frac{-\log(\eta)}{\delta}.$
(6.36)

Now consider the stopping time defined by

$\displaystyle T:=\inf\\{s\geq t-\delta,\;\text{the first species participates
at time $s$ in a coalescence event }$ $\displaystyle\text{involving at least a
proportion $\varepsilon$ of other species}\\}.$

By the Poisson construction, $T-(t-\delta)$ is an exponential random variable
with parameter $e(\varepsilon)$, so from (6.36) we deduce

$\mathbb{P}_{\varrho}(T\geq t)\leq\eta.$

Now since $T$ is a coalescence time for the first species, we have
$M(T)=\infty$ almost surely. Indeed, the assumption
$\widehat{\nu}^{g}(\\{1\\})=0$ implies that not every gene participates in the
coalescence. But since an infinite number of species participate in the
coalescence, the law of large numbers implies that in the newly formed
species, there is an infinite number of genes which do not coalesce at time
$T$. Since $M(T)=\infty$, we can define a random injection
$\sigma:\mathbb{N}\to\mathbb{N}$ mapping $k$ to the first element of the
$k$-th gene of the first species at time $T$. We then define
$\widetilde{\Pi}(u):=\sigma(\mathcal{R}^{g}(T+u))$, which has by the strong
Markov property the distribution of a marginal gene coalescent started from
$\mathbf{0}_{\infty}$, independent of $T$. Furthermore, by construction we
have $M(T+u)\geq\lvert\widetilde{\Pi}(u)\rvert$ a.s., so that finally

$\displaystyle\mathbb{P}_{\varrho}(M(t)\leq A)$
$\displaystyle\leq\mathbb{P}_{\varrho}(T>t)+\mathbb{P}_{\varrho}(t-\delta\leq
T\leq t)\,\mathbb{P}_{\varrho}(\lvert\widetilde{\Pi}(t-T)\rvert\leq A\mid
t-\delta\leq T\leq t)$
$\displaystyle\leq\mathbb{P}_{\varrho}(T>t)+\mathbb{P}(\lvert\Pi(\delta)\rvert\leq
A)$ $\displaystyle\leq 2\eta.$

iii) Now supposing $\int_{[0,1]}\widehat{\nu}_{s}(dx)\,x<\infty$, with the
same argument as previously, the first species participates in coalescence
events at some random times $0<T_{1}<T_{2}<\ldots$, distributed as a Poisson
process with parameter $\int_{[0,1]}\widehat{\nu}_{s}(dx)\,x$, and all these
events involve infinitely many species blocks (recall the marginal species
coalescent does not CDI and so in particular has $a_{s}=0$). Let $T_{0}:=0$ by
convention and for each $i$, we can define a random injection
$\sigma_{i}:\mathbb{N}\to\mathbb{N}$ mapping $k$ to the first element of the
$k$-th gene of the first species at time $T_{i}$. Now because the first
species does not change during the intervals $[T_{i},T_{i+1})$, the process
$\widetilde{\Pi}_{i}$ defined by

$\widetilde{\Pi}_{i}(u):=\sigma_{i}(\mathcal{R}^{g}(T_{i}+u))$

is a marginal gene coalescent (and so CDI by assumption), which is independent
of $T_{i}$, and there is the following equality between processes, for
$u<T_{i+1}-T_{i}$,

$M(T_{i}+u)=\widetilde{\Pi}_{i}(u).$

Finally, we have for any $t>0$, and any initial
$\varrho\in\mathcal{N}_{\infty}$,

$\displaystyle\mathbb{P}_{\varrho}(M(t)<\infty)$ $\displaystyle=\sum_{i\geq
0}\mathbb{P}_{\varrho}(T_{i}<t<T_{i+1})\,\mathbb{P}_{\varrho}(M(t)<\infty\mid
T_{i}<t<T_{i+1})$ $\displaystyle=\sum_{i\geq
0}\mathbb{P}_{\varrho}(T_{i}<t<T_{i+1})\,\mathbb{P}_{\varrho}(\widetilde{\Pi}_{i}(t-T_{i})<\infty\mid
T_{i}<t<T_{i+1})$ $\displaystyle=\sum_{i\geq
0}\mathbb{P}_{\varrho}(T_{i}<t<T_{i+1})=1,$

which concludes the proof. ∎

#### Acknowledgments.

The four authors thank the Center for Interdisciplinary Research in Biology
(Collège de France) for travel funding. ABB and ASJ would like to thank CIMAT,
A.C. and especially Víctor Rivero for support and for his comments on this
project, which started during Airam’s PhD thesis. ABB is supported by CONACYT
postdoctoral grant 234823, and ASJ by CONACYT grant CB-2014/243068.

## References

  * Berestycki et al. [2013] J. Berestycki, N. Berestycki, and J. Schweinsberg.  The genealogy of branching Brownian motion with absorption.  _The Annals of Probability_ , 41(2):527–618, Mar. 2013.  doi:10.1214/11-AOP728.
  * Berestycki et al. [2014] J. Berestycki, N. Berestycki, and V. Limic.  A small-time coupling between ${\Lambda}$-coalescents and branching processes.  _The Annals of Applied Probability_ , 24(2):449–475, Apr. 2014.  doi:10.1214/12-AAP911.
  * Berestycki [2009] N. Berestycki.  Recent progress in coalescent theory.  _Ensaios Matemáticos_ , 16(1):1–193, 2009\.
  * Bertoin [2006] J. Bertoin.  _Random Fragmentation and Coagulation Processes_.  Cambridge University Press, Cambridge, 2006.  doi:10.1017/CBO9780511617768.
  * Bertoin and Le Gall [2003] J. Bertoin and J.-F. Le Gall.  Stochastic flows associated to coalescent processes.  _Probability Theory and Related Fields_ , 126(2):261–288, 2003.
  * Bertoin and Le Gall [2006] J. Bertoin and J.-F. Le Gall.  Stochastic flows associated to coalescent processes. III. Limit theorems.  _Illinois Journal of Mathematics_ , 50(1-4):147–181, 2006.
  * [7] A. Blancas and A. Wakolbinger.  A representation for the semigroup of a two-level Fleming-Viot process in terms of the Kingman nested coalescent.  _In preparation_.
  * Blancas et al. [2018] A. Blancas, T. Rogers, J. Schweinsberg, and A. Siri-Jégousse.  The nested Kingman coalescent: Speed of coming down from infinity.  _arXiv:1803.08973 [math]_ , Mar. 2018.
  * Bolthausen and Sznitman [1998] E. Bolthausen and A.-S. Sznitman.  On Ruelle’s probability cascades and an abstract cavity method.  _Communications in Mathematical Physics_ , 197(2):247–276, 1998.  doi:10.1007/s002200050450.
  * Brunet and Derrida [2013] É. Brunet and B. Derrida.  Genealogies in simple models of evolution.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2013(01):P01006, 2013.
  * Dawson [2018] D. A. Dawson.  Multilevel mutation-selection systems and set-valued duals.  _Journal of Mathematical Biology_ , 76(1-2):295–378, Jan. 2018.  doi:10.1007/s00285-017-1145-2.
  * Degnan and Rosenberg [2009] J. H. Degnan and N. A. Rosenberg.  Gene tree discordance, phylogenetic inference and the multispecies coalescent.  _Trends in ecology & evolution_, 24(6):332–340, 2009.
  * Desai et al. [2013] M. M. Desai, A. M. Walczak, and D. S. Fisher.  Genetic diversity and the structure of genealogies in rapidly adapting populations.  _Genetics_ , 193(2):565–585, 2013.
  * Doyle [1997] J. J. Doyle.  Trees within trees: genes and species, molecules and morphology.  _Systematic Biology_ , 46(3):537–553, 1997.
  * Duchamps [2018] J.-J. Duchamps.  Trees within trees II: Nested Fragmentations.  _arXiv:1807.05951_ , July 2018.
  * Durrett and Schweinsberg [2005] R. Durrett and J. Schweinsberg.  A coalescent model for the effect of advantageous mutations on the genealogy of a population.  _Stochastic processes and their applications_ , 115(10):1628–1657, 2005.
  * Eldon and Wakeley [2006] B. Eldon and J. Wakeley.  Coalescent processes when the distribution of offspring number among individuals is highly skewed.  _Genetics_ , 172(4):2621–2633, Apr. 2006.  doi:10.1534/genetics.105.052175.
  * Etheridge [2011] A. Etheridge.  _Some Mathematical Models from Population Genetics: École d’été de Probabilités de Saint-Flour XXXIX-2009_.  Lecture notes in mathematics. Springer, 2011.
  * Felsenstein [2004] J. Felsenstein.  _Inferring phylogenies_ , volume 2.  Sinauer associates Sunderland, MA, 2004.
  * Foutel-Rodier et al. [2018] F. Foutel-Rodier, A. Lambert, and E. Schertzer.  Exchangeable coalescents, ultrametric spaces, nested interval-partitions: A unifying approach.  _arXiv:1807.05165 [math]_ , July 2018.
  * Grenfell et al. [2004] B. T. Grenfell, O. G. Pybus, J. R. Gog, J. L. Wood, J. M. Daly, J. A. Mumford, and E. C. Holmes.  Unifying the epidemiological and evolutionary dynamics of pathogens.  _Science_ , 303(5656):327–332, 2004.
  * Heled and Drummond [2009] J. Heled and A. J. Drummond.  Bayesian inference of species trees from multilocus data.  _Molecular biology and evolution_ , 27(3):570–580, 2009.
  * Kallenberg [2005] O. Kallenberg.  _Probabilistic Symmetries and Invariance Principles_.  Probability and Its Applications. Springer-Verlag, New York, 2005.  doi:10.1007/0-387-28861-9.
  * Kingman [1982] J. Kingman.  The coalescent.  _Stochastic processes and their applications_ , 13(3):235–248, 1982.
  * Lambert [2008] A. Lambert.  Population dynamics and random genealogies.  _Stochastic Models_ , 24(sup1):45–163, 2008.  doi:10.1080/15326340802437728.
  * Lambert [2017a] A. Lambert.  Random ultrametric trees and applications.  _ESAIM: Procs_ , 60:70–89, 2017a.  doi:10.1051/proc/201760070.
  * Lambert [2017b] A. Lambert.  Probabilistic models for the (sub)tree(s) of life.  _Braz. J. Probab. Stat._ , 31(3):415–475, 08 2017b.  doi:10.1214/16-BJPS320.
  * Lambert and Schertzer [2018] A. Lambert and E. Schertzer.  Coagulation-transport equations and the nested coalescents.  _arXiv:1807.09153_ , July 2018.
  * Maddison [1997] W. P. Maddison.  Gene trees in species trees.  _Systematic biology_ , 46(3):523–536, 1997.
  * Matuszewski et al. [2017] S. Matuszewski, M. E. Hildebrandt, G. Achaz, and J. D. Jensen.  Coalescent processes with skewed offspring distributions and non-equilibrium demography.  _Genetics_ , pages genetics–300499, 2017.
  * Neher and Hallatschek [2013] R. A. Neher and O. Hallatschek.  Genealogies of rapidly adapting populations.  _Proceedings of the National Academy of Sciences_ , 110(2):437–442, 2013.  doi:10.1073/pnas.1213113110.
  * Nei and Kumar [2000] M. Nei and S. Kumar.  _Molecular evolution and phylogenetics_.  Oxford university press, 2000.
  * Page and Charleston [1997] R. D. Page and M. A. Charleston.  From gene to organismal phylogeny: reconciled trees and the gene tree/species tree problem.  _Molecular phylogenetics and evolution_ , 7(2):231–240, 1997.
  * Page and Charleston [1998] R. D. Page and M. A. Charleston.  Trees within trees: phylogeny and historical associations.  _Trends in Ecology & Evolution_, 13(9):356–359, 1998.
  * Pitman [1999] J. Pitman.  Coalescents with multiple collisions.  _The Annals of Probability_ , 27(4):1870–1902, Oct. 1999.  doi:10.1214/aop/1022874819.
  * Rosenberg [2002] N. A. Rosenberg.  The probability of topological concordance of gene trees and species trees.  _Theoretical population biology_ , 61(2):225–247, 2002.
  * Sagitov [1999] S. Sagitov.  The general coalescent with asynchronous mergers of ancestral lines.  _Journal of Applied Probability_ , 36(4):1116–1125, Dec. 1999.  doi:10.1239/jap/1032374759.
  * Schweinsberg [2000a] J. Schweinsberg.  Coalescents with simultaneous multiple collisions.  _Electronic Journal of Probability_ , 5, 2000a.  doi:10.1214/EJP.v5-68.
  * Schweinsberg [2000b] J. Schweinsberg.  A necessary and sufficient condition for the $\Lambda$-coalescent to come down from infinity.  _Electronic Communications in Probability_ , 5:1–11, 2000b.  doi:10.1214/ECP.v5-1013.
  * Schweinsberg [2003] J. Schweinsberg.  Coalescent processes obtained from supercritical Galton-Watson processes.  _Stochastic Processes and their Applications_ , 106(1):107–139, July 2003.  doi:10.1016/S0304-4149(03)00028-0.
  * Schweinsberg [2017] J. Schweinsberg.  Rigorous results for a population model with selection II: genealogy of the population.  _Electronic Journal of Probability_ , 22, 2017.
  * Semple and Steel [2003] C. Semple and M. A. Steel.  _Phylogenetics_ , volume 24.  Oxford University Press, 2003.
  * Szöllősi et al. [2014] G. J. Szöllősi, E. Tannier, V. Daubin, and B. Boussau.  The inference of gene trees with species trees.  _Systematic biology_ , 64(1):e42–e62, 2014.
  * Tellier and Lemaire [2014] A. Tellier and C. Lemaire.  Coalescence 2.0: A multiple branching of recent theoretical developments and their applications.  _Molecular ecology_ , 23(11):2637–2652, 2014\.
  * Volz et al. [2013] E. M. Volz, K. Koelle, and T. Bedford.  Viral phylodynamics.  _PLoS Computational Biology_ , 9(3):e1002947, 2013\.