Bernoulli 15(4), 2009, 1287–1304 DOI: 10.3150/09-BEJ211 Size-biased branching population measures 0 1 and the multi-type xlog x condition 0 2 n PETER OLOFSSON a J Mathematics Department, Trinity University, 1 Trinity Place, San Antonio, TX 78212, USA. E-mail: [email protected] 3 1 We investigate the xlogx condition for a general (Crump–Mode–Jagers) multi-type branching ] processwithageneraltypespacebyconstructingasize-biased populationmeasurethatrelates T to the ordinary population measure via an intrinsic martingale Wt. Sufficiency of the xlogx S conditionforanon-degeneratelimitofWtisprovedandconditionsfornecessityareinvestigated. . h Keywords: general branching process; immigration; size-biased measure; xlogx condition t a m 1. Introduction [ 1 ThexlogxconditionisafundamentalconceptforsupercriticalGalton–Watsonbranching v processes, being the necessary and sufficient condition for the process to grow as its 8 3 mean. In a Galton–Watson process with offspring mean m=E[X]>1, let Zn denote 1 the number of individuals in the nth generation and let W =Z /mn. Then, W is a n n n 2 non-negativemartingale andhence W →W for somerandomvariable W. The Kesten– n . 1 Stigum theorem is given as follows. 0 0 Theorem 1.1. If E[Xlog+X]<∞, then E[W]=1; if E[Xlog+X]=∞, then W =0 1 a.s. : v Xi Here, log+x=max(0,logx). It can further be shown that P(W =0) must either be 0 or equal the extinction probability, hence E[Xlog+X]<∞ implies that W >0 exactly r a on the set of non-extinction (see, for example, Athreya and Ney (1972)). The analog for generalsingle-type branching processes appears in Jagersand Nerman (1984) and a partial result (establishing sufficiency) for general multi-type branching processesappearsinJagers(1989).Lyons,PemantleandPeres(1995)giveaslickproofof the Kesten–Stigumtheorembasedoncomparisonsbetweenthe Galton–Watsonmeasure and another measure, the size-biased Galton–Watson measure, on the space of progeny trees. In Olofsson (1998), these ideas were further developed to analyze general single- type branching processes and the current paper considers general multi-type branching This is an electronic reprint of theoriginal article published by theISI/BS in Bernoulli, 2009, Vol. 15, No. 4, 1287–1304. This reprint differs from theoriginal in pagination and typographic detail. 1350-7265 (cid:13)c 2009ISI/BS 1288 P. Olofsson processes with a general type space. In addition to providing a new proof of a known result, size-biased processes also provide tools to further analyze necessity of the xlogx condition. A crucial concept for the Lyons–Pemantle–Peres (LPP) proof is that of size bias. If the offspring distribution is {p ,p ,...} and has mean m=E[X], then the size-biased 0 1 offspring distribution is defined as kp k p = k m fork=0,1,2,...,wherewenote,inparticular,thatp =0.Asize-biasedGalton–Watson e 0 tree is constructed in the following way. Let X be a random variable that has the size- biased offspring distribution and let the ancestor v0ehave a number X0 of children. Pick oneoftheseatrandom,callherv ,giveheraneumberX ofchildrenandgivehersiblings 1 1 ordinary Galton–Watson descendant trees. Pick one of v ’s childreneat random, call her 1 v ,giveheranumberX ofchildren,givehersistersordeinaryGalton–Watsondescendant 2 2 trees and so on and so forth. With P denoting the ordinary Galton–Watson measure n restrictedto the n firstegenerations, P denoting the measure that arisesfromthe above n construction and W =Z /mn, it can be shown that the relation n n e dP =W dP (1.1) n n n holds. Hence, it is the martingale Wnethat size-biases the Galton–Watson process. The constructionof P canalso be viewedas describing a Galton–Watsonprocesswith immi- gration,wherethe immigrantsarethe siblings ofthe individualsonthe path (v ,v ,...). 0 1 Thus, the measuere P is the ordinary Galton–Watson measure and the size-biased mea- sure P is the measure of a Galton–Watson process with immigration, where the i.i.d. immigrationgroup sizes are distributed as X−1. The relation between P and P on the spaceeof family trees can now be explored using results for processes with immigration and this provides the final key to the proof.e e The general idea of using size-bias in branching processes appeared before LPP. One early example is Joffe and Waugh (1982), where size-biased Galton–Watson processes show up in the study of ancestral trees of randomly sampled individuals. This approach wasfurtherexploredbyOlofssonandShaw(2002)withaviewtowardbiologicalapplica- tions.AnapproachsimilartoLPPappearedinWaymireandWilliams(1996),developed simultaneously with, and independently of, LPP. Later applications and extensions of the powerful LPP method include Kurtz et al. (1997), Geiger (1999), Athreya (2000), Biggins and Kyprianou (2004) and Lambert (2007). Tomakethispaperself-contained,wegiveashortreviewofgeneralmulti-typebranch- ing processes and their xlogx condition in the next section. As in the Galton–Watson case, branching processes with immigration are crucial in the proof; for that purpose, we briefly discuss processes with immigration in Section 3, following Olofsson (1996). Thesize-biasedmeasureonthe spaceofpopulationtreesandits relationto the ordinary branchingmeasureisinvestigatedinSection4and,inSection5,sufficiencyofthe xlogx condition is proved. Finally, in Section 6, we discuss various conditions for necessity. The multi-type xlogx condition 1289 2. The xlogx condition for general branching processes In a general branching process, individuals are identified by descent. The ancestor is denoted by 0, the children of the ancestor by 1,2,... and so on, so that the individual x=(x ,...,x )isthex thchildofthex thchildof...ofthex thchildoftheancestor. 1 n n n−1 1 The set of all individuals can thus be described as ∞ I= Nn. n=0 [ At birth, each individual is assigned a type s, chosen from the type space S, equipped with some appropriate σ-algebra S. The type space can be quite general; usually, it is required to be a complete, separable metric (that is, Polish) space. The type s deter- mines a probability measure P (·), the life law, on the life space Ω, equipped with some s appropriate σ-algebra F. The information provided by a life ω∈Ω may differ from one application to another, but it must at least give the reproduction process ξ on S×R . + This processgivesthe sequenceof birthtimes andtypes ofthe childrenof anindividual. More precisely, let (τ(k),σ(k)) be random variables on Ω denoting the birth time (age of the mother) and type of the kth child, respectively, and define ξ(A×[0,t])=#{k:σ(k)∈A,τ(k)≤t} for A∈S and t≥0. We let τ(k)≡∞ if fewer than k children are born. The population space isdefined as ΩI,anoutcome ωI ofwhichgivesthe livesofallindividuals,together with the σ-algebra FI. The set of probability kernels {P (·),s∈S} defines a probability s measure on (ΩI,FI), the population measure P , where the ancestor’s type is s. s With each individual x∈I, we associate its type σ , its birth time τ and its life ω , x x x where σ is inherited from the mother (a function of the mother’s life) and ω is chosen x x according to the probability distribution P (·) on (Ω,F). The birth time τ is defined σx x recursivelyby letting the ancestor be born at time τ =0 and, if x is the kth child of its 0 mother y,we let τ =τ +τ(k). Note that τ and τ denote absolute time, whereas τ(k) x y x y is the mother’s age at x’s birth. An important entity is the reproduction kernel, defined by µ(s,dr×dt)=E [ξ(dr×dt)], s the expectation of ξ(dr×dt) when the mother is of type s. This kernel plays the role of m=E[X] in the simple Galton–Watson process and determines the growth rate of the process as eαt, where α is called the Malthusian parameter. We assume throughout that the process is supercritical, meaning that α>0. The existence of such an α is not automatic; sufficient conditions may be found in Jagers (1989, 1992). For the rest of this section, we leave out further technical details and assumptions, instead focusing on the main definitions and results. The details can be found in Jagers (1989, 1992) and 1290 P. Olofsson we simply refer to a process that satisfies all of the conditions needed as a Malthusian process. Given µ and α, we define the kernel µ as ∞ µ(s,dr)= b e−αtµ(s,dr×dt) (2.1) Z0 which, under certain conditiobns, has eigenmeasure π and eigenfunction h given by π(dr)= µ(s,dr)π(ds), ZS (2.2) b h(s)= h(r)µ(s,dr), ZS where both π and hdπ can be normed to probabbility measures.The measure π is called the stable type distribution and h(s) is called the reproductive value of an individual of types.Theinterpretationofπandhisthatπisthelimitingdistributionofthetypeofan individualchosenatrandomfromapopulationandh(s)isameasureofhowreproductive the type s tends to be, in a certain average sense. Moreover, after suitable norming, it can be shown that hdπ is the probability measure that is the limiting type distribution backwardinthefamilytreefromtherandomlysampledindividualmentionedabove.The mean asymptotic age of a random child-bearing in this backward sense is denoted by β and satisfies β= te−αth(r)µ(s,dr×dt)π(ds)<∞. (2.3) ZS×S×R+ Tocount,ormeasure,thepopulation,randomcharacteristics areused.Arandomchar- acteristic is a real-valuedprocess χ, where χ(a) gives the contribution to the population ofanindividualof age a.Thus, χ is a process definedonthe life spaceandby letting χ x be the characteristic pertaining to the individual x, the χ-counted population is defined as Zχ= χ (t−τ ), t x x x∈I X which is the sum of the contributions of all individuals at time t (when the individual x is of age t−τ ). The simplest example of a random characteristic is χ(a)=I (a), the x R+ indicatorforbeingborn,inwhichcaseZχ issimplythetotalnumberofindividualsborn t up to time t. To capture the asymptotics of Zχ, the crucial entity is the intrinsic martingale W , t t introduced by Nerman (1981) for single-type processes and generalized to multi-type processes in Jagers (1989). For its definition, denote x’s mother by mx and let I ={x:τ ≤t<τ }, (2.4) t mx x the set of individuals whose mothers are born at, or before, time t, but who themselves arenotyetbornattime t.ThesetI ,sometimesreferredtoasthe“cominggeneration”, t The multi-type xlogx condition 1291 generalizes the concept of generation in the Galton–Watson process. Now, let 1 W = e−ατxh(σ ), (2.5) t x h(σ ) 0 xX∈It the individuals in I summed with time- and type-dependent weights, normed by the t reproductivevalueoftheancestor.ItcanbeshownthatW isamartingalewithrespectto t theσ-algebraF generatedbythelivesofallindividualsbornbeforetandthatE [W ]=1 t s t for all s∈S. Hence, W plays the role that W =Z /mn does in the Galton–Watson t n n process and the limit of Zχ turns out to involve the martingale limit W =lim W . t t→∞ t The main convergence result is of the form E [χ(α)] e−αtZχ→ π h(s)W t αβ b P -almostsurelyforπ-almostalls∈S ast→∞.Here,σ =sisthetypeoftheancestor, s 0 E [·]= E [·]π(ds) and χ(α) is the Laplace transform of χ(a) evaluated at the point π S s α. As in the Galton–Watson case, the question is when the martingale limit W is non- R degenerate. As W →W P -a.s. and E [W ]=1, L1-convergence with respect to P is t bs s t s equivalentto E [W]=1 (Durrett (2005), page 258).Note that althoughit is the process s Zχ that is of interest and not W itself, the asymptotics are determined by W , one of t t t many examples in probability of the usefulness of finding an embedded martingale. We are ready to formulate the general xlogx condition and the main convergence result. For the reproduction process ξ, define the transform ξ¯= e−αth(r)ξ(dr×dt) (2.6) ZS×R+ whichplaystheroleofX intheGalton–Watsonprocess(infact,inthatcase,ξ¯=X/m). For future reference, let us also state an alternative representation of ξ¯. Denote the sequence of birth times andtypes in the process ξ by τ(1),σ(1),τ(2),σ(2),... and so on. Then, ∞ ξ¯= e−ατ(i)h(σ(i)). (2.7) i=1 X The xlogx condition and convergence result are given in the following theorem from Jagers (1989). Theorem 2.1. Consider a general multi-typesupercritical Malthusian branching process with E [ξ¯log+ξ¯]<∞. π Then, E [W]=1 for π-almost all s, from which it follows that s E [χ(α)] e−αtZχ→ π h(s)W t αβ b 1292 P. Olofsson in L1(P ) for π-almost all s. s 3. Processes with immigration As mentioned in the Introduction, branching processes with immigration are crucial to our proof and in this section, we state the main result for such processes. Consider a generalbranchingprocesswherenewindividualsimmigrateintothepopulationaccording tosomepointprocessη(dr×dt)withpointsofoccurrenceandtypes(τ ,σ ),(τ ,σ ),.... 1 1 2 2 The kth immigrant initiates a branching process according to the population measure P . The immigration process has the transform σk ∞ ∞ η¯= e−αth(r)η(dr×dt)= e−ατkh(σk) Z0 k=1 X anditcanbeshownthattheprocessW isnowasubmartingaleratherthanamartingale t (which is intuitively clear because offspring of immigrants may be added to the set I ). The limit of W is therefore not automatically finite, but needs a condition on the t t immigration process, established by the following lemma from Olofsson (1996). Lemma 3.1. If η¯<∞ a.s., then W →W a.s. as t→∞, where W <∞ a.s. t 4. The size-biased population measure Recall that the LPP size-biased Galton–Watson measure was constructed from the size- biasedoffspringdistribution.Generalbranchingprocessesrequireamoregeneralconcept of size-bias. In a general process, the offspring random variable X is replaced by the reproductionprocess ξ, the size of which is properly measuredby the transform ξ¯which leads to the following definition. Definition 4.1. The size-biased life law P is defined as s ξ¯(ω) P (dω)=e P (dω). s s h(s) e From Jagers (1992), we know that the eigenfunction h is finite and strictly positive, so P is well defined. The following lemma follows immediately from the definition of P . s Lemema4.2. LetPs andPs beasaboveanddenotethesetofrealizationsofreproductieon processes by Γ, equipped with a σ-algebra G. Then, e (i) for A∈F, E [ξ¯;A] s P (A)= ; s h(s) e The multi-type xlogx condition 1293 (ii) for every G-measurable function g:Γ→R, E [ξ¯g(ξ)] s E [g(ξ)]= . s h(s) e Note that P is indeed a probability measure for all s∈S because s 1 e P (Ω)= E [ξ¯]=1, s s h(s) whereE [ξ¯]=h(s) followsfromtheedefinitionofξ¯in(2.6),togetherwith(2.1)and(2.2). s Also, note that a size-biased reproduction process always contains points because 1 P (ξ(S×R )=0)= E [ξ¯;ξ(S×R )=0]=0, s + s + h(s) e inanalogywiththe size-biasedoffspringdistributioninaGalton–Watsonprocess(ξ(S× R ) is the total number of offspring of an individual). + Toconstructthesize-biasedpopulationmeasure,let Pt andPt denotetherestrictions s s of the measures P and P to the σ-algebra F . The goal is to construct a measure P s s t s on (ΩI,FI) that is such that e e e Pt(dωI)=W (ωI)Pt(dωI) s t s for all t, where Wt is the intrinseic martingale defined in (2.5). This measure is the direct extension of the size-biased measures from Lyons et al. (1995) and Olofsson(1998). The constructionalsoinvolvesthe set I ,definedin(2.4),whoseindividuals allhavemothers t that are born up to time t. Thus, the type and birth time of an individual in I is t measurablewith respectto F ,which implies that W is also measurablewith respectto t t F . t The construction of the size-biased population measure extends the construction in Olofsson(1998) as follows.Startwith the ancestor,now called v , andchoose her life ω 0 0 accordingtothesize-biaseddistributionP (dω )= ξ¯0 P (dω ).Pickoneofherchildren, s 0 h(s) s 0 born in the reproduction process ξ , such that the ith child is chosen with probability 0 e−ατih(σi). Call this child v , let her steart a population according to the size-biased ξ¯0 1 population law P and give her sisters independent descendant trees such that sister j σi initiates a branching process according to the regular population law P . Continue in σj this way and defiene the measure P to be the joint distribution of the random tree and s the random path (v ,v ,...). We shall borrow a term from Athreya (2000) and refer to 0 1 the path (v ,v ,...) of chosen indieviduals as the spine. 0 1 Now,fix an individual x in the set I defined in (2.4) and consider the probability P , t s constrained by the individual x being chosen to be in the spine. Specifically, if S(x,t) denotes the event that the individual x in F is chosen to be in the spine and A∈FeI, t 1294 P. Olofsson then we consider the measure P (·;x) defined by s Pet(A;x)=Pt(A∩S(x,t)). (4.1) s s Denote by i the individual in thee first geneeration from whom x stems, that is, x=(i,y) forsomey.Hence,ifxisinthenthgeneration,thenitisoftheformx=(x ,x ,...,x ), 1 2 n where x =i, and we let y=(x ,...,x ). In words, y is the same individual as x when i 1 2 n is viewedas the ancestor.Let ω(j) denote the lives of all individuals when j is viewedas the ancestor to obtain Pst(dωI;x)= hξ¯(0s)Ps(dω0)· e−ατξ¯ih(σi) ·Pσt−i τi(dω(i);y)· Pσt−j τj(dω(j)), (4.2) 0 j6=i Y e e where the first factor describes the size-biased choice of life of the ancestor. The second factoristhe probabilitythatthe individuali inthefirstgenerationischosentobeinthe spine and the third factor describes the size-biased probability measure of the process starting from i, constrained by the individual y being in the spine. Finally, the fourth factor describes the regular population measures stemming from the individuals in the first generation who are not chosen to be in the spine. The following proposition states the desired relation between the size-biased measure Pt and the regular population measure Pt. s s Peroposition 4.3. Let Pt and Pt be the restrictions of P and P to the σ-algebra F s s s s t and let W be as in (2.5). Then, t e e dPt s =W . dPt t s e Proof. Let P (·;x) be as in (4.1). Then, s e Pt(dωI;x)= e−ατxh(σx)Pt(dωI). s h(s) s e Further, note that for the regular population measure, we have ξ0(t) Pt(dωI)=P (dω ) Pt−τj(dω(j)) s s 0 σj j=1 Y =Ps(dω0)Pσt−i τi(dω(i)) Pσt−j τj(dω(j)) j6=i Y h(σ ) 1 =ξ¯0Ps(dω0) ξ¯i h(σ )Pσt−i τi(dω(i)) Pσt−j τj(dω(j)). 0 i j6=i Y The multi-type xlogx condition 1295 Now, let τ (i) and σ (i) denote the birth time and type of the individual y when i is y y viewed as the ancestor. We then have τ =τ +τ (i) and σ =σ (i). Multiply Pt(dωI) x i y x y s by e−ατxh(σx) to obtain h(s) e−ατxh(σx)Pt(dωI) h(s) s = hξ¯(0s)Ps(dω0)· e−ατξ¯ih(σi) · e−ατyh(i()σh()σy(i)) ·Pσt−i τi(dω(i))· Pσt−j τj(dω(j)) 0 i j6=i Y = hξ¯(0s)Ps(dω0)· e−ατξ¯ih(σi) ·Pσt−i τi(dω(i);y)· Pσt−j τj(dω(j)) 0 j6=i Y e =Pt(dωI;x), s by (4.2). Finally, sum over x∈I to get e t Pt(dωI)= e−ατxh(σx)Pt(dωI)=W Pt(dωI), s h(s) s t s xX∈It e where ωI is suppressed, but understood as the argument of τ , σ and W . (cid:3) x x t To summarize, restricted to the σ-algebra F , the size-biased population measure P t s relates to the regular population measure P via the Radon–Nikodym derivative W = s t dPest, a relation that is a straightforwardextension from Olofsson (1998), which, in turen, dPt s is the straightforward extension of the original LPP method. This result is also similar in nature to Proposition 1 in Athreya (2000), which deals with a different martingale. The individuals v ,v ,... in the spine are of particular interest in our analysis. From 0 1 now on, we will use σ ,σ ,... to denote the types of the individuals in the spine. The 0 1 inter-arrivaltimes aredenoted T ,T ,... that is, T is the time betweenthe appearances 1 2 k ofthe(k−1)thandkthindividual.Inthesingle-typecasetreatedinOlofsson(1998),the individuals inthe spine havelivesthat arei.i.d., but the situationis now muchdifferent, with dependence between consecutive individuals introduced via types. As we shall see later,thisdependenceisalsowhatpreventstheproofofnecessityofthe xlogxcondition from carrying over from the single-type case. We now state important properties of the sequences of types and inter-arrival times in two lemmas. The first lemma deals solely with the type sequence. For the rest of this section, we use the notation P rather than P since the conditional probabilities we s consider do not depend on the initial type. e e Lemma 4.4. The sequence of types (σ ,σ ,...) in the spine is a homogeneous Markov 0 1 chain with transition probabilities h(r) P(σ ∈dr|σ =s)= µ(s,dr) k+1 k h(s) e b 1296 P. Olofsson and stationary distribution ν(ds)=h(s)π(ds). Proof. In a generic reproduction process ξ, denote the birth time and type of the ith offspringbyτ(i)andσ(i),respectively.Notethedifferencebetweenσ(i)andσ ,thelatter i being the type of the ith individual in the spine. The transition probabilities satisfy P(σ ∈dr|σ =s) k+1 k e−ατ(i)h(σ(i)) e= P(σ ∈dr,v =i|σ =s)= E δ (dr) k+1 k+1 k s ξ¯ σ(i) i i (cid:20) (cid:21) X X 1 e e1 ∞ = E [e−ατ(i)h(σ(i))δ (dr)]= E [e−αth(r)ξ(dr×dt)] h(s) s σ(i) h(s) s i Z0 X h(r) = µ(s,dr), h(s) where we have usbed Lemma 4.2 applied to the function e−ατih(σi) g(ξ)= . ξ¯ i X Next, let ν(ds)=h(s)π(ds). As µ(s,dr)π(ds)=π(dr), ZS we get b h(r) µ(s,dr)ν(ds)=ν(dr) h(s) Zs∈S and thus the Markov chain of types in the spine has stationary distribution ν=hdπ. (cid:3) b The second lemma deals with the sequence of types and inter-arrival times of the individuals in the spine. Lemma 4.5. The sequence of types and inter-arrival times (σ ,T ,σ ,T ,...) of the 0 1 1 2 individuals in the spine constitutes a Markov renewal process with transition kernel h(r) P(T ∈dt,σ ∈dr|σ =s)= e−αtµ(s,dr×dt) k+1 k+1 k h(s) and the expected evalue of T when σ ∼ν is k 0 E [T ]=β<∞, ν k where β was defined in (2.3). e