collevec@unive.it Limittheoremsforvertex-reinforcedjumpprocessesonregulartrees

El e c t ro nic

Journ a l of

Pr

ob a b il i t y

Vol. 14 (2009), Paper no. 66, pages 1936–1962.

Journal URL

http://www.math.washington.edu/~ejpecp/

Limit theorems for vertex-reinforced jump processes on regular trees

Andrea Collevecchio^∗

Dipartimento di Matematica applicata^† Università Ca’ Foscari –Venice, Italy.

collevec@unive.it

Abstract

Consider a vertex-reinforced jump process defined on a regular tree, where each vertex has exactlybchildren, with b≥3. We prove the strong law of large numbers and the central limit theorem for the distance of the process from the root. Notice that it is still unknown if vertex- reinforced jump process is transient on the binary tree.

Key words:Reinforced random walks; strong law of large numbers; central limit theorem.

AMS 2000 Subject Classification:Primary 60K35, 60F15, 60F05.

Submitted to EJP on June 6, 2008, final version accepted July 13, 2009.

∗The author was supported by the DFG-Forschergruppe 718 ”Analysis and stochastics in complex physical systems”, and by the Italian PRIN 2007 grant 2007TKLTSR "Computational markets design and agent-based models of trading behavior".

The author would like to thank Burgess Davis, Fabiola del Greco and an anonymous referee for helpful suggestions.

†Ca’ Dolfin - Dorsoduro 3825/E, 30123 Venezia Venice, Italy

1 Introduction

LetD be any graph with the property that each vertex is the end point of only a finite number of edges. Denote by Vert(D)the set of vertices ofD. The following, together with the vertex occupied at time 0 and the set of positive numbers {a_ν:ν ∈ Vert(D)}, defines a right-continuous process X={X_s, s≥0}. This process takes as values the vertices ofDand jumps only to nearest neighbors, i.e. vertices one edge away from the occupied one. Given X_s, 0 ≤ s ≤ t, and {X_t = x}, the conditional probability that, in the interval(t,t+dt), the process jumps to the nearest neighbor y ofx is L(y,t)dt, with

L(y,t):=a_y+ Z t

0

1l_{X

s=y}ds, a_y>0,

where 1l_Astands for the indicator function of the setA. The positive numbers{a_ν:ν∈Vert(D)}are called initial weights, and we supposea_ν ≡1, unless specified otherwise. Such a process is said to be a Vertex Reinforced Jump Process (VRJP) onD.

Consider VRJP defined on the integers, which starts from 0. With probability 1/2 it will jump either to 1 or −1. The time of the first jump is an exponential random variable with mean 1/2, and is independent on the direction of the jump. Suppose the walk jumps towards 1 at timez. Given this, it will wait at 1 an exponential amount of time with mean 1/(2+z). Independently of this time, the jump will be towards 0 with probability(1+z)/(2+z).

In this paper we define a process to be recurrent if it visits each vertex infinitely many times a.s., and to be transient otherwise. VRJP was introduced by Wendelin Werner, and its properties were first studied by Davis and Volkov (see[8]and[9]). This reinforced walk defined on the integer lattice is studied in[8]where recurrence is proved. For fixed b ∈N:= {1, 2, . . .}, the b-ary tree, which we denote byGb, is the infinite tree where each vertex has b+1 neighbors with the exception of a single vertex, called the root and designated byρ, that is connected to b vertices. In[9]is shown that VRJP on the b-ary tree is transient if b ≥ 4. The case b = 3 was dealt in[4], where it was proved that the process is still transient. The caseb=2 is still open.

Another process which reinforces the vertices, the so called Vertex-Reinforced Random Walk (VRRW), shows a completely different behaviour. VRRW was introduced by Pemantle (see[17]).

Pemantle and Volkov (see[19]) proved that this process, defined on the integers, gets stuck in at most five points. Tarrès (see[23]) proved that it gets stuck in exactly 5 points. Volkov (in [24]) studied this process on arbitrary trees.

The reader can find in[18]a survey on reinforced processes. In particular, we would like to mention that little is known regarding the behaviour of these processes on infinite graphs with loops. Merkl and Rolles (see[14]) studied the recurrence of the original reinforced random walk, the so-called linearly bond-reinforced random walk, on two-dimensional graphs. Sellke (see[21]) proved than once-reinforced random walk is recurrent on the ladder.

We define the distance between two vertices as the number of edges in the unique self-avoiding path connecting them. For any vertex ν, denote by |ν| its distance from the root. Level i is the set of verticesν such that|ν|=i. The main result of this paper is the following.

Theorem 1.1. LetXbe VRJP onGb, with b≥3. There exist constants K⁽¹⁾_b ∈(0,∞)and K⁽²⁾_b ∈[0,∞)

such that

tlim→∞

|X_t|

t =K_b⁽¹⁾ a.s., (1.1)

|X_t| −K_b⁽¹⁾t

pt =⇒Normal(0,K⁽²⁾_b ), (1.2)

where we took the limit as t → ∞, ⇒stands for weak convergence and Normal(0, 0) stands for the Dirac mass at0.

Durrett, Kesten and Limic have proved in[11]an analogous result for a bond-reinforced random walk, called one-time bond-reinforced random walk, onGb, b ≥2. To prove this, they break the path into independent identically distributed blocks, using the classical method of cut points. We also use this approach. Our implementation of the cut point method is a strong improvement of the one used in[3]to prove the strong law of large numbers for the original reinforced random walk, the so-called linearly bond-reinforced random walk, onGb, with b≥ 70. Aidékon, in[1]gives a sharp criteria for random walk in a random environment, defined on Galton-Watson tree, to have positive speed. He proves the strong law of large numbers for linearly bond-reinforced random walk onGb, with b≥2.

2 Preliminary definitions and properties

From now on, we consider VRJPX defined on the regular treeGb, with b≥3. For ν 6= ρ, define par(ν), called the parent ofν, to be the unique vertex at level|ν| −1 connected to ν. A vertexν₀ is a child ofν if ν =par(ν₀). We say that a vertexν₀ is a descendant of the vertexν if the latter lies on the unique self-avoiding path connectingν₀toρ, andν₀6=ν. In this case,ν is said to be an ancestor ofν₀. For any vertexµ, letΛ_µbe the subtree consisting ofµ, its descendants and the edges connecting them, i.e. the subtree rooted atµ. Define

T_i := inf{t≥0:|X_t|=i}.

We give the so-called Poisson construction of VRJP on a graphD(see[20]). For each ordered pair of neighbors(u,v)assign a Poisson processP(u,v)of rate 1, the processes being independent. Call h_i(u,v), withi≥1, the inter-arrival times ofP(u,v)and letξ₁:=inf{t≥0:X_t=u}. The first jump afterξ₁is at timec₁:=ξ₁+min_vh₁(u,v) L(v,ξ₁)₋₁

, where the minimum is taken over the set of neighbors ofu. The jump is towards the neighbor vfor which that minimum is attained. Suppose we defined{(ξ_j,c_j), 1≤j≤i−1}, and let

ξ_i :=inf

t>c_i−1:X_t=u , and

j_v−1= j_u,v−1 := number of timesXjumped fromutovby timeξ_i. The first jump afterξ_ihappens at timec_i:=ξ_i+min_vh_jv(u,v) L(v,ξ_i)₋1

, and the jump is towards the neighborv which attains that minimum.

Definition 2.1. A vertexµ, with|µ| ≥2, isgoodif it satisfies the following h₁(µ₀,µ)< h₁ µ₀, par(µ₀)

1+h₁ par(µ₀),µ₀ whereµ₀=par(µ). (2.3)

By virtue of our construction of VRJP, (2.3) can be interpreted as follows. When the process X visits the vertex µ₀ for the first time, if this ever happens, the weight at its parent is exactly 1+ h₁ par(µ₀),µ₀

while the weight at µ is 1. Hence condition (2.3) implies that when the process visitsµ₀(if this ever happens) then it will visitµbefore it returns to par(µ₀), if this ever happens.

The next Lemma gives bounds for the probability that VRJP returns to the root after the first jump.

Lemma 2.2. Let

α_b:=P X_t=ρfor some t≥T₁ , and letβ_bbe the smallest among the positive solutions of the equation

x = Xb k=0

x^kp_k, (2.4)

where, for k∈ {0, 1, . . . ,b}, p_k:=

Xk j=0

b k

k j

(−1)^j Z _∞

0

1+z

j+b−k+1+ze^−zdz. (2.5)

We have Z _∞

0

1+z

b+1+zbe^−bzdz≤α_b≤β_b. (2.6) Proof. First we prove the lower bound in (2.6). The left-hand side of this inequality is the prob- ability that the process returns to the root with exactly two jumps. To see this, notice that L(ρ,T₁) is equal 1+min_ν:|ν|=1h₁(ρ,ν). Hence T₁ = L(ρ,T₁)−1 is distributed like an exponential with mean 1/b. Given that T₁ = z, the probability that the second jump is from X_T

1 toρ is equal to (1+z)/(b+1+z). Hence the probability that the process returns to the root with exactly two jumps

is Z _∞

0

1+z

b+1+zbe^−bzdz.

As for the upper bound in (2.6) we reason as follows. We give an upper bound for the probability that there exists an infinite random tree which is composed only of good vertices and which has root at one of the children ofX_T1. If this event holds, then the process does not return to the root after timeT₁(see the proof of Theorem 3 in[4]). We prove that a particular cluster of good vertices is stochastically larger than a branching process which is supercritical. We introduce the following color scheme. The only vertex at level 1 to begreenisX_T1. A vertexν, with|ν| ≥2, isgreenif and only if it is good and its parent is green. All the other vertices are uncolored. Fix a vertexµ. LetC be any event in

Hµ:=σ(h_i(η₀,η₁):i≥1, withη₀∼η₁and bothη₀ andη₁∈/Λ_µ), (2.7) that is theσ-algebra that contains the information aboutX_tobserved outsideΛ_µ. Next we show that givenC∩ {µis green}, the distribution ofh₁(par(µ),µ)is stochastically dominated by an exponen- tial(1). To see this, first notice thath₁(par(µ),µ)is independent ofC. LetD:={par(µ)is green} ∈ Hµ and set

W := h₁ µ₀, par(µ₀)

1+h₁ par(µ₀),µ₀ whereµ₀=par(µ). (2.8)

The random variableW is independent ofh₁(par(µ),µ) and is absolutely continuous with respect the Lebesgue measure. By the definition of good vertices we have

{µis green}={h₁(par(µ),µ)<W} ∩D.

Denote by f_W the conditional density ofW given D∩C∩ {h₁(par(µ),µ)<W}. We have P

h₁(par(µ),µ)≥x

{µis green} ∩C

= P

h₁(par(µ),µ)≥x

{h₁(par(µ),µ)<W} ∩C∩D

= Z _∞

0

P

h₁(par(µ),µ)≥x

{h₁(par(µ),µ)<w} ∩C∩D∩ {W=w}

f_W(w)dw

(2.9)

Using the facts thath₁(par(µ),µ)is independent ofW,C andDand

P(h₁(par(µ),µ)≥x|h₁(par(µ),µ)<w)≤P(h₁(par(µ),µ)≥x), we get that the expression in (2.9) is less or equal toP

h₁(par(µ),µ)≥ x

. Summarising P

h₁(par(µ),µ)≥ x| {µis green} ∩C

≥P

h₁(par(µ),µ)≥x

. (2.10)

The inequality (2.9) implies that ifµ₁ is a child ofµandC ∈ Hµ we have P

µ₁is green | {µis green} ∩C

≥P

µ₁is green

. (2.11)

To see this, it is enough to integrate over the value ofh₁(par(µ),µ)and use the fact that, condition- ally onh₁(par(µ),µ), the events{µ₁is green}and{µis green}∩C are independent. The probability thatµ₁ is good conditionally on{h₁(par(µ),µ) =x}is a non-increasing function ofx, while the dis- tribution ofh₁(par(µ),µ)is stochastically smaller than the conditional distribution ofh₁(par(µ),µ) given{µis green} ∩C, as shown in (2.10).

Hence the cluster of green vertices is stochastically larger than a Galton–Watson tree where each vertex haskoffspring,k∈ {0, 1, . . . ,b}, with probabilityp_k defined in (2.5). To see this, fix a vertex µand letµ_i, withi∈ {0, 1, . . . ,b}be its children. It is enough to realize thatp_kis the probability that exactlykof theh₁(µ,µ_i), withi∈ {0, 1, . . . ,b}, are smaller than 1+h₁(par(µ),µ)₋₁

h₁ µ, par(µ) . As the random variables h₁(µ,µ_i),h₁ µ, par(µ)

and h₁(par(µ),µ) are independent exponentials with parameter one, we have

p_k= b

k Z ∞

0

Z _∞

0

P h₁(µ₀,µ)< y 1+z

kP h₁(µ₀,µ)≥ y 1+z

_b−k

e^−ye^−zdydz

= b

k Z ∞

0

Z _∞

0

1−e⁻

y 1+zk

e⁻

y 1+z(b−k)

e^−ye^−zdydz

= Xk

j=0

Z _∞

0

Z _∞

0

b k

k j

(−1)^je^−y(j+b−k+1+z)/(1+z)e^−zdydz

= Xk

j=0

b k

k j

(−1)^j Z _∞

0

1+z

j+b−k+1+ze^−zdz.

(2.12)

From the basic theory of branching processes we know that the probability that this Galton–Watson tree is finite (i.e. extinction) equals the smallest positive solution of the equation

x− Xb k=0

x^kp_k=0. (2.13)

The proof of (2.6) follows from the fact that 1−β_b≤1−α_b. This latter inequality is a consequence of the fact that the cluster of green vertices is stochastically larger than the Galton-Watson tree, hence its probability of non-extinction is not smaller. As b≥3, the Galton-Watson tree is supercritical (see [4]),henceβ_b<1.

For example, if we consider VRJP onG3, Lemma 2.2 yields 0.3809≤α₃≤0.8545.

Definition 2.3. Level j≥1is acut levelif the first jump after T_jis towards level j+1, and after time T_j+1 the process never goes back to X_Tj, and

L(X_Tj,∞)<2 and L(par(X_Tj),∞)<2.

Define l₁to be the cut level with minimum distance from the root, and for i>1, l_i:=min{j>l_i−1: j is a cut level}.

Define the i-thcut timeto beτ_i:=T_li. Notice that l_i=|X_τi|.

3 l

has an exponential tail

For any vertexν∈Vert(Gb), we define fc(ν), which stands forfirst childofν, to be the (a.s.) unique vertex connected toν satisfying

h₁(ν, fc(ν)) =min

h₁(ν,µ): par(µ) =ν . (3.14) For definiteness, the rootρis not a first child. Notice that condition (3.14) does not imply that the vertex fc(ν) is visited by the process. IfXvisits it, then it is the first among the children ofν to be visited.

For any pair of distributions f and g, denote by f ∗gthe distribution ofPV

k=1M_k, where

• V has distribution f, and

• {M_k,k∈N}is a sequence of i.i.d random variables, independent ofV, each with distribution g.

Recall the definition ofp_i,i∈ {0, . . . ,b}, given in (2.5). Denote byp⁽¹⁾the distribution which assigns toi∈ {0, . . . ,b}probability p_i. Define, by recursion,p^(j) :=p^(j−1)∗p⁽¹⁾, with j≥2. The distribution p^(j) describes the number of elements, at time j, in a population which evolves like a branching process generated by one ancestor and with offspring distributionp⁽¹⁾. If we let

m:=

Xb j=1

j p_j,

then the mean ofp^(j)ism^j. The probability that a given vertexµis good is, by definition, P

h₁(µ₀,µ)< h₁ µ₀, par(µ₀) 1+h₁ par(µ₀),µ₀

whereµ₀=par(µ).

As the h₁ par(µ₀),µ₀

is exponential with parameter 1, conditioning on its value and using inde- pendence between different Poisson processes, we have that the probability above equals

P

h₁(µ₀,µ)< 1

1+zh₁ µ₀, par(µ₀)

e^−zdz= Z _∞

0

1

2+ze^−zdz=0.36133 . . . . (3.15) Hence

m=b·0.36133>1, because we assumedb≥3.

Letq₀=p₀+p₁, and fork∈ {1, 2, . . . ,b−1}setq_k=p_k+1. Setqto be the distribution which assigns toi∈ {0, . . . ,b−1}probabilityq_i. For j≥2, letq^(j):=p^(j−1)∗q. Denote byq⁽_i^j) the probability that the distributionq^(j) assigns toi∈ {0, . . . ,(b−1)b^j−1}. The mean ofq^(j) ism^j−1(m−1). From now on,ζdenotes the smallest positive integer in{2, 3, . . . ,}such that

m^ζ−1(m−1)>1. (3.16)

Next we want to define a sequence of events which are independent and which are closely related to the event that a given level is a cut level. For any vertexν ofGb letΘ_ν be the set of verticesµ such that

• µis a descendant ofν,

• the difference|µ|-|ν|is a multiple ofζ,

• µis a first child.

By subtree rooted atν we mean a subtree ofΛ_ν that containsν. Setνe=fc(ν)and let A(ν):=

∃an infinite subtree ofGb root at a child ofνe, which is composed only by

good vertices and which contains none of the vertices inΘ_ν} (3.17) Fori∈N, letA_i :=A X_T

i

. Notice that if the process reaches the first child ofν and ifA(ν)holds, then the process will never return toν. Hence ifA_i holds, and ifX_Ti+1=X_Ti+1, theniis a cut level, provided that the total weights atX_Ti and its parent are less than 2.

Proposition 3.1. The events A_iζ, with i∈N, are independent.

Proof. We recall that ζ ≥ 2. We proceed by backward recursion and show that the events A_iζ depend on disjoint Poisson processes collections. Choose integers 0 < i₁ < i₂ < . . . < i_k, with i_j∈ζN:={ζ, 2ζ, 3ζ, . . .}for all j∈ {1, 2, . . . ,k}. It is enough to prove that

P \^k

j=1

A_i

j

= Yk

j=1

P A_i

j

. (3.18)

Fix a vertexν at leveli_k. The setA(ν)belongs to the sigma-algebra generated by

P(u,w): u,w ∈ Vert(Λ_ν) . On the other hand, the setT_k−1

j=1A_ij∩ {X_T

ik =ν}belongs to

P(u,w): u∈/Vert(Λ_ν) . As the two events belong to disjoint collections of independent Poisson processes, they are independent.

AsP(A(ν)) =P(A(ρ)), we have

P

A_ik∩

k−1\

j=1

A_ij

= X

ν:|ν|=i_k

P

A_ik∩

k−1\

j=1

A_ij∩ {X_T

ik =ν}

= X

ν:|ν|=i_k

P

A(ν)∩

k\−1 j=1

A_i

j∩ {X_T

ik =ν}

= X

ν:|ν|=i_k

P A(ν) P

^k\⁻¹

j=1

A_i

j∩ {X_T

ik =ν}

=P A(ρ) X

ν:|ν|=i_k

P ^k\⁻¹

j=1

A_ij∩ {X_T

ik =ν}

=P A(ρ) P

^k\⁻¹

j=1

A_ij

.

(3.19)

The eventsA(ν)and{X_T

ik =ν}are independent, and by virtue of the self-similarity property of the regular tree we getP A(ρ)

=P A_ik

. Hence

P

A_ik∩

k\−1 j=1

A_ij

=P A_ik P

^k\⁻¹

j=1

A_ij

. (3.20)

Reiterating (3.20) we get (3.18).

Lemma 3.2. Defineγ_bto be the smallest positive solution of the equation

x=

b−1

X

k=0

x^kq^(ζ)_k , (3.21)

whereζand(q⁽ⁿ⁾_k )have been defined at the beginning of this section. We have

P(A_i)≥1−γ_b>0, ∀i∈N. (3.22) Proof. Fix i∈N and letν^∗ = X_Ti. We adopt the following color scheme. The vertex fc X_Ti

is coloredblue. A descendantµofν^∗is colored blue if it is good, its parent isblue, and either

• |µ| − |ν^∗|is not a multiple ofζ, or

• ¹_ζ |µ| − |ν^∗|

∈Nandµis not a first child.

Vertices which are not descendants ofν^∗are not colored. Following the reasoning given in the proof of Lemma 2.2, we can conclude that the number of blue vertices at levels|ν^∗| + jζ, with j≥1, is stochastically larger than the number of individuals in a population which evolves like a branching process with offspring distributionq^(ζ), introduced at the beginning of this section. Again, from the basic theory of branching processes we know that the probability that this tree is finite equals the smallest positive solution of the equation (3.21). By virtue of (3.16) we have thatγ_b<1.

The proof of the following Lemma can be found in[10]pages 26-27 and 35.

Lemma 3.3. Suppose U_n is Bin(n,p). For x ∈(0, 1)consider the entropy H(x|p):=xln x

p + (1−x)ln1−x 1−p. We have the following large deviations estimate, for s∈[0, 1],

P U_n≤sn

≤exp{−n inf

x∈[0,s]H(x|p)}. Proposition 3.4.

i) Letν be a vertex with|ν| ≥1. The quantity

P A(ν)|h₁(ν, fc(ν)) =x is a decreasing function of x, with x≥0.

ii) P A(ν)|h₁(ν, fc(ν))≤x

≥P A(ν)

, for any x ≥0.

Proof. Suppose {fc(ν) =ν}. Given

h₁(ν,ν) =x , the set of good vertices inΛ_ν is a function of x. Denote this function byT :R⁺→ {subset of vertices of Λ_ν}. A child ofν, sayν₁, is good if and only if

h₁(ν,ν₁)< h₁(ν,ν) 1+x .

Hence the smallerx is, the more likelyν₁ is good. This is true for any child ofν. As for descendants ofν at level strictly greater than|ν|+2, their status of being good is independent ofh₁(ν, fc(ν)).

Hence T(x) ⊃ T(y) for x < y. This implies that the connected component of good vertices continingν is larger if{h₁(ν,ν) =x}rather than{h₁(ν,ν) = y}, for x< y. Hence

P A(ν)|h₁(ν, fc(ν)) =x, fc(ν) =ν

≥P A(ν)|h₁(ν, fc(ν)) = y, fc(ν) =ν

, for x< y.

Using symmetry we get i). In order to prove ii), use i) and the fact that the distribution ofh₁(ν, fc(ν)) is stochastically larger that the conditional distribution ofh₁(ν, fc(ν))given{h₁(ν, fc(ν))≤x}. Denote by[x]the largest integer smaller than x.

Theorem 3.5. For VRJP defined onGb, with b≥3, and s∈(0, 1), we have P l_[sn]≥n

≤expn

−[n/ζ] inf

x∈[0,s]H

x

(1−γ_b)ϕ_bo

, (3.23)

whereγ_b was defined in Lemma 3.2, and ϕ_b:=€

1−e^−bŠ €

1−e^−(b+1)Š b

b+2. (3.24)

Proof. By virtue of Proposition 3.1 the sequence 1l_Akζ, with k ∈ N, consists of i.i.d. ran- dom variables. The random variable P_[n/ζ]

j=1 1l_Ajζ has binomial distribution with parameters P A(ρ)

,[n/ζ]

. We define the event

B_j:={the first jump afterT_j is towards level j+1 and L X_Tj,T_j+1

<2, and L par(X_Tj),T_j+1

<2}.

Let Ft be the smallest sigma-algebra defined by the collection{X_s, 0 ≤ s≤ t}. For any stopping timeSdefineFS :=

A:A∩ {S≤t} ∈ Ft . Now we show P€

B_j | FT_i−1

Š≥€

1−e^−bŠ €

1−e^−(b+1)Š b

b+2=ϕ_b, (3.25)

where the inequality holds a.s.. In fact, by time T_i the total weight of the parent ofX_Ti is stochasti- cally smaller than 1+ an exponential of parameter b, independent ofFTi−1. Hence the probability that this total weight is less than 2 is larger than 1−e^−b. Given this, the probability that the first jump after T_i is towards level i+1 is larger than b/(b+2). Finally, the conditional probability that T_i+1−T_i < 1 is larger than 1−e^−(b+1). This implies, together withζ ≥ 2, that the random variableP[n/ζ]

j=1 1l_B

j is stochastically larger than a binomial(n,ϕ_b). For anyi∈N, and any vertexν with|ν|=iζ, set

Z := min

1, h₁ ν, par(ν) 1+h₁ par(ν),ν E := {X_Tiζ =ν} ∩ {L(par(ν),T_iζ)<2}. We have

B_iζ∩ {X_Tiζ=ν}={h₁(ν, fc(ν))<Z} ∩E.

Moreover, the random variable Z and the event E are both measurable with respect the sigma- algebra

Hfν :=σn

P(par(ν),ν),

P(u,w): u,w∈/Vert(Λ_ν) o .

Let f_Z be the density of Zgiven{h₁(ν, fc(ν))<Z}∩E. Using 3.4, ii), and the independence between h₁(ν, fc(ν))andHfν, we get

P A_iζ

B_iζ∩ {X_Tiζ =ν}

=P A(ν)

{h₁(ν, fc(ν))<Z} ∩E

= Z _∞

0

P A(ν)

{h₁(ν, fc(ν))<z}

f_Z(z)dz≥P A(ν)

= X

ν:|ν|=iζ

P A(ν)∩ {X_Tiζ=ν}

=P(A_iζ).

(3.26)

The first equality in the last line of (3.26) is due to symmetry. Hence P(A_iζ

B_iζ)≥P(A_iζ). (3.27)

If A_k∩B_k holds then k is a cut level. In fact, on this event, when the walk visits level k for the first time it jumps right away to level k+1 and never visits level k again. This happens because X_Tk+1 = fc(X_Tk) has a child which is the root of an infinite subtree of good vertices. Moreover the total weights atX_T

k and its parent are less than 2. Define e_n:=

[n/ζ]X

i=1

1l_A

iζ∩B_iζ.

By virtue of (3.22), (3.25), (3.27) and Proposition 3.1 we have thate_nis stochastically larger than a bin([n/ζ],(1−γ_b)ϕ_b). Applying Lemma 3.3, we have

P l_[sn]≥n

≤P e_n≤[sn]

≤exp n

−[n/ζ] inf

x∈[0,s]H

x

(1−γ_b)ϕ_bo .

The functionH x

(1−γ_b)ϕ_b

is decreasing in the interval(0,(1−γ_b)ϕ_b). Hence forn>1/ (1− γ_b)ϕ_b

, we have inf_x∈[0,1/n]H x

(1−γ_b)ϕ_b

=H 1/n

(1−γ_b)ϕ_b . Corollary 3.6. For n>1/ (1−γ_b)φ_b

, by choosing s=1/n in Theorem 3.5, we have P l₁≥n

≤expn

−[n/ζ] inf

x∈[0,1/n]H x

(1−γ_b)ϕ_bo

=exp n

−[n/ζ]H1 n

(1−γ_b)ϕ_bo ,

(3.28)

where, from the definition of H we have

nlim→∞H 1

n

(1−γ_b)ϕ_b

=ln 1

1−(1−γ_b)ϕ_b >0.

4 τ

has finite (2 + δ)-moment

The goal of this section is to prove the finiteness of the 11/5 moment of the first cut time. We adopt the following strategy

• first we prove the finiteness of all moments for the number of vertices visited by timeτ₁, then

• we prove that the total time spent at each of these sites has finite 12/5-moment.

Fixn∈Nand let

Π_n:= number of distinct vertices thatXvisits by timeT_n,

Π_n,k:=number of distinct vertices thatXvisits at levelkby timeT_n. LetT(ν):=inf{t≥0:X_t=ν}. For any subtree EofGb, b≥1, define

δ(a,E):=sup

¨ t:

Z t 0

1l{^Xs∈E}ds≤a

« . The processX_δ(t,E)is called the restriction ofXtoE.

Proposition 4.1(Restriction principle (see [8])). Consider VRJPXdefined on a treeJ rooted at ρ. Assume this process is recurrent, i.e. visits each vertex infinitely often, a.s.. Consider a subtree Je rooted atν. Then the process X_δ(t,Je)is VRJP defined onJe. Moreover, for any subtreeJ^∗disjoint from Je, we have that X_δ(t,Je)and X_δ(t,J∗)are independent.

Proof. This principle follows directly from the Poisson construction and the memoryless property of the exponential distribution.

Definition 4.2. Recall that P(x,y), with x,y∈Vert Gb

are the Poisson processes used to generateX onGb. LetJ be a subtree ofGb. Consider VRJPVonJ which is generated by using

P(u,v):u,v ∈ Vert(J) , which is the same collection of Poisson processes used to generate the jumps of X from the vertices ofJ. We say thatVis theextensionofXinJ. The processes V_t and X_δ(t,J)coincide up to a random time, that is the total time spent byXinJ.

We construct an upper bound for Π_n,k, with 2 ≤ k ≤ n−1. . Let G(k) be the finite subtree of Gb composed by all the vertices at level i with i ≤ k−1, and the edges connecting them. Let V be the extension ofX toG(k). This process is recurrent, because is defined on a finite graph. The total number of first children at levelk−1 is b^k−2, and we order them according to when they are visited by V, as follows. Letη₁ be the first vertex at level k−1 to be visited by V. Suppose we have definedη₁, . . . ,η_m−1. Letη_m be the first child at levelk−1 which does not belong to the set {η₁,η₂, . . . ,η_m−1}, to be visited. The vertices η_i, with 1≤ i≤ b^k−2 are determined byV. All the other quantities and events such as T(ν)andA(ν), withν running over the vertices ofGb, refer to the processX. Define

f_n(k):=1+b²inf{m≥1: 1l_A(par(ηm))=1}.

Let J := inf{n:T(η_n) =∞}, if the infimum is over an empty set, let J =∞. Suppose thatA(η_m) holds, then X, after time T(η_m), is forced to remain inside Λ_ηm, and never visits fc(η_m) again.

This implies that T(η_m+1) = ∞. Hence, if J = m then T_m−1

i=1 (A(par(η_i)))^c holds, and f_n(k) ≥ 1+b²(m−1). Similarly ifJ =∞ then f_n(k) =1+b²b^k−2 =1+b^k, which is an obvious upper bound for the number of vertices at levelkwhich are visited byX. On the other hand, ifJ=mthen the number of vertices at levelkwhich are visited byXis at most 1+(m−1)b². In fact, the processes XandVcoincide up to the random time when the former process leaves G(k)and never returns to it. Hence ifT(η_i)<∞thenXvisited exactlyi−1 distinct first children at levelk−1 before time T(η_i). On the event {J = m}we have that {T(η_m−1 < ∞} ∩ {T(η_m) =∞}, hence exactlym−1 first children are visited at levelk−1. This implies that at most 1+ (m−1)b²vertices at levelkare visited.

We conclude that f_n(k)overcounts the number of vertices at level kwhich are visited, i.e. Π_n,k ≤ f_n(k).

Recall thath₁(ν, fc(ν)), being the minimum over a set ofbindependent exponentials with rate 1, is distributed as an exponential with mean 1/b.

Lemma 4.3. For any m∈N, we have

P f_n(k) > 1+mb²

≤(γ_b)^m. Proof. Given T_m−1

i=1 (A(par(η_i))^c the distribution ofh(par(η_m),η_m) is stochastically smaller than an exponential with mean 1/b. Fix a set of verticesν_iwith 1≤i≤m−1 at levelk−1 and each with a different parent. Givenη_i =ν_i fori≤m−1, consider the restriction ofVto the finite subgraph obtained from G(k) by removing each of theν_i and par(ν_i), withi ≤ m−1. The restriction ofV to this subgraph is VRJP, independent ofTm−1

i=1 (A(par(η_i))^c, and the total time spent by this process in levelk−2 is exponential with mean 1/b. This total time is an upper bound forh(par(η_m),η_m).

This conclusion is independent of our choice of the verticesν_i with 1≤ i≤ m−1. Finally, using Proposition 3.4 i), we have

P f_n(k)>1+mb²| f_n(k)>1+ (m−1)b²

=P (A(par(η_m)))^c|

m\−1 i=1

(A(par(η_i))^c

≤P (A(par(η_m)))^c

≤γ_b.

(4.29)

Leta_n,c_nbe numerical sequences. We say that c_n=O(a_n)ifc_n/a_nis bounded.

Lemma 4.4. For p≥1, we haveE” Π^p_n—

=O(n^p).

Proof. Consider first the case p >1. Notice thatΠ_n,0 = Π_n,n =1. By virtue of Lemma 4.3, we have that sup_nE[f_n^p]<∞. By Jensen’s inequality

E[Π_n^p] =E



 2+ Xn−1 k=1

Π_n,k)

!p

≤n^pE



ⁿ⁻¹X

k=1

Π_n,k^p n +2^p

n



≤n^pE



Xⁿ⁻¹

k=1

f_n^p(k) n +2^p

n



 =O(n^p).

(4.30) As for the casep=1,

E[Π_n]≤2+ Xn−1 k=1

E[f_n(k)] =O(n).

Let

Π:=X

ν

1l_{νis visited before time τ₁}.

where the sum is over the vertices ofGb. In words,Πis the number of vertices visited beforeτ₁. Lemma 4.5. For any p>0we haveE[Π^p]<∞.

Proof. By virtue of Lemma 4.4, Æ

E Π^2p_n

≤C_b,p⁽¹⁾n^p, for some positive constantC⁽¹⁾_b,p. Hence using Cauchy-Schwartz,

E[Π^p] = X∞ n=1

E

Π^p_n1l{^l1=n}

≤ X∞ n=1

Æ E

Π^2p_n

P(l₁≥n)

≤C⁽¹⁾_b,p X∞ n=1

n^pexpn

−1

2[n/ζ]H1 n

(1−γ_b)ϕ_bo

<∞. In the last inequality we used Corollary 3.6.

Next, we want to prove that the 12/5-moment of L(ρ,∞)is finite. We start with three intermediate results. The first two can be found in[9]. We include the proofs here for the sake of completeness.

Lemma 4.6. Consider VRJP on{0, 1}, which starts at1, and with initial weights a₀ =c and a₁=1.

Define

ξ(t):=inf n

s:L(1,s) =t o

. We have

sup

t≥1

E

–L(0,ξ(t)) t

3™

=c³+3c²+3c. (4.31)

Proof. We have L(0,ξ(t+dt)) = L(0,ξ(t)) +χη, where χ is a Bernoulli which takes value 1 with probability L(0,ξ(t))dt, andη is exponential with mean 1/t. Given L 0,ξ(t)

, the random variablesχ andηare independent. Hence

E h

L(0,ξ(t+dt))i

−E h

L(0,ξ(t))i

= E[L(0,ξ(t))]

t dt,

i.e. E[L(0,ξ(t))] is solution of the equation y^′(t) = y(t)/t, with initial condition y(1) = c (see [8]). Hence

E[L(0,ξ(t))] =c t. Similarly

E h

L(0,ξ(t+dt))²i

=E h

L(0,ξ(t))² i

+2E h

L(0,ξ(t))E h

χ | L(0,ξ(t)) ii

E[η] + E h

χ² | L(0,ξ(t)) i

E[η²]

=E h

L(0,ξ(t))²i

+ (2/t)E h

L(0,ξ(t))²i

dt+ (2/t²)E h

L(0,ξ(t))i dt

=E h

L(0,ξ(t))²i

+ (2/t)E h

L(0,ξ(t))²i

dt+ (2c/t)dt.

ThusE h

L(0,ξ(t))² i

satisfies the equation y^′= (2/t)y+ (2c/t), with y(1) =c². Then, E

h

L(0,ξ(t))²i

=−c+€ c²+cŠ

t². Finally, reasoning in a similar way, we get thatE

h

L(0,ξ(t))³i

satisfies the equation y^′= (3/t)y+ 6(c²+c), with y(1) =c³. Hence,

E h

L(0,ξ(t))³i

=−3(c²+c)t+€

c³+3c²+3cŠ t³. Divide both sides byt³, and use the fact thatc>0 to get (4.31).

A rayσ is a subtree ofGb containing exactly one vertex of each level of Gb. Label the vertices of this ray using{σ_i,i≥0}, whereσ_i is the unique vertex at leveliwhich belongs toσ. Denote byS the collection of all rays ofGb.

Lemma 4.7. For any ray σ, consider VRJP X^(σ) := {X_t^(σ), t ≥ 0}, which is the extension of Xto σ.

Define

T_n^(σ) := inf{t >0:X_t^(σ)=σ_n}, L^(σ)(σ_i,t) := 1+

Z t 0

1l_{X(σ) s =σ_i}ds.

We have that

E

L^(σ)(σ₀,T_n^(σ))³

≤(37)ⁿ. (4.32)

Proof. By the tower property of conditional expectation,

E h

L^(σ)(σ₀,T_n^(σ))3i

=E



 L^(σ)(σ₁,T_n^(σ))3

E



 L^(σ)€

σ₀,T_n^(σ)Š L^(σ)€

σ₁,T_n^(σ)Š

!3 L^(σ)€

σ₁,T_n^(σ)Š







. (4.33)

At this point we focus on the process restricted to{0, 1}. This restricted process is VRJP which starts at 1, with initial weightsa₁=1, anda₀=1+h₁(σ₀,σ₁)andσ₀=ρ. By applying Lemma 4.6, and

using the fact thath₁(σ₀,σ₁)is exponential with mean 1, we have

E



 L^(σ)€

σ₀,T_n^(σ)Š L^(σ)€

σ₁,T_n^(σ)Š

!3 L^(σ)€

σ₁,T_n^(σ)Š



≤E

3(1+h₁(σ₀,σ₁)) + (1+h₁(σ₀,σ₁))²+ (1+h₁(σ₀,σ₁))³

=37.

(4.34) Then

E h

L(σ₀,T_n)3i

=E



E



 L^(σ)€

σ₀,T_n^(σ)Š L^(σ)€

σ₁,T_n^(σ)Š

!3 L^(σ)€

σ₁,T_n^(σ)Š



 L^(σ)(σ₁,T_n^(σ))3





≤37E h

L^(σ)(σ₁,T_n^(σ))3i .

(4.35)

The Lemma follows by recursion and restriction principle.

Next, we prove that

L(ρ,T(σ_n))≤L^(σ)(σ₀,T_n^(σ)). (4.36) In fact, we have equality ifT(σ_n)<∞, because the restriction and the extension ofXtoσcoincide during the time interval[0,T(σ_n)]. IfT(σ_n) =∞, it means thatXleft the rayσat a times<T_n^(σ). Hence

L(ρ,T(σ_n)) =L^(σ)(σ₀,s)≤ L^(σ)(σ₀,T_n^(σ)).

Hence, for anyν, with|ν|=n, we have E

L(ρ,T(ν))³

≤(37)ⁿ. (4.37)

Lemma 4.8. E h

L(ρ,∞)12/5i

<∞.

Proof. Recall the definition ofA(ν)from (3.17) and set D_k:= [

ν:|ν|=k−2

A(ν).

IfA(ν)holds, after the first time the process hits the first child ofν, if this ever happens, it will never visitν again, and will not increase the local time spent at the root. Roughly, our strategy is to use the extensions on paths to give an upper bound of the total time spent at the root by time T_k and show that the probability thatT_k

i=1D_i^cdecreases quite fast ink.

Using the independence between disjoint collections of Poisson processes, we infer thatA(ν), with

|ν|= k−2 are independent. In fact eachA(ν)is determined by the Poisson processes attached to pairs of vertices inΛ_ν. Hence

P(D^c_k)≤(γ_b)^bk−2 (4.38)

Define d = inf{n ≥ 1: 1l_D

n = 1}. Fix k ∈N. On the set {d = k}, define µ to be one of the first children at level k−1 such that A(par(µ)) holds. On {T(µ) < ∞} ∩ {d = k}, we clearly have L(ρ,∞) =L(ρ,T(µ)). On the other hand, on{T(µ)<∞}∩{d=k}, we have that, after the process reachesµit will never return to the root. Hence

L(ρ,∞) =1+ Z T(µ)

0

1l_{Xu=ρ}du+ Z _∞

T(µ)

1l_{Xu=ρ}du=1+ Z T(µ)

0

1l_{Xu=ρ}du=L(ρ,T(µ)).