ON THE TRANSIENCE OF RANDOM INTERLACEMENTS

in PROBABILITY

ON THE TRANSIENCE OF RANDOM INTERLACEMENTS

BALÁZS RÁTH¹

ETH Zürich, Department of Mathematics, Rämistrasse 101, 8092 Zürich email: [email protected]

ARTËM SAPOZHNIKOV¹

ETH Zürich, Department of Mathematics, Rämistrasse 101, 8092 Zürich email: [email protected]

SubmittedFebruary 23, 2011, accepted in final formJune 23, 2011 AMS 2000 Subject classification: 60K35; 82B43

Keywords: Random interlacement; transience; random walk; resistance; intersection of random walks; capacity.

Abstract

We consider the interlacement Poisson point process on the space of doubly-infiniteZ^d-valued trajectories modulo time-shift, tending to infinity at positive and negative infinite times. The set of vertices and edges visited by at least one of these trajectories is the graph induced by the random interlacements at leveluof Sznitman[9]. We prove that for anyu>0, almost surely, the random interlacement graph is transient.

1 Introduction

The model of random interlacements was recently introduced by Sznitman in[9]. Among other results in[9], he proved that the random interlacement graph is almost surely connected. This result was later refined in[6]and[7]by showing that every two points of the random interlace- ment graph are connected via at mostdd/2erandom walk trajectories, and this number is optimal.

In this paper we further exploit the method of[7]in order to show that the graph induced by the random interlacements is almost surely transient in dimensionsd≥3.

1.1 The model

LetW be the space of doubly-infinite nearest-neighbor trajectories inZ^d (d≥3) which tend to infinity at positive and negative infinite times, and letW^∗be the space of equivalence classes of trajectories inW modulo time-shift. We writeW for the canonicalσ-algebra onW generated by the coordinatesX_n,n∈Z, andW^∗for the largestσ-algebra onW^∗for which the canonical mapπ^∗ from(W,W)to(W^∗,W^∗)is measurable. Letube a positive number. We say that a Poisson point

1THE RESEARCH OF BOTH AUTHORS HAS BEEN SUPPORTED BY THE GRANT ERC-2009-ADG 245728-RWPERCRI.

379

measureµonW^∗has distribution Pois(u,W^∗)if the following properties hold: for a finite subset AofZ^d, denote byµAthe restriction ofµto the set of trajectories fromW^∗that intersectA, and by N_Abe the number of trajectories in Supp(µA), thenµA=PN_A

i=1δπ^∗(X_i), whereX_iare doubly-infinite trajectories fromW parametrized in such a way thatX_i(0)∈AandX_i(t)∈/Afor all t<0 and for alli∈ {1, . . . ,N_A}, and

(1) The random variableN_Ahas Poisson distribution with parameterucap(A)(see (2.2) for the definition of the cap(A)).

(2) GivenN_A, the pointsX_i(0),i∈ {1, . . . ,N_A}, are independent and distributed according to the normalized equilibrium measure onA(see (2.8) for the definition).

(3) GivenN_Aand(X_i(0))^Ni=1^A , the corresponding forward and backward paths are conditionally independent, (X_i(t),t ≥ 0)^Ni=1^A are distributed as independent simple random walks, and (X_i(t),t≤0)^Ni=1^A are distributed as independent random walks conditioned on not hittingA.

Properties (1)-(3) uniquely define Pois(u,W^∗)as proved in Theorem 1.1 in [9]. In fact, Theo- rem 1.1 in[9]gives a coupling of the Poisson point measuresµ(u)with distribution Pois(u,W^∗) for allu>0, but we will not need such a general statement here. We also mention the following property of the distribution Pois(u,W^∗), which will be useful in the proofs. It follows from the above definition of Pois(u,W^∗).

(4) Letµ1andµ2be independent Poisson point measures onW^∗with distributions Pois(u₁,W^∗) and Pois(u₂,W^∗), respectively. Thenµ1+µ2has distribution Pois(u₁+u₂,W^∗).

We refer the reader to [9] for more details. For a Poisson point measure µ with distribution Pois(u,W^∗), therandom interlacement graphI =I(µ)(at levelu) is defined as the subgraph of Z^d induced byµ, i.e., its vertices and edges are those that are traversed by at least one of the random walks from Supp(µ). It follows from[9]thatI is a translation invariant ergodic random subgraph ofZ^d.

We consider the simple random walk on the graphI, with uniform edgeweights, i.e., at each step the random walker moves to a uniformly chosen neighbor of the current vertex. We say that a graph is transient if the simple random walk on the graph is transient. SinceI is a translation invariant ergodic random subgraph ofZ^d, it is transient with probability 0 or 1.

1.2 The result

Our main result is the following theorem.

Theorem 1. Let d≥3and u>0. Letµbe a random point measure on W^∗distributed asPois(u,W^∗), andPbe the law ofµ. Then,P-a.s., the random interlacement graphI =I(µ)is transient.

The main ingredient of the proof of Theorem 1 is Proposition 1. For x,y ∈Z^d and a positive integer r, we write x^{I ∩}←→^B(r)y if there is a nearest-neighbor path inI that connectsxand y and uses only vertices ofI from thel^∞-ball of radiusrcentered at the origin. (In particular,x andy must be vertices inI ∩B(r).)

Proposition 1. Let d≥3and u>0. LetI be the random interlacement graph at level u. There exist constants c=c(d,u)>0and C=C(d,u)<∞such that for all R≥1,

P





I ∩B(R)6=;, \

x,y∈I ∩B(R)

§

x^{I ∩B(2R)}←→ y ª





≥1−Cexp€

−cR^1/6Š

. (1.1)

Remark 1. The exponent 1/6 is not optimal, but suffices for the proof of Theorem 1. In fact, Theorem 1 follows if the probability in (1.1) tends to 1, asR→ ∞, faster than any polynomial.

Remark 2. Random interlacements were defined on arbitrary transient graphs in [10]. It was proved in[11]that for any transient transitive graphG, the interlacement graph on Gis almost surely connected for allu>0 if and only ifGis amenable. The following question arises naturally:

does Theorem 1 hold for any transient amenable transitive graph?

2 Notation and facts about Green function and capacity

In this section we collect most of the notation, definitions and facts used in the paper. Fora∈R, we write|a|for the absolute value of a,bac for the integer part of a, and daefor the smallest integer not less thana. Forx∈Z^d, we write|x|for max |x₁|, . . . ,|x_d|

. For a setS, we write|S| for the cardinality ofS. ForR>0 andx∈Z^d, letB(x,R) ={y∈Z^d : |x−y| ≤R}be thel^∞-ball of radiusRcentered atx, andB(R) =B(0,R). We denote by1(A)the indicator of eventA, and by E[X;A]the expected value of random variableX1(A).

Throughout the paper we always assume that d≥3. For x ∈Z^d, let P_x be the law of a simple random walk X onZ^d withX(0) = x. We write g(·,·) for the Green function of the walk: for x,y ∈Z^d, g(x,y) =P∞

t=0P_x[X(t) = y]. We also write g(·)for g(0,·). The Green function is symmetric and, by translation invariance,g(x,y) =g(y−x). It follows from[2, Theorem 1.5.4] that for anyd≥3 there exist a positive constantc_g=c_g(d)and a finite constantC_g=C_g(d)such that for allxand yinZ^d,

c_gmin€

1,|x−y|^2−dŠ

≤g(x,y)≤C_gmin€

1,|x−y|^2−dŠ

. (2.1)

Definition 2.1. LetKbe a subset ofZ^d. The energy of a finite Borel measureνonKis E(ν) =

Z

K

Z

K

g(x,y)dν(x)dν(y) = X

x,y∈K

g(x,y)ν(x)ν(y). The capacity ofKis

cap(K) =•

infν E(ν)˜−1

, (2.2)

where the infimum is over probability measuresν onK. (We use the convention that∞⁻¹=0, i.e., cap(;) =0.)

The following properties of the capacity immediately follow from (2.2):

Monotonicity: for anyK₁⊂K₂⊂Z^d, cap(K₁)≤cap(K₂); (2.3) Subadditivity: for anyK₁,K₂⊂Z^d, cap(K₁∪K₂)≤cap(K₁) +cap(K₂); (2.4) Capacity of a point: for any x∈Z^d, cap({x}) =1/g(0). (2.5) It will be useful to have an alternative definition of the capacity.

Definition 2.2. LetKbe a finite subset ofZ^d. The equilibrium measure ofKis defined by e_K(x) =P_x[X(t)∈/K for allt≥1]1(x∈K), x∈Z^d. (2.6)

The capacity ofKis then equal to the total mass of the equilibrium measure ofK:

cap(K) =X

x

e_K(x), (2.7)

and the unique minimizer of the variational problem (2.2) is given by the normalized equilibrium measure

ee_K(x) =e_K(x)/cap(K). (2.8) (See, e.g., Lemma 2.3 in[1]for a proof of this fact.)

As a simple corollary of the above definition, we get P_xH_K<∞=X

y∈K

g(x,y)e_K(y), forx∈Z^d. (2.9) Here, we write H_K for the first entrance time in K, i.e., H_K =inf{t ≥0 : X(t)∈K}. We will repeatedly use the following bound on the capacity ofB(0,R)ind≥3 (see (2.16) on page 53 in [2]): there exist constantsc_b=c_b(d)>0 andC_b=C_b(d)<∞such that for all positiveR,

c_bR^d−2≤cap(B(0,R))≤C_bR^d−2. (2.10) Finally, we will often use in the proofs the following large deviation bounds for the Poisson dis- tribution, which can be proved using the exponential Chebyshev enequality. Letξbe a random variable which has Poisson distribution with parameterλ, then

P[λ/2≤ξ≤2λ]≥1−2e^−λ/10. (2.11) Throughout the text, we writecandC for small positive and large finite constants, respectively, that may depend ondandu. Their values may change from place to place.

3 Proof of Theorem 1

We recall the following result about an equivalent characterization of the transience of simple random walk on a graph. The statement and proof of a more general theorem about an equivalent characterisation of the transience of reversible Markov chains can be found on page 398 of[3]. Lemma 1. Let G = (V,E)denote a countable, simple graph in which the degree of each vertex is finite. The simple random walk on G is transient if and only if there exist real numbers(u(x,y))x,y∈V

with the following properties:

(i) u(y,x) =−u(x,y)and u(x,y)6=0only if{x,y} ∈E, (ii) P

x∈V

P

y∈Vu(x,y)

<∞andP

x∈V

P

y∈Vu(x,y) 6=0, (iii) P

x∈V

P

y∈Vu(x,y)²<∞.

We refer to a function(u(x,y))x,y∈V satisfying(i)as aflowonGandu(x,y)as the amount of net flow from vertex x to vertexy. We say thatP

y∈Vu(x,y)is the net influx at vertexx. Condition (ii) states that the influxes are absolutely summable (this can be thought of as a relaxation of Kirchoff’s law) and that there is a nonzero net influx into the network. Condition(iii)says that

the Thompson energy of the flow is finite. We are going to prove Theorem 1 by constructing such a flow on the graphI.

Denote byS^d thed-dimensional Euclidean unit sphere. Givenv∈S^d and"∈(0, 1), we define the graphI(v,")by

I(v,") =I ∩

∞

[

n=1

B(nv,n^"). (3.1)

The setS_∞

n=1B(nv,n^")is roughly shaped like a paraboloid with an axis parallel tov. We denote

byC∞(v,")the maximal subgraph ofI(v,")in which every connected component is infinite. (If I(v,")does not contain an infinite connected component, we setC_∞(v,") =;.)

Lemma 2. For any u>0and0< " <1, we have P



 [

M≥1

¦∀v∈S^d : B(M)∩ C_∞(v,")6=;©



=1. (3.2)

Proof. For anyz∈Z^d, define the events A_z=

¨

∀x,y∈ I ∩B(z,1

4|z|^"): x^{I ∩}

B(z,¹₂|z|^")

←→ y

«

, B_z=

I ∩B(z,1

8|z|^")6=;

. It follows from the Borel-Cantelli lemma and Proposition 1 thatP(lim inf_z∈ZdA_z∩B_z) =1, i.e., almost surely the number ofz∈Z^d for whichA_z∩B_z does not occur is finite.

Note that there exists an integermsuch that for everyv∈S^d, there exists aZ^d-valued sequence (z_i)^∞_i=1with z₁ ∈B(m)and|z_i| → ∞, such that for all i, (a) B(z_i,¹

2|z_i|^")⊂S∞

n=1B(nv,n^")and

(b) B(z_i,¹₈|z_i|^") and B(z_i+1,¹₈|z_i+1|^") are subsets of B(z_i+1,¹₄|z_i+1|^"). Indeed, one can take, for

example, a discrete approximation of theR^d-valued sequence ((i+i₀)v)^∞_i=1 for large enoughi₀. (Note thati₀can be chosen independent ofv.)

Let M be an almost surely finite random variable such that, for allv∈S^d andi≥M, the events A_z

i andB_z

i hold. Then, for alli≥M,I ∩B(z_i,¹

8|z_i|^")6=;, and every vertex inI ∩B(z_i,¹

8|z_i|^")is connected to every vertex inI ∩B(z_i+1,¹₈|z_i+1|^")by a path inI(v,"). This implies (3.2).

Definition 3.1. It follows from Lemma 2 that we can almost surely assign (in a measurable way) to everyv∈S^d a (random) simple nearest-neighbor pathw_v= (w_v(n))^∞_n=0in the graphI(v,"). In particular, for alln6=m∈N,w_v(n)6=w_v(m), and lim_n→∞|w_v(n)|=∞.

Our construction of the flowuwith finite energy is analogous to the proof of Pólya’s theorem in [4]. For everyv∈S^d define(u_v(x,y))x,y∈I to be the unit flow that goes fromw_v(0)to∞along the simple pathw_v, more precisely letu_v(x,y) =−u_v(y,x) =1 ifw_v(n) =xandw_v(n+1) = y for somen∈Nand, otherwise, letu_v(x,y) =0. With this definition we have

X

y∈I

u_v(x,y) =1[x=w_v(0)]. (3.3) Note that for anyv∈S^d the flowu_vsatisfies(i)and(ii)of Lemma 1, but fails to satisfy(iii). We define the flowuas the average of the flowsu_vwith respect tov, more precisely let

u(x,y):= Z

S^d

u_v(x,y)dλ(v)

whereλis the Haar measure onS^d normalized to be a probability measure.

Now we check that uis a flow with finite energy on I, i.e., the conditions of Lemma 1 hold.

The functionuinherits property(i)from the flowsu_v. From (3.3) it readily follows that we have P

y∈Iu(x,y)≥0 for allx∈ I and thatP

x∈I

P

y∈Iu(x,y)

=1 holds, from which(ii)follows.

It only remains to show that the energy ofuis finite, i.e.,(iii)holds. Note thatu(x,y)6=0 only if

|x−y|=1. We have

|u(x,y)| ≤ Z

S^d

|u_v(x,y)|dλ(v)≤ Z

S^d

1[x∈

∞

[

n=1

B(nv,n^") ]dλ(v)≤C(|x|^")^d−1

|x|^d−1 . (3.4) Now choose 0< " <¹₄ in Definition 3.1. The corresponding flowuhas finite energy:

X

x∈Z^d

X

y∈Z^d

u(x,y)² ≤ X∞

n=1

X

|x|=n

X

|x−y|=1

u(x,y)^2(3.4)≤ C X∞

n=1

X

|x|=n

n2("−1)(d−1) d≥3

≤ C X∞

n=1

n^4"−2<∞.

Therefore, the flowusatisfies the conditions of Lemma 1, which proves Theorem 1.

4 Proof of Proposition 1

4.1 Bounds on the capacity of certain collections of random walk trajecto- ries

The aim of this subsection is to prove Lemma 6 (withΦ(X_N,T)defined in (4.2)), which will be used in the proof of Lemma 7.

The following lemma is proved in[7] ford≥5, see Lemma 3 there. The casesd=3, 4 can be proved similarly. Therefore, we state this lemma without proof.

Lemma 3. Let(x_i)i≥1be a sequence inZ^d, and let X_i be a sequence of independent simple random walks onZ^d with X_i(0) =x_i. Let

F(n,d) =







n^1/2 if d=3, logn if d=4, and 1 if d≥5.

Then for all positive integers N and n, we have E





N

X

i,j=1 2n

X

s,t=n+1

g€

X_i(s),X_j(t)Š



≤C€

N nF(n,d) +N²n^3−d/2Š

. (4.1)

Let(X_i(t) : t≥0)i≥1be a sequence of nearest-neighbor trajectories onZ^d, andX_N= (X₁, . . . ,X_N). For positive integersNandT, we define the subsetΦ(X_N,T)ofZ^d as

Φ(X_N,T) =

N

[

i=1

X_i(t) : 1≤t≤T . (4.2)

Lemma 4. Let X_ibe a sequence of independent simple random walks onZ^d with X_i(0) =x_i. There exists a positive constant c such that for any sequence(x_i)i≥1⊂Z^dand for all positive integers N and T ,

cap€

Φ(X_N,T)Š

≤ N T

g(0), and Ecap€

Φ(X_N,T)Š

≥cmin N T

F(T,d),T^d−22

, (4.3)

where the function F is defined in Lemma 3.

Remark 3. Heuristically, Ecap€

Φ(X_N,T)Š

is at least _F^{cN T}₍

T,d) when the random walks in X_N are well separated, and at least cap(B(c T^1/2))^(2.10)≥ c T^d−22 when the set Φ(X_N,T)saturates the ball B(c T^1/2).

Proof. The proof of this lemma is similar to the proof of Lemma 4 in[7], so we give only a sketch here. (Note that the definition ofΦ(X_N,R)in[7]is different from the one in (4.2).)

The upper bound on the capacity ofΦ(X_N,T)follows from (2.4) and (2.5). Letn=bT/2c. By the definition of the capacity (2.2) and the Jensen inequality,

Ecap€

Φ(X_N,T)Š

≥N²n²



E





N

X

i,j=1

X2n

s,t=n+1

g(X_i(s),X_j(t))









−1

. The lower bound in (4.3) now follows from Lemma 3.

As a corollary of Lemma 4 we obtain the following lemma.

Lemma 5. Let X_ibe a sequence of independent simple random walks onZ^d with X_i(0) =x_i. There exists a positive constant c such that for any sequence(x_i)i≥1⊂Z^dand for all positive integers N and T ,

P

cap€

Φ(X_N,T)Š

≥cmin N T

F(T,d),T^d−22

≥ c

(logT)². (4.4) Proof. Remember the Paley-Zygmund inequality[5]: Let ξbe a non-negative random variable with finite second moment. For anyθ∈(0, 1), P[ξ≥θEξ]≥(1−θ)²[Eξ]²/E[ξ²].

We first consider the case d = 3. Note that in this case, min _{N T}

F(T,d),T^d−22

= T^1/2. Since Φ(X_N,T)⊇Φ(X₁,T), by (2.3), it suffices to show that

P” cap€

Φ(X₁,T)Š

≥c T^1/2—

≥c.

It follows from (4.3) thatEcap€

Φ(X₁,T)Š

≥c T^1/2. On the other hand, the setΦ(X₁,T)is con- tained in B(X₁(0),M), whereM =max{|X₁(t)−X₁(0)| : 1≤ t≤ T}. Therefore, by (2.3) and (2.10), cap€

Φ(X₁,T)Š

≤ C M. In particular, sinceEM²≤C T, we haveEh cap€

Φ(X₁,T)Š2i

≤ C T. The result now follows from the Paley-Zygmund inequality.

Letd≥4. An application of the Paley-Zygmund inequality and (4.3) gives

P

cap€

Φ(X_N,T)Š

≥cmin N T

F(T,d),T^d−22

≥

cmin _{N T}

F(T,d),T^d−22 2

N²T² . (4.5)

We distinguish two cases. If min _{N T}

F(T,d),T^d−22

= _F^{N T}_(T,d), the result immediately follows from (4.5) and the definition of F. Otherwise, if min

N T

F(T,d),T^d−22

= T^d−22 , we take N⁰ ≤ N in

h

T^d−42 F(T,d), 2T^d−42 F(T,d)i

. Such a choice is possible, since 1 ≤ T^d−42 F(T,d)≤ N. The result then follows from (4.5) by observing that cap€

Φ(X_N,T)Š

≥cap€

Φ(X_N0,T)Š

by (2.3).

In the next lemma we show that the capacity ofΦ(X_N,T)is large with high probability.

Lemma 6. Let" ∈(0, 1). Let X_i be a sequence of independent simple random walks onZ^d with X_i(0) = x_i. There exists a positive constant c such that for any sequence(x_i)i≥1⊂Z^d and for all positive integers N and T ,

Ph cap€

Φ(X_N,T)Š

≥cmin

N T^1−"2 ,T(d−2)(1−") 2

i≥1−exp€

−c T^"/2Š

. (4.6)

Proof. For positive integersN,eTandk, we define the subsetΦk(X_N,Te)ofZ^d by Φk(X_N,Te) =

N

[

i=1

¦X_i(t) : (k−1)Te+1≤t≤kTe© .

It follows from the Markov property, (4.4), and the definition of the functionF, that Ph

cap€

Φk(X_N,Te)Š

≥cmin

NTe^1/2,Te^d−22

| X_i(t), i∈ {1, . . . ,N}, t≤(k−1)Tei

≥ c (logTe)². Therefore, for anyδ >0,

P





cap







beT^δc

[

k=1

Φk(X_N,eT)





≥cmin

NTe^1/2,Te^d−22





≥1−

–

1− c

(logeT)²

™beT^δc

≥1−exp€

−ceT^δ/2Š .

The result follows by observing thatSbeT^δc

k=1Φk(X_N,Te)⊆Φ(X_N,bTe^1+δc), and by taking"=δ/(1+ δ).

4.2 Bounds on the capacity of certain subsets of random interlacement

The aim of this subsection is to prove Lemma 10, which states that with high probability for x ∈ I, the connected component ofI ∩B(x,R) that contains x has large capacity. We prove the statement by constructing explicitly for x ∈ I a connected subset of I ∩B(x,R)of large capacity that containsx. In this construction, we exploit property (4) of Pois(u,W^∗), which allows to describe I as the union of independent identically distributed random interlacement graphs I1, . . . ,Id−2. We begin with auxiliary lemmas.

Let Abe a finite set of vertices in Z^d. Let µ be a random point measure with distribution Pois(u,W^∗), andµAits restriction to the set of trajectories fromW^∗that intersectA. We can write the measureµAasPN_A

i=1δ_π^∗₍X_i)(recall the notation from Section 1.1), whereN_A=|Supp(µA)|, and X₁, . . . ,X_NAare doubly-infinite trajectories fromW parametrized in such a way thatX_i(0)∈Aand X_i(t)∈/Afor allt<0 and for alli∈ {1, . . . ,N_A}. We define the setΨ(µ,A,T)as

Ψ(µ,A,T) =

N_A

[

i=1

X_i(t) : 1≤t≤T . (4.7)

Lemma 7. Let"∈(0, 1). Letµbe a Poisson point measure with distributionPois(u,W^∗), then for all finite subsets A ofZ^d and for all positive integers T , one has

Ph

cap Ψ(µ,A,T)

≥cmin

cap(A)T^1−"2 ,T(d−2)(1−") 2

i≥1−C e^−cmin(^{T"/2, cap(A)}). (4.8)

Proof. It follows from property (1) of Pois(u,W^∗)thatN_Ahas the Poisson distribution with param- eterucap(A). Therefore, by (2.11),PN_A≥ccap(A)

≥1−C e^−ccap(A). Properties (2) and (3) of Pois(u,W^∗)imply that givenN_A, the forward trajectoriesX₁, . . . ,X_N

Aare distributed as independent simple random walks. Therefore, Lemma 6 applies, giving that

Ph

cap Ψ(µ,A,T)

≥cmin

N_AT^1−"2 ,T(d−2)(1−") 2

i≥1−e^{−c T"/2}.

The result follows.

Let X be a simple random walk onZ^d with X(0) =x. Letµ⁽²⁾,µ⁽³⁾, . . . be independent random point measures with distribution Pois(u,W^∗)(the parameteruis fixed here), which are also inde- pendent ofX. We denote byPxthe joint law ofX andµ⁽ⁱ⁾’s. LetT be a positive integer. We define the following sequence of random subsets ofZ^d:

U⁽¹⁾(x,T) ={X(t) : 1≤t≤T}, (4.9) and fors≥2 (see (4.7) for notation),

U^(s)(x,T) = Ψ€

µ^(s),U^(s−1)(x,T),TŠ

. (4.10)

Note that for eachs≥1,Ss

i=1U⁽ⁱ⁾(x,T)is a connected subset ofZ^d. In the next lemma, we show that for anyγ >0, with high probability, the setSs

i=1U⁽ⁱ⁾(x,T)is a subset ofB(x,sT^(1+γ)/2). Lemma 8. Letγ∈(0, 1). There exist c=c(u,d,s)>0and C=C(u,d,s)<∞such that

Px





s

[

i=1

U⁽ⁱ⁾(x,T)⊆B(x,sT^(1+γ)/2)



≥1−C e^{−c Tγ}. (4.11) Proof. We denote the event{Ss

i=1U⁽ⁱ⁾(x,T)⊆B(x,sT^(1+γ)/2)}byD_s, and its complement byD_s^c. Ifs=1, (4.11) follows from Hoeffding’s inequality: Px

”D^c₁—

≤2d e^−Tγ/8. Assume that (4.11) is proved fors⁰<s. Then

Px

”D_s^c—

≤P” D^c_s−1—

+Px

”D_s^c,D_s−1— , and it remains to show thatPx

”D^c_s,D_s−1—

≤C e^{−c Tγ}. Note that ifD_s−1occurs,

|Supp(µ⁽_U^s)(s−1)(x,T))| ≤ |Supp(µ⁽_B^s₍⁾_x,(s−1)T(1+γ)/2))|.

(See Section 1.1 for the notation.) Let us denote the right hand side of the above inequality by N. It follows from property (1) of Pois(u,W^∗)thatNhas the Poisson distribution with parameter ucap€

B(x,(s−1)T^(1+γ)/2)Š

. In particular, using (2.10) and (2.11), we obtain that Px

”N≥C T^{(d−2)(1+γ)/2}—

≤C e^{−c T(1+γ)/2}≤C e^{−c Tγ}. On the other hand, properties (2) and (3) of Pois(u,W^∗)imply that

Px

”D_s^c,D_s−1—

≤Px

”N≥C T^{(d−2)(1+γ)/2}—

+C T^{(d−2)(1+γ)/2}Px

”D₁^c—

≤C e^{−c Tγ}. This completes the proof of the lemma.

The next lemma follows immediately from Lemma 7 and the definition ofU^(s)(x,T).

Lemma 9. Let " ∈(0, 1/2). For any positive integer s, there exist c = c(d,u,s) > 0 and C = C(d,u,s)<∞such that for all positive integers T ,

Px





s

\

i=1

ncap€

U⁽ⁱ⁾(x,T)Š

≥cmin

T^i(1−")2 ,T(d−2)(1−") 2

o



≥1−Cexp€

−c T^"/2Š

. (4.12)

Proof. The cases=1 follows from (4.9) and Lemma 6. Lets≥2. Note that, forc∈(0, 1), the event in (4.12) withc^sin place ofcis implied by the event

s

\

i=1

ncap€

U⁽ⁱ⁾(x,T)Š

≥cmin cap€

U⁽ⁱ⁻¹⁾(x,T)Š

T^1−"2 ,T(d−2)(1−") 2

o,

where we set by convention cap€

U⁽⁰⁾(x,T)Š

=1. The result now follows (by induction ins) from (4.12) fors=1, Lemma 7 and the definition ofU^(s)(x,T), see (4.10).

Corollary 1. It follows from Lemmas 8 and 9 that for any"∈(0, 1/2),

Px





d−2

[

i=1

U⁽ⁱ⁾(x,T)⊆B(x,(d−2)T(1+")/2), cap€

U^(d−2)(x,T)Š

≥c T(d−2)(1−") 2



≥1−C e^{−c T"/2}.

(4.13) In particular on the event in(4.13),Sd−2

i=1U⁽ⁱ⁾(x,T)is a connected subset of B(x,(d−2)T(1+")/2). Let µbe a Poisson point measure with distribution Pois(u,W^∗), and letI be the corresponding random interlacement graph at levelu. (See Section 1.1 for the definition.) Forx∈ I, letC(x,R) be the connected component ofI ∩B(x,R)that contains x. We defineC(x,R)as an empty set for x ∈ I/ . In the next lemma we show that for x ∈ I, the capacity of C(x,R)is large enough with high probability.

Lemma 10. For all"∈(0, 2/3), R>0, and x∈Z^d, we have P”

x∈ I, cap(C(x,R))<cR(d−2)(1−")—

≤C e^−cR"/2. (4.14)

Proof. Letµ⁽¹⁾, . . . ,µ^(d−2)be independent Poisson point measures with distribution Pois(_d−2^u ,W^∗). LetPbe the joint law ofµ⁽ⁱ⁾. By property (4) of Pois(u,W^∗), the measureµhas the same law as Pd−2

i=1µ⁽ⁱ⁾. Therefore, we may assume thatµ=Pd−2

i=1µ⁽ⁱ⁾. In particular, the random interlacement graphI =I(µ)equalsSd−2

i=1I⁽ⁱ⁾, whereI⁽ⁱ⁾=I(µ⁽ⁱ⁾)are independent random interlacement graphs at level _d−2^u , and the vertices and edges ofI are the ones ofZ^d that are traversed by at least one of the random walks fromSd−2

i=1Supp(µ⁽ⁱ⁾).

It follows from (4.13) (withT =eR²) and property (3) of Pois(_d−2^u ,W^∗)that for anyδ∈(0, 1/2), Re>0,x∈B(eR)andi∈ {1, . . . ,d−2},

P”

x∈ I⁽ⁱ⁾, cap€

C(x,eR^1+δ)Š

<ceR^{(d−2)(1−δ)}—

≤C e^−ceRδ. The result follows by takingδ="/(2−").

4.3 Proof of Proposition 1

Proposition 1 will follow from Lemma 13, which states that with high probability, any two vertices fromI ∩B(R)are connected by a path inI ∩B(CR)for large enoughC. This result will follow from (4.14), (4.15) and property (4) of Pois(u,W^∗).

We begin with auxiliary lemmas. Lemma 11 is standard, so we only give a sketch of the proof here.

Lemma 11. Let A be a subset of B(R). Let X be a simple random walk onZ^d with X(0) =x∈B(R). Let H_Abe the entrance time of X in A, and T_B(r)the exit time of X from B(r). Then there exist c>0 and C<∞such that for all R>0and x∈B(R),

P_x”

H_A<T_B(CR)—

≥cR^2−dcap(A).

Proof. We use the identity (2.9). SinceAis a subset ofB(R), the inequality (2.1) implies that, for anyy∈Aandx∈B(R),g(x,y)≥c_g(2R)^2−d. By (2.7) and (2.9),P_x

H_A<∞

≥c_g(2R)^2−dcap(A). On the other hand, fory∈Aandz∈/B(CR), the inequality (2.1) givesg(z,y)≤C_g((C−1)R)^2−d. Therefore, by (2.7), (2.9) and the strong Markov property ofX applied at time T_B(CR), we have P_x”

T_B(CR)<H_A<∞—

≤C_g((C−1)R)^2−dcap(A). The result follows by takingClarge enough.

Lemma 12. There exist c >0and C <∞such that for all R>0and for all subsets U and V of B(R), we have

P

•

U^{I ∩}←→^B(CR)V

˜

≥1−Cexp€

−cR^2−dcap(U)cap(V)Š

. (4.15)

Proof. Letµbe a random point measure with distribution Pois(u,W^∗). Remember from Section 1.1 thatµU =PN_U

i=1δπ^∗(Xi), where N_U = |Supp(µU)| andX₁, . . . ,X_N

U are doubly-infinite trajectories from W parametrized in such a way that X_i(0) ∈ U and X_i(t) ∈/ U for all t < 0 and for all i∈ {1, . . . ,N_U}.

It follows from property (1) of Pois(u,W^∗)and (2.11) that P N_U≥ccap(U)

≥1−C e^−ccap(U). Therefore, by Lemma 11 and properties (2) and (3) of Pois(u,W^∗), we have

P

•

U^{I ∩}←→^B(CR)V

˜

≥ 1−P N_U<ccap(U)

−€

1−cR^2−dcap(V)Šccap(U)

≥ 1−Cexp€

−cR^2−dcap(U)cap(V)Š .

In these inequalities we also used the fact that cap(V)≤CR^d−2, which follows from (2.3) and (2.10). The proof is complete.

As a corollary of Lemmas 10 and 12 we get the following lemma.

Lemma 13. There exist c>0and C<∞such that for all R>0and x,y∈B(R), we have P

•

x,y∈ I,

§

x^{I ∩}←→^B(CR) y ªc˜

≤Cexp€

−cR^1/6Š

. (4.16)

Proof. Letµbe a Poisson point measure with distribution Pois(u,W^∗), andµ⁽¹⁾,µ⁽²⁾andµ⁽³⁾ be independent Poisson point measures with distribution Pois(u/3,W^∗). LetPbe the joint law ofµ⁽ⁱ⁾. By property (4) of Pois(u,W^∗), the measureµhas the same law asP3

i=1µ⁽ⁱ⁾. Therefore, we may assume thatµ=P3

i=1µ⁽ⁱ⁾, so that the random interlacement graphI =I(µ)equalsS3 i=1I⁽ⁱ⁾, whereI⁽ⁱ⁾ =I(µ⁽ⁱ⁾)are independent random interlacement graphs at levelu/3. In particular,

the vertices and edges ofI are the ones ofZ^d that are traversed by at least one of the random walks fromS3

i=1Supp(µ⁽ⁱ⁾).

Let C⁽ⁱ⁾(x,R)be the connected component of x in I⁽ⁱ⁾∩B(x,R). In particular, C⁽ⁱ⁾(x,R) ⊆ C(x,R), but it is not true in general thatS3

i=1C⁽ⁱ⁾(x,R) =C(x,R). SinceRis fixed throughout the proof, we writeC⁽ⁱ⁾(x)forC⁽ⁱ⁾(x,R). We have forx,y∈B(R),

P

•

x,y∈ I,

§

x^{I ∩B(CR)}←→ y ªc˜

≤

3

X

i,j=1

P

•

x∈ I⁽ⁱ⁾,y∈ I^(j),

§

x^{I ∩B(CR)}←→ y ªc˜

.

For each i,j∈ {1, 2, 3}, choosek∈ {1, 2, 3}which is different fromiand j. By construction, the setI^(k)is independent fromI⁽ⁱ⁾andI^(j). For each suchi,j, andk, we obtain

P

•

x∈ I⁽ⁱ⁾,y∈ I^(j),

§

x^{I ∩}←→^B(CR) y ª^c˜

≤P

x∈ I⁽ⁱ⁾,y∈ I^(j),

C⁽ⁱ⁾(x)^I(k)←→^∩B(CR)C^(j)(y) c

. We define the eventsE₁⊆ {x∈ I⁽ⁱ⁾}andE₂⊆ {y∈ I^(j)}as

E₁=¦ cap€

C⁽ⁱ⁾(x)Š

>cR^2(d−2)/3©

, and E₂=¦ cap€

C^(j)(y)Š

>cR^2(d−2)/3© . We denote the intersectionE₁∩E₂byE. By Lemma 10 (with"=1/3), we get

P”¦

x∈ I⁽ⁱ⁾©

\E₁— +P”¦

y∈ I^(j)©

\E₂—

≤C e^−cR1/6.

Note thatC⁽ⁱ⁾(x)andC^(j)(y)are subsets ofB(2R). Therefore, it follows from Lemma 12 and the independence ofI^(k)fromI⁽ⁱ⁾andI^(j), that

P

E\

C⁽ⁱ⁾(x)^I(k)←→^∩B(CR)C^(j)(y)

≤ CE” exp€

−cR^2−dcap€

C⁽ⁱ⁾(x)Š cap€

C^(j)(y)ŠŠ

;E—

≤ Cexp€

−cR^(d−2)/3Š . Putting the bounds together gives the result.

Proof of Proposition 1. We will use a standard covering argument to derive (1.1) from (4.16).

Take the constant Cfrom the statement of Lemma 13. It suffices to prove (1.1) forR≥2C. Let R⁰=bR/2Cc. For eachz∈Z^d, we define the events

A⁽¹⁾_z =

I ∩B(z,R⁰)6=; , A⁽²⁾_z = \

x,y∈I ∩B(z,2R⁰)

§

x^{I ∩B}←→^(z,R)y ª

, andA=T

z∈B(R)A⁽¹⁾_z ∩A⁽²⁾_z . It follows from property (1) of Pois(u,W^∗)and (2.10) that P(A⁽¹⁾_z ) =1−e^{−ucap(B(z,R0))}≥1−e^−cR,

and from Lemma 13 that

P(A⁽²⁾_z )≥1−C e^−cR1/6.

In particular, P(A)≥ 1−C⁰exp(−cR^1/6). It remains to note thatAimplies the event in (1.1).

Indeed, for allz,z⁰∈B(R)with|z−z⁰|=1,B(z,R⁰)∪B(z⁰,R⁰)⊆B(z, 2R⁰); thus ifAoccurs then every vertex in the non-empty setI ∩B(z,R⁰)is connected to every vertex in the non-empty set I ∩B(z⁰,R⁰)by a path inI ∩B(z,R)⊆B(2R). Since any two vertices inB(R)are connected by a nearest-neigbor path inB(R),Aimplies the event in (1.1). The result follows.

Acknowledgments.We would like to thank A.-S. Sznitman for suggesting this problem to us.

References

[1] N. C. Jain and S. Orey (1973) Some properties of random walk paths.J. Math. Anal. Appl.

43, 795-815.MR0359004

[2] G. Lawler (1991)Intersections of random walks,Birkhäuser, Basel.MR1117680

[3] T. Lyons (1983) A Simple Criterion for Transience of a Reversible Markov Chain.Ann. Probab.

11, 393-402.MR0690136

[4] R. Lyons and Y. Peres (2011)Probability on Trees and Networks. Cambridge University Press.

In preparation. Current version available athttp://mypage.iu.edu/~rdlyons/.

[5] R. E. A. C. Paley and A. Zygmund (1932) A note on analytic functions in the unit circle.Proc.

Camb. Phil. Soc.28, 266-272.

[6] E. B. Procaccia and J. Tykesson (2011) Geometry of the random interlacement.

arXiv:1101.1527.

[7] B. Ráth and A. Sapozhnikov (2010) Connectivity properties of random interlacement and intersection of random walks. arXiv:1012.4711.

[8] F. Spitzer (2001)Principles of random walks,2nd edition, Springer-Verlag.MR0388547 [9] A.-S. Sznitman (2010) Vacant set of random interlacements and percolation. Ann. Math.

171, 2039-2087.MR2680403

[10] A. Teixeira (2009) Interlacement percolation on transient weighted graphs. Electron. J.

Probab.14, 1604-1628.MR2525105

[11] A. Teixeira and J. Tykesson (2011) Random interlacements and amenability.

arXiv:1103.2109.