XinxingChen andDayueChen Somesufficientconditionsforinfinitecollisionsofsimplerandomwalksonawedgecomb

El e c t ro nic

Journ a l of

Pr

ob a b il i t y

Vol. 16 (2011), Paper no. 49, pages 1341–.

Journal URL

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

Some sufficient conditions for infinite collisions of simple random walks on a wedge comb

Xinxing Chen^∗and Dayue Chen^†

Abstract

In this paper, we give some sufficient conditions for the infinite collisions of independent simple random walks on a wedge comb with profile{f(n),n∈Z}. One interesting result is that two independent simple random walks on the wedge comb will collide infinitely many times if f(n) has a growth order as nlogn. On the other hand, if {f(n),n ∈Z} are given by i.i.d. non- negative random variables with finite mean, then for almost all wedge combs with such profile, three independent simple random walks on it will collide infinitely many times.

Key words:wedge comb, simple random walk, infinite collision property, local time.

AMS 2010 Subject Classification:Primary 60J10, 60K37.

Submitted to EJP on November 1, 2010, final version accepted June 21, 2011.

∗Department of Mathematics, Shanghai Jiaotong University, Shanghai 200240, China; Research partially supported by the NSFC grant No. 11001173. [email protected]

†School of Mathematical Sciences & Center for Statistical Science, Peking University, Beijing 100871, China; Research partially supported by the NSFC grant No. 10625101 and the 973 grant No. 2011CB808000. [email protected], http://www.math.pku.edu.cn/teachers/dayue/indexE.htm

1 Introduction

In this paper, we study the number of collisions of two independent simple random walks on an infinite connected graph with finite degrees. Let X ={X_n} and X⁰= {X⁰_n}be independent simple random walks starting from the same vertex. As usual, we say that the graph has the infinite collision property if X and X⁰ collide infinitely often, i.e.,|{n:X_n = X_n⁰}|= ∞, almost surely. Likewise we say that the graph has the finite collision property if X andX⁰ collide finitely many times almost surely. Krishnapur and Peres[5]first finds the example Comb(Z)on which two independent simple random walks will collide finitely many times. Notice thatZ⊂Comb(Z⁾⊂Z^{2 and both}Z^andZ² have the infinite collision property. This indicates that the infinite collision property is not simply monotone. So we are interested in probing the subgraphs of Comb(Z).

Let f be a function mapping Z^intoR⁺. It induces a graph called wedge comb, Comb(Z^,f), with the set of vertices

V={(n,x): n,x∈Z^,−f(n)≤ x≤ f(n)}

and the set of edges{[(n,x),(n,y)]:|x− y|=1} ∪ {[(n, 0),(m, 0)]:|m−n|=1}.

Chen, Wei and Zhang[3]shows that Comb(Z^,f) has the infinite collision property when f(n)≤n¹⁵. Recently, Barlow, Peres and Sousi[1]gives a sufficient condition (in terms of Green functions) for the infinite collision property and shows that Comb(Z^,f) has the infinite collision property when f(n)≤ n; while it has the finite collision property when f(n) =n^α for each α >1. Collisions on other graphes, such as random clusters and random trees are studied in[1]and[2]. We will restrict our attention to wedge combs, and give a sufficient condition for a wedge comb to have the infinite collision property.

Theorem 1.1. Let f˘(n) =1∨max_−n≤i≤n f(i). If X∞

n=1

1

f˘(n) =∞, (1.1)

then Comb(Z^,f ) has the infinite collision property.

We like to point out that it is not required that f(n)is monotone innforn≥0. This would enable us to deal with a large class of wedge combs. As an application of Theorem 1.1, one can improve the results of[3]and[1].

Corollary 1.2. If f(−n) +f(n) =O(nlogn), then Comb(Z^,f ) has the infinite collision property.

Corollary 1.2 should be compared with Theorem 1.3. Unfortunately there is a gap. We still do not know the answer for 1< β≤2.

Theorem 1.3. Let f(x) =|x|log^β(|x| ∨1)for x∈Z^{. If}β >2, then the total number of collisions by two independent simple random walks on Comb(Z^,f ) is a.s. finite.

A natural question to ask is what happens if there are more than two independent simple random walks. Suppose thatX, X⁰andX⁰⁰are independent simple random walks on a graph. If|{n:X_n = X⁰_n=X⁰⁰_n}|=∞almost surely, then we say that the three processes collide together infinitely often and that the graph has the infinitely many triple collisions property. It is shown in[1]thatZ^{has the} infinitely many triple collisions property; while Comb(Z^,α) has the finitely many triple collisions property for anyα >0.

Theorem 1.4. Let {f(n),n∈Z} are independent and identically distributed random variables with lawµsupported in[0,∞). Ifµhas finite mean, then almost surely Comb(Z^,f ) has the infinitely many triple collisions property.

Theorem 1.1 will be proved in the next section. Proofs of Theorems 1.3 and 1.4 will be given in Section 4 and Section 3 respectively. Throughout this paper we use the following notation. For u,v ∈V^{, Pu} is the probability measure of the simple random walk X starting fromu, and P^u,v is the joint probability measure of the two random walksX andX⁰starting fromuandv, respectively.

E^u andE^u,v stand for the corresponding expectations. For vertex x ∈V^{, we write x}1 for the first coordinate ofx andx₂ for the second coordinate, i.e.,x = (x₁,x₂). Fora,b∈R^,a∨b=max{a,b} anda∧b=min{a,b}. For setA,|A|stands for the number of elements ofA.

2 Proof of Theorem 1.1

LetX ={X_n,n≥0}be a simple random walk on Comb(Z^,f). Write X_n= (Un,V_n)forn≥0. Then {U_n}is a random process onZ. Define a sequence of stopping times: T₀=0 and

T_k+1:=inf{n>T_k:U_n6=U_n−1}.

Almost surelyT_k<∞for eachk≥1. By definition,X stays in the line segment{u} ×[−f(u),f(u)], whereu=U_Tk, during time[T_k,T_k+1−1]. LetW_k=U_Tk. Then{W_k,k≥0}is a simple random walk onZ(by the strong Markov property).

Forn≥1, let

Vn={(x1,x₂)∈V^:|x₁| ≤n}, and

θ_n=inf{m≥0 :X_m6∈V_n−1}. (2.1) Notice that ifX₀∈V_n−1 thenθ_n is the hitting time of{(−n, 0),(n, 0)}byX.

LetX⁰ be another simple random walk on Comb(Z^,f), independent ofX, andU_n⁰,V_n⁰,W_k⁰,T_k⁰,θ_n⁰ be the corresponding counterparts. Define another sequence of stopping times by settingσ0=0 and

σ_m+1:=inf{n> σ_m: U_n=U_n⁰ and (U_n6=U_n−1orU_n⁰ 6=U_n⁰₋₁)}. Lemma 2.1. For any" >0, there exists d∈N^{such that}

P^u,v€

σN≥θd N∧θ_{d N}⁰ Š

< ", for all N∈Nand for all u,v∈VN with u₁+u₂+v₁+v₂ being even.

Proof. Forn≥0, define

Z_2n=U_n−U_n⁰ and Z_2n+1=U_n+1−U_n⁰. Define a sequence of stopping times inductively by settingτ0=0 and

τ_m=inf{n> τ_m−1:Z_n6=Z_n−1}.

By the strong Markov property,{Z_τm,m≥0}is a simple random walk onZ. Suppose thatu,v∈VN. Writeu= (u1,u₂)andv= (v1,v₂). Then|u₁|,|v₁| ≤Nand

Z_τ0=u₁−v₁∈[−2N, 2N]. (2.2)

By definition, ifZ_τm=0 then

U_k=U_k⁰, U_k6=U_k−⁰ ₁, τm=2k for somek∈Z^{+; or} U_k+1=U_k⁰, U_k6=U_k⁰, τm=2k+1 for somek∈Z^+.

Notice that U_n +V_n +U_n⁰ +V_n⁰ is always even under the assumption that U₀ +V₀ +U₀⁰ +V₀⁰ = u₁+u₂+v₁+v₂ is even. This fact, together with thatU_k+1 =U_k⁰ 6=U_k, implies thatU_k+1 =U_k+⁰ ₁. For eachM≥0, let

ξ(0,M):=|{m:Z_τ

m=0, 0≤m≤M}|, the local time of 0 by{Z_τm,m≥0}. As a result of the previous argument,

{ξ(0,M)≥N} ⊆ {σN ≤τM} ⊆ {σN≤T_M∧T_M⁰ }. (2.3) For each we ∈Z^{, letPwe} be the probability measure of a simple random walkWfonZstarting from w. Usee ξ(·e ,·)to denote the local time byWf. By (9.11) of[7], there exists x ∈Nsuch that, for any we∈Z^,|we| ≤2N,

P^we(ξ(e0,x N²)≤N)< "

2. (2.4)

By (2.2), (2.4) and the argument that{Z_τm,m≥0}is a simple random walk onZ^{, for anyN}∈N andu,v∈VN

P^u,v(ξ(0,x N²)≤N) =P^u1−v1(ξ(e 0,x N²)≤N)< "

2. (2.5)

Furthermore, by Theorem 2.13 of[7]and the argument thatW is a simple random walk onZ^{, we} can findd∈Nsuch that for anyN∈N^andu∈VN,

P^u(T_{x N}²≥θd N) =P^u( max

0≤k≤x N²|W_k| ≥d N) =P^u1( max

0≤k≤x N²|Wf_k| ≥d N)≤ "

4. (2.6) Combining (2.3), (2.5) with (2.6), we arrive at the desired conclusion.

P^u,v€

σN ≥θd N∧θ_{d N}⁰ Š

=P^u,v€

σN ≥θd N∧θ_{d N}⁰ ,σN ≥τx N²

Š+P^u,v€

σN≥θd N∧θ_{d N}⁰ ,σN< τx N²

Š

≤P^u,v σ_N ≥τ_{x N}²

+P^u,v€

σ_N≥θ_{d N}∧θ_{d N}⁰ ,σ_N≤T_{x N}²∧T_{x N}⁰ 2

Š

≤P^u,v(ξ(0,x N²)≤N) +P^u,v€

θd N ≤T_{x N}² or θ_{d N}⁰ ≤T_{x N}⁰ 2

Š

≤P^u,v(ξ(0,x N²)≤N) +P^u θd N ≤T_{x N}²

+P^v θd N≤T_{x N}²

≤"

ƒ The above lemma shows that, with a small exception, the number of collisions is bounded by depar- ture timesθ andθ⁰ ofU andU⁰ linearly. In the following applications of Lemma 2.1,"=1/2, we can findd∈N, such that for allN∈Nand for allu,v∈VN withu₁+u₂+v₁+v₂being even,

P^u,v€

σN≥θd N∧θ_{d N}⁰ Š

< 1

2. (2.7)

Obviously,d≥2. We fix suchd throughout this section.

Next, we want to estimate the probability that there is at least one collision ofX andX⁰onceU and U⁰collide. To this end, we define a sequence of events. Form≥0, let

Ψm=

X_n=X⁰_n, |V_n|+|V_n⁰| ≥ |V_σm|+|V_σ⁰

m|

for someσm≤n<inf{h> σm:V_h=0 orV_h⁰=0} . Notice thatΨ_m occurs ifX_σm=X_σ⁰

m. Moreover, suppose that(u, 0),(u,v)∈V^{with v}being even, if Ψm∩ {X_σm= (u, 0),X_σ⁰

m= (u,v)}occurs thenX enters the segment{u} ×[−f(u),f(u)]and collides withX⁰at a vertex with height greater than or equal to v/2 after timeσ_mbut before X or X⁰ exits the segment. Here, by height (of a vertex) we mean the distance from the vertex to the x-axis. The next lemma shows that these events have good bounds.

Lemma 2.2. There exist c₁,c₂>0, such that for all(u,v)∈Vwith v being even, c₁

|v| ∨1≤P(u,0),(u,v)(Ψ0)≤ c₂

|v| ∨1.

Proof. We first examine the case that f(u)≥2v>0 andvis even. Forx ∈Z^{, define} τx =inf{n>0 :X_n= (u,x)},

andτ⁰_x similarly. Ifτ2v< τ0andX⁰stays in{u} ×[v/2, 3v/2]before timeτ2v, thenX andX⁰must collide before timeτ2v< τ0∧τ⁰₀at a vertex whose height is greater than or equal tov/2. Therefore

P(u,0),(u,v)(Ψ0)≥P(u,0),(u,v)

X₁= (u, 1), τ2v≤v²∧τ0, τ⁰_v/2∨τ⁰_3v/2≥v²

=P^(u,0)(X1= (u, 1))P^(u,1)€

τ2v≤v²,τ2v < τ0

ŠP^(u,v)€

τ_v/2∨τ_3v/2≥v²Š

=1 4P^(u,1)€

τ2v≤v²,τ2v < τ0

ŠP^(u,v)€

τ_v/2∨τ_3v/2≥v²Š

. (2.8)

Obviously, ifX starts from vertex(u, 1)thenX will stay at{u}×[1, 2v−1]∩Z²before timeτ0∧τ2v. Consider a simple random walk onZ^{. Let}{ηi}be i.i.d. random variables withP(η1 =1) =P(η1=

−1) =1/2, andS_k=1+Pk

i=1ηi fork≥0. Define stopping times τe2v=inf

k>0 :S_k≥2v and τe0=inf

k>0 :S_k≤0 .

Both{eτ2v≤v²}and{eτ2v <τe0}are increasing events of{ηi,i≥1}. By the FKG inequality and the gambler’s ruin problem (or refer to Lemma 3.1 of[7]),

P€

τe2v≤v²,τe2v<τe0

Š≥P(eτ2v≤v²)P(eτ2v<τe0) =P(eτ2v ≤v²) 1

2v. (2.9)

It can be verified that {X_n : 0 ≤ n≤τ0∧τ2v}conditioned on {X₀ = (u, 1)} has the same law as {S_n: 0≤n≤τe2v∧τe0}. So

P^(u,1)€

τ2v≤v²,τ2v< τ0

Š=P€

τe2v≤v²,τe2v<τe0

Š. (2.10)

By Theorem 2.13 of[7]again, there existsc₁>0 independent ofuandv, such that P(eτ2v ≤v²)≥c₁ and P^(u,v)€

τ_v/2∨τ_3v/2≥v²Š

≥c₁. (2.11)

Taking (2.8)-(2.11) together, we obtain the first inequality of the lemma.

P^(u,0),(u,v)(Ψ0)≥ c²₁

8v. (2.12)

We now turn to the proof of the second inequality. Define H=

X∞

n=0

1_{X

n=X_n⁰,n<τ0∧τ⁰₀},

the number of collisions ofX andX⁰before one of them exits{u} ×[1,f(u)]. Then

E^(u,0),(u,v)(H) = X∞

n=0 f(u)

X

x=1

P^(u,0),(u,v)(X_n=X⁰_n= (u,x), n< τ0∧τ⁰₀)

= X∞

n=0 f(u)

X

x=1

P^(u,0)(Xn= (u,x), n< τ0)P^(u,v)(Xn= (u,x), n< τ0)

≤2 X∞

n=0 f(u)

X

x=1

P^(u,0)(Xn= (u,x), n< τ0)P^(u,x)(Xn= (u,v), n< τ0)

=2 X∞

n=0

P^(u,0)(X2n= (u,v), 2n< τ0)

=2E^(u,0)(number of visits to(u,v)byX before returning to(u, 0) ).

In the previous arguments, the inequality follows from the property of reversible Markov chain and the fact that the reversible measure for x∈[1,f(u)]∩Zis just the degree of the vertex. Therefore

P^(u,v)(X_n= (u,x), n< τ0)≤2P^(u,x)(X_n= (u,v), n< τ0). By Theorem 9.7 of[7],

E^(u,0),(u,v)(H)≤2. (2.13)

The second inequality of the lemma will follow once we show that there existsc₂>0 independent ofu,vsuch that

E^(u,0),(u,v)(H|Ψ0)≥c₂v. (2.14) When the eventΨ0occurs, there is a collision at vertex(u,w)for somewwithw≥v/2. Conditioned on this event, the total number of collisions in the set {u} ×[v/3,f(u)] will be greater than the number of collisions that take place before the first time that one of the random walks exits this interval. A lower bound could be obtained by considering two independent simple random walks in an interval, starting at v/2. Before hitting eitherv/3 or 2v/3, the average number of collisions is the average number of returning to the starting point before exiting the interval, which is exactly the Green function of a simple random walk starting atv/2, before exiting the interval(v/3, 2v/3). This is of orderv.

By (2.13) and (2.14), we conclude that P^(u,0),(u,v)(Ψ0) ≤2/(c₂v). This completes the proof of the case that f(u)≥2v>0 andvis even. The proof can be modified to treat other cases and is omitted

here. ƒ

Now we are ready to state a key lemma. To be concise, we set f˘(n) =1∨ max

−n≤i≤nf(i). As a result, ˘f is a strictly positive and increasing function onZ^+.

Lemma 2.3. There exists c>0such that, for all N ∈Nand for all u,v∈VN with u₁+u₂+v₁+v₂ being even,

P^u,v X_n=X_n⁰ for somen∈[0,θ_{d N}∧θ_{d N}⁰ )

≥ cN

˘f(d N) +N. Proof. Let

H= XN

m=1

|V_σm| ∨ |V_σ⁰

m| ∨1 1_Ψ

m1_{σ

m<θd N∧θ_{d N}⁰ }.

IfH >0 then X andX⁰collide before timeθd N∧θ_{d N}⁰ . We shall use the second moment method to estimate the probability of{H>0}. Calculate directly as follows.

E^u,v(H) =

N

X

m=1

E^u,v

(|V_σm| ∨ |V_σ⁰

m| ∨1)1_Ψ

m1_{σ

m<θd N∧θ_{d N}⁰ }

= XN

m=1

E^u,vh E^u,v

(|V_σm| ∨ |V_σ⁰

m| ∨1)1_Ψm1_{{σm<θd N∧θ}0 d N}

X_i,X⁰_i, 0≤i≤σm

i

= XN

m=1

E^u,vh

(|V_σm| ∨ |V_σ⁰

m| ∨1)P^u,v€ Ψm

X_i,X_i⁰, 0≤i≤σm

Š;σm< θd N∧θ_{d N}⁰ i

=

N

X

m=1

E^u,vh (|V_σ

m| ∨ |V_σ⁰

m| ∨1)P^Xσm,Xσm0 Ψ0

;σm< θd N∧θ_{d N}⁰ i

(2.15)

≥ XN

m=1

E^u,v€

c₁;σm< θd N∧θ_{d N}⁰ Š

by Lemma 2.2

≥c₁NP^u,v(σ_N < θ_{d N}∧θ_{d N}⁰ )≥ c₁

2N by (2.7).

Here the equation (2.15) is by the strong Markov property. Applying Lemma 2.2 and the strong Markov property again, we have the following estimates.

E^u,v(H²)

=E^u,v XN

m=1

(|V_σm| ∨ |V_σ⁰

m| ∨1)1_Ψ

m1_{σ

m<θd N∧θ_{d N}⁰ }

XN

n=1

(|V_σn| ∨ |V_σ⁰

n| ∨1)1_Ψ

n1_{σ

n<θd N∧θ_{d N}⁰ }

!

=E^u,v XN

m=1

(|V_σm| ∨ |V_σ⁰

m| ∨1)²1_Ψ

m1_{σ

m<θd N∧θ_{d N}⁰ }

!

+2E^u,v XN

m=1

(|V_σm| ∨ |V_σ⁰

m| ∨1)1_Ψ

m1_{σ

m<θd N∧θ_{d N}⁰ }

XN

n>m

(|V_σn| ∨ |V_σ⁰

n| ∨1)1_Ψ

n1_{σ

n<θd N∧θ_{d N}⁰ }

!

≤2 ˘f(d N)E^u,v XN

m=1

(|V_σm| ∨ |V_σ⁰

m| ∨1)1_Ψ

m1_{σ

m<θd N∧θ_{d N}⁰ }

!

+2 XN

m=1

XN

n>m

E^u,v

(|V_σm| ∨ |V_σ⁰

m| ∨1)1_Ψ

m1_{σ

m<θd N∧θ_{d N}⁰ }(|V_σn| ∨ |V_σ⁰

n| ∨1)1_Ψ

n1_{σ

n<θd N∧θ_{d N}⁰ }

=2 ˘f(d N)E^u,v(H) +2

N

X

m=1 N

X

n>m

E^u,v (|V_σ

m| ∨ |V_σ⁰

m| ∨1)1_Ψ

m1_{σ

m<θd N∧θ_{d N}⁰ }

× (|V_σn| ∨ |V_σ⁰

n| ∨1)P^Xσn,Xσn0 (Ψ0)1_{σ

n<θd N∧θ_{d N}⁰ }

≤2 ˘f(d N)E^u,v(H) +2c₂

N

X

m=1 N

X

n>m

E^u,v (|V_σ

m| ∨ |V_σ⁰

m| ∨1)1_Ψ

m1_{σ

m<θd N∧θ_{d N}⁰ }

≤(2 ˘f(d N) +2c₂N)E^u,v(H). By the H¨older inequality,

P^u,v(H>0)≥[E^u,v(H)]²

E^u,v[H²] ≥ E^u,v(H)

2 ˘f(d N) +2c₂N ≥ c₁N 4 ˘f(d N) +4c₂N.

We have reached the conclusion of the lemma. ƒ

Proof of Theorem 1.1. It suffices to consider the case that two independent simple random walks on Comb(Z^,f) starting from the same vertex (0, 0). Notice that as X,X⁰ start from (0, 0), almost surelyθd∧θ_d⁰ < θ_d²∧θ_d⁰2< θ_d³∧θ_d⁰3<· · ·. Define form≥1,

Υm={X_n=X⁰_n for some n∈[θd^m∧θ_d^0m,θd^m+1∧θ_d⁰m+1)}.

We writeP=P^(0,0),(0,0)andt=θd^m∧θ_d^0m for short. By the strong Markov property and Lemma 2.3, there existsc>0 such that for allm∈N

P(Υm|1_Υ

i, 1≤i<m, X_n,X⁰_n, n≤θd^m∧θ_d^0m)

=P^Xt,X0t X_n=X_n⁰ for some n∈[0,θ_d^m+1∧θ_d⁰m+1)

≥ cd^m f˘(d^m+1) +d^m+1. We will show below that (1.1) implies that X∞

m=1

d^m

f˘(d^m) +d^m =∞. (2.16)

Consequently,P(Υminfinitely often)=1 by the second Borel-Cantelli Lemma (extended version, Page 237 of[4]). Furthermore,

P(Xn=X⁰_n infinitely often)≥P(Υm infinitely often) =1.

We now prove (2.16). If ˘f(d^m)≤d^m for infinitely manym, then it is trivial and we have nothing to do. Otherwise, there existsm₀such that ˘f(d^m)>d^m for allm≥m₀. Hence it suffices to prove

X∞

m=1

d^m

f˘(d^m) =∞. (2.17)

SetD_m=d+d²+· · ·+d^m. Thend^m≤D_m≤d^m+1, and d^m

f˘(d^m)≥ 1 d

D_m+1

X

l=Dm+1

1 f˘(l). So

X∞

m=1

d^m f˘(d^m) ≥ 1

d X∞

m=1 D_m+1

X

l=Dm+1

1

˘f(l) = 1 d

X∞

l=d+1

1

f˘(l)=∞.

Hence (2.16) holds in either case and the proof of the theorem is completed. ƒ

3 Proof of Theorem 1.4

In this section we will show a slightly more general result from which Theorem 1.4 will follow.

Theorem 3.1. If P_n

i=−nf(i) =O(n), then Comb(Z^,f ) has the infinitely many triple collisions prop- erty.

To prove the theorem we introduce yet another independent simple random walk X⁰⁰ on Comb(Z^{,f). For any u,v,w} ∈ V^{, we write Pu,v,w} for the joint probability measure of the three independent simple random walksX,X⁰andX⁰⁰starting fromu,vandw, respectively. LetE^u,v,w be the corresponding expectation. By the assumption of Theorem 3.1, there existsc>4, such that for alln∈N^,

Xn

i=−n

f(i)≤

c 2−2

‹

n. (3.1)

Hence we fix f andcwhich satisfy (3.1) throughout this section. Since ([−n,n]× {0})∩Z²⊆Vn=

n

[

i=−n

{i} ×[−f(i),f(i)]

!

∩Z^2, therefore

2n≤ |Vn| ≤cn. (3.2)

Recall thatθn is defined in (2.1).

Lemma 3.2. For any" >0, there exists d∈N\ {1}such thatP^u(θd n≤n²)≤"for all n∈N^{and for} all u∈Vn.

Proof. For eachwe∈Z^{, letPwe} be the probability measure of a simple random walkWfonZ^starting from w. By Theorem 2.13 ofe [7]and the argument thatW is a simple random walk onZ^{, there} existsd ∈N\ {1}which depends only on", such that for alln∈Nand for allu∈Vn

P^u(θ_{d n}≤n²)≤P^u

max

0≤k≤n²|W_k| ≥d n

=P^u1

max

0≤k≤n²|Wf_k| ≥d n

≤P⁰

max

0≤k≤n²|Wf_k| ≥(d−1)n

≤".

ƒ Forx ∈V^{, let}τ_x =inf{m≥0 : X_m=x}be the hitting time ofx byX.

Lemma 3.3. For " >0, there exists c₁ ∈Nsuch that P^u τv > c₁n²

≤ "for all n∈Nand for all u,v∈Vn.

Proof. Fix 0< " <1,n∈N^andu∈Vn. Leth,c₁∈N^{such that} h> 8(c+1)

" and c₁> 6c²h²

" . (3.3)

Suppose that the random walkX starts from vertexu∈Vn. Sinceθhn=τ₍hn,0)∧τ₍₋hn,0)foru∈Vn, then

P^u(τv>c₁n²)≤P^u(τv> θhn) +P^u(θhn>c₁n²)

≤P^u(τv> τ_(hn,0)) +P^u(τv> τ_(−hn,0)) +P^u(θhn>c₁n²). (3.4) Hence we are going to estimate probabilities of the three events above.

Because Comb(Z^,f) is a tree, there exists a unique simple path fromvto(hn, 0). Ifuis a vertex on the path, then by the gambler’s ruin problem and the fact thatX is a recurrent process,

P^u(τv> τ₍hn,0)) = dist(u,v) dist(v,(hn, 0)) where dist(·,·)is the graph distance. By the assumption (3.3),

P^u(τ_v> τ_(hn,0))≤ 2n+max_−n≤k≤nf(k)

hn−n ≤ 2+c h−1 < "

3. (3.5)

Ifuis not on the path, then with probability oneX will reach the path first atv,(v₁, 0)or(u₁, 0). A slight change in the proof actually shows that (3.5) holds for these cases. So in all cases, (3.5) gives an upper bound of the probability of the first event. Similarly, the probability of the second event is also small.

P^u(τ_v> τ_(−hn,0))< "

3. (3.6)

We now study the third event. Let ˜Gbe the spanning tree of Vhn, which is a connected subgraph of Comb(Z^,f). The processX before timeθhnis also a simple random walk on ˜G^{. Regard}G^{e as an} electric network that each edge is assigned a unit conductance. Then by Proposition 10.6 of[6],

E^u(θhn)≤c_Geℜ(u↔ {−hn,hn}), wherec

Ge is twice of the total conductance andℜ(u↔ {−hn,hn})is the effective resistance between uand{−hn,hn}. SinceGe is a tree, we can easily get that

c_Ge =2|Vhn| −2 and ℜ(u↔ {−hn,hn})≤ |Vhn|.

Consequently,E^u(θhn)≤2|Vhn|²≤2c²h²n². By the Markov inequality and (3.3), we get the proba- bility of the third event

P^u(θhn>c₁n²)≤ "

3. (3.7)

Combining (3.4)-(3.7) together we complete the proof of the lemma. ƒ

By Lemmas 3.2 and 3.3, we can findc₁∈N^andd∈N\ {1}such that P^u(τv>c₁n²)≤ 1

4 and P^u(θd n≤c₁n²)≤ 1

4. (3.8)

for alln∈Nand for allu,v∈Vn. Fix such c₁ andd throughout this section. We are now ready to proceed to a similar key argument as Lemma 2.3.

Lemma 3.4. There exists c₂>0such that for all N ∈N\{1}and for all u,v,w∈VN with(−1)^u1+u2= (−1)^v1+v2= (−1)^w1+w2,

P^u,v,w€

X_n=X⁰_n=X_n⁰⁰for somen∈ 0,Ȋ

≥ c₂ logN, whereΘ =θ_{d N}∧θ_{d N}⁰ ∧θ_{d N}⁰⁰ =inf

m≥0 :{X_m,X_m⁰,X_m⁰⁰} 6⊆V_{d N−}1 .

Proof. FixN ∈N\ {1}andu,v,w ∈VN. Notice that Θis the first time that one ofX,X⁰,X⁰⁰ exits Vd N−1. Let

H=

2c₁N²

X

n=0

1_{X

n=X_n⁰=X⁰⁰_n∈VN,n<Θ}. We will prove that

E^u,v,w(H)≥c^∗₁ and E^u,v,w(H²)≤c^∗₂E^u,v,w(H)logN. (3.9) Then by the H¨older inequality,

P^u,v,w(Xn=X⁰_n=X_n⁰⁰for somen<Θ)≥P^u,v,w(H>0)≥

E^u,v,w(H)2

E^u,v,w H² ≥ c₁^∗ c₂^∗logN.

Now we begin to prove (3.9). For x ∈VN, letq_n(u,x) =P^u(X_n = x,θd N > n). Thenq_2n(x,x) is decreasing innby the spectral theory (or referring to[1]). By the strong Markov property, for any c₁N²≤n≤2c₁N² withu₁+u₂+x₁+x₂+nandk+nbeing even,

P^u(Xn=x,θd N >n) = Xn

k=0

P^u(Xn=x,τx =k,n< θd N)

= Xn

k=0

P^u(τx =k< θd N)P^u(Xn= x,n< θd N |τx =k< θd N)

= Xn

k=0

P^u(τx =k< θd N)qn−k(x,x)

≥ Xn

k=0

P^u(τx =k< θd N)q2c₁N²(x,x)

=q2c₁N²(x,x)P^u(τx ≤n,θd N > τx)

≥q_2c1N²(x,x) P^u(τx ≤c₁N²) +P^u(θd N>c₁N²)−1

≥1 2q_2c

1N²(x,x) by (3.8).

As a result,

E^u,v,w(H) = X

x∈VN

2c₁N²

X

n=0

P^u,v,w(Xn=X_n⁰ =X_n⁰⁰=x,Θ>n)

= X

x∈VN

2c₁N²

X

n=0

P^u(X_n=x,θd N >n)P^v(X_n=x,θd N >n)P^w(X_n=x,θd N>n)

≥ 1 8

X

x∈VN

X

c₁N²≤n≤2c₁N² u₁+u2+x₁+x₂+neven

”q_2c

1N²(x,x)—3

≥ c₁N² 16

X

x∈VN

”q_2c1N²(x,x)—3

≥ c₁N² 16|VN|²





 X

x∈VN

q_2c1N²(x,x)







3

≥ c₁ 16c²





 X

x∈VN

q_2c1N²(x,x)







3

.

The third inequality is by the H¨older inequality. Applying the H¨older inequality and (3.8) again, we have the following estimates.

X

x∈VN

q_2c1N²(x,x)≥ X

x∈VN

X

y∈Vd N

q_c1N²(x,y)q_c1N²(y,x)

≥1 4

X

x∈VN

X

y∈Vd N

[q_c1N²(x,y)]²

≥ 1

4|Vd N| X

x∈VN





 X

y∈Vd N

q_c1N²(x,y)







2

≥ |VN| 4|Vd N| min

x∈VN



 X

y

P^x(Xc₁N²= y,θd N >c₁N²)





2

≥ 1 2cd min

x∈VN

”P^x(θd N >c₁N²)—2

≥ 1 4cd. Combining the two estimates together, we obtain that

E^u,v,w(H)≥ c₁ 16c²·

1 4cd

3

= c₁ 1024c⁵d³. The first part of (3.9) is proved by choosingc₁^∗=c₁c⁻⁵d⁻³/1024.

We now turn to the second moment, i.e., the second part of (3.9). Since that Comb(Z^,f) is a graph with uniformly bounded degree, by Corollary 14.6 of [8], there exists c₀^∗ > 0 such that P^x(Xk =

y)≤c₀^∗/p

kfor allx,y∈V^{. Hence,} P^x,x,x€

X_k=X_k⁰ =X_k⁰⁰Š

=X

y∈V

P^x,x,x X_k=X_k⁰ =X⁰⁰_k = y