Printer Friendly

Convergence to the coalescent and its relation to the time back to the most recent common ancestor.

For the class of haploid exchangeable population models with non-overlapping generations and population size N it is shown that, as N tends to infinity, convergence of the time-scaled ancestral process to Kingman's coalescent and convergence in distribution of the scaled times back to the most recent common ancestor (MRCA) to the corresponding times back to the MRCA of the Kingman coalescent are equivalent.

Extensions of this equivalence are derived for exchangeable population models being in the domain of attraction of a coalescent process with multiple collisions. The proofs are based on the property that the total rates of a coalescent with multiple collisions already determine the distribution of the coalescent.

It is finally shown that similar results cannot be obtained for the full class of exchangeable coalescents allowing for simultaneous multiple collisions of ancestral lineages, essentially because the total rates do not determine the distribution of a general exchangeable coalescent.

Keywords: absorption time, ancestral process, coalescent, exchangeability, most recent common ancestor, simultaneous multiple collisions

1 Introduction

Coalescent theory has been proven to be a powerful tool to analyse the ancestry of a sample of n individuals (genes, particles, DNA-sequences) taken from a large (haploid) population. In the literature a variety of convergence results can be found ([13], [17], [18]) which ensure convergence to a coalescent process, in particular, to the Kingman coalescent ([5] - [8], [9]).

In its kernel coalescent theory boils down to a collection of methods, formulas, and convergence results for the class of exchangeable population models with non-overlapping generations and fixed population size N [member of] N : {1, 2, ...} introduced by Cannings ([1], [2]). These models assume that each individual i [member of] {1, ..., N} in generation r produces a random number [v.sup.(r).sub.i] of offspring and that the offspring of all the N individuals of generation r form the following (r + 1)-th generation. Since the total population size is assumed to be fixed (= N), the relation [v.sup.(r).sub.1] + ... + [v.sup.(r).sub.N] = N has to be satisfied for each generation r. Therefore, for fixed r the offspring variables cannot be stochastically independent, except for the trivial case when [v.sup.(r).sub.i] [equivalent to] 1 for all i [member of] {1, ..., N}. It is therefore assumed that, for each fixed generation r, the offspring sizes [v.sup.(r).sub.1], ..., [v.sup.(r).sub.N] are exchangeable, i.e. the joint distribution of ([v.sup.(r).sub.[pi]1]), ..., [v.sup.(r).sub.[pi]N]) does not depend on the permutation [pi] of the indices 1, ..., N. It is furthermore assumed that the random vectors [v.sup.(r)] : = ([v.sup.(r).sub.1], ..., [v.sup.(r).sub.N]), r [member of] Z, are independent and identically distributed, which makes the model homogeneous over time. We will often write [v.sub.i] instead of [v.sup.(0).sub.i]) for convenience.

In recent years the literature on coalescent processes increased rapidly. More and more problems around these processes have been addressed and got solved. However, the number of open problems increased as well. In this paper it is discussed how convergence results for ancestral processes and convergence results for times back to the most recent common ancestor (MRCA) are related.

The paper is structured as follows. In Sections 2 and 3 we briefly recall the well-known theory on time-discrete ancestral processes and their convergence to time-continuous limiting coalescent processes as the total population size N tends to infinity. In Section 4 we show that convergence of the time-scaled ancestral process always implies the convergence of the corresponding times back to the MRCA (Proposition 4.1). More delicate is the converse question, i.e. whether the convergence of the times back to the MRCA already ensures the convergence of the time-scaled ancestral processes to some limiting ancestral process. The answer to this question depends on the type of the limiting coalescent process. In Section 5 we give a positive answer to this question for the situation when the population model is in the domain of attraction of the Kingman coalescent (Proposition 5.1). In Section 6 (see Theorem 6.4) the result is extended to the class of coalescent processes allowing for multiple collisions. For more information on such processes we refer to Pitman [15] and Sagitov [16]. In Section 7 we finally verify that results of this type cannot be extended to the full class of exchangeable coalescent processes ([13], [17], [18]) allowing for simultaneous multiple mergers of ancestral lineages.

2 Time-discrete coalescent processes

Consider an exchangeable population model with total population size N as introduced in Section 1. Fix n [member of] {1, ..., N} and sample n individuals from the current generation. For r [member of] [N.sub.0] : {0,1, 2, ...} let [R.sub.r] := [R.sup.(n).sub.r] (N) denote the random equivalence relation on {1, ..., n} containing (i, j) if and only if the individuals i and j have a common ancestor r generations backward in time. It is well known (Kingman [6]) that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a time-homogeneous Markov chain with state space [[epsilon].sub.n], the set of all equivalence relations on {1, ..., n}, and initial state [R.sub.0] [equivalent to] [[DELTA].sub.n] := {(i, i) |1 [less than or equal to] i [less than or equal to] n}, the diagonal relation. The transition probabilities [p.sub.[xi][eta]] = [p.sub.[xi][eta]] (N) := P([R.sub.r], = |[R.sub.r-1] = [xi]),[xi],[eta] [member of] [[epsilon].sub.n], are equal to zero for [xi] [subset or not equal to] [eta] and equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

for [xi] [subset or equal to] [eta], where [(x).sub.0] := 1 and [(x).sub.k] := x(x - 1) ... (x - k + 1) for x [member of] R and k [member of] N. Here a = [absolute value of [eta]] denotes the number of equivalence classes (blocks) of [eta] b = [absolute value of xi] the number of classes of [xi], and [b.sub.1], ..., [b.sub.a] are the group sizes of merging classes of [xi] ([??] [b.sub.1] + ... + [b.sub.a] = b). The process R is called a discrete ancestral process or a discrete n-coalescent.

The functions [[PHI].sub.j] := [[PHI].sup.(N).sub.j], j [member of] {1, ..., N}, are consistent (see, for example, Eq. (3) of [10]) in the sense that [[PHI].sub.a+1]([b.sub.1], ..., [b.sub.a], 1) = [[PHI].sub.a] ([b.sub.1], ..., [b.sub.a]) - [[a.summation over (i=1)][[PHI].sub.a] ([b.sub.1], ..., [b.sub.i-1], [b.sub.i] + 1, [b.sub.i+1], ..., [b.sub.a]) (2)

for a, [b.sub.1], ..., [b.sub.a] [member of] N with b := [b.sub.1] + ... + [b.sub.a] < N. In the appendix (Lemma 8.1) it is shown that the consistency (2) implies that the functions [[PHI].sub.j], j [member of] {1, ..., N}, are monotone in the sense that

[[PHI].sub.j] ([k.sub.1], ..., [k.sub.j]) [less than or equal to] [[PHI].sub.l] ([m.sub.1], ..., [m.sub.l]) (3)

for 1 [less than or equal to] l [less than or equal to] j [less than or equal to] N and [k.sub.1], ..., [k.sub.1], [m.sub.1], ..., [m.sub.1] [member of] N with [k.sub.1] [greater than or equal to] [m.sub.1], ..., [k.sub.l] [greater than or equal to] [m.sub.l] and [k.sub.1] + ... + [k.sub.j] [less than or equal to] N.

Instead of considering the random relation [R.sub.r] it is often convenient to record in a sample of size n [member of] {1, ..., N} only the number [D.sub.r] = [D.sup.(n).sub.r] : = [absolute value of [R.sup.(n).sub.r] (N)] of ancestors r generations backward in time. It is well known and follows easily from (1) that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a Markov chain with state space {1, ..., n}, initial state [D.sub.0] [equivalent to] n, and transition probabilities [p.sub.ij] = [p.sub.ij] (N) := P ([D.sub.r] = j | [D.sub.r -1] = i) given by (see Kingman [5] - [7])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

Note that [p.sub.ij] = 0 for i < j and, therefore, the transition matrix [([p.sub.ij]).sub.i,j [member of]]{1, ..., n}] has eigenvalues

[[lambda].sub.i] = [[lambda].sub.i] (N) := [p.sub.ii] = [[PHI].sub.i] (1, ...,1) = E([v.sub.1] ... [v.sub.i]), i [member of] {1, ..., n}. (5)

Obviously, the consistency relation (2) puts certain constraints on the transition probabilities [p.sub.ij]. It does not seem to be straightforward to describe these constraints directly in terms of the [p.sub.ij]. The process D is called the block-counting process or class-counting process.

3 Convergence to time-continuous coalescent processes

The consistency (2) and the monotonicity (3) of the functions [[PHI].sub.j], j [member of] {1, ..., N}, are two important properties needed in order to prove convergence-to-the-coalescent results. All these convergence-to-the-coalescent results have of course been stimulated by the seminal work of Kingman [5] and finally led to a full classification of all possible limiting processes for the case of exchangeable reproduction. For detailed information on convergence-to-the-coalescent results we refer to [13], [17] and [18]. In order to state such results we need to introduce for N [member of] N \ {1} the so-called coalescence probability

[C.sub.N] = [P.sub.21] (N) = [[PHI].sup.(N).sub.1] (2) = E([v.sub.1]([v.sub.1] - 1))/N-1 = Var([v.sub.1])/N-1,

i.e., the probability that two individuals, randomly chosen from some generation, are descended from the same parent. Note that [c.sub.N] = 0 if and only if P([v.sub.1] = 1) = 1. The coalescence probability [c.sub.N] (see, for example, [9], [13]) is a crucial quantity in coalescent theory. Roughly speaking, the time has to be measured in units of [t/[C.sub.N]] generations in order to achieve convergence to the coalescent as the total population size N tends to infinity. The following convergence result is essentially Theorem 2.1 of [13], however we state this theorem in the notation used in [12].

Theorem 3.1 Assume that [C.sub.N] > 0 for all sufficiently large N, that [lim.sub.N[right arrow][infinity]] [C.sub.N] = 0, and that the limits

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

exist for all j [member of] N and [k.sub.1] [greater than or equal to] ... [greater than or equal to] [k.sub.j] > 2. Then, the limits (6) exist for the wider range of parameters j, [k.sub.1], ..., [k.sub.j] [member of] N satisfying [k.sub.1] + ... + [k.sub.j] > j and also the limits

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

exist for all j [member of] N. Moreover, for each sample size n [member of] N, the time-scaled process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges in the Skorohod topology as N tends to infinity to a time-continuous Markov chain [([R.sup.(n).sub.t]).sub.t[greater than or equal to]0], with transition matrices [e.sup.tQ], t [greater than or equal to] 0, and generator [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with entries

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where a := [absolute value of [eta]] and [b.sub.1], ..., [b.sub.a] [member of] N are the group sizes of merging classes of [xi].

Note that, in general, the limiting process [([R.sup.(n).sub.t]).sub.t[greater than or equal to] 0] allows for simultaneous multiple collisions of ancestral lineages. It is therefore called an n-coalescent with simultaneous multiple collisions.

Theorem 3.1 remains valid, if the population size N is replaced by [N.sub.l], where [([N.sub.l]).sub.l[member of]N] is a subsequence of population sizes satisfying [lim.sub.l[right arrow][infinity]], [N.sub.l] = [infinity]. In that case of course all limits 'N [right arrow] [infinity]' appearing in Theorem 3.1 have to be interpreted as 'l [right arrow] [infinity]'.

Convergence to Kingman's rt-coalescent [([R.sup.(n).sub.t]).sub.t[greater than or equal to]0], which allows only for binary mergers of ancestral lineages, occurs if all the limits in (6) are zero except for [[phi].sub.1](2). The following convergence theorem is one of the fundamental results of coalescent theory.

Theorem 3.2 Assume that [C.sub.N] > 0 for all sufficiently large N. Then, the following conditions are equivalent.

(i) [[phi].sub.1] (3) := [lim.sub.N [right arrow][infinity]](3)/[C.sub.N] = 0, i.e., triple mergers of ancestral lineages are asymptotically negligible in comparison with binary mergers.

(ii) For each sample size n [member of] N, the time-scaled ancestral process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges in the Skorohod topology to Kingman's n-coalescent [([R.sup.(n).sub.t]).sub.t[greater than or equal to]0] as N [right arrow] [infinity].

Remark: Note (see Theorem 6.1 of [10]) that Theorem 3.2 remains valid if in (ii) the symbol R is replaced by D and [R.sup.(n).sub.t] by [D.sup.(n).sub.t]:= [absolute value of [R.sup.(n).sub.t]]. There is also an equivalent formulation of (i) in terms of the eigenvalues [[lambda].sub.2] and [[lambda].sub.3] introduced in (5), namely

(iii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The equivalence of (i) and (iii) is seen as follows. The consistency (2) implies that [[lambda].sub.2] = [[PHI].sub.2](1,1) = [[PHI].sub.1] (1) - [[PHI].sub.1] (2) = 1 - [C.sub.N] and that [[lambda].sub.3] = [[PHI].sub.3] (1, 1,1) = [[PHI].sub.2] (1,1) - 2[[PHI].sub.2] (2,1) = 1 - [C.sub.N] - 2[[PHI].sub.2](2,1), i.e. [[PHI].sub.2](2,1) = (1 - [C.sub.N] - [[lambda].sub.3])/2. Therefore, again using (2),

[[PHI].sub.1] (3) - [[PHI].sub.1] (2) - [[PHI].sub.2] (2, 1) - [C.sub.N] - 1 - [C.sub.N] - [[lambda].sub.3]/2 = 3/2 [C.sub.N] - 1 - [[lambda].sub.3]/2

or, equivalently, 2[[PHI].sub.1](3)/[C.sub.N] = 3 - (1 - [[lambda].sub.3])/[C.sub.N], from which the equivalence of (i) and (iii) follows immediately.

At the end of Section 5 further equivalent conditions are formulated involving times back to the most recent common ancestor.

4 Time back to the most recent common ancestor

For N [member of] N and n [member of] {1, ..., N} let [T.sub.n N] := inf{r [member of] [N.sub.0] : [D.sup.(n).sub.r] (N) = 1} denote the number of generations back to the most recent common ancestor (MRCA) of a sample of size n.

Proposition 4.1 Assume that the conditions of Theorem 3.1 or Theorem 3.2 are satisfied. Then, for each sample size n [member of] N, as N [right arrow][infinity], the scaled time [C.sub.N] [T.sub.n,N] back to the MRCA converges in distribution to

[T.sub.n] := inf{t > 0 : [D.sup.(n).sub.t] = 1}

where [D.sup.(n).sub.t] := [absolute value of [R.sup.(n).sub.t]] 1, t [greater than or equal to] 0, and [([R.sup.(n).sub.t]).sub.t[greater than or equal to]0] is the limiting n-coalescent with simultaneous multiple collisions appearing in Theorem 3.1 or Kingman's n-coalescent appearing in Theorem 3.2.

Proof: Fix n [member of] N and t [greater than or equal to] 0. By Theorem 3.1 or Theorem 3.2, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as N [right arrow] [infinity]. As the function [[epsilon].sub.n] [contains as member] [xi][??][xi] [member of] {l, ..., n} is continuous, it follows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as N [right arrow] [infinity]. Thus, for t [greater than or equal to] 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which implies that [C.sub.N][T.sub.n,N] [??] [T.sub.n] as N [right arrow] [infinity].

Remark: If the eigenvalues [[lambda].sub.i] := [[lambda].sub.i] (N), i [member of] {1, ..., N}, are distinct, then there exists the following alternative proof of Proposition 4.1 based on an explicit formula for the distribution function of [T.sub.n,N]. Fix n [member of] N and t [greater than or equal to] 0. By Lemma 3.1. of [11], for N [greater than or equal to] n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the second sum extends over all integers [i.sub.0], ..., [i.sub.k] satisfying 1 = [i.sub.0] < [i.sub.1] < ... < [i.sub.k-1] < [i.sub.k] = n. Under the conditions of Theorem 3.1 or Theorem 3.2, the asymptotic formula

[p.sub.ij] (N) = [[delta].sub.ij] + [C.sub.N] [g.sub.ij] + o ([C.sub.N]), i,j [member of] {1, ..., n} (8)

holds, where [[delta].sub.ij] denotes the Kronecker symbol and G = [([g.sub.ij]).sub.i,j[member of]{1, ..., n}] is the generator of the process [([D.sup.(n).sub.t]).sub.t[greater than or equal to]0] with entries

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

i,j [member of] {1,..., n}. Now, (8) ensures that, for i, j [member of] {1, ..., n} with i [not equal to] j,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [P.sub.ij]/1 - [[lambda].sub.i] [right arrow][g.sub.ij]/[g.sub.i] =: [r.sub.ij]

with [g.sub.i] := -[g.sub.ii], i [member of] N. From (7) it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The alternative proof of Proposition 4.1 is complete.

Remark: Note that the alternative proof above is valid as long as the eigenvalues [[lambda].sub.1], (N), ..., [[lambda].sub.N] (N) are distinct for all sufficiently large N.

The sequence [([T.sub.n]).sub.n[member of]N] satisfies (see, for example, Eq. (2) of [4]) the distributional recursion [T.sub.1] = 0 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [[tau].sub.n] is exponentially distributed with parameter [g.sub.n] and [I.sub.n] is a random variable independent of [T.sub.2], ..., [T.sub.n-1], [[tau].sub.n] with distribution P([I.sub.n] = k) = [r.sub.nk] = [g.sub.nk]/[g.sub.n], k [member of] {1, ..., n - 1}.

Under the conditions of Theorem 3.1 or Theorem 3.2 we have, for each n [member of] N, pointwise convergence of the corresponding transforms [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Under the conditions of Theorem 3.2 (Kingman case), [T.sub.n] [??] [[tau].sub.2] + ... + [[tau].sub.n], n [member of] N, where [[tau].sub.2], [[tau].sub.3], ... are independent random variables and [[tau]].sub.i] is exponentially distributed with parameter [g.sub.i] = i(i - 1)/2, i [member of] {2, 3 ...}. In particular,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The rest of this section deals with a result similar to that provided in Proposition 4.1, but for the situation when the sample size n = [n.sub.N] depends on the total population size N.

Theorem 4.2 Suppose that the conditions of Theorem 3.1 or Theorem 3.2 are satisfied. Then, for any sequence ([n.sub.N])[N.sub.[member of]N] satisfying [n.sub.N] [member of] {1, ..., N and [lim.sub.N[right arrow][infinity]] [n.sub.N] = [infinity], the process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges in the Skorohod topology to [([D.sub.t]).sub.t[greater than or equal to]0] as N [right arrow] [infinity], where [([D.sub.t]).sub.t[greater than or equal to]0] is a non-increasing Markov process with state space N and generator G = [([g.sub.ij]).sub.i,j[member of]N] with entries (9), i, j [member of] N.

Proof: The proof is identical to that of Theorem 3 in [3]. Note that the formula for the rates [g.sub.ij] can be easily read off from (4) or (9).

Corollary 4.3 Suppose that the conditions of Theorem 3.1 or 3.2 are satisfied. Then, for any sequence ([n.sub.N])N[member of]N satisfying [n.sub.N] [member of] {1, ..., N} and [lim.sub.N[right arrow][infinity]], [n.sub.N] - [right arrow], the scaled time [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] back to the MRCA converges in distribution to T := inf{t > 0 : [D.sub.t] = 1}.

Proof: By Theorem 4.2, for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] The proof t).

of Proposition 4.1 shows that, whenever the time-scaled ancestral process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges to an exchangeable n-coalescent, then the convergence [C.sub.N][T.sub.n],[??] [T.sub.n] holds for the corresponding times [T.sub.n,N] and [T.sub.n] back to the MRCA. In the following we are interested in the converse of Proposition 4.1. Is the convergence [C.sub.N] [T.sub.n,N] [??] [T.sub.n], n [member of] N, where ([T.sub.n])n[member of]N is some sequence of random variables, sufficient to ensure convergence in the Skorohod topology of the time-scaled ancestral process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to some n-coalescent process ([R.sup.(n).sub.t])t[greater than or equal to]0, n [member of] N? The answer to this questions is less obvious and more subfile as it looks at a first glance. We therefore approach this question in three steps. First we consider the Kingman case (Section 5). Afterwards, the results are extended to coalescents with multiple collisions (Section 6). Finally we address this problem for the full class of exchangeable coalescents allowing for simultaneous multiple collisions of ancestral lineages (Section 7).

5 The Kingman case

The following proposition is a kind of converse of Proposition 4.1 for the Kingman case.

Proposition 5.1 Assume that, for n [member of] {2, 3}, [C.sub.N][T.sub.n,N] [??] [T.sub.n]:= [[summation].sup.n.sub.i=2] [[tau].sub.i] as N [right arrow] [infinity], where [[tau].sub.2], [[tau].sub.3] are independent and [[tau].sub.i] is exponentially distributed with parameter [g.sub.i] := i(i - 1)/2, i [member of] {2, 3}. Then, the condition (i) (and hence (ii)) of Theorem 3.2 holds.

Proof: Define [[mu].sub.i] := 1 - [[lambda].sub.i] for convenience. Obviously, [C.sub.N] - [p.sub.21] = 1 - [P.sub.22] = 1 - [[lambda].sub.2] = [[mu].sub.2]. For n = 2, Eq. (7) reduces to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now let N [right arrow] [infinity] to conclude that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Taking the logarithm yields [lim.sub.N[right arrow][infinity]] [t/[C.sub.N]] log (1 - [C.sub.N]) = -t. Thus, [C.sub.N] [right arrow] 0 as N [right arrow] 0. Next, consider (7) for n = 3, i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as [p.sub.21] = [[mu].sub.2] and [P.sub.32] = [[mu].sub.3] - [P.sub.31]. Define x := [x.sub.N] := [[mu].sub.2]/ [[mu].sub.3] and y := [y.sub.N] := [P.sub.31]/[P.sub.21] = [P.sub.31]/[[mu].sub.2]. From the remark after Theorem 3.2 it is known that x and y are related via

y = 3/2 - 1/2x.

We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

as xy = (3x - 1) /2 and hence (1 - xy)/(1 - x) = 3/2. By assumption, as N [right arrow] [infinity], (11) converges to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the convergence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

must hold. Thus, [t/[C.sub.N]] log(1 - [[mu].sub.3])[right arrow] -3t, and, hence, log(1 - [[mu].sub.3])/[[mu].sub.2] [right arrow] -3, which is only possible, if [[mu].sub.3]/[[mu].sub.2] [right arrow] 3. Thus, [x.sub.N] [right arrow] 1/3, or, equivalently, [y.sub.N] [right arrow] 0, and Proposition 5.1 is established.

Remark: For n [member of] N let [T.sub.n] : [[summation].sup.n.sub.i=2] [[tau].sub.i], where [[tau].sub.2], [[tau].sub.3], ... are independent random variables and [[tau].sub.i] is exponentially distributed with parameter [g.sub.i] = i(i - 1)/2, i [member of] N \ {1}. Proposition 5.1 together with Proposition 4.1 show that condition (i) of Theorem 3.2 is equivalent to

(iv) [c.sub.N] [T.sub.n,N] [??] [T.sub.n] as N [right arrow] [infinity] for n [member of] {2,3}.

Since condition (i) of Theorem 3.2 implies (ii) of the same theorem, an application of Theorem 4.1 shows that (iv) is also equivalent to

(v) [c.sub.N] [T.sub.n,N] [??] [T.sub.n] as N [right arrow] [infinity] for all n [member of] N.

6 Multiple collisions

We now generalize Proposition 5.1 to coalescents with multiple collisions. Roughly speaking, we will verify that convergence of all the times back to the most recent common ancestor already implies convergence of the time-scaled ancestral processes.

Exchangeable coalescents are time-continuous [epsilon]-valued Markov processes, where [epsilon] denotes the set of all equivalence relations on N. During each transition equivalence classes are allowed to merge together. Pitman [15] and Sagitov [16] independently introduced the class of coalescents allowing for multiple collisions, also called [LAMBDA]-coalescents as they can be characterized by a finite measure [LAMBDA] on the unit interval [0,1]. The full class of exchangeable coalescent processes allowing for simultaneous multiple mergers of ancestral lineages has been studied by Mohle and Sagitov [13] and Schweinsberg [18]. For N [member of] N let [[??].sub.n] : [epsilon] [right arrow] [[epsilon].sub.n] denote the natural restriction to the set [[epsilon].sub.n] of all equivalence relations on {1, ..., n}.

Lemma 6.1 Assume that [lim.sub.N[right arrow] [c.sub.N]] = 0. Then there exists a subsequence [([N.sub.l]).sub.l[member of]N] of positive integers with [lim.sub.l[right arrow][infinity]] [N.sub.l] = [infinity] and an exchangeable coalescent R = [([R.sub.t]).sub.t[greater than or equal to]0] such that, for each sample size n [member of] N, the time-scaled ancestral process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges in the Skorohod topology to ([[??].sub.n] [[R.sub.t]).sub.t[greater than or equal to]0] as l [right arrow] [infinity].

Proof: Let [k.sub.1], ..., [k.sub.j] [member of] N with [k.sub.1] + ... + [k.sub.j] > j. The monotonicity (3) ensures that [[PHI].sup.(N).sub.j] ([k.sub.1], ..., [k.sub.j]) [less than or equal to] [[PHI].sub.1] (2) = [C.sub.N]. Thus, the sequence [([[PHI].sup.(N).sub.j] ([k.sub.1], ..., [k.sub.j])/[C.sub.N]).sub.N[member of]N] is bounded. Because these are countable many such sequences (for each j there are '[absolute value of [N.sup.j]] - 1' such sequences), there exists a (diagonal) subsequence [([N.sub.l]).sub.l[member of]N] with [lim.sub.l[right arrow][infinity]] [N.sub.l] = [infinity] such that the limit [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] exists for all j, [k.sub.1], ..., [k.sub.j] [member of] N with [k.sub.1] + ... + [k.sub.j] > j. Now apply Theorem 3.1 (with N replaced by [N.sub.l]) to conclude that, for each sample size n, the time-scaled ancestral process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges in the Skorohod topology to [R.sup.(n)] as l [right arrow] [infinity], where [R.sup.(n)] = [([R.sup.(n).sub.t]).sub.t[greater than or equal to]0] is some n-coalescent allowing for simultaneous multiple collisions. The sequence [([R.sup.(n)]).sub.n[member of]N] of n-coalescents is consistent in the sense that for sample sizes m, n [member of] N with m [less than or equal to] n the process ([[??].sub.m], [[R.sup.(n).sub.t]).sub.t[greater than or equal to]0] is distributional equal to [R.sup.(m)] = [([R.sup.(m).sub.t]).sub.t[greater than or equal to]0]. Therefore, by an application of Kolmogoroff's extension theorem, there exists an exchangeable coalescent process R = [([R.sub.t]).sub.t[greater than or equal to]0] such that the distribution of ([[[??].sub.n][R.sub.t]).sub.t[greater than or equal to]0] coincides with that of [R.sup.(n)] for all n [member of] N.

Lemma 6.2 Assume that [lim.sub.N[right arrow][infinity]] [c.sub.N] = 0 and that, for each sample size n [member of] N, the time-scaled number of generations back to the MRCA [C.sub.N] [T.sub.n,N] converges in distribution to some random variable [W.sub.n] as N [right arrow] [infinity]. Then, there exists an exchangeable coalescent process R = [([R.sub.t]).sub.t[greater than or equal to]0] such that [W.sub.n] [??] [T.sub.n] := inf {t > 0 : [absolute value of [[??].sub.n] [R.sub.t]] = 1 }for all n [member of] N.

Proof: By Lemma 6.1 there exists a subsequence [([N.sub.l]).sub.l[member of]N] of positive integers with [lim.sub.l[right arrow]] [N.sub.l] = [infinity] and some exchangeable coalescent process R = [([R.sub.t]).sub.t[greater than or equal to]0] such that, for each n [member of] N, the time-scaled ancestral process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges in the Skorohod topology to [([[??].sub.n][R.sub.t]).sub.t[greater than or equal to]0] as l [right arrow] [infinity]. In particular, for all sample sizes n [member of] N and all times t [greater than or equal to] 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

i.e., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as l [right arrow] [infinity] for all n [member of] N. By assumption, [C.sub.N][T.sub.n],[??] [W.sub.n] for all n [member of] N. Therefore, [W.sub.n] [??] [T.sub.n] for all n [member of] N.

Remark: Let R be an exchangeable coalescent process. In general (see the following section for more details), the marginal distributions of the times [T.sub.n] := inf{t > 0 : [absolute value of [[??].sub.n] [R.sub.t]] = 1}, n [member of] {2, 3, ...}, do not determine the distribution of R completely. In particular, the uniqueness of the (distribution of the) coalescent R in Lemma 6.2 is in general not guaranteed. However, if it is in addition know that the coalescent process R allows only for multiple mergers of ancestral lineages, i.e. if R is a [LAMBDA]-coalescent with [LAMBDA] some finite measure on the unit interval [0, 1], then (see the following Lemma 6.3) the distribution of R is already uniquely determined by the marginal distributions of the times [T.sub.n], n [member of] {2, 3, ...}.

Lemma 6.3 The measure [LAMBDA] of a [LAMBDA]-coalescent R = [([R.sub.t]).sub.t[greater than or equal to]0] is uniquely determined by the marginal distributions of the times [T.sub.n] := inf{t > 0 : [absolute value of [[??].sub.n][R.sub.t]] = 1}, n [member of] {2, 3, ...}.

Proof: The times [T.sub.n] can take the value [infinity] with positive probability only if [LAMBDA] [equivalent to] 0. Thus, without loss of generality we can and do assume that [LAMBDA] [not equal to] 0, in which case all the random variables [T.sub.n], n [member of] N, are almost surely real valued. Assume for a moment that [LAMBDA] is not concentrated in 1. Then, the basic formula

[g.sub.n+1] - [g.sub.n] = n [[integral].sub.[0,1]] [(1 - x).sup.n-1] [LAMBDA](dx), n [member of] N, (12)

(which follows easily from (14)) implies that the sequence [([g.sub.n]).sub.n[member of]N] of total rates is strictly increasing. In particular, the total rates are pairwise distinct, and, therefore, as in (10), for n [member of] {2, 3,...} and t [greater than or equal to] 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the probabilities [r.sub.ij] := [g.sub.ij] /[g.sub.i], 1 [less than or equal to] j [less than or equal to] i [less than or equal to] n, are the transition probabilities of the jump process of [([absolute value of [[??].sub.n][R.sub.t]]).sub.t[greater than or equal to]0] and the second sum extends over all integers [i.sub.0], ..., [i.sub.k] satisfying 1 = [i.sub.0] < if < ... < [i.sub.k-1] < [i.sub.k] = n. The above formula shows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

where the [a.sub.nk] are some non-zero coefficients which do not depend on t (we do not need to know these coefficients in detail). If [LAMBDA] is concentrated in 1, then [g.sub.k] = 1 for all k [member of] {2,3, ...} and (13) holds as well, if we choose [a.sub.nk] := 1/(n - 1) for all k [member of] {2, ..., n}. From (13) it follows that the total rates [g.sub.k], k [member of] {2, ..., n}, are uniquely determined by the distribution of [T.sub.n]. Thus, the total rates [g.sub.n], n [member of] N, are uniquely determined by the marginal distributions of the times [T.sub.n], n [member of] N. From (12) it follows that the moments of [LAMBDA] are uniquely determined by the sequence [([g.sub.n]).sub.n[member of]N]. As the measure [LAMBDA] is concentrated on [0,1], it is uniquely determined by its moments which completes the proof. If the given sequence of Cannings models is in the domain of attraction of a coalescent with multiple collisions ([LAMBDA]-coalescent), i.e., if [[phi].sub.2] (2, 2) := [lim.sub.N[right arrow][infinity]] [[PHI].sup.(N).sub.2] (2, 2)/[c.sub.N] = 0, then Lemma 6.2 can be strengthened as follows.

Theorem 6.4 Suppose that [c.sub.N] > 0 for sufficiently large N, that [lim.sub.N[right arrow] [c.sub.N]] = 0, that [[phi].sub.2] (2, 2) := [lim.sub.N[right arrow][infinity]] [[PHI].sup.(N).sub.2] (2, 2)/[C.sub.N] = 0, and that, for each sample size n [member of] N, the time-scaled number of generations [C.sub.N][T.sub.n,N] back to the MRCA converges in distribution to some random variable [W.sub.n] as N [right arrow] [infinity].

Then, there exists a [LAMBDA]-coalescent R = [([R.sub.t]).sub.t[greater than or equal to]0] such that

(i) [W.sub.n] [??] [T.sub.n] := inf{t > 0 : [absolute value of [[??].sub.n][R.sub.t]] = 1}for all n [member of] N and

(ii) for each sample size n [member of] N, as N tends to infinity, the time-scaled ancestral process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges in the Skorohod topology to ([[??].sub.n][R.sub.t])t[greater than or equal to]0.

The measure [LAMBDA] is uniquely determined by (i).

Proof: Let [([N.sup.(0).sub.l]).sub.l[member of]N] be some arbitrary subsequence of N. As in the proof of Lemma 6.2, but starting with the arbitrary subsequence [([N.sup.(0).sub.l]).sub.l[member of]N], it follows that there exists a subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that, for each sample size n [member of] N, as l [right arrow] [infinity], the time-scaled ancestral process ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges in the Skorohod topology to [([[??].sub.n] [R.sub.t]).sup.t[greater than or equal to]0], where R = [([R.sub.t]).sub.t[greater than or equal to] 0] is some exchangeable coalescent process. From the assumption [[phi].sub.2] (2, 2) = 0 it follows that R cannot have simultaneous multiple collisions, i.e. R must be a [LAMBDA]-coalescent. The convergence in the Skorohod topology in particular implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and from the assumption [C.sub.N][T.sub.n,N] [??] [W.sub.n] we conclude that [W.sub.n] [??] for all n [member of] N, which proves (i). In order to verify (ii) it remains, by the criterion of subsequences, to show that the distribution of R does not depend on the particular subsequence [([N.sup.(0).sub.l]),.sub.l[member of]N]. By Lemma 6.3, the distribution of R is uniquely determined by the sequence [([N.sup.(0).sub.l]).sub.l[member of]N]. In particular, the distribution of R does not depend on the particular subsequence ([N.sup.(0).sub.l]).sub.l[member of]N].

7 Simultaneous multiple collisions

The results presented so far are essentially based on the property that the total rates

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

of a [LAMBDA]-coalescent R = [([R.sub.t]).sub.t[greater than or equal to]0], i.e. a coalescent with multiple collisions, already determine the measure [LAMBDA] completely. This property follows simply from (12) and the fact that --since the measure [LAMBDA] is concentrated on the unit interval--the moments of [LAMBDA] uniquely determine the measure A. Note that there is even a formula available (see Eq. (16) of [12]) which expresses the rates

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

n, k [member of] N with k < n, directly in terms of the total rates [g.sub.n], n [member of] N.

It is natural to ask whether the above mentioned property carries over to the wider class of exchangeable coalescent processes with simultaneous multiple collisions. In the following it is shown that, in general, the total rates do not determine the distribution of an exchangeable coalescent.

Schweinsberg [18] characterizes exchangeable coalescents via a finite measure [XI] on the infinite simplex [DELTA] : {x = ([x.sub.1], [x.sub.2], ...) : [x.sub.1] [greater than or equal to] [x.sub.2] [greater than or equal to] ... [greater than or equal to] 0, [[summation].sup.[infinity].sub.i=1] [x.sub.i] [less than or equal to] 1}. Decomposing [XI] = + [[XI].sub.0] + a[[delta].sub.0] with 0 [less than or equal to] a [less than or equal to] [infinity] and [[XI].sub.0] having no atom at zero, each ([k.sub.1], ..., [k.sub.j]) -collision ([k.sub.1], ..., [k.sub.j] [member of] N with [k.sub.1] [greater than or equal to] ... [greater than or equal to] [k.sub.j] and [k.sub.1] [greater than or equal to] 2) occurs at the rate (see [18, Eq. (11)])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

where s := [absolute value of {1 [less than or equal to] i [less than or equal to] j : [k.sub.i] = 1}] denotes the number of singletons, r := j - s, [absolute value of x] := [[summation].sup.[infinity].sub.i=1] [x.sub.i] and (x, x) := [[summation].sup.[infinity].sub.i=1] [x.sup.2.sub.i]. In particular,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

If the measure [XI] is concentrated on the subset of points x [member of] [DELTA] satisfying [x.sub.i] = 0 for i [greater than or equal to] 3, then only for l [member of] {0,1} the last sum in (16) is non-zero and it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

In the following we construct a class of [XI]-coalescents which all have the same total rates. Fix a constant c [member of] (0, 1). If the measure [XI] is concentrated on the subset of points x [member of] [DELTA] satisfying [x.sub.i] = 0 for i [greater than or equal to] 3 and [x.sub.1] + [x.sub.2] = c, then (17) reduces to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let X be a random variable taking values in the interval [c/2, c] and let [XI] denote the distribution of (X, c - X, 0, 0, ...). Then, we have

[[phi].sub.j] (2, 1, ..., 1) = [(1 - c).sup.j-1] + (j - 1)c[(1 - c).sup.j-2] E (X (c - X)/[X.sup.2] + [(c - X).sup.2]). (18)

It is straightforward (Take, for example, X [equivalent to] 3c/4 and Y such that P(Y = c/2) = 3/5 and P(Y = c) = 2/5.) to construct two (even infinitely many) random variables X and Y both taking values in [c/2, c], such that [P.sub.X] [not equal to] [P.sub.Y] but

E(X(c-X)/[X.sup.2] + [(c - X).sup.2]) = E (Y(c-Y)/[Y.sup.2] + [(c - Y).sup.2]).

Let [XI] and [XI]' denote the distribution of (X, c - X, 0, 0, ...) and (Y, c - Y,0,0, ...) respectively. Then [XI] [not equal to] [XI]'. Let R denote a standard [XI]-coalescent and R' denote a standard [XI]'-coalescent. The processes R and R' do not have the same distribution. However, from (18) and the general formula (see, for example, p. 1556 of [13])

[g.sub.n] = [n-1.summation over (j=1)]j[[phi].sub.j] (2,1, ..., 1), n[member of]N

for the total rates [g.sub.1], [g.sub.2], ... of exchangeable coalescent processes it follows that the total rates of R and R' coincide. Thus, in general the total rates do not determine the distribution of an exchangeable coalescent completely.

As a consequence, the marginal distributions of the times [T.sub.n], n [member of] {2,3, ...}, do not determine the measure [XI] of the coalescent. Therefore, Lemma 6.3 cannot be extended to the full class of all exchange-able coalescents and, as a consequence, without the assumption [[phi].sub.2] (2, 2) = 0 in Theorem 6.4, a coalescent R satisfying the condition (i) of Theorem 6.4 is in general not uniquely determined such that condition (ii) of Theorem 6.4 cannot hold in general.

8 Appendix

Lemma 8.1 The functions [[PHI].sub.j], j [member of] {1, ..., N}, defined via (1), are monotone in the sense that

[[PHI].sub.j] ([k.sub.1], ..., [k.sub.j]) [less than or equal to] [[PHI].sub.l] ([m.sub.1], ..., [m.sub.l]) (19)

for 1 [less than or equal to] l [less than or equal to] j [less than or equal to] N and [k.sub.1], ..., [k.sub.j], [m.sub.1], ..., [m.sub.l] [member of] N with [k.sub.1] [greater than or equal to] [m.sub.1], ..., [k.sub.l] [greater than or equal to] [m.sub.l] and [k.sub.1] + ... + [k.sub.j] < N.

Remark: The following proof of Lemma 8.1 uses only the consistency relation (2) and is hence shorter and more transparent than earlier proofs mentioned in [14] and going back to [13].

Proof: We prove (19) inductively on the difference d:= j - l [member of] {0, ..., N - 1}. By (2),

[[PHI].sub.l] ([m.sub.1], ... [m.sub.l]) [greater than or equal to] [[PHI].sub.l] ([m.sub.1], ..., [m.sub.i-1], [m.sub.i] + [m.sub.i+1], ..., [m.sub.l])

for i [member of] {1, ..., l}. Thus, iteratively, (19) holds for j = l, i.e. for d = 0. Again, from (2) and (19) (for d = 0), it follows that

[[PHI].sub.l] ([m.sub.1], ..., [m.sub.l])[greater than or equal to] [[PHI].sub.l+1] ([m.sub.1], ... [m.sub.l],1) [greater than or equal to] [[PHI].sup.l+1] ([k.sub.1], ..., [k.sub.l+1]),

i.e., (19) holds for j = l + 1, i.e. for d = 1. Now apply (19) (with d = 1) (j - l)-times to conclude that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and (19) is established.

References

[1] CANNINGS, C. (1974) The latent roots of certain Markov chains arising in genetics: a new approach, I. Haploid models. Adv. Appl. Probab. 6, 260-290.

[2] CANNINGS, C. (1975) The latent roots of certain Markov chains arising in genetics: a new approach, II. Further haploid models. Adv. Appl. Probab. 7, 264-282.

[3] DONNELLY, P. (1991) Weak convergence to a Markov chain with an entrance boundary: ancestral processes in population genetics. Ann. Probab. 19, 1102-1117.

[4] FREUND, F. AND MOHLE, M. (2007) On the time back to the most recent common ancestor and the external branch length of the Bolthausen-Sznitman coalescent. Preprint.

[5] KINGMAN. J.F.C. (1982) Exchangeability and the evolution of large populations. In Exchangeability in Probability and Statistics, eds G. Koch and F. Spizzichino, North-Holland, Amsterdam, pp. 97-112.

[6] KINGMAN, J.F.C. (1982) On the genealogy of large populations. J Appl. Probab. 19A, 27-43.

[7] KINGMAN, J.F.C. (1982) The coalescent. Stoch. Process. Appl. 13, 235-248.

[8] KINGMAN, J.F.C. (2000) Origins of the coalescent: 1974-1982. Genetics 156, 1461-1463.

[9] MOHLE, M. (1998) Robustness results for the coalescent. J. Appl. Probab. 35, 438-447.

[10] MOHLE, M. (2000) Total variation distances and rates of convergence for ancestral coalescent processes in exchangeable population models. Adv. Appl. Probab. 32, 983-993.

[11] MOHLE, M. (2004) The time back to the most recent common ancestor in exchangeable population models. J. Appl. Probab. 36, 78-97.

[12] MOHLE, M. (2006) On sampling distributions for coalescent processes with simultaneous multiple collisions. Bernoulli 12, 35-53.

[13] MOHLE, M. AND SAGITOV, S. (2001) A classification of coalescent processes for haploid exchangeable population models. Ann. Probab. 29, 1547-1562.

[14] MOHLE, M. AND SAGITOV, S. (2003) Coalescent patterns in diploid exchangeable population models. J. Math. Biol. 47, 337-352.

[15] PITMAN, 7. (1999) Coalescents with multiple collisions. Ann. Probab. 27, 1870-1902.

[16] SAGITOV, S. (1999) The general coalescent with asynchronous mergers of ancestral lines. J. Appl. Probab. 36, 1116-1125.

[17] SAGITOV, S. (2003) Convergence to the coalescent with simultaneous multiple mergers. J. Appl. Probab. 40,839-854.

[18] SCHWEINSBERG, 7. (2000) Coalescents with simultaneous multiple collisions. Electron. J Probab. 5, 1-50.

Martin Mohle

Mathematisches Institut, Heinrich-Heine-Universitat Dusseldorf Universitatsstr. 1, 40225 Dusseldorf Germany

E-mail address: moehle@math.uni-duesseldorf.de
COPYRIGHT 2008 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Mohle, Martin
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUGE
Date:Jan 1, 2008
Words:7677
Previous Article:Analysis of an algorithm catching elephants on the Internet.
Next Article:Generating functions of stochastic L-systems and application to models of plant development.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters