# A note on the transience of critical branching random walks on the line.

Gantert and Muller (2006) proved that a critical branching random walk (BRW) on the integer lattice is transient by analyzing this problem within the more general framework of branching Markov chains and making use of Lyapunov functions. The main purpose of this note is to show how the same result can be derived quite elegantly and even extended to the nonlattice case within the theory of weighted branching processes. This is done by an analysis of certain associated random weighted location measures which, upon taking expectations, provide a useful connection to the well established theory of ordinary random walks with i.i.d. increments. A brief discussion of the asymptotic behavior of the left- and rightmost particles in a critical BRW as time goes to infinity is provided in the final section by drawing on recent work by Hu and Shi (2008).

Keywords: branching random walk, critical regime, recurrence, transience, minimal and maximal position, random weighted location measure, renewal theory

1 Introduction

Consider a cloud of particles which moves on the line as follows. Initially there is one particle sitting at the origin which after one unit of time splits into a random number of new particles having distribution [([p.sub.j]).sub.j [greater than or equal to] 0], where [p.sub.0] = 0. The daughter particles are then independently displaced relative to their mother's site in accordance with the same step size distribution Q, say. This process continues indefinitely, i. e., each new born particle splits after one unit of time in accordance with [([p.sub.j]).sub.j [greater than or equal to] 0], and the relative displacement of each daughter particle with respect to its mother's site has distribution Q and is independent of the relative displacements of its siblings as well as of the history of the process. This model describes a special nonexfinctive BRW the specialization being that the relative displacements of siblings (given their total number) are i.i.d. rather than chosen from a general point process on R. Likewise, one may adopt the viewpoint as in Gantert and Muller (2006) that any new born particle lives forever and performs a random walk with step size distribution Q. Right before each jump it produces j - 1 daughter particles with probability [p.sub.j] (j [greater than or equal to] 1) which start independent random walks of the same kind at initial positions relative to their mother's site chosen in accordance with Q. Note that the cloud size evolves as a simple nonextinctive Galton-Watson process [([Z.sub.n]).sub.n [greater than or equal to] 0] with one ancestor and offspring distribution [([p.sub.j]).sub.j [greater than or equal to] 0. A more detailed specification of the model will be given in Section 2 after having described the main problem to be addressed in this note.

Suppose that Q has positive mean but also positive mass on (-[infinity], 0). Then all particles in the cloud are moving towards [infinity] with probability one while, on the other hand, their trajectories will also have negative excursions. Hence the ever increasing number of independently moving particles might cause bounded neighborhoods of 0 be visited infinitely often if the cloud is growing fast enough. We are thus led to the question whether there exists a branching threshold [m.sup.*] such that any bounded neighborhood of 0 (or any other x [member of] R in the same irreducibility class) is recurrent, i.e., a.s. visited by infinitely many particles, if m > [m.sup.*], while being transient, if m < [m.sup.*], where m := [[summation].j [greater than or equal to] 1] [jp.sub.j] is the mean offspring (including the reproducing particle). In the case of an irreducible lattice random walk, the positive answer has been given by Comets et al. (1998) in their analysis of the more general BRW in random environment. Moreover, transience holds true in the boundary case m = [m.sup.*], as recently been proved by Gantert and Muller (2006) within the more general framework of branching Markov chains where the random walk is replaced with an arbitrary irreducible Markov chain on a countable state space, see Benjamini and Peres (1994) for the basics and also the classification of possible regimes of such models as to their recurrence behavior. Further results on the recurrence or transience of various generalizations of the classical BRW may be found in Machado and Popov (2000, 2003); Machado et al. (2001); Menshikov and Volkov (1997). An essential tool in these works is the use of Lyapunov test functions, and this constitutes the main difference to the present note. Our main purpose is in fact to demonstrate how certain random weighted location measures to be defined in Section 2 and their connection to renewal and fluctuation theory for classical random walks (cf. Section 3) may be utilized as an alternative tool in order to not only reproduce the afore-mentioned results for lattice BRWs but to provide also without much additional effort an extension to the situation where Q is nonlattice. Our main result will be stated in Section 2 after the necessary formal details including a definition of recurrence and transience for BRWs. The proof will be given in Section 4. Finally, Section 5 provides some fairly sharp information on the position of the leftmost and the rightmost particle in a critical BRW as time goes to infinity. Our theorems stated there follow without much ado from a recent result by Hu and Shi (2008).

2 Model description and main results

Let V be the infinite Ulam-Harris tree with vertex set [[union].sub.n [greater than or equal to] 0] [N.sup.n] where N = {1, 2, ...} denotes the set of positive integers and [N.sup.0] := {[empty set]} by convention. Each vertex v = ([v.sub.1], ..., [v.sub.n]) of length [absolute value of v] = n, shortly written as [v.sub.1][v.sub.2] ... [v.sub.n] hereafter, is uniquely connected to the root [empty set] by the path [empty set] [right arrow] [v.sub.1] [right arrow] [v.sub.1] [v.sub.2] [right arrow] ... [right arrow] [v.sub.1] [v.sub.2] ... [v.sub.n]. If w = [w.sub.1] ... [w.sub.m] denotes another vertex, we write vw for the concatenation of v and w, i.e., for [v.sub.1] ... [v.sub.n] [w.sub.1] ... [w.sub.m]. In the present context, each v is interpreted as a (potential) particle of the n-th generation. It is the mother of the successors [vi := [v.sub.1] ... [v.sub.n] i, i [member of] N, and an ancestor of any vw, w [member of] V. In places where it occurs [v.sub.1] ... [v.sub.n] := [empty set] is stipulated whenever n = 0.

The following weighted branching model assigns a random weight L(v) [member of] {0,1} and a random position S(v) in R to each node v of the tree, where L(v) = 1 means that particle v is actually alive. Let ([OMEGA], U, P) be a given probability space which carries i.i.d. random sequences

T(v) [cross product] X(v) := [([T.sub.i](v), [X.sub.i](v)).sub.i [greater than or equal to] 1] : [OMEGA] [right arrow] [({0, 1} x R).sup.N], v [member of] V.

Furthermore, [([T.sub.i](v)).sub.i [greater than or equal to] 1] and [([X.sub.i](v)).sub.i [greater than or equal to] 1] are independent as well for each v [member of] V with

P([T.sub.1](v) = ... = [T.sub.j](v) = 1,[T.sub.j+1](v) = [T.sub.j+2](v) = ... = 0) = [p.sub.j]

for j [greater than or equal to] 1 and [X.sub.1](v), [X.sub.2](v), ... being i.i.d. having common distribution Q. Put L([empty set]) := 1, S([empty set]) := 0, and define recursively

L(vi) := L(v)[T.sub.i](v) and S(vi) := S(v) + [X.sub.i](v)

for v = [v.sub.1] ... [v.sub.n] [member of] V and i [member of] N, thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The total size of the n-th generation (number of particles alive at time n) is now given by

[Z.sub.n] := [summation over ([absolute value of v=n])] L(v)

for n [greater than or equal to] 0 and forms a simple Galton-Watson process with offspring distribution [([p.sub.j]).sub.j [greater than or equal to] 0]. Throughout this article, we will make the standing assumption that [([Z.sub.n]).sub.n [greater than or equal to] 0] is supercritical, i.e., m > 1 or, equivalently, [p.sub.1] < 1 (as [p.sub.0] = 0). In order to describe the positions of all living particles at time n, we introduce the random location measures

[[PI].sub.n] := [summation over ([absolute value of v]=n])] L(v)[[delta].sub.S(v)], n (greater than or equal to) 0

and call [([[PI]].sub.n]).sub.n [greater than or equal to] 0] a BRW on R with offspring distribution [([p.sub.j]).sub.j [greater than or equal to] 0] and increment distribution Q. Put also

[PI] := [summation over n ([greater than or equal to] 0]) [[PI].sub.n] = [summation over (v[member of]V)] L(v)[[delta].sub.S(v)]

which is the associated overall empirical occupation measure and will be called branching renewal measure of [([[PI].sub.n]).sub.n [greater than or equal to] 0].

Definition 2.1 A BRW [([[PI].sub.n]).sub.n [greater than or equal to] 0] with increment distribution Q is called d-arithmetic if Q is d-arithmetic, i.e., if

d := sup{c > 0 : Q(cZ) = 1} > 0,

and is called nonarithmetic (0-arithmetic) otherwise.

So the lattice-span of [([[PI].sub.n]).sub.n [greater than or equal to] 0] is just the lattice-span d of its increment distribution Q (= 0 in the nonarithmefic case). Notice that d = [infinity] if Q = [[delta].sub.0]. Excluding this case, we may and will assume hereafter w.l.o.g. that d = 1 whenever d > 0. It is convenient to further define [G.sub.0] := R and [G.sub.1] := Z.

Since our interest lies in those BRWs that do not move in one direction only we make the standing assumption hereafter that the increment distribution Q puts mass on (-[infinity], 0) as well as (0, [infinity]), that is,

Q((-[infinity], 0)) [conjunction] Q((0, [infinity])) > 0.

Such a Q as well as an associated BRW is called genuinely two-sided hereafter. The definitions of recurrence and transience for a genuinely two-sided BRW [([[PI].sub.n]).sub.n [greater than or equal to] 0] are preceded by the following classification result (a zero-one law) for its branching renewal measure [PI]. For intervals I [subset] R, let [H.sub.I] : R [right arrow] [0, 1] be the function given by

[H.sub.I](t) := P([PI](t + I) < [infinity]), t [member of] R.

Then put H := [H.sub.(-[infinity],0)], thus H(t) = P([PI]((-[infinity],t)) < [infinity]), and [H.sub.[epsilon]] := [H.sub.(-[epsilon], [epsilon])], thus [H.sub.[epsilon]](t) = P([PI]((t - [epsilon], t + [epsilon])) < [infinity]).

Proposition 2.2 Let [([[PI].sub.n]).sub.n [greater than or equal to] 0] be a genuinely two-sided, d-arithmetic BRW, d [member of] {0, 1}, with increment distribution Q. Suppose also [p.sub.0] = 0 and [p.sub.1] < 1. Then either [H.sub.[epsilon]] [equivalent to] 0 for all [member of] > 0, or [H.sub.[epsilon]] [equivalent to] 1 for all [epsilon] > 0. Similarly, either H [equivalent to] 0 or H [equivalent to] 1.

Remark 2.3 (a) Plainly, in the 1-arithmetic case the dichotomy for the [H.sub.[epsilon]] reduces to the statement that the [PI]({n}), n [member of] Z, are either all a.s. finite or all a.s. infinite. Moreover, a reflection argument (replace X(v) with -X(v) for each v [member of] V) shows that the zero-one dichotomy holds for [H.sub.(0,[infinity])] as well.

(b) If Q is concentrated on one halfline and having an atom at 0, then Proposition 2.2 may fail. For instance, if Q([N.sub.0]) = 1, p := Q({0}) [member of] (0,1) and mp > 1, then it is easily seen that P([PI]({0}) < [infinity]) (= [H.sub.[epsilon](0) for [epsilon] [member of] (0,1)) equals the extinction probability [q.sup.*] [member of] (0, 1) of the supercritical Galton-Watson process defined as [Z.sup.*.sub.n] := [[summation].sub.[absolute value of v]=n] L(v)[1.sub.{S(v)=0}], n [greater than or equal to] 0. The function H in this situation equals 1 on (-[infinity], 0], takes values in (0, [q.sup.*]] on (0, [infinity]) and converges to 0 as t [right arrow] [infinity].

Definition 2.4 (a) A genuinely two-sided 1-arithmetic BRW [([[PI].sub.n]).sub.n [greater than or equal to] 0] is called recurrent if

[PI]({k}) = [summation over n ([greater than or equal to] 0)] [[PI].sub.n]({k}) = [infinity] a.s. (1)

for some (and then all) k [member of] Z, and transient otherwise.

(b) A genuinely two-sided nonarithmetic BRW [([[PI].sub.n]).sub.n [greater than or equal to] 0] is called (topologically) recurrent if

[PI](I) = [summation over (n [greater than or equal to] 0)] [[PI].sub.n](I) = [infinity] a.s. (2)

for some (and then all) nonempty bounded open intervals I, and transient otherwise.

In order to present our main result, we now confine to the case where Q has finite positive mean [mu](Q).

Defining the Laplace transform of Q

[PSI]([theta]) := [integral] [e.sup.-[theta]x] Q(dx)

with domain [D.sub.[PSI]] := {[theta] : [PSI]([theta]) < [infinity]}, we make the additional assumption that there exists a (necessarily unique) v > 0 such that

[integral][absolute value of x][e.sup.-vx] Q(dx) < [infinity] and [PSI]'(v) = -[integral] x[e.sup.-vx] Q(dx) = 0. (3)

Positivity of v follows from [PSI]'(0) = -[mu](Q) < 0 and the convexity of [PSI] on [D.sub.[PSI]] (which contains at least [0, v]). If v is not an interior point of [D.sub.[PSI]], then [PSI]'(v) is actually the left-hand derivative of [PSI] at v

Theorem 2.5 Let [([[PI].sub.n]).sub.n [greater than or equal to] 0] be a genuinely two-sided, d-arithmetic BRW, d [member of] {0, 1}, with increment distribution Q. Suppose also [p.sub.0] = 0, [p.sub.1] < 1, [mu](Q) [member of] (0, [infinity]), and that (3) holds true. Then [([[PI].sub.n]).sub.n [greater than or equal to] 0] is recurrent, if m[PSI](v) > 1, and transient otherwise.

In view of this result, the BRW [([[PI].sub.n]).sub.n [greater than or equal to] 0] is called critical, if m[PSI](v) = 1, subcritical, if m[PSI](v) < 1, and supercritical, if m[PSI](v) > 1.

3 Random weighted location measures and an associated random walk

This section is devoted to the necessary prerequisites in order to prove our main results in the next section. We start by defining the random weighted location measures (rw.l.m.)

[[LAMBDA].sub.n] := [m.sup.-n][[PI].sub.n] = [m.sup.-n] [summation over ([absolute value of v]=n)] L(v)[[delta].sub.S(v)], n [greater than or equal to] 0

as well as their multivariate extensions

[[LAMBDA].sub.0:n] := [m.sup.-n] [summation over ([absolute value of v]=n)] L(v)[[delta].sub.S(v)], n [greater than or equal to] 0

where

S(v) := ([S.sub.0](v), [S.sub.1](v), ..., [S.sub.n-1](v), [S.sub.n](v)),

with [S.sub.k](v) := S([v.sub.1]... [v.sub.k]) if v = [v.sub.1] ... [v.sub.n] and 0 [greater than or equal to] k [greater than or equal to] n. Since [[LAMBDA].sub.0:n]([R.sup.n+1]) = [[LAMBDA].sub.n](R) = [m.sup.-n][Z.sub.n], n [greater than or equal to] 0, forms a positive martingale with mean one, we see that

[[bar.[LAMBDA]].sub.n] := E[[LAMBDA].sub.n] and [[bar.[LAMBDA]].sub.0:n] := E[[LAMBDA].sub.0:n]

are both probability distributions for each n. Of course, E[[LAMBDA].sub.n] and E[[LAMBDA].sub.0:n] are the measures more explicitly given by

(E[[LAMBDA].sub.n])(A) = E[[LAMBDA].sub.n](A) and (E[[LAMBDA].sub.0:n])(B) = E[[LAMBDA].sub.0:n](B)

for measurable A [subset] R and B [subset] [R.sup.n+1].

For any [theta] [member of] [D.sub.[PSI]], let us further define the r.w.l.m.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as well as the probability distribution

[Q.sub.[theta]](dx) := [PSI][([theta]).sup.-1][e.sup.-[theta]x]Q(dx).

We point out that the [[LAMBDA].sup.[theta].sub.n] and [[LAMBDA].sup.[theta].sub.0:n] are the counterparts of [[LAMBDA].sub.n], respectively [[LAMBDA].sub.0:n] for the weighted branching model based upon [([T.sup.[theta]](v) [cross product] X(v)).sub.v[member of]V], where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Plainly, [[LAMBDA].sub.n] = [[LAMBDA].sup.0.sub.n], [[LAMBDA].sub.0:n] = [[LAMBDA].sup.0.sub.0:n], T(v) = [T.sup.0](v) and Q = [Q.sub.0].

The following two lemmata provide the connection to random walks. The first of them has been given in various places, see Lemma 4.1 in Biggins and Kyprianou (1997), Proposition 11 in Biggins and Kyprianou (2005), Lemma 1 in Bingham and Doney (1975), or p. 289 in Durrett and Liggett (1983).

Lemma 3.1 For each [theta] [member of] [D.sub.[PSI]], let [P.sub.[theta]] (= P if [theta] = 0) be a probability measure on ([OMEGA],U) and [([bar.S].sub.n]).sub.n [greater than or equal to] 0] a sequence of random variables on ([OMEGA],U) which, under [P.sub.[theta]], constitutes a random walk with [[bar.S].sub.0] := 0 and increment distribution [Q.sub.[theta]]. Then

[[bar.[LAMBDA]].sup.[theta].sub.0:n] = [P.sub.[theta]](([[bar.S].sub.0], ..., [[bar.S].sub.n]) [member of] x),

in particular [[bar.[LAMBDA]].sup.[theta].sub.n] = [Q.sup.*n.sub.[theta]] for all n [greater than or equal to] 0.

We will also need an extension of the previous lemma to a certain class of stopping lines, called homogeneous stopping lines (HSL) hereafter. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[sigma.bar]([S.sub.0], [S.sub.1], ...) := inf{n [greater than or equal to] 0 : ([S.sub.0], ..., [S.sub.n]) [member of] [B.sub.n]}

be any formal stopping rule where [B.sub.n] [member of] B([R.sup.n+1]) for n [greater than or equal to] 0 and inf 0 := [infinity], and let

[Y.sub.n] := [[pi].sub.0:n]({[sigma.bar] = n}),

for n [greater than or equal to] 0 where [[pi].sub.0:n] denotes the projection [([S.sub.k]).sub.k [greater than or equal to] 0] [??] ([S.sub.0], ..., [S.sub.n]). For v = ([v.sub.1], [v.sub.2], ...) [member of] [N.sup.N] (viewed as the boundary of V), we further define

[[sigma].sub.v] := [sigma.bar](S(v)), S(v) = [([S.sub.n](v)).sub.n [greater than or equal to] 0] := (S([empty set]), S([v.sub.1]), S([v.sub.1][v.sub.2]), ...),

and then

S := {v|[[sigma].sub.v] : v [member of] [N.sup.N]} [intersection] V = {v|[[sigma].sub.v] : v [member of] [N.sup.N], [[sigma].sub.v] < [infinity]},

where v[absolute value of 0 := [empty set], v]n := [v.sub.1] ... [v.sub.n] for n [member of] N, and v|[infinity] := v. We call S the HSL associated with [sigma.bar]. It consists of all nodes v [member of] V that are obtained as stopping places when applying the same rule [sigma.bar] to the random walks S(v) along all infinite paths v of the tree. Notice that S may be empty and that S = {v : [absolute value of v] = n} in the case [sigma.bar] [equivalent to] n. Stopping lines, also called optional lines, have been defined in varying generality in the literature, the most general one appearing in lagers (1989), which also provides the basic framework. We mention further Chauvin (1991), Kyprianou (2000), and Biggins and Kyprianou (2004) and note that the last reference contains the definition that is closest to that of an HSL and called very simple line there.

Lemma 3.2 Given any HSL S associated with a stopping rule [sigma.bar], put [sigma] := [sigma.bar]([[bar.S].sub.0],[[bar.S].sub.1], ...). Then the following assertions hold true for each [theta] [member of] [D.sub.[PSI]]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

for all n [greater than or equal to] 0 and B [member of] B([R.sup.n+1]), in particular

[P.sub.[theta]]([sigma] = n) = 1/[(m[PSI]([theta])).sup.n] E ([summation over (v[member of]S,[absolute value]=n] L(v)[e.sup.-[theta]S(v)]) = [[bar.[LAMBDA]].sup.[theta].sub.0:n]([Y.sub.n]) (5)

for each n [greater than or equal to] 0 and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Finally, putting [Z.sup.[theta].sub.S] := [[summation].sub.v[member of]S] L(v)[e.sup.-[theta]S(v)] and [Z.sub.S] := [Z.sup.0.sub.S] = [[summation].sub.v[member of]S] L(v),

E[Z.sup.[theta].sub.S] = [E.sub.[theta]][(m[PSI]([theta])).sup.[sigma]][1.sub.{[sigma]<[infinity]}] and E[Z.sub.S] = E[m.sup.[sigma]][1.sub.{[sigma]<[infinity]}] (7)

for all [theta] [member of] [D.sub.[PSI]].

Proof: Noting {[sigma] = n} = {([[bar.S].sub.0], ..., [[bar.S].sub.n]) [member of] [Y.sub.n] and the fact that v [member of] S, [absolute value of v] = n holds iff S(v) [member of] [Y.sub.n], we infer from Lemma 3.1

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which proves (4). The assertions (5) and (6) being direct consequences, let us directly turn to (7). But for [theta] [member of] [D.sub.[PSI]], we infer with the help of (5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and thus the first half of (7). For the second choose [theta] = 0.

In view of the previous result a HSL S associated with [sigma.bar] will be called hereafter HSL associated with [sigma], where [sigma] = [sigma.bar]([[bar.S].sub.0], [[bar.S].sub.1], ...).

4 Proofs of Proposition 2.2 and Theorem 2.5

The following common partial order relations [??] and [??] on V will be needed hereafter: Write v [??] w if v [not equal to] w and v belongs to the ancestral line of w, while v [??] w also allows v = w. Moreover, v [??] ([??]) C for any C [subset] V shall mean that w [??] ([??])v for all w [member of] C. Now we can define the pre-S random location measure as

[[PI].sup.[??].sub.S] := [summation over (v[??]S)] L(v)[[delta].sub.S(v)]

for an arbitrary HSL S. Finally, put also

T := {v [member of] V : L(v) = 1} and [T.sub.n] := {v [member of] T : [absolute value of v] = n}.

The following lemma provides the key to the proof of Proposition 2.2.

Lemma 4.1 In the situation of Proposition 2.2, the function [H.sub.I] is constant for each nonempty open interval I.

Proof: Note that [H.sub.I](t) = [H.sub.t+I](0) for all intervals I and t [member of] R. Hence it suffices to verify that, fixing any nonempty open I with [H.sub.I](0) < 1 and any t [member of] [G.sub.d], we have [H.sub.I](t) = [H.sub.I](0).

Case 1. I bounded.

Since Q is genuinely two-sided, the associated random walk [([[bar.S].sub.n]).sub.n [greater than or equal to] 0] is topologically irreducible on [G.sub.d], that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

for all x [member of] [G.sub.d] and [member of] > 0. For the subsequent argument, we restrict ourselves to the nonarithmetic case, the arithmetic one being even simpler. If I = (x, x + 4[epsilon]) for some x [member of] R and [epsilon] > 0, put [I.sub.1] := (x, x+2[epsilon]), [I.sub.2] := (x + [epsilon], x + 3[epsilon]), and [I.sub.3] := (x + 2[epsilon], x + 4[epsilon]). By (8), there are [k.sub.1], [k.sub.2], [k.sub.3], such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consequently, with k := [k.sub.1] [disjunction] [k.sub.2] [disjunction] [k.sub.3],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Next, since [H.sub.I](0) < 1, the event {[PI](I) = [infinity]} has positive probability 1 - [H.sub.I](0), and on this event the stopping times [[sigma].sub.0] := 0,

[[sigma].sub.i] := inf{n > [[sigma].sub.i-1] + k : S(v) [member of] I for some v [member of] [T.sub.n]}, i [greater than or equal to] 1,

are all a.s. finite. Let [v.sup.i] be the leftmost (with respect to lexicographic ordering) vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that S([v.sup.i]) [member of] I (i [greater than or equal to] 1). Then it follows with the help of the strong Markov property that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all n [greater than or equal to] 1, where [1.sub.j] := 1 ... 1 (j times). Consequently, if [PI](I) - [infinity], then

[E.sub.i] : {[[sigma].sub.i] < [infinity] and S([v.sup.i][1.sub.j]) [member of] t + I for some 1 [less than or equal to] j [less than or equal to] k)

occurs a.s. for at least one i [greater than or equal to] 1, that is, [[upsilon].sub.1] := inf {i [greater than or equal to] 1 : [E.sub.i] occurs} < [infinity] a.s. on {[PI](I) - [infinity]}. But the previous argument can be repeated (using again the strong Markov property) for the sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to infer [v.sub.2] := inf {i > [[upsilon].sub.1] : [E.sub.i] occurs} < [infinity] a.s. on {[PI](I) - [infinity]} and thus via induction that indeed {[PI](I) - [infinity]} - lim [sup.sub.i[right arrow][infinity]], [E.sub.i] a.s. We have thus shown that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and thereby [H.sub.I] (t) [greater than or equal to] [H.sub.I] (0) < 1. By interchanging the roles of I and t + I (now possible as [H.sub.t+I] (0) = [H.sub.I] (t) < 1), we get the reverse inequality and thus the constancy of [H.sub.I].

Case 2. I unbounded.

Then I equals either R, in which case there is nothing to prove, or (-[infinity], x), or (x, [infinity]) for some x [member of] R. But for the last two alternatives, an even simpler geometric trials arguments than above may be employed to give the asserted result. Further details are therefore omitted.

Proof of Proposition 2.2: Let f(s) := [[summation].sub.j[greater than or equal to] 0] [p.sub.j] [S.sup.j] denote the generating function of [Z.sub.1] and observe that [p.sub.0] = 0 and [p.sub.1] < 1 ensure f (S) [less than or equal to] s for all s [member of] [0, 1] with equality holding iff s [member of] {0, 1}. Put

[[[PI]].sub.v] :- [summation over (w [member of] V)] [L.sub.v](w)[[delta].sub.S(vw)-S(v)]

with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any w = [w.sub.1] ... [w.sub.k] [member of] V, thus [L.sub.v] (w) = L(vw)/L(v) if L(v) > 0. Then the [[[PI]].sub.v] are just copies of [PI], obtained by looking at the subtree rooted at v with weights (T (vw) [cross product] X [(vw)).sub.w[member of]v]. Our independence assumptions further ensure that the [[PI]].sub.v] for v [member of] [N.sup.n] are independent.

For any nonempty interval open I, note the obvious identity

[PI](t+I) - [[delta].sub.0](t+I) + [[Z.sub.1].summation over (j=1)] [[[PI]].sub.j] (t - S(j)+I), t [member of] R.

By combining this with the constancy of [H.sub.I] (Lemma 4.1), it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all t [member or] R, that is,

[H.sub.I] - f o [H.sub.I]. (10)

But this shows [H.sub.I] [equivalent to] 0 or [equivalent to] 1, for {s : f (s) [greater than or equal to] s} = {0, 1}.

If I = (-[epsilon], [epsilon]) for any [epsilon] > 0, we must still verify that [H.sub.[eta]] = [H.sub.[epsilon]] for each [eta] [member of] (0, [epsilon]). If [H.sub.[epsilon]] [equivalent to] 1, then [H.sub.[eta]] [equivalent to] 1 for [eta][member of] (0, [epsilon]) is indeed a trivial consequence of [H.sub.[eta]] [greater than or equal to] [H.sub.[epsilon]]. If [H.sub.[epsilon]] [equivalent to] 0, then 1 - [H.sub.[epsilon]] (0) = P([PI]((-[epsilon], [epsilon])) = [infinity]) = 1 which in turn implies 1 - [H.sub.[eta]] (t) = P([PI](t - [eta], t + [eta])) = [infinity]) > 0 for some t [member of] [G.sub.d] and thus excludes [H.sub.[eta]] [equivalent to] 1. Hence, [H.sub.[eta]] [equivalent to] 0 by another appeal to Lemma 4.1 and the proof of the asserted dichotomy is complete.

We proceed with two lemmata relevant to the proof of Theorem 2.4. The first provides a link between the behavior of H (t) = [PI]((-[infinity], t)) and the following Galton-Watson process generated by ladder lines. Let [([[sigma].sub.n]).sub.n [greater than or equal to] 0] be the possibly terminating renewal sequence of strictly descending ladder epochs associated with [([[bar.S].sub.n]).sub.n [greater than or equal to]0], defined by [[sigma].sub.0] := 0 and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where as usual inf 0 := [infinity]. Denote by [S.sub.n] the HSL associated with [[sigma].sub.n], called ladder line, and observe that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] forms a Galton-Watson process (generated by these lines), possibly in the generalized sense that individuals have an infinite number of offspring with positive probability. If so the process is trivially supercritical.

Lemma 4.2 In the situation of Proposition 2.2 the following statements are equivalent:

(i) H [equivalent to] 0, i.e., [PI]((-[infinity], x)) - [infinity] a.s. for all x [member of] R.

(ii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is supercritical.

Proof: If (i) holds true then [S.sub.n] is a.s. nonempty and thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] an a.s. nonextinctive supercritical Galton-Watson process. Conversely, the event of nonexfinction of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has positive probability under (ii), and since S(v) < 0 for infinitely many v [member of] T on this event, we infer [PI]((-[infinity], 0)) = [infinity] with positive probability which in turn implies (i) by an appeal to Proposition 2.2.

Our second lemma is obtained by a geometric trials argument similar to the one in the proof of Proposition 2.2.

Lemma 4.3 In the situation of Proposition 2.2 suppose additionally that Q has finite positive mean. Then the following statements are equivalent:

(i) H [equivalent to] 0.

(ii) [H.sub.[epsilon]] [equivalent to] 0 for all [epsilon] > 0.

Proof: Clearly, it suffices to show that (i) implies (ii), that is, if any interval (-[infinity], x) is a.s. visited infinitely often, then we have the same for any bounded open interval I.

The following argument is given for the nonarithmetic case, but the modifications in the case d = 1 are straightforward and thus omitted. For b [greater than or equal to] 0, let [tau](b) := inf{n [greater than or equal to] 1 : [[bar.S].sub.n] > b} and [R.sub.b] = [[bar.S].sub.[tau](b)] - b the associated overshoot (the first strictly ascending ladder height for b = 0). As Q has finite mean, the same holds true for [R.sub.0] and [R.sub.b] converges in distribution to [R.sub.[infinity]] say, with distribution function

P([R.sub.[infinity]] [less than or equal to] r) = 1/E[R.sub.0] [[integral].sup.r.sub.0] ([R.sub.0] > x) dx, r [greater than or equal to] 0.

Consequently, we can pick some positive t and [epsilon] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

After these observations the geometric trials argument goes as follows. Assuming (i) and thus a fortiori [PI]((-[infinity], -t)) = [infinity] a.s., we can pick a (random) sequence of nodes [v.sup.1], [v.sup.2], ... such that S ([v.sup.j]) [less than or equal to] -t for each j [greater than or equal to] 1. Start with [[??].sup.1] := [v.sup.1] and follow the path [v.sup.1], [v.sup.1]1, [v.sup.1]11, ... until the first [v.sup.1][1.sub.[upsilon]] with S([v.sup.1] [1.sub.[upsilon]]) > 0 or, equivalently, S([v.sup.1],[1.sub.[upsilon]]) - S([v.sup.1]) > -S([v.sup.1]), where [1.sub.n] := 1 ... 1 (n-times) should be recalled. But our assumptions ensure that (S ([v.sup.1][1.sub.n]) - S[([v.sup.1])).sub.n [greater than or equal to] 1] is independent of S([v.sup.1]) and having the same distribution as [([[bar.S].sub.n]).sub.n [greater than or equal to]1]. Consequently, by our choice of t, [epsilon] and the stopping time [upsilon], there is a chance of at least p that S([v.sup.1] [1.sub.[upsilon]]) [member of] (0, [epsilon]]. Now pick the first node [[??].sup.2] from [[??].sup.2], [[??].sup.3], ... of length > [absolute value of [v.sup.1]] + [upsilon], follow the path [[??].sup.2], [[??].sup.2]1, [[??].sup.2]11, ... until S([[??].sup.2] [1.sub.k]) > 0 for the first time. Again, the interval (0, [epsilon]] is hit with probability at least p and independent of the first trial, by the strong Markov property. Continuing this way, the interval (0, [epsilon]] is hit once after an a.s. finite number of rounds and then indeed infinitely often, thus showing [PI]((0, [epsilon])) = [infinity] a.s. But Proposition 2.2 now ensures [PI]((x - [eta], x + [eta])) = [infinity] a.s. for all x [member of] R and [eta] > 0, i.e., (ii) holds true.

Proof of Theorem 2.5: (a) We give first an argument which does not require the previous two lemmata but works only in the 1-arithmetic case. Let [sigma] = inf {n [greater than or equal to] 1 : [[bar.S].sub.n] = 0} and S be the associated HSL. Then [Z.sub.S] = [Z.sup.[theta].sub.S] for all [theta] together with (7) in Lemma 3.2 shows that

E[Z.sub.S] = E[Z.sup.[theta].sub.S] = [E.sub.[theta]][(m[PSI]([theta])).sup.[sigma]] [1.sub.{[sigma]< [infinity]}]

for each [theta] [member of] [D.sub.[PSI]]. Now choose [theta] = v and notice that [([[bar.S].sub.n]).sub.n[greater than or equal to] 0] has drift [PSI]'(v) = 0 under [P.sub.v] and is therefore recurrent on Z, i.e., [P.sub.v] ([sigma] < [infinity]) = 1. Consequently,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Considering once again the Galton-Watson process [([[??].sub.]).sub.n [greater than or equal to] 0], say, of all particles visiting 0 with first generation size [Z.sub.S], we thus infer this process be critical or subcritical, if m[PSI](v) [less than or equal to] 1, and supercritical otherwise. In the latter case, it has a positive chance of survival, that is, P([PI]({0}) < [infinity]) < 1. Proposition 2.2 then ensures that this probability must be 0 as claimed, in other words, the BRW is recurrent. If m[PSI]<(v) [less than or equal to] 1, then almost certain extinction of [([[??].sub.n]).sub.n[greater than or equal to] 0] naturally gives P([PI]({0}) < [infinity]) = 1 and hence the transience of [([[PI].sub.n]).sub.n[greater than or equal to]0]. In the critical case we should mention that P([Z.sub.s] = 1) = 1 is easily excluded.

(b) Suppose now we are in the nonarithmetic case. The following argument embarks on Lemma 4.3 by which it suffices to consider the function H so as to assess recurrence or transience of the given BRW By Lemma 4.2 and in the notation from there, this can be done by computing the mean offspring [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of the Galton-Watson process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Suppose first m[PSI]<(v) [less than or equal to] 1 and notice that S(v) < 0 for all v [member of] [S.sub.1] in combination with v > 0 implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consequently, by (7) of Lemma 3.2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] thus being subcritical we infer, by Lemma 4.2, that [PI]((-[infinity], 0)) < [infinity] a.s. and thereby transience of [([[PI].sub.n]).sub.n[greater than or equal to]0] as claimed.

If [e.sup.v[epsilon]] = m[PSI]<(v) > 1 (with [epsilon] > 0 defined by this equality), consider the stopping times [[sigma].sup.[epsilon].sub.0] [equivalent to] 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for n [greater than or equal to] 1, and let [S.sup.[epsilon].sub.n], n [greater than or equal to] 0, be the associated HSL. Under [P.sub.v], all [[sigma].sup.[epsilon].sub.n] are a.s. finite as [([[bar.S].sub.n]).sub.n[greater than or equal to]0] has drift 0 and is therefore recurrent. By another appeal to (7) of Lemma 3.2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which in combination with the inequality

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We thus arrive at the conclusion that the Galton-Watson process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is supercritical and therefore surviving with positive probability. As

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the process [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is also supercritical and therefore [PI]((-[infinity], 0)) = [infinity] a.s. by Lemma 4.2. This proves the recurrence of [([[PI].sub.n]).sub.n[greater than or equal to] 0].

5 Extremal particle positions in a critical BRW

Once knowing that the critical BRW is transient and thus drifting to [infinity], it is natural ask for its minimal speed or, equivalently, the asymptotic behavior of the leftmost particle in the cloud as time goes to infinity. Define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In the critical case, it is not surprising and in fact following from an old more general result by Biggins (1976, 1977) that

[Min.sub.n]/n [right arrow] 0 a.s.

However, by drawing on recent work of Hu and Shi (2008) (see also Alsmeyer (2007)), we can provide far more precise information about the behavior of [Min.sub.n] under some additional conditions, and also about the naturally related one on the behavior of the rightmost particle (maximal speed) in the cloud. Towards this end, we make the additional assumptions hereafter that the step size distribution Q has bounded support and that

E[Z.sup.2.sub.1] = [summation over (n [greater than or equal to] 1)] [n.sup.2][P.sub.n] < [infinity]. (11)

The following result then follows directly from the more general Theorem 1.2 in Hu and Shi (2008) (note that v = 1 in this work).

Theorem 5.1 Let [([[PI].sub.n]).sub.n[greater than or equal to]0] be a genuinely two-sided critical BRW satisfying [p.sub.0] = 0, [p.sub.1] < 1, [mu](Q) [member of] (0, [infinity]) and (11). Suppose further the step size distribution Q to be bounded. Then (with v defined by (3))

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as well as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The natural way for getting a similar result for the rightmost particle is to resort to the previous one after a reflection of the given BRW at a suitable line x [??] [gamma]x. Put [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is strictly decreasing and continuous on {[mu] < + [PHI]([mu]) < [PSI] ([??])} [subset] (p (Q), [infinity]). Defining further

[gamma] := sup{[mu] : m[PHI]([mu]) [greater than or equal to] > 1}, (12)

Biggins (1976) also showed that

[Max.sub.n]/n [right arrow] [gamma] a.s.

Now, if [gamma] is given along with a [kappa] > 0 such that (12) holds together with

1 = m[PHI]([gamma]) = m[e.sup.-[kappa][gamma]] [PSI] (-[kappa]) and [gamma] = - [PHI]'(-[kappa])/[PHI](-[kappa]) (13)

(the latter identity is an equivalent statement for that the derivative of [theta] [??] [e.sup.[theta][gamma]] [PSI]([theta]) at [theta] = -[kappa] be 0), then one can easily check that the reflected [([[PI].sub.n]).sub.n[greater than or equal to] 0], defined as

[[??].sub.n] = [summation over ([absolute value of v = n)] L(v)[[delta].sub.[gamma]n-S(v)]

is again genuinely two-sided with positive drift, critical and satisfying all conditions of Theorem 5.1. As for its leftmost particle position [[??].sub.n] at time n, we can thus apply Theorem 5.1 and have also the obvious relation

[Max.sub.n] = [gamma]n - [[??].sub.n]

for all n [greater than or equal to] 0. Thus we finally arrive at the following result for the rightmost particle position.

Theorem 5.2 Under the same conditions as in Theorem 5.1 let [gamma] be defined by (12). Suppose additionally the existence of a [kappa] > 0 such that the pair ([gamma], [kappa]) satisfies (13). Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as well as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

References

G. Alsmeyer. Minimal position and critical martingale convergence in branching random walks. Technical report, Universitat Minster, 2007.

I. Benjamini and Y. Peres. Markov chains indexed by trees. The Annals of Probability, 22(1):219-243, 1994. ISSN 00911798.

J. D. Biggins. The first- and last-birth problems for a multitype age-dependent branching process. Advances in Appl. Probability, 8(3):446-459, 1976. ISSN 0001-8678.

J. D. Biggins. Chernoff's theorem in the branching random walk. J Appl. Probability, 14(3):630-636, 1977. ISSN 0021-9002.

J. D. Biggins and A. E. Kyprianou. Seneta-heyde norming in the branching random walk. The Annals of Probability, 25(1):337-360, 1997. ISSN 00911798.

J. D. Biggins and A. E. Kyprianou. Measure change in multitype branching. Advances in Applied Probability, 36(2):544-581, 2004. ISSN 00018678.

J. D. Biggins and A. E. Kyprianou. Fixed points of the smoothing transform: the boundary case. Electron. J. Probab., 10:no. 17, 609-631 (electronic), 2005. ISSN 1083-6489.

N. H. Bingham and R. A. Doney. Asymptotic properties of super-critical branching processes ii: Crump-mode and jirina processes. Advances in Applied Probability, 7(1):66-82, 1975. ISSN 00018678.

B. Chauvin. Product martingales and stopping lines for branching brownian motion. The Annals of Probability, 19(3):1195-1205, 1991. ISSN 00911798.

F. Comets, M. V. Menshikov, and S. Y. Popov. One-dimensional branching random walk in a random environment: a classification. Markov Process. Related Fields, 4(4):465-477, 1998. ISSN 1024-2953. I Brazilian School in Probability (Rio de Janeiro, 1997).

R. Durrett and T. M. Liggett. Fixed points of the smoothing transformation. Z. Wahrsch. verw. Gebiete, 64(3):275-301, 1983. ISSN 0044-3719.

N. Gantert and S. Muller. The critical branching Markov chain is transient. Markov Process. Related Fields, 12(4):805-814, 2006. ISSN 1024-2953.

Y. Hu and Z. Shi. Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees. arXiv : math/0702799v3, Mar. 2008.

P. Jagers. General branching processes as Markov fields. Stochastic Process. Appl., 32(2):183-212, 1989. ISSN 0304-4149.

A. E. Kyprianou. Martingale convergence and the stopped branching random walk. Probab. Theory Related Fields, 116(3):405-419, 2000. ISSN 0178-8051.

F. P. Machado and S. Y. Popov. One-dimensional branching random walks in a Markovian random environment. J Appl. Probab., 37(4):1157-1163, 2000. ISSN 0021-9002.

F. P. Machado and S. Y. Popov. Branching random walk in random environment on trees. Stochastic Process. Appl., 106(1):95-106, 2003. ISSN 0304-4149.

F. P. Machado, M. V. Menshikov, and S. Y. Popov. Recurrence and transience of multitype branching random walks. Stochastic Process. Appl., 91(1):21-37, 2001. ISSN 0304-4149.

M. V. Menshikov and S. E. Volkov. Branching Markov chains: qualitative characteristics. Markov Process. Related Fields, 3(2):225-241, 1997. ISSN 1024-2953.

Gerold Alsmeyer and Matthias Meiners

Institut fur Mathematische Statistik, Fachbereich Mathematik, Einsteinstrasse 62, D-48149 Munster. Germany