1 Introduction and results
Independently introduced in [33] and [30], Ξ-coalescents are exchangeable Markovian processes Π=(Πt)t≥0 on the set of partitions of N:={1,2,…} whose transitions are due to mergers of partition blocks. The distribution of Π is characterised by a finite measure Ξ on the infinite simplex
where |x|:=∑i∈Nxi. We exclude Ξ=0, since it leads to a coalescent without coalescence events. Ξ-coalescents allow that disjoint subsets of blocks merge into distinct new blocks, hence they are also called coalescents with simultaneous multiple mergers. If Ξ is concentrated on [0,1]×{0}×{0}×⋯, only a single set of blocks is allowed to merge. Such a coalescent is a Λ-coalescent, see [32]. In this case, Λ is a finite measure on [0,1], the restriction of Ξ on the first coordinate of Δ. The restriction Π(n) of Π on [n]:={1,…,n} is called the Ξ-n-coalescent. Denote the blocks of Πt by (Bi(t))i∈N, where i is the least element of the block (we set Bi(t)=∅ if i is not a least element of a block). Clearly, 1∈B1(t). We call B1(t) the block of 1 at time t. Due to the exchangeability of the Ξ-coalescent, Kingman’s correspondence ensures that, for every t≥0, the asymptotic frequencies
exist almost surely, where |A| denotes the cardinality of the set A.
The family of Ξ-coalescents is a diverse class of processes with very different properties, see e.g. the review [15] for Λ-coalescents. We will focus on Ξ-coalescents with dust, i.e. Ξ fulfils (see [33])
where ν0(dx)=Ξ(dx)/(x,x) with (x,x):=∑i∈Nx2i for x=(x1,x2,…)∈Δ. These coalescents are characterised by a non-zero probability that, at any time t, there is a positive fraction of N, the dust, that has not yet merged. Note that i∈N is part of the dust at time t if and only if {i} is a block at time t, which is called a singleton block. The asymptotic frequency of the dust component is St:=1−∑i∈Nfi(t). Having dust is equivalent to P(St>0)>0 for all t>0. We are interested in Ξ-coalescents which stay infinite, i.e. which almost surely have an infinite number of blocks for each t>0. We will put some further emphasis on simple Λ-coalescents satisfying
This class includes Dirac coalescents with Λ=δp, the Dirac measure in p∈(0,1]. Consider the frequency process f1:=(f1(t))t≥0 of the block of 1. For Λ-coalescents, Pitman characterises f1 as follows (reproduced from [32], adjusted to our notation).
Proposition 1.
[32, Proposition 30] No matter what Λ, the process f1 is an increasing pure jump process with càdlàg paths, f1(0)=0 and limt→∞f1(t)=1. If μ−1=∞ then almost surely f1(t)>0 for all t>0 and limt↘0f1(t)=0. If μ−1<∞ then f1 starts by holding at zero until an exponential time with rate μ−1, when it enters (0,1] by a jump, and proceeds thereafter by a succession of holds and jumps, with holding rates bounded above by μ−1.
Moreover, in [32, Section 3.9], a general formula for the moments of f1(t) for fixed t>0 is provided.
For two particular coalescents without dust, further properties of f1 are known. For Kingman’s n-coalescent (Λ=δ0), the complete distribution of block sizes is explicitly known, see [24, Theorem 1], from which one can derive some properties of the block of 1 due to exchangeability. For the Bolthausen–Sznitman coalescent (Λ the uniform distribution on [0,1]) the block of 1 can be characterised as in [32, Corollary 16]. For instance, f1 is Markovian for the Bolthausen–Sznitman coalescent.
Different specific aspects of the block of 1 have been analysed for different Λ/Ξ-n-coalescents including their asymptotics for n→∞.
Due to the exchangeability of the Ξ-coalescent, any result for the distribution of the block of 1 holds true for the block containing any other i∈N. We want to further describe f1 for Ξ-coalescents with dust. For any finite measure Ξ on Δ which fulfils (2), we introduce
We see that γ∈(0,1], since
Define Δf:=⋃k∈N{x∈Δ:x1+⋯+xk=1}. We extend Proposition 1 for Ξ-coalescents with dust which stay infinite, i.e. have almost surely infinitely many blocks for each t≥0 (equivalent to Ξ(Δf)=0, see Lemma 4). While the extension to Ξ-coalescents and the explicit waiting time distributions are a direct follow-up from Pitman’s proof, we provide a more detailed description of the jump heights of f1. Proposition 1 ensures that the jumps of f1 are separated by (almost surely) positive waiting times, we denote the value of f1 at its kth jump with f1[k] for k∈N.
-
• Minimal clade size: The size Mn of the block of 1 for the n-coalescent at its first jump. For Kingman’s n-coalescent and for Λ beta-distributed with parameters (2−α,α) with α∈(1,2), Xn converges in distribution for n→∞, see [6] and [34]. For the Bolthausen–Sznitman n-coalescent, log(Mn)/log(n) converges in distribution [14]. These results do not cover Λ/Ξ-coalescents with dust.
-
• The number of blocks involved in the first merger of the block of 1, see [34]. The results cover Λ-coalescents with dust.
Theorem 1.
In any Ξ-coalescent Π with dust and Ξ(Δf)=0, the asymptotic frequency process f1:=(f1(t))t≥0 of the block of 1, defined by Eq. (1), is an increasing pure jump process with càdlàg paths, f1(0)=0 and limt→∞f1(t)=1, but f1(t)<1 for t>0 almost surely. The waiting times between almost surely infinitely many jumps are distributed as independent Exp(μ−1) random variables. Its jump chain (f1[k])k∈N can be expressed via stick-breaking
where (Xj)j∈N are pairwise uncorrelated, Xj>0 almost surely and E(Xj)=γ for all j∈N. In particular, E(f1[k])=1−(1−γ)k. In general, (Xj)j∈N are neither independent nor identically distributed.
Remark 1.
From Theorem 1, the dependence between f1 and its jump times is readily seen as follows. Recall [32, Eq. (51)] that E(f1(t))=1−e−t for any Λ-coalescent with Λ([0,1])=1. If we would have independence, integrating E(f1(t)) over the waiting time distribution Exp(μ−1) for the first jump of f1 would yield E(f1[1])=(1+μ−1)−1, in contradiction to E(f1[1])=1/μ−1 by Theorem 1.
Dirac coalescents (Λ=δp for some p∈(0,1]) are a family of Λ-coalescents with dust. They have been introduced as simplified models for populations in species with skewed offspring distributions (reproduction sweepstakes), see [9]. Their jump chains (discrete time Dirac coalescents) can also arise as large population size limits in conditional branching process models [21, Theorem 2.5].
We further characterise f1 as follows, including an explicit formula for its distribution at its first jump.
Proposition 2.
Let Λ=δp, p∈[12,1) and q:=1−p. f1 takes values in the set
For x=∑i∈Nbipqi−1∈Mp, we have
where Yd=Geo(p), J:={i∈N|bi=1} and j:=maxJ. The process f1 is not Markovian whereas its jump chain (f1[k])k∈N is Markovian.
Remarks 2.
-
• The law of f1[1] is a discrete measure on [0,1] for Dirac coalescents. Surprisingly different properties arise for different values of p. For instance, M2/3={∑i∈Nbi3−i:bi∈{0,2},1≤∑i∈Nbi<∞} is a subset of the ternary Cantor set which is nowhere dense in [0,1], whereas M1/2, the set of all x∈[0,1] with finite 2-adic expansion, is dense in [0,1].
-
• We omitted f1[1] for the star-shaped coalescent (Λ=δ1), since it just jumps from 0 to 1 at time Td=Exp(1).
-
• Recall that f1 is Markovian for the Bolthausen–Sznitman coalescent in contrast to f1 for the Dirac coalescents specified above.
Our key motivation was to provide a more detailed description of the jump chain of f1, especially properties of the value f1[1] at the first jump which is the asymptotic frequency of the minimal clade. Theorem 1 provides a first-order limit result for all Ξ-coalescents with dust.
Corollary 1.
Let Π be a Ξ-coalescent with dust and Π(n) its restriction on [n]. Let Mn be the minimal clade size, i.e. the size of the block of 1 at its first merger in Π(n). Then, Mn/n→f1[1] almost surely, f1[1]>0 almost surely and E(f1[1])=γ.
Compared to the known results listed above for the minimal clade size for dust-free coalescents, the minimal clade size is much larger asymptotically for n→∞ (O(n) compared to o(n)).
The law of f1[1] in (7) follows from the following more general description of f1[1] for simple Λ-coalescents. We introduce, for a finite measure Λ on [0,1] with μ−1=∫10x−1Λ(dx)<∞,
We have α∈[0,1] since x−1≤x−2 on (0,1] (if μ−1<∞, we have Λ({0})=0). Additionally, α>0 if and only if μ−2<∞, so if Λ characterises a simple coalescent (recall that μ−2≥μ−1>0 since we exclude Λ=0).
Proposition 3.
Let Λ fulfil (3). Then,
where (Pi)i∈N are i.i.d. with Pid=μ−1−2x−2Λ(dx). We have
Given (Pi)i∈N, C and (B(k)i)k∈N,i∈[k] are independent and (B(k)i)k∈N,i∈[k] is defined as
where b=(b1,…,bj)∈{0,1}j−1×{1}, J:={i∈[j]|bi=1} and, for each i∈N, I(i):=min{j≥i+1:B(j)i=1}. We have
(10)
P((B(j)1,…,B(j)j)=b|(Pi)i∈N)=∏i∈J∖{j}P(I(i)∈J|(Pi)i∈N)∏i∈[j−1]∖JP(I(i)∉J|(Pi)i∈N)almost surely,Remarks 3.
-
• The distribution of C is known from [16, Proposition 3.1].
-
• The distribution of f1[1] for Dirac coalescents with p>12 has a structure somewhat similar to the Cantor distribution, see e.g. [26] and [18]. The Cantor distribution is the law of ∑i∈NBipqi−1 for p∈(0,1), where (Bi)i∈N are i.i.d. Bernoulli variables with success probability 12, whereas in our case (Bi)i∈N are dependent Bernoulli variables with success probabilities P(Bi=1)=P(∑k≥iB(k)i1{C=k}=1)=pqi−1+∑k>ip2qk−1=pqi−1(1+q), see Eq. (9). The Cantor distribution is a shifted infinite Bernoulli convolution. Infinite Bernoulli convolutions are the set of distributions of ∑i∈Nωi(−1)Bi with ωi∈R for i∈N satisfying ∑i∈Nω2i<∞, see [31, Section 2]. They have been an active field of research since the 1930’s, e.g. see [10, 35] and the survey [31].
Our main tool for the proofs is Schweinsberg’s Poisson construction of the Ξ-coalescent. The article is organised as follows. We recall (properties of) the Poisson construction in Section 2. Section 3 characterises staying infinite for Ξ-coalescents with dust. These prerequisites are then used to prove the results for Ξ-coalescents with dust in Section 4 and for simple Λ-coalescents in Section 5.
2 Poisson construction of a Ξ-coalescent and the block of 1
We recall the construction of a Ξ-n-coalescent Π from [33]. We are only interested in constructing a Ξ-coalescent with dust, which implies Ξ({0})=0, see Eq. (2).
Let P be a Poisson point process on A=[0,∞)×N∞0 with intensity measure
where, for x∈Δ, P(x) is a probability measure on N0 with P(x)({k})=xk and P(x)({0})=1−|x| (Kingman’s paintbox) and ν0 is defined as in Eq. (2). For n∈N, the restriction Π(n) of Π to [n] can be constructed by starting at t=0 with each i∈[n] in its own block. Then, for each subsequent time (T=)t with a Poisson point (T,(Ki)i∈N), merge all present blocks i (at most n) with identical ki>0, where i is the least element of the block (there are only finitely many points of P that lead to a merger of blocks in [n]). Π is then pathwise defined by its restrictions (Π(n))n∈N. From now on we will assume without loss of generality that the Ξ-coalescent with dust is constructed via the Poisson process P.
The block of 1 can only merge at Poisson points P=(T,(Ki)i∈N) with K1>0. We take a closer look at these Poisson points. We introduce exchangeable(Q) indicators following [32, p.1884]: These are exchangeable Bernoulli variables which are conditionally i.i.d. given a random variable X with distribution Q on [0,1] which gives their success probability. Alternatively, we denote these as exchangeable(X) indicators if we can specify X.
Lemma 1.
For any finite measure Ξ on Δ fulfilling (2), P splits into two independent Poisson processes
P1 has almost surely finitely many points on any set [0,t]×N∞0, thus we can order
where Tj<Tj+1 almost surely for j∈N.
(Tj)j∈N is a homogeneous Poisson process on [0,∞) with intensity μ−1.
Proof.
P1 and P2 are obtained by restricting P on the disjoint subsets A1:=[0,∞)×N×N∞0 and A2:=[0,∞)×{0}×N∞0 of A. Thus, P1 and P2 are independent Poisson processes (restriction theorem [25, p.17]) with intensity measures ν1=ν(⋅∩A1) and ν2=ν(⋅∩A2). For any Borel set B⊆[0,∞) and λ being the Lebesgue measure,
Thus, on any bounded set B, P1 has almost surely finitely many points, which can be ordered as described. Projecting P1 on the first coordinate t of A yields a Poisson process with intensity measure μ−1dt (mapping theorem [25, p.18]).
Now, we project the points of P1 on the coordinate of (K(j)i)i∈N. Recall the construction of a Poisson process as a collection of i.i.d. variables with distribution (μ(C))−1μ on sets of finite mass C of the intensity measure μ, e.g. [25, p.23]. It shows that we can treat the collection of (Tj,(K(j)i)i∈N) with, for instance, Ti∈[k,k+1) for k∈N as a random number of i.i.d. random variables with distribution (1⋅μ−1)−1ν1. Since ν1 has a product structure on A1, we have that ((K(j)i)i∈N)j∈N are i.i.d. in j and have distribution, for m∈N,
for l1∈N and l2,…,lm∈N0. Consider (1{K(1)1=K(1)i})i≥2. To show that they are exchangeable(Q) indicators, [32, Eq. (27)] has to be fulfilled, i.e. we need to show P({i∈[m]:K(1)i=K(1)1}=M)=E(X|M|−1(1−X)m−|M|) for Xd=Q and any M⊆[m] with 1∈M. Using Eq. (13) we compute
P({i∈[m]:K(1)i=K(1)1}=M)=∑j∈NP({i∈[m]:K(1)i=j}=M,K(1)1=j)=1μ−1∫Δ∑j∈Nx|M|j(1−xj)m−|M|ν0(dx)=E(X|M|−1(1−X)m−|M|).
Clearly, P(X>0)=1 since Ξ({0})=0 and E(X)=μ−1−1∫Δ(x,x)ν0(dx)=γ. □Remarks 4.
-
• Q can be seen as the expected value of the random probability measure Qx:=|x|−1∑i∈Nxiδxi for x∈Δ with x drawn from μ−1−1|x|ν0(dx). In the Poisson construction, this means we draw a “paintbox” x∈Δ and then record in which box the ball of 1 falls, if we only allow it to fall in boxes 1,2,….
-
• Consider a simple Λ-coalescent. Projecting P2 on its first component, so (T,(Ki)i∈N)↦T, yields a homogeneous Poisson process with intensity μ−2−μ−1<∞. To see this, proceed analogously as for P1. Then, Eq. (12) for ν2 reads the same except for replacing P(x)(N) by P(x)({0})=1−|x|.
For a Λ-coalescent (with Λ({0})=0) the Poisson construction simplifies, since Ξ only has mass on {x∈Δ:x2=x3=⋯=0} and thus P can be seen as a Poisson process on [0,∞)×{0,1}∞ with intensity measure dt⊗∫[0,1]⊗n∈NP(x)x−2Λ(dx), where P(x) is the Bernoulli distribution with success probability x∈(0,1].
When constructing simple Λ-coalescents, even the process P itself has almost surely finitely many points (Tj,(K(j)i)i∈N) on any set [0,t]×{0,1}∞ (which we can again order in the first coordinate). As described in [32, Example 19] and analogously to Lemma 1, we can construct each (potential) merger at point (Tj,(K(j)i)j∈N) of a simple Λ-coalescent as follows (while between jumps, we wait independent Exp(μ−2) times). First choose Pi∈(0,1] from μ−1−2x−2Λ(dx), we have E(Pi)=μ−1−2∫[0,1]x−1Λ(dx)=α. Then, throw independent coins (K(j)i)i∈N with probability Pi for ‘heads’ (=1) for each block present and merge all blocks whose coins came up ‘heads’. Again, (Pi)i∈N are i.i.d. and the ‘coins’ K(j)i are exchangeable(Pi) indicators. Analogously to above, we thus have
Lemma 2.
Let Λ be a finite measure on [0,1] fulfilling (3). For the Poisson process P=(Tj,(K(j)i)i∈N)j∈N, ((K(j)i)i∈N)j∈N is an i.i.d. sequence (in j) of sequences of exchangeable(Pj) indicators, where (Pj)j∈N are i.i.d. with P1d=μ−1−2x−2Λ(dx). In particular, E(Pi)=α.
Since many proofs will build on the properties of different sets of exchangeable indicators, we collect some well-known properties in the following
Proof.
These properties essentially follow from the de Finetti representation of an infinite series of exchangeable variables as conditionally i.i.d. variables. The lemma is a collection of well-known properties as e.g. described in [3, Sections 2 and 3], arguments of which we use in the following.
An infinite exchangeable sequence is conditionally i.i.d. given an almost surely unique random measure α. This measure is the weak limit of the empirical measures, in our case, n−1∑ni=1δKi, which has limit X′δ1+(1−X′)δ0 for some random variable X′ with values in [0,1]. Given α, the indicators are α-distributed. However, since X gives the success probability of each Bernoulli coin, we have X=X′ almost surely, so X is almost surely unique. The rest of a) is just the strong law of large numbers e.g. from [3, 2.24] (E(K1)≤1), the limit is X′. Part b) follows from measure theory since the limit is measurable in the σ-field spanned by the summed variables. For c), we again check Pitman’s condition [32, Eq. 27]. Let M⊆[m]. We have that X, Y are independent from b). With P(Ki=Li=1|X,Y)=XY almost surely,
since given X, Y, both (Ki)i∈N and (Li)i∈N are independent. This shows c). □
3 When does a Ξ-coalescent with dust stay infinite?
A crucial assumption for our results is that the Ξ-coalescent Π has almost surely infinitely many blocks that may merge in the mergers where 1 participates in. The property
is called staying infinite, while P(Πthas finitely many blocks∀t>0)=1 is the property of coming down from infinity. These properties have been thoroughly discussed for Ξ-coalescents, see e.g. [33, 27] and [20].
We recall the condition for Ξ-coalescents with dust to stay infinite.
Lemma 4.
Let Δf:={x∈Δ:x1+⋯+xk=1for somek∈N} and Ξ be a finite measure on Δ fulfilling Eq. (2). The Ξ-coalescent stays infinite if and only if Ξ(Δf)=0. If Ξ(Δf)>0, then the Ξ-coalescent has infinitely many blocks until the first jump of f1 almost surely and the Ξ-coalescent neither comes down from infinity nor stays infinite.
Proof.
Let Δ∗:={x∈Δ:|x|=1}. All Ξ-coalescents considered are constructed via the Poisson construction with Poisson point process P.
First, assume Ξ(Δ∗)=0. We recall the (well-known) property that for a Ξ-coalescent with dust Ξ(Δ∗)=0 is equivalent to P(St>0∀t)=1, where St is the asymptotic frequency of the dust component. We use the remark on [12, p.1091]: For Ξ-coalescents with dust, (−logSt)t≥0 is a subordinator. The subordinator jumps to ∞ (corresponds to St=0) if and only if for its Laplace exponent Φ, we have limη↘0Φ(η)>0. For a Ξ-coalescent with dust we have limη↘0Φ(η)=∫Δ∗ν0(dx). Hence, Ξ(Δ∗)=0 almost surely guarantees infinitely many singleton blocks for all t≥0, so the corresponding Ξ coalescent stays infinite.
Now assume Ξ(Δ∗)>0. The subordinator (−logSt)t≥0 jumps from finite values (St>0) to ∞ (St=0) after an exponential time with rate ν0(Δ∗). This shows that the Ξ-coalescent does not come down from infinity. Assume further that Ξ(Δf)=0. Then, [33, Lemma 31] shows that the Ξ-coalescent either comes down from infinity or stays infinite, so it stays infinite.
Finally, assume Ξ(Δf)>0. Split P into independent Poisson processes P′1:={(T,(Ki)i∈N)∈P:κ∈Δf} and P′2:={(T,(Ki)i∈N)∈P:κ∉Δf}, where κ:=(limn→∞n−1∑i∈[n]1{Ki=j})j∈N (again restriction theorem [25, p.17], Lemma 3 shows κ exists almost surely). Their intensity measures are defined as in Eq. (11), but using ν′1(⋅):=ν0(⋅∩Δf) and ν′2:=ν0−ν′1 instead of ν0. Since ν′1(Δf)≤μ−1<∞, for any t>0 there are almost surely finitely many P∈P′1 with T<t. Consider such P=(T,(Ki)i∈N) with T smallest. Observe that until T, we can construct the Ξ-coalescent using only the points of P′2, which is the construction of a Ξ′-coalescent with Ξ′(dx):=(x,x)ν′2(dx). Since ∫Δ|x|ν′2(dx)<μ−1<∞ and Ξ′(Δf)=0, the proof steps above show that the Ξ-coalescent has infinitely many blocks until T. Now consider the merger at time T. The form of ν′1 ensures that (Ki)i∈N can only take finitely many values, and Lemma 3a) ensures that infinitely many Ki’s show each value. Thus, all blocks present before time T are merged at T into a finite number of blocks (given by which Ki’s show the same number). This shows that if Ξ(Δf)>0, the Ξ-coalescent stays neither infinite nor comes down from infinity. Additionally, this shows that either the block of 1 already merged at least once before T or it merges at T, thus there are infinitely many blocks before the first merger of 1. □
4 The block of 1 in Ξ-coalescents with dust – proofs and remarks
Proof of Theorem 1.
As in Lemma 1, split the Poisson point process P used to construct the Ξ-coalescent in P1 and P2. We also use the notation from Lemma 1 and its proof. The block of 1 in the Ξ-n-coalescent for any n∈N can only merge at times t for which there exists a Poisson point (T,(Ki)i∈N)∈P1. Lemma 1 states that the set of times T forms a homogeneous Poisson process with rate μ−1. This shows that potential jump times are separated by countably many independent Exp(μ−1) random variables. Kingman’s correspondence yields that f1 exists almost surely at each potential jump time. To see this, observe that even though the partition of N induced by the Poisson construction is not exchangeable, the partition on N∖{1} is, and the asymptotic frequencies of the former and the latter coincide. Since f1 is by definition constant between these jump points, f1 has càdlàg paths almost surely. Since any blocks change by mergers, f1 is increasing.
The value of f1 at 0 follows by definition. Since Π stays infinite (see Lemma 4), at each P∈P1 infinitely many blocks can potentially merge. Lemma 1 shows that the indicators of whether blocks present immediately before P merge with the block of 1 are exchangeable(X) indicators with X>0 almost surely. Then, Lemma 3 ensures that a positive fraction of them almost surely does, causing f1 to jump (since a positive fraction of merging blocks has positive frequency). Thus, every Poisson point leads to a merger almost surely, which shows that f1 jumps at all potential jump times described above. Since, for all t, either St>0 or non-dust blocks not including 1 exist (having asymptotical frequency >0), f1(t)<1 for all t≥0.
We consider the jump chain of f1. Set X1:=f1[1]. Since f1[k]∈(0,1) for all k∈N and f1 increases, f1[k+1]=f1[k]+(1−f1[k])Xk+1 for Xk+1∈(0,1). Iterating this yields f1[k]=∑ki=1Xi∏i−1j=1(1−Xj) for k≥2. The properties of (Xk)k∈N follow from the Poisson construction and Lemma 1. Consider the blocks present at time Tk−, where the kth Poisson point of P1 is Pk=(Tk,(K(k)i)i∈N). The block with least element i merges with the block of 1 if K(k)i=K(k)1. Consider the kth Poisson point at time Tk. Xk gives the fraction of the asymptotic frequency of non-singleton blocks and singleton blocks at time Tk−, i.e. the fraction of 1−f1(Tk−), that is merged with the block of 1 at Tk. Denote L(k−)i:=1{{i}is a block atTk−}. Then, recording the asymptotic frequencies of merged non-singleton and singleton blocks,
Since by construction, ΠTk−∖{1} is an exchangeable partition of N∖{1}, (L(k−)i)i∈N are exchangeable(St−) indicators with St−=1−∑∞i=1fi(Tk−). Recall that Lemma 1 tells us that (1{K(k)1=K(k)i})i≥2 are exchangeable(X′) indicators with X′d=Q. (K(k)i)i∈N is independent from (Πt)t<Tk, since the Poisson points of P1 are i.i.d., so Lemma 3 c) and a) show
The independence of (K(k)i)i∈N from (Πt)t<Tk is also crucial for the next two equations. Compute, with P(K(k)1=K(k)i)=E(X′)=γ for i∈N,
E(Xk)=∑i≥2P(K(k)1=K(k)i)E(fi(Tk−)1−f1(Tk−))+E(X′)E(1−∑∞i=1fi(Tk−)1−f1(Tk−))=γE(1−f1(Tk−)1−f1(Tk−))=γ.
Analogously, for l<k, Xl only depends on Poisson points P1,…,Pl, so
E(XkXl)=E(∑i≥21{K(k)1=K(k)i}fi(Tk−)1−f1(Tk−)Xl+X′1−∑∞i=1fi(Tk−)1−f1(Tk−)Xl)=γE(1−f1(Tk−)1−f1(Tk−)Xl)=γ2,
showing that Xk,Xl are uncorrelated. An analogous computation shows that E(∏i∈{l1,…,lm}Xli)=∏i∈{l1,…,lm}E(Xli) for distinct l1,…,lm∈N. With this,
To prove limt→∞f1(t)=1 almost surely, observe that f1 is bounded and increasing, thus limt→∞f1(t) exists. Monotone convergence and limt→∞E(f1(t))=limk→∞E(f1[k])=1 show the desired. Note that (Xk)k∈N is in general neither independent nor identically distributed, see Section 6. □Proof of Corollary 1.
By the Poisson construction the block of 1 for Π(n) can only merge at times given by Poisson points in P1. Consider (T1,(K(1)i)i∈N)∈P1. While T1 is the time of the first jump of f1 (see the proof of Theorem 1), there does not necessarily need to be a merger of {1} in the n-coalescent Π(n), if we have K(1)1≠K(1)i for the least elements i of all other blocks of Π(n) immediately before T1. However, Lemma 1 shows that (1{K(1)1=K(1)i})i≥2 are exchangeable indicators. The mean n−1∑ni=21{K(1)1=K(1)i}, as argued in the proof of Theorem 1, converges to an almost surely positive random variable for n→∞. As shown in Lemma 4, any Ξ-coalescent with dust has infinitely many blocks almost surely before T1. Thus, there exists N, a random variable on N, so that 1 is also merging at time T1 in Π(n) for n≥N almost surely. This yields limn→∞n−1Mn=limn→∞n−1|B1(T1)∩[n]|=f1(T1)=f1[1] almost surely. All further claims follow from Theorem 1. □
Remark 5.
Let Q(n) be the number of blocks merged at the first collision of the block of 1 in a Λ-n-coalescent with dust. [34, 1.4] shows that n−1Q(n) converges in distribution. We argue that this convergence also holds in Lp for all p>0 and, for simple Λ-n-coalescents, almost surely.
The proof of Corollary 1 shows that (T1,(K(1)i)i∈N)∈P1 causes the first merger in the n-coalescent for n large enough (almost surely, but since n−1Q(n)∈[0,1] for all n, convergence in Lp is not affected by the null set excluded). Split Q(n) into Q(n)0, the number of non-singleton blocks and Q(n)1, the number of singleton blocks merged at T1. For the limit, we can ignore the non-singleton blocks merged. To see this, recall Q(n)0≤Kn, where Kn is the total number of mergers for the Λ-n-coalescent, since a non-singleton block has to be the result of a merger. [12, Lemma 4.1] tells us that n−1Kn→0 in L1 for n→∞ for Ξ-coalescents with dust. This shows that the L1-limit of n−1Q(n) is the same as of the one of n−1Q(n)1. n−1Q(n)1 already appeared in the part of the proof of Theorem 1 leading to Eq. (14), its limit almost surely exists and equals X′1−∑∞i=1fi(T1−)1−f1(T1−). Since n−1Q(n)1 is bounded in [0,1], it also converges in Lp, p>0. So n−1Q(n) converges in L1. Since it is bounded in [0,1] it also converges in Lp, p>0. For simple Ξ-n-coalescents, [11, Lemma 4.2] shows n−1Kn→0 almost surely, so in this case the steps above ensure also almost sure convergence of n−1Q(n).
5 The block of 1 in simple Λ-coalescents – proofs and remarks
Proof of Proposition 3.
Let P:=(Pi)i∈N be the coin probabilities coming from the Poisson process used to construct the simple Λ-coalescent Π as described in Section 2. As shown in the proof of Theorem 1, the Poisson point belonging to PC where 1 first throws ‘heads’ in the Poisson construction is the Poisson point where f1 jumps for the first time. We have P(C=k|P)=Pk∏k−1i=1(1−Pi). Integrating the condition and using the independence of (Pi)i∈N as well as E(P1)=α (see Lemma 2), we see that C is geometrically distributed with parameter α.
To describe f1[1] at the Cth merger (Poisson point), recall that the restriction Π−1 of Π to N∖{1} has the same asymptotic frequencies as Π. Thus, we can see f1[1] as the asymptotic frequency of the newly formed block of Π−1 at the time of the Poisson point PC. This follows since Π−1 has infinitely many blocks before (see Lemma 4) and then, as in the proof of Theorem 1, there will be a newly formed block of Π−1 at the Cth Poisson point (and the unrestricted block in Π includes 1).
We consider Π−1 at the kth Poisson point with coin probability Pk. For {i}∈N∖{1} to remain a (singleton) block and not be merged for the first k−1 mergers and then to be merged at the kth, we need ∏j∈[k−1](1−K(j)i)=1 and K(k)i=1. (1{∏j∈[k−1](1−K(j)i)=1,K(k)i=1})i∈N are exchangeable(Pk∏j∈[k−1](1−Pj)) indicators. Let
be the set of i∈N∖{1} whose first merger is the kth overall merger. We call Sk the kth singleton set (of Π−1). From the strong law of large numbers for exchangeable indicators, see Lemma 3a), we directly have that Sk has asymptotic frequency Pk∏j∈[k−1](1−Pj) almost surely.
Now, consider the asymptotic frequency f∗[k] of the newly formed block at the kth merger of Π−1. By construction, there is only one newly formed block at each merger. Sk is a part of the newly formed block. Any other present block with more than two elements (non-singleton block) is merged if and only if its indicator K(k)i=1 (we order by least elements). For k=1, the newly formed block is S1. For k=2, it is either S2 or S1∪S2, if the coin of the the block S1 formed in the first merger comes up ‘heads’.
Applied successively, this shows that the newly formed block at the kth merger consists of a union of a subset of the singleton sets (Sk′)k′<k and the set Sk. For its asymptotic frequency, we have
where the B(k)i, i∈[k], are non-independent Bernoulli variables which are 1 if the ith singleton set Si is a part of the newly formed block at the kth merger of Π−1.
If Λ({1})>0, Pk=1 is possible. In this case, at the kth Poisson point all remaining singletons form Sk and all blocks present at merger k−1 merge with Sk. There are no mergers at Poisson points Pl, l>k, so we do not consider Eq. (15) for l>k.
Assume Λ({1})=0. For (B(k)i)k∈N,i∈[k], we have B(k)k=1 for all k∈N since the kth singleton set is formed at the kth Poisson point and is a part of the newly formed block. The coins thrown at the kth Poisson point to decide whether other singleton sets Si, Sj with i,j<k are also parts of the newly formed block are either independent given P when they are in different blocks, or identical when they are in the same block. The set Si uses the coin of the block newly formed at the ith merger. Let I(i) be the Poisson point at which this block merges again (and Si with it). At the I(i)th Poisson point and for all further Poisson points indexed with j≥I(i), we have B(j)i=B(j)I(i), since the singleton sets Si and SI(i) are in the same block for mergers j≥I(i).
The property (i) of I(i) in the proposition follow directly from its definition as the minimum number of coin tosses until the first comes up ‘heads’. The property (ii) is just integrating (i) and using that (Pi)i∈N are i.i.d. with E(P1)=α (see Lemma 2), the conditional independence is the conditional independence of coin tosses of distinct blocks from the Poisson construction. To see Eq. (10), observe that Si for i<j is a part of the newly formed block at the jth merger of the Λ-coalescent (i∈J) if and only if I(i)∈J. If I(i)∈J, either we have I(i)=j, so Si is merged for the first time after it has been formed at the jth merger, or we have that I(i)<j which means that it has already merged with at least one other singleton set and that, as parts of the same block, they both again merged at the jth merger. If I(i)∉J, the singleton set Si neither merges at the jth merger for the first time after being formed nor merges with any other singleton set before that is then merging at the jth merger, so Si is not a part of the newly merged block at the jth merger.
If Λ({1})=0, the arguments hold true for all j∈N. If Λ({1})>0 this holds true for all i,j≤K:=mink∈N{Pk=1}(<∞almost surely), where all singleton sets merge and f∗[K]=1. However, in this case C≤K, so we still can establish Eq. (9). □
Remarks 6.
-
• (I(i))i∈N is useful to construct the asymptotic frequencies of the Λ-coalescent. Given P, at the kth merger, there are the singleton sets (Sj)j∈[k] with almost sure frequencies Pj∏i∈[j−1](1−Pi) which were already formed in the k collisions, and unmerged singleton blocks with frequency ∏i∈[k](1−Pi). Using (I(i))i∈[k], we can indicate which singleton sets form a block. Si is a single block if I(i)>k, if I(i)≤k it is a part of a block where SI(i) is also a part of. This can be seen as a discrete version of the construction of the Λ-coalescent from the process of singletons as described in [15, Section 6.1]
-
• The variables (I(i))i∈N are useful to express other quantities of the Λ-coalescent. For instance, the number of non-singleton blocks in a simple Λ-coalescent at the kth merger is given by k−∑i∈[k−1]1{I(i)≤k}.
To prove Proposition 2, we need the following result.
Proof.
We adjust the proof of [4, Theorem 7.11]. Assume that x∈Mp has two representations x=∑i∈Nbipqi−1=∑i∈Nb′ipqi−1 with bi≠b′i for at least one i. Let i0 be the smallest integer with bi0≠b′i0. Without restriction, assume bi0−b′i0=1. Then,
Thus, pqi0−1=∑i>i0(b′i−bi)pqi−1<∑i>i0pqi−1=pqi0, simplifying to p<q, in contradiction to the assumption p≥12. □
Proof of Proposition 2.
From Eq. (15) we see that f1 only takes values in Mp, since Pk=p for all k∈N and C<∞ almost surely. Recall the definition of the singleton sets Si and their properties from the proof of Proposition 3. The asymptotic frequency of Si is pqi−1 almost surely. Lemma 5 ensures that there is a unique representation f1[l]=x=∑∞i=1bipqi−1 in Mp, let J:={i∈N:bi=1} and j:=maxJ. This means that f1[l]=x is equivalent to that the block of 1 at its lth jump consists of the union of all Si with i∈J and 1. This also shows that the lth jump of f1 is at the jth jump of the Dirac coalescent, since if f1 jumps at the kth merger of the Dirac coalescent, the newly formed block includes Sk.
Since Pi=p for all i∈N, we have α=p and Eq. (9) simplifies to f1[1]=∑Ci=1B(C)ipqi−1, where Cd=Geo(p) is independent from (B(k)i)k∈N,i∈[k]. The latter fulfil
with Yd=Geo(p), since the joint distribution in Proposition 3 again simplifies, we can ignore the conditioning and I(i)−id=Geo(p) for all i∈N.
Since f1[1]=x uniquely determines the values of C and (B(C)i)i∈[C], we have
which shows Eq. (7) when we insert the distributions expressed in terms of their geometric distributions.
In order to verify that the jump chain (f1[i])i∈N is Markovian, we show that f1[1],…,f1[l] does not contain more information on f1[l+1] than f1[l] does. Without restriction, assume that the lth jump f1[l] of f1 takes place at the kth jump of the Dirac coalescent. Then, f1[l+1] is constructed from the blocks present after the kth merger. For each subsequent Poisson point Pk+1,…, blocks present are merged if their respective coins come up ‘heads’ until (and including), at Pk′, the coin of the block of 1 comes up ‘heads’ for the first time since Pk. Thus, only information about the block partition at merger k can change the law of the next jump. f1[l]=x gives the information which singleton sets S1,…,Sk are parts of the block of 1 at merger k of Π and which are not. f1[l]=x contains no information about how the other singleton sets, Si with bi=0, are merged into blocks at collisions before k apart from that it tells us that B(j)i=0 for j∈J and i∉J, which means that all Si with i∉J did not merge at the jth collisions, j∈J. This is due to that any Si with B(j)i=1 would merge with the newly formed block at merger j and thus would be in a block with Sj and also in the block of 1 at merger k. However, analogously we see that knowing f1[1],…,f1[l] does not give any additional information about the block structure at the kth merger, but only how the set of Si which are in the block of 1 at merger k behaved at the earlier mergers J. Thus, (f1[l])l∈N is Markovian. However, (f1(t))t≥0 is not Markovian. In order to see this consider, for 0<t0<t1<t2,
p(t2,t1,t0):=P(f1(t2)=p+pq2|f1(t1)=p,f1(t0)=0)=P(f1(t2)=p+pq2,f1(t1)=p,f1(t0)=0)P(f1(t1)=p,f1(t0)=0).
We will show that p(t2,t1,t0) depends on t0, which shows that f1 is not Markovian.We can express all events in terms of the independent waiting times for Poisson points, i.e. the successive differences between the first component T of the Poisson points (T,(Ki)i∈N)∈P. Here, we use the split of the Poisson points into the independent Poisson point processes P1 and P2 from Lemma 1. The waiting times between points in P1 are Exp(μ−1)-distributed, the waiting times between points in P2 are Exp(μ−2−μ−1)-distributed, see Lemma 1 and Remark 4. We will relabel τ=μ−1 and ρ=μ−2−μ−1 for a clearer type face. Let T1,T2,… be the waiting times between points in P1 and T′1,T′2,… be the waiting times between points in P2. All waiting times are independent one from another. We recall that for Td=Exp(α), P(T>a)=e−αa and P(T∈(a,a+b])=e−αa(1−e−αb) for a,b≥0.
The event {f1(t1)=p,f1(t0)=0} means that the first jump of f1 adds the singleton set S1 at a time in (t0,t1]. Thus, there has to be only a single point of P1 with first component T1≤t1 and the smallest time T′1 of points of P2 has to be greater than T1. We compute, conditioning on T1 for the third equation,
P(f1(t1)=p,f1(t0)=0)=P(t0<T1≤t1<T1+T2,T1<T′1)=∫t1t0P(T2>t1−x)P(T′1>x)τe−τxdx=∫t1t0e−τ(t1−x)e−ρxτe−τxdx=τρe−τt1∫t1t0ρe−ρxdx=τρe−τt1(e−ρt0−e−ρt1).
Analogously, we compute (by conditioning on T1,T2 for the second equality)
Remark 7.
Our proof of Proposition 2 relies on the unique representation in Mp. This means that it also holds true for all p∈(0,2−1) where each x∈Mp has a unique representation in Mp, e.g. for all transcendental p. If the representation is not unique, Eq. (16) is still correct, but the right side of Eq. (17) does not show P(f1[1]=x). Instead, the latter shows the contribution to P(f1[1]=x) from the paths of f1 which fulfil C=j,B(j)1=b1,…,B(j)j−1=bj−1 (recall that j,b1,…,bj−1 depend on the representation of x). Moreover, P(f1[1]=x) then is the sum over P(C=j)P(B(j)1=b1,…,B(j)j−1=bj−1) for the tuples j,b1,…,bj−1 coming from the different representations of x (the sets of paths are disjoint if the parameter sets (j,b1,…,bj−1) differ). Since the proof of our results on the Markov property of both f1 and its jump chain also rely on the unique representation of x (to read off which blocks merged when), the proof does not extend if p does not allow a unique representation of x.
6 Example
We provide a concrete example showing that the random variables (Xk)k∈N from Theorem 1 are, in general, neither independent nor identically distributed.
Choose Λ=δ12 and consider f1 in the corresponding Λ-coalescent. Recall that f1[l]=x∈M12 already fixes which singleton sets Sk are parts of the block of 1 at its lth merger and which are not. First, assume f1[1]=X1=58=12+123∈M12, which means that the coin of 1 comes up ‘heads’ for the first time at the third Poisson point and the block of 1 is S1∪S3, while S2 is a block of its own (an event happening with probability >0). Assume further f1[2]=1116=58+116. This sets X2=(f1[2]−f1[1])/(1−X1)=16∉M12. We read off that the coin of the block of 1 also comes up ‘heads’ at the fourth collision, where the block of 1 merges with S4. We also see that the coin of the only other block S2 comes up ‘tails’. We thus have, since we throw fair coins, P(X2=16|X1=58)=P(f1[2]=1116|f1[1]=58)=14. Since X1=f1[1]∈M12 for any realisation, X1 and X2 have different distributions. To see also non-independence, consider f1[1]=X1=12 (coin of 1 comes up ‘heads’ at first coin toss, block of 1 is S1, occurs with probability 12). In this case P(X2=16|X1=12)=0, since f1[2]=X1+(1−X1)X2=712∉M12.