Speed of the biased random walk on a Galton–Watson tree Elie A¨ıd´ekon∗ 1 1 0 December 19, 2011 2 c e D Summary. We give an expression of the speed of the biased random 6 walk on a Galton–Watson tree. In the particular case of the simple ran- 1 dom walk, we recover the result of Lyons, Pemantle and Peres [7]. The ] proof uses a description of the invariant distribution of the environment R seen from the particle. P . h Keywords. Random walk, Galton–Watson tree, speed, invariant mea- t a sure. m [ 2010 Mathematics Subject Classification. 60J80, 60G50, 60F15. 3 v 1 Introduction 3 1 3 4 Let T be a Galton–Watson tree with root e, and ν be its offspring distribution with values . 1 in N. We suppose that m := E[ν] > 1, so that the tree is super-critical. In particular, 1 1 the event S that T is infinite has a positive probability, and we let q := 1−P(S) < 1 be 1 : the extinction probability. We call ν(x) the number of children of the vertex x in T. For v i x ∈ T\{e}, we denote by x the parent of x, that is the neighbour of x which lies on the X ∗ r path from x to the root e, and by xi,1 ≤ i ≤ ν(x) the children of x. We call T the tree a ∗ T on which we add an artificial parent e to the root e. ∗ For any λ > 0, and conditionally on T , we introduce the λ-biased random walk ∗ (X ) which is the Markov chain such that, for x (cid:54)= e , n n≥0 ∗ λ (1.1) P(X = x |X = x) = , n+1 ∗ n λ+ν(x) 1 (1.2) P(X = xi|X = x) = for any 1 ≤ i ≤ ν(x), n+1 n λ+ν(x) ∗LPMA, Universit´e Paris 6, 4, place Jussieu,75005 Paris, France. Email: [email protected] 1 and which is reflected at e . It is easily seen that this Markov chain is reversible. We de- ∗ note by P the quenched probability associated to the Markov chain (X ) starting from x n n x and by P the annealed probability obtained by averaging P over the Galton–Watson x x measure. They are respectively associated to the expectations E and E . x x When λ < m, we know from Lyons [6] that the walk is almost surely transient on the event S. Moreover, if we denote by |x| the generation of x, Lyons, Pemantle and Peres [8] showed that, conditionally on S, the limit (cid:96) := lim |Xn| exists almost surely, is λ n→∞ n determinist and is positive if and only if λ ∈ (λ ,m) with λ := E[νqν−1]. This is the c c regime we are interested in. For any vertex x ∈ T , let ∗ (1.3) τ := min{n ≥ 1 : X = x} x n be the hitting time of the vertex x by the biased random walk, with the notation that min∅ := ∞, and, for x (cid:54)= e , ∗ β(x) := P (τ = ∞) x x∗ bethequenchedprobabilityofneverreachingtheparentofxwhenstartingfromx. Notice that we have β(x) > 0 if and only if the subtree rooted at x is infinite. Then, let (β ,i ≥ 0) i be, under P, generic i.i.d. random variables distributed as β(e), and independent of ν. Theorem 1.1. Suppose that m ∈ (1,∞) and λ ∈ (λ ,m). Then, c (cid:44) (cid:20) (cid:21) (cid:20) (cid:21) (ν −λ)β (ν +λ)β (cid:96) = E 0 E 0 . λ λ−1+(cid:80)ν β λ−1+(cid:80)ν β i=0 i i=0 i The speed in the case λ = 1 was already obtained by Lyons, Pemantle and Peres [7], who found that (cid:96) = E[ν−1] whereas Ben Arous, Hu, Olla and Zeitouni [2] computed the 1 ν+1 derivative of (cid:96) at the point λ = m. In this paper, the authors give another represen- λ tation of the speed (cid:96) , at least when λ is close enough to m. In the zero speed regime λ λ ≤ λ , Ben Arous, Fribergh, Gantert and Hammond [1] showed tightness of the properly c rescaled random walk, though a limit law fails. A central limit theorem was obtained by Peres and Zeitouni [10], by means, in the case λ = m, of a construction of the invariant distribution on the space of trees. The invariant distribution in the case λ > m was given in [2]. We mention that, so far, the only case in the transient regime λ < m for which such an invariant distribution was known was the simple random walk case λ = 1 studied in [7]. Theorem 4.1 in Section 4 gives a description of the invariant measure for 2 all λ ∈ (λ ,m). In the setting of random walks on Galton–Watson trees with random con- c ductances, Gantert, Mu¨ller, Popov and Vachkovskaia [5] obtained a similar formula for the speed via the construction of the invariant measure in terms of effective conductances. The paper is organized as follows. Section 2 introduces some notation and the concept of backward tree seen from a vertex. Section 3 investigates the law of the tree seen from a vertex that we visit for the first time. Using a time reversal argument, we are able to describe the distribution of this tree in Proposition 3.2. Then, we obtain in Section 4 the invariant measure of the tree seen from the particle. Theorem 1.1 follows in Section 5. 2 Preliminaries 2.1 The space of words U We let U := {e} ∪ (cid:83) (N∗)n be the set of words, and |u| be the length of the word u, n≥1 where we set |e| := 0. We equip U with the lexicographical order. For any word u ∈ U with label u = i ...i , we denote by u ∈ U the word with letters in reversed order 1 n u := i ...i (and e := e). If u (cid:54)= e, we denote by u the parent of u, that is the word n 1 ∗ i ...i , and by u the word i ...i , which stands for the ancestor of u at generation 1 n−1 ∗ 1 n−k k |u|−k. We have u := e if k = |u| and u := u if k = 0. Finally, for u,v ∈ U, we denote ∗ ∗ k k by uv the concatenation of u and v. We add to the set of words the element e , which ∗ stands for the parent of the root and we write U := U ∪{e }. We set |e | = −1, hence ∗ ∗ ∗ u = e for k = |u|+1 for any u ∈ U. We denote by S := {x , 1 ≤ k ≤ |x|+1} the set ∗ ∗ x ∗ k k of strict ancestors of x. 2.2 The space of trees T Following Neveu [9], a tree T is defined as a subset of U such that • e ∈ T, • if x ∈ T\{e}, then x ∈ T, ∗ • if x = i ...i ∈ T\{e}, then any word i ...i j with j ≤ i belongs to T. 1 n 1 n−1 n We call T the space of all trees T. For any tree T, we define T as the tree on which we ∗ add the parent e to the root e. Then, let T := {T ,T ∈ T }. For a tree T ∈ T , and a ∗ ∗ ∗ vertex u ∈ T , we denote by ν (u) = ν (u) the number of children of u in T , and we ∗ T T∗ ∗ 3 notice that ν (e ) = ν (e ) = 1. We will write only ν(u) when there is no doubt about T ∗ T∗ ∗ which tree we are dealing with. We introduce double trees. For any u ∈ U, let u− := (u,−1) and u+ := (u,1). Given two trees T,T+ ∈ T , we define the double tree T−•T+ as the tree obtained by drawing an edge between the roots of T and T+. Formally, T−•T+ is the set {u−, u ∈ T}∪{u+, u ∈ T+}. We root the double tree at e+. Given r an element of T, we say that X is the r-parent of Y in T−•T+ if either • Y = y+ and X = y+, ∗ • Y = e+ and X = e−, • Y = y− with y ∈/ S ∪{u ∈ U : u ≥ r} and X = y−, r ∗ • Y = r− and X = r− for some k ∈ [1,|r|]. ∗ ∗ k k−1 In words, the r-parent of a vertex x is the vertex which would be the parent of x if we were ’hanging’ the tree at r. Notice that we defined the r-parent only for the vertices which do not belong to {u− : u ∈ U, u ≥ r}. e− e+ T T+ T−•T+ Figure 1: A double tree 4 2.3 The backward tree B (T ) x ∗ Let δ be some cemetery tree. For a tree T ∈ T and a word x ∈ U, we define the tree ∗ ∗ T ≤x ∈ T ∪{δ} cut at x by ∗ ∗ (cid:40) δ if x ∈/ T , T ≤x := ∗ ∗ T \{u ∈ U : x < u} if x ∈ T . ∗ ∗ e e ∗ ∗ e e x = 1121 x = 1211 T B (T ) ∗ x ∗ Figure 2: The backward tree at x In other words, if x ∈ T , then T ≤x is the tree T in which you remove the strict descen- ∗ ∗ ∗ dants of x. We call U≤x the set of words U \{u ∈ U : x < u}. We now introduce the ∗ ∗ ’backward’ tree at x. For any word x ∈ U, let Ψ : U≤x → U≤x such that: x ∗ ∗ • for any k ∈ [0,|x|+1], Ψ (x ) = x , x ∗ ∗ k |x|−k+1 • for any k ∈ [1,|x|] and v ∈ U such that x v is not a descendant of x , Ψ (x v) = ∗ ∗ x ∗ k k+1 k Ψ (x )v. x ∗ k The application Ψ is a bijection, with inverse map Ψ . For any tree T ∈ T , we call x x ∗ ∗ backward tree at x the tree (2.4) B (T ) := Ψ (T ≤x), x ∗ x ∗ image of T ≤x by Ψ , with the notation that Ψ (δ) := δ. This is the tree obtained by ∗ x x cutting the descendants of x and then ’hanging’ the tree T at x. We observe that, ∗ 5 • ν (e ) = 1, Bx(T∗) ∗ • ν (x) = 0, Bx(T∗) • for any other u ∈ B (T ), we have ν (u) = ν (Ψ (u)). x ∗ Bx(T∗) T∗ x Recall that T is a Galton–Watson tree with offspring distribution ν. Lemma 2.1. Let x ∈ U. The distributions of the trees B (T ) and T≤x are the same. x ∗ ∗ Proof. For any sequence (k ,u ∈ U) ∈ NU, denote by M(k ,u ∈ U) ∈ T the unique tree u u ∗ such that for any u ∈ M(k ,u ∈ U) the number of children of u is 1 if u = e and k u ∗ u otherwise. Take (κ(u),u ∈ U) i.i.d. random variables distributed as ν. Then notice that the tree M(κ(u),u ∈ U) is distributed as T . Therefore, we set in this proof ∗ T := M(κ(u),u ∈ U). ∗ We check that we can extend the map Ψ to a bijection on U by letting Ψ (xv) := xv x ∗ x for any strict descendant xv of x. Suppose that x ∈ T . We know that if u ∈ B (T ), ∗ x ∗ then the number of children of u is 1 if u = e , 0 if u = x and κ(Ψ (u)) otherwise. By ∗ x definition, this yields that B (T ) = M(κ(Ψ (u))1 ,u ∈ U). x ∗ x {u(cid:54)=x} Let T(cid:101) := M(κ(Ψ (u)),u ∈ U). We notice that M(κ(Ψ (u))1 ,u ∈ U) = T(cid:101)≤x. ∗ x x {u(cid:54)=x} ∗ Therefore, if x ∈ T , then ∗ B (T ) = T(cid:101)≤x. x ∗ ∗ We check that the equality holds also when x ∈/ T . Observe that T(cid:101) is distributed as T ∗ ∗ ∗ to complete the proof. (cid:50) 3 The environment seen from the particle at first- visit times For any tree T ∈ T , we denote by PT∗ a probability measure under which (X ) is a ∗ ∗ n n≥0 Markov chain on T with transition probabilities given by (1.1) and (1.2). For any vertex ∗ x ∈ T , we denote by PT∗ the probability PT∗(·|X = x). We will just write P if the tree ∗ x 0 x T is clear from the context. ∗ 6 Lemma 3.1. Suppose that λ > 0. Let T be a tree in T , x be a vertex in T and ∗ ∗ ∗ (e = u ,u ,...,u = x) be a nearest-neighbour trajectory in T such that u ∈/ {e ,x} for ∗ 0 1 n ∗ j ∗ any j ∈ (0,n). Then, PT∗(X = u , ∀j ≤ n) = PBx(T∗)(X = Ψ (u ), ∀j ≤ n). e∗ j j e∗ j x n−j Proof. We decompose the trajectory (u ,j ≤ n) along the ancestral path S . Let j := 0. j x 0 Supposing that we know j , we define j as the smallest integer j > j such that u i i+1 i+1 i ji+1 is an ancestor of x different from u . Let m be the integer such that u = x. We ji jm+1 see that necessarily j = 1, (u ,u ) = (e ,e) and (u ,u ) = (x ,x). For i ∈ [1,m], 1 j0 j1 ∗ jm jm+1 ∗ let c be the cycle (u ,u ,...,u ). Notice that in this cycle, the vertex u is the i ji ji+1 ji+1−1 ji unique element of S visited, at least twice at times j and j −1. We set for any cycle x i i+1 c = (z ,z ,...,z ), 0 1 k k−1 (cid:89) PT∗(c) := PT∗(X = z ) z 1 (cid:96)+1 (cid:96) (cid:96)=0 (cid:81) with the notation that := 1. Using the Markov property, we see that ∅ m m (cid:89) (cid:89) (3.5) PT∗(X = u , ∀j ≤ n) = PT∗(c ) PT∗ (X = u ). e∗ j j i uji 1 ji+1 i=1 i=1 For any vertex z, let a(z) := (λ+ν (z))−1. Notice that the term corresponding to i = m T∗ in the second product is PT∗(X = x) = a(x ). x∗ 1 ∗ For any z (cid:54)= e , let N (z) be the number of times the oriented edge (z,z ) is crossed by ∗ u ∗ the trajectory (u ,j ≤ n). Notice that the oriented edge (z ,z) is crossed 1+N (z) times j ∗ u when z ∈ S . Using the transition probabilities (1.1) and (1.2), we deduce that x m−1 |x|−1 (cid:89) PT∗ (X = u ) = (cid:89) (cid:0)λa(x )a(x )(cid:1)Nu(x∗k)a(x ). uji 1 ji+1 ∗k ∗k+1 ∗k+1 i=1 k=1 Therefore, we can rewrite (3.5) as (3.6) PT∗(X = u , ∀j ≤ n) = Π Π e∗ j j 1 2 where m (3.7) Π := (cid:89)PT∗(c ), 1 i i=1 |x|−1 (3.8) Π := a(x ) (cid:89) (cid:0)λa(x )a(x )(cid:1)Nu(x∗k)a(x ). 2 ∗ ∗ ∗ ∗ k k+1 k+1 k=1 7 We look now at the probability PBx(T∗)(X = v , ∀j ≤ n), where v := Ψ (u ). We e∗ j j j x n−j decompose the trajectory (v ,j ≤ n) along S . Observe that (v ,j ≤ n) is the time- j x j reversed trajectory of (u ,j ≤ n) looked in the backward tree. Therefore, the cycles of j (v , j ≤ n) are the image by Ψ of the time-reversed cycles of (u , j ≤ n). We need some j x j (cid:16) (cid:17) ← ← notation. Let c be the path c time-reversed, and Ψ c be its image by Ψ , that is i i x i x (cid:16) (cid:17) ← Ψ c = (Ψ (u ),Ψ (u ),...,Ψ (u )). x i x ji+1−1 x ji+1−2 x ji Let PBx(T∗)(cid:16)Ψ (cid:16)←c (cid:17)(cid:17) := ji(cid:89)+1−2PBx(T∗)(X = Ψ (u )|X = Ψ (u )). x i 1 x (cid:96) 0 x (cid:96)+1 (cid:96)=ji We introduce for any vertex z ∈ B (T ), x ∗ (cid:0) (cid:1)−1 a (z) := λ+ν (z) B Bx(T∗) and, for z (cid:54)= e , N (z) the number of times the trajectory (v ,j ≤ n) crosses the directed ∗ v j edge (z,z ). Equation (3.6) reads for the trajectory (v , j ≤ n), ∗ j (3.9) PBx(T∗)(X = v , ∀j ≤ n) = Π Π e∗ j j B,1 B,2 where m Π := (cid:89)PBx(T∗)(cid:16)Ψ (cid:16)←c (cid:17)(cid:17), B,1 x i i=1 |x|−1 Π := a (x ) (cid:89) (cid:0)λa (x )a (x )(cid:1)Nv(x∗k)a (x ). B,2 B ∗ B ∗ B ∗ B ∗ k k+1 k+1 k=1 Going from T to B (T ), we did not change the configuration of the subtrees located ∗ x ∗ (cid:16) (cid:16) (cid:17)(cid:17) (cid:16) (cid:17) ← ← outside the ancestral path S of x. This yields that PBx(T∗) Ψ c = PT∗ c which x i i Π is PT∗(c ) since the Markov chain (X ) is reversible. By definition of in (3.7), we i n n≥0 1 get Π Π = . B,1 1 We observe that a (z) = a(Ψ (z)) whenever z ∈/ {e ,x}, and Ψ (x ) = x by B x ∗ x ∗ ∗ k |x|−k+1 definition. Moreover, for any k ∈ [1,|x|−1], we have N (x ) = N (x ). This gives v ∗ u ∗ k |x|−k 8 that |x|−1 Π = a(e) (cid:89) (cid:16)λa(x )a(x )(cid:17)Nu(x∗|x|−k)a(x ) B,2 ∗ ∗ ∗ |x|−k+1 |x|−k |x|−k k=1 |x|−1 = a(x ) (cid:89) (cid:16)λa(x )a(x )(cid:17)Nu(x∗|x|−k)a(x ), ∗ ∗ ∗ ∗ |x|−k+1 |x|−k |x|−k+1 k=1 Π Π hence, recalling (3.8), = . Equations (3.6) and (3.9) lead to B,2 2 PT∗(X = u , ∀j ≤ n) = PBx(T∗)(X = v , ∀j ≤ n) e∗ j j e∗ j j which completes the proof. (cid:50) Weintroduceξ , thek-thdistinctvertexvisitedbythewalk, andθ := τ theso-called k k ξ k first-visit time. They can be defined by θ = 1, ξ = X and for any k ≥ 2 by 1 1 1 (3.10) θ := min{i > θ such that X ∈/ {X ,1 ≤ j < i}}, k k−1 i j (3.11) ξ := X . k θ k Wegivethedistributionofthetreeseenatafirst-visittimeθ , conditionallyon{θ < τ }. k k e∗ Proposition 3.2. Suppose that λ > 0. Let k ≥ 1. Under P (·|θ < τ ), we have e∗ k e∗ (B (T ),(Ψ (X )) ) (=d) (cid:0)T≤ξk,(X ) (cid:1). ξk ∗ ξk θk−j j≤θk ∗ j j≤θk Proof. For any relevant bounded measurable map F and any word x ∈ U, we have E (cid:2)F (B (T ),(Ψ (X )) )1 (cid:3) e∗ ξk ∗ ξk θk−j j≤θk {ξk=x,θk<τe∗} = E (cid:2)F (B (T ),(Ψ (X )) )1 (cid:3) e∗ x ∗ x θk−j j≤θk {ξk=x,θk<τe∗} (cid:104) (cid:16) (cid:17) (cid:105) = E F B (T ),(X(cid:101) ) 1 e∗ x ∗ j j≤θ(cid:101)k {ξ(cid:101)k=x,θ(cid:101)k<τ(cid:101)e∗} by Lemma 3.1, where (X(cid:101) ) is the λ-biased random walk on the tree B (T ), and the n n≥0 x ∗ variables θ(cid:101) , ξ(cid:101) and τ are the analogues of θ , ξ and τ for the Markov chain (X(cid:101) ) . k k (cid:101)e∗ k k e∗ n n≥0 By Lemma 2.1, this yields that E (cid:2)F (B (T ),(Ψ (X )) )1 (cid:3) = E (cid:2)F (cid:0)T≤x,(X ) (cid:1)1 (cid:3) e∗ ξk ∗ ξk θk−j j≤θk {ξk=x,θk<τe∗} e∗ ∗ j j≤θk {ξk=x,θk<τe∗} = E (cid:2)F (cid:0)T≤ξk,(X ) (cid:1)1 (cid:3). e∗ ∗ j j≤θk {ξk=x,θk<τe∗} We complete the proof by summing over x ∈ U. (cid:50) 9 The last lemma gives the asymptotic probability that n is a first-visit time. To state it, we introduce the regeneration epochs (Γ ,k ≥ 1) defined by Γ := inf{(cid:96) ∈ {0}∪{θ ,k ≥ k 1 k 1} : X (cid:54)= (X ) ∀j ≥ (cid:96), X (cid:54)= e } and for any k ≥ 2, j (cid:96) ∗ (cid:96) ∗ (3.12) Γ := inf{(cid:96) > Γ : (cid:96) ∈ {θ ,k ≥ 1},X (cid:54)= (X ) ∀j ≥ (cid:96)}, k k−1 k j (cid:96) ∗ where (X ) stands for the parent of the vertex X . For any k ≥ 1, it is well-known (cid:96) ∗ (cid:96) that, under P, the random walk after time Γ is independent of its past. Moreover, k the walk (X , (cid:96) ≥ Γ ) seen in the subtree rooted at X is distributed as (X ,(cid:96) ≥ 0) (cid:96) k Γ (cid:96) k under P (·|τ = ∞). We refer to Section 3 of [8] for the proof of such facts. We e e∗ have that Γ < ∞ for any k ≥ 1 almost surely on the event S when λ < m, and k E [Γ |τ = ∞] < ∞ if and only if λ ∈ (λ ,m). e 2 e∗ c Lemma 3.3. Suppose that m > 1 and λ ∈ (0,m). We have 1 lim P (n ∈ {θ , k ≥ 1},τ > n) = . n→∞ e∗ k e∗ Ee[Γ2|τe∗ = ∞] Proof. By the Markov property at time n and the branching property at vertex X , we n observe that P (n ∈ {θ , k ≥ 1},τ > n)P (τ = ∞) = P (n ∈ {Γ ,k ≥ 1}, τ = ∞) e∗ k e∗ e e∗ e∗ k e∗ hence P (n ∈ {θ , k ≥ 1},τ > n) = P (n ∈ {Γ ,k ≥ 1}|τ = ∞). e∗ k e∗ e∗ k e∗ We notice that P (n ∈ {Γ ,k ≥ 1}|τ = ∞) = P (n − 1 ∈ {Γ ,k ≥ 1}|τ = ∞). e∗ k e∗ e k e∗ We mention that Γ = 0 on the event that τ = ∞, when starting from e. Since 1 e∗ (Γ − Γ ,k ≥ 1) are a sequence of i.i.d random variables under P (·|τ = ∞) with k+1 k e e∗ mean E [Γ |τ = ∞], the lemma follows from the renewal theorem pp. 360, XI.1 [4]. (cid:50) e 2 e∗ 4 Asymptotic distribution of the environment seen from the particle We equip T and T with the topology generated by finite subtrees. For any tree T ∈ T ∗ and any x ∈ T , let ∗ T := {u ∈ T : u ≥ x} x be the subtree composed of x and its descendants. We recall that B (T ) defined in (2.4) x ∗ is the tree backward. This section is devoted to the asymptotic distribution of the tree 10