Modern Stochastics: Theory and Applications

Let ${X_{1}},{X_{2}},\dots $ be independent copies of a random variable X taking values in $(0,\infty )$. For $N\in \mathbb{N}:=\{1,2,\dots \}$ define ${S_{N}}:={X_{1}}+\cdots +{X_{N}}$ and ${W_{i}}:={X_{i}}/{S_{N}}$, $i\in \{1,\dots ,N\}$. The weights ${W_{1}},\dots ,{W_{N}}$ are exchangeable random variables with ${W_{1}}+\cdots +{W_{N}}=1$. In particular, $\mathbb{E}({W_{i}})=1/N$, $i\in \{1,\dots ,N\}$. Consider the Cannings model [6, 7] with population size N and nonoverlapping generations such that, conditional on ${W_{1}},\dots ,{W_{N}}$, the offspring sizes ${\nu _{1}},\dots ,{\nu _{N}}$ have a multinomial distribution with parameters N and ${W_{1}},\dots ,{W_{N}}$. Thus, the offspring distribution is ${i_{1}},\dots ,{i_{N}}\in {\mathbb{N}_{0}}:=\{0,1,2,\dots \}$ with ${i_{1}}+\cdots +{i_{N}}=N$. For degenerate X, i.e. $\mathbb{P}(X=c)=1$ for some real constant $c>0$, this model reduces to the classical Wright–Fisher model with deterministic weights ${W_{i}}=1/N$, $i\in \{1,\dots ,N\}$. It is straightforward to check that the offspring sizes have joint descending factorial moments where ${(x)_{0}}:=1$ and ${(x)_{k}}:=x(x-1)\cdots (x-k+1)$ for $x\in \mathbb{R}$ and $k\in \mathbb{N}$. In [15] this model is studied for the case when X is Pareto distributed. If X is gamma distributed with density $x\mapsto {x^{r-1}}{e^{-x}}/\Gamma (r)$, $x>0$, for some $r>0$, then $({W_{1}},\dots ,{W_{N}})$ is symmetric Dirichlet distributed with parameter r, leading to the Cannings model with the offspring distribution ${i_{1}},\dots ,{i_{N}}\in {\mathbb{N}_{0}}$ with ${i_{1}}+\cdots +{i_{N}}=N$, where ${[x]_{0}}:=1$ and ${[x]_{i}}:=x(x+1)\cdots (x+i-1)$ for $x\in \mathbb{R}$ and $i\in \mathbb{N}$. This Dirichlet multinomial model has been studied extensively in the literature (see, for example, Griffiths and Spanò [13]). In a series of papers [16, 17, 19] a subclass of Cannings models, called conditional branching process models in the spirit of Karlin and McGregor [23, 24], has been investigated, whose offspring distributions are (by definition) obtained by assuming that $\mathbb{P}({X_{1}}+\cdots +{X_{N}}=N)>0$ and conditioning on the event that ${X_{1}}+\cdots +{X_{N}}=N$. This construction based on conditioning is rather different from the construction based on sampling from a random partition of the unit interval we are dealing with in this article. Note however that several concrete examples (such as the classical Wright–Fisher model and the above mentioned Dirichlet multinomial model) can be constructed in both ways, either by sampling or by conditioning. For example, the Dirichlet multinomial model is obtained by taking N independent and identically distributed negative binomial random variables ${X_{1}},\dots ,{X_{N}}$ with parameter $r>0$ and $p\in (0,1)$, so with distribution $\mathbb{P}({X_{1}}=k)=\left(\genfrac{}{}{0.0pt}{}{r+k-1}{k}\right){p^{r}}{(1-p)^{k}}$, $k\in {\mathbb{N}_{0}}$, and conditioning on the event that ${X_{1}}+\cdots +{X_{N}}=N$.

The closely related model studied by Schweinsberg [37] differs from ours, since sampling is performed without replacement from a discrete super-critical Galton–Watson branching process, as explained in [37, Section 1.3]. In that model, X is integer valued and satisfies $\mathbb{E}(X)>1$. In our model, X does not need to be integer valued and its mean is allowed to be less than 1. Moreover, the sampling in our multinomial model is with replacement, whereas in Schweinsberg’s model it is without replacement.

The same multinomial scheme with an additional dormancy mechanism is considered in the recent work by Cordero et al. [8]. A class of Dirichlet models in the domain of attraction of the Kingman coalescent is also studied in two recent works by Boenkost et al. [4, 5] with an emphasis on Haldane’s formula [14]. We refer the reader to Athreya [1] for some more information on Haldane’s formula.

Fix $n\in \{1,\dots ,N\}$ and sample n individuals from the current generation. For $r\in {\mathbb{N}_{0}}$ define a random partition ${\Pi _{r}^{(N,n)}}$ of $\{1,\dots ,n\}$ such that $i,j\in \{1,\dots ,n\}$ belong to the same block of ${\Pi _{r}^{(N,n)}}$ if and only if the individual i and j share a common parent r generations backward in time. The process ${\Pi ^{(N,n)}}:={({\Pi _{r}^{(N,n)}})_{r\in {\mathbb{N}_{0}}}}$, called the discrete-time n-coalescent, takes values in the space ${\mathcal{P}_{n}}$ of partitions of $\{1,\dots ,n\}$. As in [15] we are interested in the limiting behavior of the discrete-time n-coalescent as the total population size N tends to infinity. It is easily seen (and well known) that the discrete-time n-coalescent is a time-homogeneous Markovian process. The transition probabilities ${p_{\pi {\pi ^{\prime }}}}:=\mathbb{P}({\Pi _{r+1}^{(N,n)}}={\pi ^{\prime }}\hspace{0.1667em}|\hspace{0.1667em}{\Pi _{r}^{(N,n)}}=\pi )$ are given by if each block of ${\pi ^{\prime }}$ is a union of some blocks of π, where $j:=|{\pi ^{\prime }}|$ denotes the number of blocks of ${\pi ^{\prime }}$ and ${k_{1}},\dots ,{k_{j}}$ are the group sizes of merging blocks of π. Note that ${\Phi _{j}^{(N)}}({k_{1}},\dots ,{k_{j}})$ is defined for all $N,j,{k_{1}},\dots ,{k_{j}}\in \mathbb{N}$. Since the random variables ${W_{1}},\dots ,{W_{N}}$ are exchangeable and satisfy ${W_{1}}+\cdots +{W_{N}}=1$, it follows for all $N,j,{k_{1}},\dots ,{k_{j}}\in \mathbb{N}$ with $j\le N$ that Multiplication by ${(N)_{j}}$ ($=0$ for $j>N$) shows that the consistency relation holds for all $N,j,{k_{1}},\dots ,{k_{j}}\in \mathbb{N}$. Moreover, for all $j,l\in \mathbb{N}$ with $j\ge l$ and all ${k_{1}},\dots ,{k_{j}},{m_{1}},\dots ,{m_{l}}\in \mathbb{N}$ with ${k_{1}}\ge {m_{1}},\dots ,{k_{l}}\ge {m_{l}}$, the monotonicity relation holds. Note that (5) follows from (4) by induction on the difference $d:=j-l\in {\mathbb{N}_{0}}$. We refer the reader to [30, Definition 2.2] and the remark thereafter for similar statements and proofs for the full class of Cannings models. Choosing $j=1$ and ${k_{1}}=2$ in (3) shows that two individuals share a common ancestor one generation backward in time with probability ${c_{N}}:={\Phi _{1}^{(N)}}(2)=N\mathbb{E}({W_{1}^{2}})$, the so-called coalescence probability. We also introduce the effective population size ${N_{e}}:=1/{c_{N}}$. Note that ${c_{N}}=N\mathbb{E}({W_{1}^{2}})\ge N{(\mathbb{E}({W_{1}}))^{2}}=1/N$ or, equivalently, ${N_{e}}\le N$. All Cannings models having an effective population size strictly larger than N (such as the Moran model having effective population size ${N_{e}}=N(N-1)/2>N$ for $N\ge 4$ and most of the extended Moran models studied by Eldon and Wakeley [11] and Huillet and Möhle [18]) therefore do not belong to the class of models we are dealing with in this article.

General results for Cannings models concerning the convergence of their genealogical tree to an exchangeable coalescent process as the total population size tends to infinity are provided in [32]. For information on the theory of exchangeable coalescent processes we refer the reader to Pitman [33], Sagitov [34] and Schweinsberg [35, 36]. Coalescents with multiple collisions (Λ-coalescents) are Markovian stochastic processes taking values in the set of partitions of $\mathbb{N}$. They are characterized by a finite measure Λ on the unit interval. Important examples are Dirac-coalescents, where $\Lambda ={\delta _{a}}$ is the Dirac measure at a given point $a\in [0,1]$, including the prominent Kingman coalescent (Kingman [26, 25, 27]), where $\Lambda ={\delta _{0}}$ is the Dirac measure at 0, and the star-shaped coalescent, where $\Lambda ={\delta _{1}}$. Other important examples are beta coalescents, where $\Lambda =\beta (a,b)$ is the beta distribution with parameters $a,b>0$, including the Bolthausen–Sznitman coalescent, where Λ is the uniform distribution on the unit interval ($a=b=1$).

The full class of exchangeable coalescent processes (Ξ-coalescents) allowing for simultaneous multiple collisions of ancestral lineages is characterized by a finite measure Ξ on the infinite simplex $\Delta :=\{x=({x_{1}},{x_{2}},\dots ):{x_{1}}\ge {x_{2}}\ge \cdots \ge 0,{\textstyle\sum _{i=1}^{\infty }}{x_{i}}\le 1\}$. An example is the two-parameter Poisson–Dirichlet coalescent with parameters $\alpha >0$ and $\theta >-\alpha $, where the characterizing measure $\nu (\mathrm{d}x):=\Xi (\mathrm{d}x)/{\textstyle\sum _{i=1}^{\infty }}{x_{i}^{2}}$ on Δ is (by definition) the Poisson–Dirichlet distribution $\nu =\mathrm{PD}(\alpha ,\theta )$ with parameters $\alpha >0$ and $\theta >-\alpha $. For more information on the Poisson–Dirichlet coalescent we refer the reader to Section 6 of [31]. In most studies, continuous-time coalescent processes ${({\Pi _{t}})_{t\in T}}$ with index set $T=[0,\infty )$ are considered. Note however that all Ξ-coalescents can as well be introduced with discrete time $T={\mathbb{N}_{0}}$. In this case one speaks about a discrete-time Ξ-coalescent ${({\Pi _{r}})_{r\in {\mathbb{N}_{0}}}}$. The following terminology is taken from [16, Definition 2.1].

Conditions on the tails of the distribution of X are provided which ensure that the population model with the offspring distribution (1) is in the domain of attraction of some exchangeable coalescent process. The tail condition is of the standard form $\mathbb{P}(X>x)\sim {x^{-\alpha }}\ell (x)$ as $x\to \infty $, where $\alpha \ge 0$ and ℓ is a function slowly varying at ∞. The results are collected in Theorem 1 in Section 2. It turns out that the three parameter values $\alpha \in \{0,1,2\}$ are boundary cases. Consequently, six different regimes ($\alpha >2$, $\alpha =2$, $\alpha \in (1,2)$, $\alpha =1$, $\alpha \in (0,1)$ and $\alpha =0$) are considered leading to different limiting behaviors of the ancestral process. Theorem 1 also provides the asymptotics of the coalescence probability ${c_{N}}$ as $N\to \infty $ for all six cases. In Section 3 some illustrating examples are provided including the case studied in [15] when X is Pareto distributed. The proofs are provided in the main Section 4. They are based on general convergence-to-the-coalescent theorems for Cannings models provided in [32] and combine (Abelian and Tauberian) arguments from the theory of regularly varying functions in the spirit of Karamata [20–22] with techniques used by Huillet [15] for the Pareto case and by Schweinsberg [37] for the related model where the sampling is performed without replacement.

For most of the results it is assumed that there exist a constant $\alpha \ge 0$ and a function $\ell :(0,\infty )\to (0,\infty )$ slowly varying at ∞ such that Our main result (Theorem 1) clarifies the limiting behavior of the ancestral structure of the Cannings model with the offspring distribution (1) as the total population size N tends to infinity under the assumption (6). It turns out that the parameter values $\alpha \in \{0,1,2\}$ are boundary cases. It is hence natural to distinguish six regimes corresponding to the parameter ranges $\alpha >2$, $\alpha =2$, $\alpha \in (1,2)$, $\alpha =1$, $\alpha \in (0,1)$ and $\alpha =0$. In order to state the result it is convenient to introduce the function ${\ell ^{\ast }}:(1,\infty )\to (0,\infty )$ via Note that ${\ell ^{\ast }}$ is nondecreasing, slowly varying at ∞ and satisfies $\ell (x)/{\ell ^{\ast }}(x)\to 0$ as $x\to \infty $, see, for example, Bingham and Doney [3, p. 717 and 718] or Eq. (1.5.8) on p. 26 of Bingham, Goldie and Teugels [2] and the remarks thereafter. More precisely, for every $\lambda >0$, as $x\to \infty $, where the convergence holds by the uniform convergence theorem for slowly varying functions. Thus, ${\ell ^{\ast }}$ is a de Haan function (with ℓ-index 1) and hence slowly varying. For general information on de Haan theory we refer the reader to Chapter 3 of [2].

The main (and only) result of this article is the following.

The six cases of Theorem 1 are summarized in Table 1. In the table, $\mu :=\mathbb{E}(X)$, $\rho :=\mathbb{E}({X^{2}})$, ${\ell ^{\ast }}(x):={\textstyle\int _{1}^{x}}\ell (t)/t\hspace{0.1667em}\mathrm{d}t$, $x>1$, and ${({a_{N}})_{N\in \mathbb{N}}}$ is a sequence such that ${\ell ^{\ast }}({a_{N}})\sim {a_{N}}/N$ as $N\to \infty $.

Conjectures and open problems.

Theorem 1 should also hold for Schweinsberg’s model [37], since sampling without replacement (instead of sampling with replacement) should neither influence the asymptotics of the coalescence probability nor the limiting processes arising in Theorem 1. Note that in [37] the subclass of models without replacement is studied where the function ℓ in (6) is constant. We leave the analysis of Schweinsberg’s model under the more general assumption (6) for the interested reader.

In contrast, conditional branching process models [16, 17, 19] seem to be harder to analyse and behave quite differently in general. Even for the subclass of so-called compound Poisson models, only partial results are available. Theorems 2.2 and 2.3 of [19] clarify that many unbiased compound Poisson models are in the domain of attraction of the Kingman coalescent, and [19, Theorem 2.5] (subcritical case) demonstrates that the limiting behavior of compound Poisson models can differ substantially from all scenarios arising in Theorem 1. To the best of the authors knowledge, the limiting behavior of the ancestral structure of unbiased conditional branching process models as $N\to \infty $ under assumptions of the form (6) has not been fully addressed in the literature. We leave this analysis for future research.

The Pareto example is easily generalized in various ways by replacing $\ell \equiv 1$ by some other slowly varying function. For example, choosing for ℓ (a power of) the logarithm leads to the following example.

For illustration three examples with discrete X are provided.

We close this section with a concrete example belonging to the boundary case (vi) ($\alpha =0$).

The following auxiliary result (Lemma 1) is a modified version of Lemma 5 of Schweinsberg [37], adapted to our model. The result may be also viewed as a weak version of Cramér’s large deviation theorem (see, for example, [10, Theorem 2.2.3]). Recall that $\mu :=\mathbb{E}(X)\in (0,\infty ]$.

We now prove part (i) of Theorem 1.

We now prepare the proofs of the parts (ii) and (iii) of Theorem 1. We need the following two auxiliary results.

We now turn to the proofs of the parts (ii) and (iii) of Theorem 1. We first consider part (iii) ($1<\alpha <2$). The boundary case $\alpha =2$ (part (ii) of Theorem 1) will be studied afterwards.

We now turn to the boundary case $\alpha =2$, so we prove part (ii) of Theorem 1.

We now turn to the proofs of the three remaining parts (iv)–(vi) of Theorem 1. We first consider the case $0<\alpha <1$ corresponding to part (v) of Theorem 1. The boundary cases (iv) ($\alpha =1$) and (vi) ($\alpha =0$) will be considered afterwards. Assume that $0<\alpha <1$. Then (6) is exactly Eq. (2.3b) of Bingham and Doney [3] with $n=0$, $\beta =\alpha \in (0,1)$ and $L(x):=\Gamma (1-\alpha )\ell (x)$. By [3, Theorem A], (6) is hence equivalent (see [3, Eq. (2.1)]) to $1-\psi (u)\sim {u^{\alpha }}L(1/u)=\Gamma (1-\alpha ){u^{\alpha }}\ell (1/u)$ as $u\to 0$.

Let us now turn to the (boundary) case $\alpha =1$, so we now assume that $\mathbb{P}(X>x)\sim {x^{-1}}\ell (x)$ as $x\to \infty $ for some function ℓ slowly varying at ∞.

We finally turn to the case $\alpha =0$ corresponding to the last part (vi) of Theorem 1.