SURVIVAL, EXTINCTION AND APPROXIMATION OF DISCRETE-TIME BRANCHING RANDOM WALKS 1 FABIO ZUCCA 1 0 2 Abstract. Weconsiderageneraldiscrete-timebranchingrandomwalkonacountablesetX. We n relate local, strong local and global survival with suitable inequalities involving the first-moment a matrix M of the process. In particular we provethat, while the local behavior is characterized by J M, the global behavior cannot be completely described in terms of properties involving M alone. 7 Moreoverweshowthatlocallysurvivingbranchingrandomwalkscanbeapproximatedbysequences 1 ofspatiallyconfinedandstochasticallydominatedbranchingrandomwalkswhicheventuallysurvive locally if the (possibly finite) state space is large enough. An analogous result can be achieved by ] approximatingabranchingrandomwalkbyasequenceofmultitypecontactprocessesandallowing R a sufficiently large number of particles per site. We compare these results with the ones obtained P in thecontinuous-timecase and we give some examples and counterexamples. . h t a m Keywords: branching random walk, branching process, percolation, multitype contact process. [ AMS subject classification: 60J05, 60J80. 4 v 1. Introduction 1 7 The theory of branching random walks (BRWs from now on) has a long history dating back to 6 3 the earlier works on discrete-time branching processes (see [10] for the original work of Galton and . 3 Watson and [1, 13]). In the last 20 years much effort has been put in the study of continuous- 0 0 time BRWs (see [15, 17, 18, 21, 22] just to name a few). Among all the topics which have been 1 : studied there is the distinction between local and global survival (see for instance [24,26, 2, 3]) and v i the relation between multitype contact processes and BRWs (see [4]); besides, some papers have X r explored the subject of continuous-time BRWs on random environments (see for instance [12]). a Discrete-timeBRWshavebeenstudiedinitiallyasanaturalgeneralization ofbranchingprocesses (see [1, 5, 6, 7, 8, 13] just to mention a few). In recent years there has been a growing interest on discrete-time BRWs on deterministic graphs and on random environments (see [9, 11, 14, 19, 20, 23]). It is well-known that any continuous-time BRW admits a discrete-time counterpart with the same behavior (see Section 2.2), thus, under a certain point of view, discrete-time BRWs generalize continuous-time BRWs; this is the analogous of the construction of the jump chain associated to a continuous-time Markov chain. Hence discrete-time BRWs help to understand continuous-time processes as well (see for instance [2, 3]). There are many reasons for studying fairly simple and non-interacting models such as BRWs. One of them is the well-known connection with percolation theory. Besides, they are fundamental tools in the journey to understanding more sophisticated models: for instance, they are frequently usedascomparisontoprovesurvivalorextinctionofdifferentparticlesystemsusingthewell-known 1 technique called coupling. This last reason justifies our choice of studying truncated BRWs (see Sections 3.3 and 6). One of the differences between the discrete-time and the continuous-time settings is that in the second one the Markov property identifies a unique family of distributions for the time intervals between births and deaths and thus a unique family of laws for the random number of children of each particle. Hence, even if a continuous-time process seems to be a more realistic picture in view of applications, on the other hand it appears as a strong restriction if compared to the wide choice of reproduction laws that one can consider in the discrete-time case. Moreover, it is customary in the continuous-time setting, to study a one-parameter family of BRWs simultaneously in order to compute the intervals correspondingto different behaviors (see Section 2.2 for details). In contrast, the main results for discrete-time BRWs deal with one single process; nevertheless this is not a serious restriction and it is easy to see that the results on survival which are known for continuous- time BRWs can be obtained by applying the results for discrete-time BRWs to their discrete-time counterparts. Inthis sensethe results of this paper“generalize” those of [2,3]; we give moredetails in the outline of the paper below. We study the survival of a BRW in the first part of this paper. As for the topic of the second part, namely the approximation of a BRW, we see that, while the results on the spatial approximation (see Section 5) generalize those of [4, Section 3], the results about the approximation by truncated BRWs (see Section 6) cannot be seen as a generalization of the analogous results of [4, Section 5]. This is due to the fact that the discrete-time counterpart of a continuous-time truncated BRW is not a discrete-time truncated BRW. Indeed note that in the definition of a truncated BRW (see Section 3.3 and [4, Section 2]) the time scale is essential. Theaimof thispaperisthreefold: wewanttostudytheglobal, local andstronglocalbehavior of discrete-time BRWs, the possibility of approximating BRW with a sequence of “spatially confined” and stochastically dominated BRWs and, finally, the approximation of a BRW by means of a sequence of truncated BRWs which are, essentially, multitype contact processes. The results of this paper generalize those of [2, 3, 4] not only because the class of discrete-time BRWs extends the class of continuous-time BRWs butalso since some of the theorems are stronger and require weaker hypotheses. Here is the outline of the paper. In Section 2 we define discrete-time BRWs and discuss their main properties. Thisis anaturalgeneralization oftheclass ofmultitype Galton–Watson branching process (see [13, Section II.2])similar tothose introducedin other papers(see [2, 3,11,23] forsome recent references). In Section 2.2 we briefly introduce continuous-time BRWs and we construct their discrete-time counterparts. In Section 3 we give the technical definitions and we state some basic results. Section 4.1 is devoted to the study of local and global survival. The main result (Theorem 4.1) characterizes local survival by means of the first-moment matrix M of the process (see Section 2.1), and global survival using a possibly infinite-dimensional generating function associated to the BRW. This theorem generalizes [3, Theorems 4.1, 4.3 and 4.7]. An independent 2 proof of Theorem 4.1(1) appeared in [23, Theorem 2.4]. A similar, but weaker, result for a limited class of continuous-time BRWs can be found in [24] and, for the whole class of continuous-time BRWs, in [2, 3]. We show that, in general, global survival cannot be characterized in terms of the first-moment matrix alone (see Example 4.4), nevertheless some functional inequalities involving only the first-moment matrix M must hold in case of global survival (see Theorem 4.1). We introduceaclassoffairlyregularBRWs,whichincludesBRWsonquasi-transitivegraphsandBRWs on regular graphs, for which we can give a complete characterization of global survival in terms of the matrix M. Roughly speaking, the regularity that we require is the possibility of mapping these BRWs into multitype Galton–Watson processes for which a complete characterization of the global survival is known (see for instance [13] and Theorem 4.1(5)). In Section 4.2 we show that local survival can be described, as the global one, by means of an infinite-dimensional generating function; this is the key to discuss strong local survival. This kind of survival was already studied, for instance, in [11] for a BRW on a random environment on Z. Here, using a different technique, we are able to treat a large class of transitive BRWs on deterministic graphs. In Section 5 we first generalize a Theorem due to Sarymshakov and Seneta (see [25, Theorem 6.8]) and then we use this result (Theorem 5.1) to obtain an approximation of a general BRW, which is not necessarily irreducible, by means of a sequence of spatially confined BRWs (Theorem 5.2); this last one is a generalization of [4, Theorem 3.1]. Here we obtain, as a particular case, that if we have a surviving process, then by confining it to a sufficiently large (possibly finite and not necessarily connected) proper subgraph the resulting BRW survives as well; this result was already known for irreducible BRWs confined to connected subgraphs. At the end of the section we give some examples and counterexamples. Section 6deals with theapproximation of the BRW witha sequence of truncated BRWs. The key to obtain such a result is the comparison of our process with a suitable oriented percolation (as explained in Section 6.1). The strategy is then applied to some classes of regular BRWs in Theorem 6.5 (concerning local behavior) and Theorem 6.7 (concerning global behavior). Finally in Section 7 we briefly discuss some open questions and possible future developments. 2. The dynamics: discrete and continuous time 2.1. Discrete-time branching random walks. We start with the construction of a generic discrete-time BRW (see also [3] where it is called infinite-type branching process) on a set X which isatmostcountable. Tothisaimweconsiderageneralfamilyµ = µ ofprobabilitymeasures x x∈X { } on S := f : X N : f(y) < . The updating rule is the following: a particle at a site X { → y ∞} x X lives one unit of time, then, with probability µ , a function f S is chosen and the P x X ∈ ∈ original particle is replaced by f(y) particles at y, for all y X; this is done independently for all ∈ the particles. Here is another equivalent dynamics: define the function H : S N as H(f) := f(x) X → x∈X and denote by ρ the measure on N defined by ρ () := µ (H−1()); this is the law of the random x x x P · · 3 number of children of every particle living at x. For each particle, independently, we pick a number n at random, according to the law ρ , and then we choose a function f H−1(n) with probability x ∈ µ (f)/ρ (n) µ (f)/ µ (g) and, again, we replace the particle at x with f(y) particles x x ≡ x g∈H−1(n) x at y (for all y X). P ∈ More precisely, given a family fi,n,x i,n∈N,x∈X of independent SX-valued random variable such { } that, for every x X, fi,n,x i,n∈N have the common law µx, then the discrete-time BRW ηn n∈N ∈ { } { } is defined iteratively as follow ηn(y) ∞ j η (x)= f (x) = 1l f (x) (2.1) n+1 i,n,y {ηn(y)=j} i,n,y y∈X i=1 y∈X j=0 i=1 X X XX X starting from an initial condition η . We denote the BRW by (X,µ); the initial value will beclearly 0 indicated each time. Denote by m := f(y)µ (f) the expected number of particles from x to y (that is, xy f∈SX x the expected number of children that a particle living at x can send to y) and suppose that P sup m < + ; most of the results of this paper still hold without this hypothesis, x∈X y∈X xy ∞ nevertheless it allows us to avoid dealing with an infinite expected number of offsprings. Note that P m = nρ (n) =:ρ¯ . y∈X xy n≥0 x x (n) We denote by M = (m ) the first-moment matrix and by m the entries of the matrix P P xy x,y∈X xy Mn. We call diffusion matrix the matrix P with entries p(x,y) = m /ρ¯ . xy x Fromequation(2.1),itisstraightforwardtoprovethattheexpectednumberofparticles, starting from an initial condition η , satisfies the recurrence equation Eη0(η (x)) = (Eη0(η )M)(x) = 0 n+1 n m Eη0(η (y)) hence y∈X yx n P Eη0(η (x)) = m(n)η (y). (2.2) n yx 0 y∈X X Moreover, the family of probability measures, µ induces in a natural way a graph structure x x { } on X that we denote by (X,E ) where E := (x,y) : m > 0 (x,y) : f S ,µ (f) > µ µ xy X x { } ≡ { ∃ ∈ 0,f(y) > 0 . Roughly speaking, (x,y) is and edge if and only if a particle living at x can send a } child at y with positive probability (from now on wpp). We say that there is a path from x to y, and we write x y, if it is possible to find a finite sequence x n such that x = x, x = y and → { i}i=0 0 n (x ,x ) E for all i = 0,...,n 1. If x y and y x we write x ⇋ y. i i+1 µ ∈ − → → Recall that the matrix M = (m ) is said to be irreducible if and only if the graph (X,E ) xy x,y∈X µ is connected, otherwise we call it reducible. We denote by deg(x) the degree of a vertex x, that is, the cardinality of the set y X :(x,y) E . µ { ∈ ∈ } The colony can survive in different ways: we say that the colony survives locally wpp at y X ∈ starting from x X if ∈ Pδx(limsupη (y) > 0) > 0; n n→∞ 4 we say that it survives globally wpp starting from x if Pδx η (w) > 0, n N > 0. n ∀ ∈ (cid:16)wX∈X (cid:17) Moreover, following [11], we say that the there is strong local survival wpp at y X starting from ∈ x X if ∈ Pδx(limsupη (y)> 0) = Pδx η (w) > 0, n N > 0. n n ∀ ∈ n→∞ (cid:16)wX∈X (cid:17) From now on when we talk about survival, “wpp” will be tacitly understood. Often we will say simply that local survival occurs “starting from x” or “at x”: in this case we mean that x = y. Clearly local survival implies global survival and, if x y then local survival at x implies local → survival at y starting from x. Analogously, if x y then global survival starting from y implies → global survival starting from x. Moreover if x ⇋ y then local (resp. global) survival starting from x is equivalent to local (resp. global) survival starting from y. In particular, if M is irreducible then the process survives locally (resp. globally) at one vertex if and only if it survives locally (resp. globally) at every vertex. Assumption 2.1. We assume henceforth that for all x X there is a vertex y ⇋ x such that ∈ µ (f : f(w) = 1) < 1, that is, in every equivalence class (with respect to ⇋) there is at least y w⇋y one vertex where a particle can have a number of children different from one wpp. P Remark2.2. ThepreviousassumptionguaranteesthattherestrictionoftheBRWtoanequivalence class is nonsingular (see [13, Definition II.6.2]). There is a technical reason behind the previous assumption: if we consider the classical Galton–Watson branching process, that is, X := x is a { } singleton and µ can be considered as a probability measure on N, then it is well-known that x if µ (1) = 1 then m = 1 and there is survival with probability 1; x xx • if µ (1) < 1 then there is survival wpp if and only if m > 1. x xx • Hence the condition m > 1 is equivalent to survival under Assumption 2.1. This will be used xx implicitly in Theorem 4.1(1) and (5) (but it is not needed, for instance, in Theorem 4.1(2), (3) and (4)). A particular, but meaningful, subclass of discrete-time BRWs is described by the following updating rule: a particle at site x lives one unit of time and is replaced by a random number of children, withlaw ρ . Thechildren aredispersedindependentlyon thesites of thegraph, according x to a stochastic matrix P. Note that this rule is a particular case of the general one, since here one simply chooses f(y)! µ (f)= ρ f(y) y (p(x,y))f(y), f S . (2.3) x x X f(y)! ∀ ∈ y ! Py y X Y Clearly in this case the expected number oQf children at y of a particle living at x is 5 m = p(x,y)ρ¯ . (2.4) xy x 2.2. Continuous-time branching random walks. Continuous-time BRWs have been studied extensively by many authors; in this section we make use of a natural correspondence between continuous-time BRWs and discrete-time BRWs which preserves both local and global behaviors. Incontinuoustimeeachparticlehasanexponentiallydistributedrandomlifetimewithparameter 1. The breeding mechanisms can be regulated by putting on each edge (x,y) and for each particle at x, a clock with Exp(λk )-distributed intervals (where λ > 0), each time the clock rings the xy particle breeds in y. Equivalently one can associate to each particle at x a clock with Exp(λk(x))- distributedintervals(k(x) = k ): eachtimetheclockringstheparticlebreedsandtheoffspring y xy is placed at random according to a stochastic matrix P (where p(x,y) = k /k(x)). P xy Theformal construction of a BRW in continuous time is based on the action of a semigroup with infinitesimal generator f(η):= η(x) ∂−f(η)+λ k ∂+f(η) , (2.5) L x xy y xX∈X (cid:16) yX∈X (cid:17) where ∂±f(η):= f(η δ ) f(η). x ± x − Every continuous-time BRW has a discrete-time counterpart and they both survive or both die (locally or globally); here is the construction. The initial particles represent the generation 0 of the discrete-time BRW; the generation n+1 (for all n 0) is obtained by considering the children of ≥ all the particles of generation n (along with their positions). Clearly the progenies of the original continuous-time BRW and of its discrete-time counterpart are both finite (or both infinite) at the same time. In this sense the theory of continuous-time BRWs, as long as we are interested in the probability of survival (local, strong local and global), is a particular case of the theory of discrete-time BRWs. Elementary calculations show that each particle living at x, before dying, has a random number of offsprings given by equation (2.3) where 1 λk(x) i k xy ρ (i) = , p(x,y) = , (2.6) x 1+λk(x) 1+λk(x) k(x) (cid:18) (cid:19) and this is the law of the discrete-time counterpart. Using equation (2.4), it is straightforward to show that m = λk . From equation (2.6) we have that, for any λ > 0, the discrete-time xy xy counterpart satisfies Assuption 2.1. Given x X, two critical parameters are associated to the continuous-time BRW: the global 0 ∈ survival critical parameter λ (x ) and the local survival one λ (x ). They are defined as w 0 s 0 λw(x0) := inf λ > 0: Pδx0 ( t: ηt = 0) < 1 { ∃ } (2.7) λs(x0) := inf λ > 0: Pδx0 ( t¯: ηt(x0)= 0, t t¯) < 1 , { ∃ ∀ ≥ } where 0 is the configuration with no particles at all sites and Pδx0 is the law of the process which starts with one individual in x . If the graph (X,E ) is connected then these values do not depend 0 µ 6 on the initial configuration, provided that this configuration is finite (that is, it has only a finite number of individuals), nor on the choice of x . See [2] and [3] for a more detailed discussion on 0 the values of λ (x ) and λ (x ). w 0 s 0 3. Technical definitions In this section we give some technical definitions and we state some basic facts which are widely used in the rest of the paper. 3.1. Reproduction trails. A fundamental tool which is useful throughout the whole paper is the reproductiontrail; thisallows ustogiveanalternative construction oftheBRW.Wefixaninjective map φ :X X Z N N. Let the family fi,n,x i,n∈N,x∈X be as in Section 2.1 and let η0 be the × × × → { } initial value. For any fixed realization of the process we call reproduction trail to (x,n) X N a ∈ × sequence (x ,i ,1),(x ,i ,j ),...,(x ,i ,j ) (3.8) 0 0 1 1 1 n n n such that η (x ) i < 0, 0 < j f (x ) and φ(x ,x ,i ,j ) = i , where 0 < l n. − 0 0 ≤ 0 l ≤ il−1,l−1,xl−1 l l−1 l l−1 l l ≤ The interpretation is the following: i is the identification number of the particle, which lives at x n n at time n and is the j -th offspring of its parent. The sequence x ,x ,...,x is the path induced n 0 1 n { } by the trail (sometimes, we say that the trail is based on this path). Given any element (x ,i ,j ) l l l of the trail (3.8), we say that the particle identified by i is a descendant of generation n l of the n − particle identified by i and the trail joining them is (x ,i ,j ),...,(x ,i ,j ). We say also that the l l l l n n n trail of the particle i is a prolongation of the trail of the particle i . n l Roughly speaking the trail represents the past history of each single particle back to its original ancestor, that is, the one living at time 0; we note that from the couple (n,i ), since the map φ is n injective, we can trace back the entire genealogy of the particle. The random variable η (x) can n be alternatively defined as the number of reproduction trails to (x,n). This construction does not coincide with the one induced by the equation (2.1) butthe resulting processes have the same laws. Finally, whenµ doesnotdependonx X, itis worthmentioninganother possibleconstruction x ∈ of the process as a Markov chain indexed by trees (see for instance [28, Section 5.C]). 3.2. Generating functions. Later onwewillneedsomegenerating functions,both1-dimensional andinfinitedimensional. DefineTn := m(n)andϕ(n) := m m m x y∈X xy xy x1,...,xn−1∈X\{y} xx1 x1x2··· xn−1y (by definition ϕ(0) := 0 for all x,y X). Tn is the expected number of particles alive at time n xy ∈ P x P (n) when the initial state is a single particle at x. The interpretation of ϕ is more subtle. It plays xy in the BRW theory the same role played the first-return probabilities in random walk theory (see (n) [28, Section 1.C]). Roughly speaking, ϕ is the expected number of particles alive at y at time xy n when the initial state is just one particle at x and the process behaves like a BRW except that every particle reaching y at any time i < n is immediately killed (before breeding). 7 Let us consider the following family of 1-dimensional generating functions (depending on x,y ∈ X) ∞ ∞ Γ(x,y λ) := m(n)λn, Φ(x,y λ) := ϕ(n)λn. | xy | xy n=0 n=1 X X It is easy to prove that Γ(x,x λ) = Φ(x,x λ)i for all λ > 0, hence | i∈N | −1 1 P Γ(x,x λ) = , λ C : λ < limsup n m(n) , (3.9) xy | 1−Φ(x,x|λ) ∀ ∈ | | (cid:18) n∈N q (cid:19) −1 and we have that limsup n m(n) = max λ R : Φ(x,x λ) 1 for all x X. In n∈N xy { ∈ | ≤ } ∈ (cid:18) q (cid:19) particular Φ(x,x 1) 1 if and only if limsup n m(n) 1. | ≤ n∈N xy ≤ To the family µ we can associate anotheqr generating function G: [0,1]X [0,1]X which x x∈X { } → can be considered as an infinite dimensional power series (see also [3, Section 3]). More precisely, for all z [0,1]X the function G(z) [0,1]X is defined as follows ∈ ∈ G(z x) := µ (f) z(y)f(y). (3.10) x | fX∈SX yY∈X Note that G is continuous with respect to the pointwise convergence topology of [0,1]X and non- decreasing with respect to the usual partial order of [0,1]X (see [3, Sections 2 and 3] for further details); notethatv < w meansthatv(x) w(x)forallx X andv(x ) < w(x )forsomex X. 0 0 0 ≤ ∈ ∈ All these generating functions will be useful for instance in Section 4.1 to prove Theorem 4.1 and to discuss Examples 4.4 and 4.5. In Section 4.2 more properties of G will be established in order to prove some results related to local survival and strong local survival. Note that the generating function G can be explicitly computed, for instance, if equation (2.3) holds. Indeed in this case it is straightforward to show that G(z x) = F(Pz(x)) where F(y) = | ∞ ρ(n)yn and Pz(x) = p(x,y)z(y). In particular if ρ(n) = 1 ( ρ¯x )n (for instance if n=0 y∈X 1+ρ¯x 1+ρ¯x we are dealing with the discrete-time counterpart of a continuous-time BRW, see equation (2.6)), P P we have G(z x) = 1 , that is, | 1+ρ¯x(1−Pz(x)) 1 G(z) = (3.11) 1+M(1 z) − where 1(x) := 1 for all x X, the ratio is to be intended as coordinatewise and Mv(x) := ∈ m v(y) for all v [0,1]X; in this case m is given by equation (2.4). y∈X xy ∈ xy P 3.3. Coupling. Thefamily of BRWs can beextended to themoregeneral class of truncated BRWs whereamaximumofm N particlespersiteareallowed; wedenotethisprocessasaBRW . m ∈ ∪{∞} The general dynamics is given by the following recursive relation ηnm(y) ∞ j ηm (x)= m f (x) =m 1l f (x). (3.12) n+1 ∧ i,n,y ∧ {ηnm(y)=j} i,n,y y∈X i=1 y∈X j=0 i=1 X X XX X 8 Clearly the BRW is the usual BRW and the BRW is a contact process. ∞ 1 Inthefollowing sections wewanttocomparetwo (ormore)truncated BRWs. Whatwearegoing to state is a discrete-time analogous of a well-known technique called coupling. Roughly speaking, given two processes η and ξ , under certain conditions one can find two possibly different n n n n { } { } processes η′ and ξ′ with the same finite-dimensional distribution as the original ones and { n}n { n}n such that if η′ ξ′ then η′ ξ′ for all n N. 0 ≥ 0 n ≥ n ∈ The condition that we use is the following: suppose we have two families µ = µ and x x∈X { } ν = ν such that µ (F−1()) = ν () for all x X and for some family of functions F { x}x∈X x x · x · ∈ { x}x∈X such that F : supp(µ ) supp(ν ) and F (f) f for all f supp(µ ). The meaning of the maps x x x x x → ≤ ∈ F is as follows: given any possibleoffspring outcome g of a particle living at x (breeding according x to the law ν ) there is a set of outcomes which occurs with the same probability, namely F−1(g), x x for a particle living at x (breeding according to the law µ ); furthermore the number of newborn x particles in the first case is pointwise not larger than the number of newborns in the second one. This suggests that the BRW (X,µ), in some sense, dominates the BRW (X,ν). Under the previous condition, given k ≤ m ≤ ∞, it is possible to construct a process {(ηnm,ξnk)}n∈N such that (1) {ηnm}n∈N is a BRWm behaving according to µ; (2) {ξnk}n∈N is a BRWk behaving according to ν; (3) ηm ξk implies ηm ξk for all n N a.s. 0 ≥ 0 n ≥ n ∈ To check (3), note that, for any x X, given the family of random variables fi,n,x i,n∈N (with ∈ { } law µx) then Fx(fi,n,x) i,n∈N are iid with common law νx. Whence the evolution equation of { } {ηnm}n∈N is (3.12) and, similarly, {ξnk}n∈N satisfies ξn(y) ξk (x) = k F f (x), (3.13) n+1 ∧ x◦ i,n,y y∈X i=1 X X whence (3) follows by induction using equations (3.12) and (3.13). A typical choice for the family of functions F is F (f) := f (where Y X) which can be seen as a (truncated) BRW x x∈X x Y { } | ⊆ restricted to Y, that is, all the offsprings sent outside Y are killed. This procedure of comparison is called coupling between {ηnm}n∈N and {ξnk}n∈N. We note that if {ηnm}n∈N dies out locally (resp. globally) a.s. then {ξnk}n∈N dies out locally (resp. globally) a.s. More generally a coupling between {ηnm}n∈N and {ξnk}n∈N is a choice of a common law {ζx}x∈X for the process {(ηnm,ξnk)}n∈N such that ζx((f,g) : f ≥ g, f,g ∈ SX) = 1 for all x ∈ X and ζ ((f,g)) = µ (f), ζ ((f,g)) = ν (g). In many situations this construction of g∈SX x x f∈SX x x ζ can be carried out effortlessly. Px x∈X P { } 4. Local, strong local and global survival 4.1. Local and global survival. Consider the discrete-time BRW generated by the family µ = µ of probabilities and suppose now that the process starts with one particle at x , hence x x 0 { } 9 η = δ . In this section we want to find conditions for global, local and strong local survival. 0 x0 Recall that if X is finite then local survival is equivalent to global survival: this is trivial for an irreducible matrix M; in the general case global survival, starting from x , is equivalent to local 0 survival at some y X such that x y (the same arguments of [3, Remark 4.4] apply). 0 ∈ → Theorem 4.1. Let (X,µ) be a BRW. (1) There is local survival starting from x if and only if limsup n m(n) > 1. 0 n→∞ x0x0 (2) There is global survival starting from x if and only if there existsqz [0,1]X, z(x ) < 1, 0 0 ∈ such that G(z x) z(x), for all x. | ≤ (3) If there is global survival starting from x , then there exists v [0,1]X, v(x ) > 0, such that 0 0 ∈ a) Mv v ≥ b) for all x, Mv(x) = v(x) if and only if G(1 (1 t)v;x) = 1 (1 t)v(x), t [0,1]. − − − − ∀ ∈ (4) If there is global survival starting from x0, then liminfn∈N n x∈Xm(xn0)x ≥ 1. (5) If X is a finite set then there is global survival startqing from x if and only if P 0 liminfn∈N n x∈Xmx(n0)x > 1. q P Proof. (1) Fix x X, consider a path Π := x ,x ,...,x = x and consider its number 0 0 1 n 0 ∈ { } of cycles # i = 1,...,n : x = x ; the expected number of trails based on such a path i 0 { } is n−1m . This is also the expected number of particles living at x , descending i=0 xixi+1 0 from the original particle at x and whose genealogy is described by the path Π, that is, Q 0 their mothers were at x , their grandmothers at x and so on. We associate to the n−1 n−2 BRW starting at x a Galton–Watson branchingprocess with a different time scale as in [2, 0 Theorem 3.1] and [3, Theorems 4.1 and 4.7] where the n-th generation is the set of particles living at x whose trail are based on paths with n cycles. This process is nonsingular due 0 to Assumption 2.1, and its survival is equivalent to the local survival of the BRW. The expected number of children in this branching process is Φ(x,x 1), thus we have a.s. local | extinction if and only if Φ(x,x 1) 1, that is, limsup n m(n) 1. | ≤ n∈N xy ≤ (2) Let q¯ (x) and q¯(x) be the probability of global extinctionqbefore or at the n-th generation n and the probability of global extinction respectively, starting from a single initial particle at x. Clearly q¯ = G(q¯ ) and q¯ q¯ as n . If q¯(x ) < 1 then take z = q¯ as a n+1 n n 0 → → ∞ solution of G(z) z (remember that G is continuous). On the other hand, if there exists ≤ z [0,1]X such that z(x )< 1 and G(z) z, since G is nondecreasing and q¯ = 0 z then 0 0 ∈ ≤ ≤ q¯ z for all n N, hence q¯ z. Thus q¯(x ) < 1. n 0 ≤ ∈ ≤ (3) Let z such that G(z) z, z(x ) < 1. Define v = 1 z, take the derivative of the 0 ≤ − convex function φ(t) := G(1 (1 t)v;x) 1+(1 t)v(x) at t = 1 and remember that − − − − φ(0) φ(1) = 0. ≤ 10