3 Proof of Proposition 1.1

ISSN:1083-589X in PROBABILITY

Disjoint crossings, positive speed and deviation estimates for first passage percolation

Ghurumuruhan Ganesan

Abstract

Consider bond percolation on the square latticeZ²where each edge is independently open with probabilityp.For some positive constantsp0∈(0,1), 1and2,the follow- ing holds: ifp > p0,then with probability at least1−_n¹4 there are at least_log²ⁿ_ndisjoint open left-right crossings inBn:= [0, n]²each having length at most2n,for alln≥2.

Using the proof of the above, we obtain positive speed for first passage percolation with independent and identically distributed edge passage times{t(ei)}i satisfying E(logt(e1))⁺ < ∞; namely,lim sup_n^Tpl(0,n)_n ≤ Qa.s. for some constant Q < ∞, whereTpl(0, n) denotes the minimum passage time from the point(0,0)to the line x = n taken over all paths contained inBn.Finally, we also obtain corresponding deviation estimates for nonidentical passage times satisfyinginfiP(t(ei) = 0)>²₃.

Keywords:First passage percolation, zero passage times, deviation estimates.

AMS MSC 2010:60K35.

Submitted to ECP on May 7, 2014, final version accepted on August 7, 2014.

1 Introduction

Consider bond percolation inZ²where each bond is independently open with prob- abilityp.A bond that is not open is said to be closed. For integerM ≥1 and >0,let Rn,(M)denote the rectangle[0, n]×[0,d(Mlogn)¹⁺e].Heredxerepresents the smallest integer greater thanx.All constants mentioned henceforth are independent ofn.A path Π = (e₁, ..., e_t)of edges contained inR_n,(M)is said to be an open left-right crossing if everye_i is open ande₁ intersects the left side ofR_n,(M)ande_ttouches the right side ofRn,(M).

Proposition 1.1. Fixδ >0and >0.

(i) Ifp > ²₃,there are positive constants M₁ =M₁(p, δ)and C₁ =C₁(p, δ)so that with probability at least1−^C_nδ¹,there exists an open left-right crossing ofR_n,0(M₂), for all n≥1.

(ii) If p > p₀ := 1−3⁻³²¹₂

, there are positive constants M₂ = M₂(p, δ) and C₂ = C₂(p, δ)so that with probability at least1−^C_nδ²,there exists an open left-right crossing ofRn,0(M2)containing at most2nedges, for alln≥1.

For proof of (i), we use a contour argument and we use oriented paths to control the length of the crossings in the proof of (ii). For further analysis regarding critical values for oriented percolation, we refer to Durrett (1984) and references therein.

The following result is a consequence of Proposition 1.1. Forn≥1,letB_n:= [0, n]².

∗EPFL, Lausanne, Switzerland. E-mail:[email protected]

Theorem 1.2. Fixδ >0and >0and letp₀be as in Proposition 1.1.

(i) Ifp > ²₃, there are positive constants γ₁ = γ₁(p, δ) and C₁ = C₁(p, δ)so that with probability at least1−^C_n¹_δ,there are at least _log^γ1n_n open left-right crossings ofBn,for all n≥2.

(ii) Ifp > p0, there are positive constantsγ2 = γ2(p, δ) andC2 =C2(p, δ)so that with probability at least1−^C_nδ²,there are at least _log^γ2n_n open left-right crossings of Bn,each containing at most2nedges, for alln≥2.

As an application of Proposition 1.1, we obtain positive speed and deviation esti- mates for first passage percolation.

1.1 First passage percolation

Consider the square latticeZ^{2with edges}{ei}_i≥1.The passage times{t(ei)}_i≥1 are independent and identically distributed (i.i.d.) having the same distribution as a random variableX.For a pathπ containingkedges g1, ..., gk,letT(π) := Pk

i=1t(gi)denote its passage time. Let Tll(0, n) = minπT(π) be the minimum passage time from the line x = 0 to the line x = n where the minimum is taken over all paths π contained in B_n.Similarly,T_pl(0, n)andT_pp(0, n) = min_πT(π)be, respectively, the minimum passage time from(0,0)to the linex=nand from(0,0)to(n,0),again over all paths contained inBn.Clearly,

T_ll(0, n)≤T_pl(0, n)≤T_pp(0, n) a.s.

We have the following result.

Theorem 1.3. IfP(X <∞) = 1,there exists a finite constantQ1≥0so that:

(i)lim sup_n^Tll(0,n)_n ≤Q1a.s.

IfE(logX)⁺<∞,there exists a finite constantQ2≥0so that:

(ii)lim sup_n^Tpl(0,n)_n ≤Q₂a.s.

(iii) For every >0,we have

P

Tpp(0, n)

n > Q2+

−→0

asn→ ∞.

IfEX <∞,then:

(iv)lim sup_n ^Tpp(0,n)_n ≤EX a.s.

If we think of _T ⁿ

pp(0,n),_T ⁿ

pl(0,n) or _T ⁿ

ll(0,n) as the corresponding speed of first passage percolation, then (i)-(iv) of the above result implies positive speed even if expected passage time is not finite.

Suppose now the passage time is zero with large probability. It is then intuitive to expect infinite speed and we have the following result.

Proposition 1.4. IfP(X= 0)>²₃ andE(logX)⁺ <∞,then^Tpl(0,n)_n −→0a.s. asn→ ∞ and ^Tpp(0,n)_n −→0in probability asn→ ∞.

Finally, we obtain deviation estimates for first passage percolation with independent passage times but not necessarily identically distributed.

Theorem 1.5. SupposeinfiP(t(ei) = 0)> ²₃ andinfiP(t(ei)<∞) = 1.

(i) We have ^Tll(0,n)_n −→0a.s. asn→ ∞.

(ii) Ifsup_iEt(e_i)<∞,then

ETpp(0, n)≤C1(logn)² (1.1)

for alln≥1and for some positive constantsβ1andC1.In particular, we have ^Tpp(0,n)_n −→

0in probability asn→ ∞.

(iii) Ifsup_iEt(ei)^K <∞for someK >1,we have P T_pp(0, n)≥n^β2

≤ C₂

n^{β3 (1.2)}

for all n ≥ 1 and for some positive constants β2 < min

1,_K−1¹

, β3 > 1 and C2. In particular, we have ^Tpp(0,n)_n −→0a.s. asn→ ∞.

(iv) Ifsup_iEe^st(ei)<∞for somes >0,we have P Tpp(0, n)≥β4(logn)³

≤ C3

n^{β5 (1.3)}

for alln≥1and for some positive constantsβ₄, β₅>1andC₃. The proof of the above theorem uses Proposition 1.1(ii).

The paper is organized as follows: In Section 2, we prove Theorems 1.3 and 1.5 assuming Proposition 1.1. In Section 3, we prove Proposition 1.1.

2 Proof of Theorems 1.3 and 1.5

Proof of Theorem 1.3: We prove (iv) first. IfEX <∞,then the result follows from strong law of large numbers since

Tb(0, n)

n ≤ 1

n

n

X

i=1

t(fi).

This proves (iv). We now prove (i)-(iii).

(i) SinceP(X <∞) = 1,we choose a finiteN large enough so thatP(X ≤N)> p0. ForM ≥1letR⁰_n,0(M) = [0, n]×[1, Mlogn+ 1]be the shifted rectangle. Also fori≥1, letfi denote the edge from(i−1,0)to(i,0).We set an edge einR⁰_n,0(M)to be open if its passage timet(e) ≤N.Setδ = 2in Proposition 1.1 and let A_n denote the event that the rectangleR⁰_n,0(M)contains an open left-right crossing containing less than2n edges, whereM = M3 is as in Proposition 1.1(ii). Since we only need to hit the line x=nfrom the linex= 0,we have that

Tll(0, n)

n ≤2N+Jn1(A1 ^c_n) (2.1)

whereJ_n= ¹_nPn

i=1t(f_i).SinceP(A^c_n)≤ ^C_n¹₂ for some positive constantC₁,we have that X

n≥1

P(A^c_n)<∞.

Thus by Borel-Cantelli Lemma, we have thatP(lim inf_nA_n) = 1and this implies that

J_n1(A1 ^c_n)−→0a.s. (2.2)

asn→ ∞.This proves (i) withQ1= 2N.

To prove (ii)-(iii), we assume henceforth that X <∞a.s. andEX =∞.ChooseN finite, sufficiently large so thatP(X ≤N)> p₀.Set the edgeeto be open ift(e)≤N.

Clearly each edge is independently open with probability at leastp₀. We prove (iii) first and obtain (ii) as a Corollary.

(iii) Let{h1,i}_1≤i≤Mlogn+1be the set of edges forming the left vertical side ofR⁰_n,0(M) and including the edge from(0,0)to(0,1).Similarly let{hn,i}1≤i≤Mlogn+1be the set of

edges forming the right vertical side ofR⁰_n,0(M)and including the edge from(n,0) to (n,1).We then have that

T_pp(0, n) = T_pp(0, n)11(A_n) +T_pp(0, n)11(A^c_n)

≤



 X

j=1,n

Mlogn+1

X

i=1

t(h_j,i) + 2N n



1(A1 _n) +

n

X

i=1

t(f_i)

! 1

1(A^c_n). (2.3)

Thus T_pp(0, n)

n ≤2N+I1,n+I2,n+Jn1(A1 ^c_n) (2.4) where

I_1,n= 1 n

Mlogn+1

X

i=1

t(h_1,i), I_2,n= 1 n

Mlogn+1

X

i=1

t(h_n,i)

and Jn is as in (2.1). From (2.2), the third term goes to zero a.s. as n → ∞. For the first two terms, we apply Feller’s theorem (Theorem 8.9, Durrett (2001)) with an = exp ⁿ⁻¹_M

.Indeed foram≤n < am+1,we have 1

n

Mlogn+1

X

i=1

t(h1,i)≤ 1 a_m

m+1

X

i=1

t(h1,i) = e^1/M a_m+1

m+1

X

i=1

t(h1,i)

so that

lim sup

n

I1,n≤e^1/Mlim sup

m

1 am

m

X

i=1

t(h1,i). (2.5)

Since

P(t(h1,n)> an) =P

logX > n−1 M

=P

(logX)⁺> n−1 M

forn≥2,we have that X

n

P(t(h1,n)> an) =X

n

P M(logX)⁺+ 1> n

≤ME(logX)⁺+ 2.

SinceE(logX)⁺<∞,we have from Feller’s theorem that the right hand side of (2.5) is zero a.s. This implies that

I1,n−→0a.s. (2.6)

asn→ ∞.SinceI1,nhas the same distribution asI2,nwe have that I2,n−→0in probability.

From (2.4), the result (iii) then follows withQ2= 2N.

(ii) The analysis is the same as above except that we obtain Tpl(0, n)

n ≤2N+I_1,n+J_n1(A1 ^c_n) (2.7) instead of (2.5), since we only need to hit the linex=n.From (2.6) and (2.2), the result then follows.

Proof of Proposition 1.4: Fixδ= 2in Proposition 1.1(i) and letAndenote the event that the rectangleR⁰_n,0(M)defined in proof of Theorem 1.3 contains a left-right crossing containing only edges with zero passage time. HereM =M2is as in Proposition 1.1(i).

Arguing as in the paragraph preceding (2.4), we get that Tpp(0, n)

n ≤I1,n+I2,n+Jn1(A1 ^c_n)

where I_1,n, I_2,n and J_n are as in (2.4). The result follows by an analogous analysis following (2.4).

Proof of Theorem 1.5: We consider the shifted rectangleR⁰_n,1(M) = [1, n]×[1,(logn)²+ 1]. Let A_n denote the event that R⁰_n,1(M)has a left-right crossing consisting of edges with zero passage times. Following an analogous analysis as preceding (2.3) we obtain

Tpp(0, n)≤



 X

j=1,n

(logn)²+1

X

i=1

t(hj,i)



1(A1 n) +

n

X

i=1

t(fi)

! 1

1(A^c_n). (2.8)

(i) follows by an analogous analysis as Proposition 1.4.

(ii) For the estimate onETpp(0, n),we obtain from (2.8) that

ETpp(0, n) ≤ (2(logn)²+ 2)Et(h1,1) +E

n

X

i=1

t(fi)11(A^c_n)

!

= (2(logn)²+ 2)Et(h_1,1) +E

n

X

i=1

t(f_i)

! P(A^c_n)

≤ (2(logn)²+ 2)Et(h1,1) +nEt(f1)C1

n

for some constantC1>0.The second equality is becauseA^c_nis independent of{t(fi)}i. This proves (1.1) in (ii). The convergence in probability follows since _n¹ET_pp(0, n)−→0 asn→ ∞.

(iii) Letδ >0be fixed. From (2.3) and from the estimate onP(A^c_n)in Proposition 1.1 we then have forx >0that

P(T_pp(0, n)>2x)

≤P



 X

j=1,n

(logn)²+1

X

i=1

t(h_j,i)>2x



+ C n^δ

≤P



 [

j=1,n

(logn)²+1

[

i=1

t(h_j,i)> x (logn)²+ 1



+ C n^δ.

≤X

j,i

P t(hj,i)> x((logn)²+ 1)⁻¹ + C

n^δ. (2.9)

We now set δ = 2and x = ((logn)²+ 1)n^θ in (2.9). Here we chooseθ > 0 so that max(1, K−1)< θ⁻¹< K.Thus from (2.9), we get

P T_pp(0, n)>(2(logn)²+ 2)n^θ

≤ X

i,j

P t(hi,j)> n^θ + C

n^δ

≤ (2(logn)²+ 2) 1 n^θK sup

i Et(e_i)^K+ C

n^δ. (2.10)

This proves (1.3) in (iii). Since θK > 1 and θ < 1, we obtain from (2.10) and Borel- Cantelli Lemma that ^Tpp(0,n)_n −→0a.s. asn→ ∞.

(iv) We setδ= 2andx= 2δ₁(logn)³in (2.9). From (2.9), we get P Tpp(0, n)>4δ1(logn)³

≤ X

i,j

P t(h_i,j)>2δ₁(logn)³((logn)²+ 1)⁻¹ + C

n^δ

≤ X

i,j

P(t(hi,j)> δ1logn) + C n^δ

≤ X

i,j

e^−sδ1lognEe^st(hi,j)+ C n^δ

≤ (2(logn)²+ 2)e^−sδ1lognsup

i Ee^st(ei)+ C n^δ,

where the second estimate follows from Markov inequality. Choosingδ1 large, proves (iv).

3 Proof of Proposition 1.1

Proof of Proposition 1.1(i): We use a counting argument and again the fact that either an open left-right crossing occurs or a closed dual top-bottom crossing occurs but not both. As above, we fix a midpointxof an edge at the bottom side ofR_n,0(M)and suppose that there is a dual top-bottom crossing ofRn,0(M)with length k ≥ Mlogn, intersecting x.There are at most 4.3^k−1 dual paths intersecting xand each is closed with probability(1−p)^k.Since there are at mostnchoices forx,we have that a closed dual top bottom crossing occurs with probability at most

n X

k≥Mlogn

4.3^k−1(1−p)^k≤ 1 n^δ+1

providedM is large. The sum above is convergent since1−p < ¹₃. Fixing such anM proves the result.

Proof of Proposition 1.1(ii): Fixp0>0andp > p0.We use comparison with oriented percolation. We draw oriented arrows from (i, j) to (i+ 1, j −1) and from (i, j) to (i+ 1, j+ 1).To draw arrows from(i, j)to(i+ 1, j−1),we letS1andS2 be the bonds from(i, j)to(i, j−1)and from(i, j−1)to(i+ 1, j−1),respectively. LetEidenote the event thatS_i is open. We draw arrow from (i, j)to(i+ 1, j−1)if E₁∩E₂ holds. An analogous procedure is used for drawing oriented arrows from(i, j)to(i+ 1, j+ 1).

We have that P^p(E1 ∩E2) = p² ≥ p²₀. We start from the left side of Rn,0(M) and continue this oriented percolation process iteratively. LetP^ordenote the corresponding probability measure and let LRn denote the event that there exists an oriented left- right crossing ofRn,0(M).IfLRnoccurs, there is an open left-right crossing ofRn,0(M) containing at most2nedges in the original bond percolation. Using a contour argument as in Durrett (1984), we have that

P^or(LRn)≥1− 1 n^δ+1

providedp₀andM are large. Fixing such ap₀andM establishes the result.

To obtain the estimate on Por(LR_n), we letC denote the collection of all oriented paths starting from the left side E_{lef t} of R_n,0(M). We grow the cluster from vertices with eveny coordinate inElef t and for every vertex x ∈ C, there is an oriented path from Elef t tox.As in Durrett (1984), we place a squareS_x⁰⁰ on each vertexx ∈ Z^{2 of} C.Ifx = (i, j), thenS⁰⁰_x has endvertices (i, j−1),(i+ 1, j),(i, j+ 1)and (i−1, j). The

edges ofS_x⁰⁰ are oriented in such a way that the squareS_x⁰⁰forms a clockwise oriented contour aroundx.If two oriented edges in opposite directions coincide, they “cancel"

each other and we draw nothing. There is an outermost contour Πof ∪_x∈CS_x⁰⁰ that is oriented clockwise and enclosesElef t.Oriented arrows with at least one end-vertex in Cand crossingΠare called boundary arrows and we say such arrows were terminated in the cluster growing process.

Suppose that there is no oriented left-right crossing ofR_n,0(M).Letz_uandz_fdenote the rightmost points of intersection of Π and the top and bottom edge of R_n,0(M), respectively. Let Π1 denote the part ofΠ from zu to zf. The path Π1 is contained in Rn,0(M).We writeLR^c_n=S

1≤j≤n−1Aj∩LR_n^c,whereAjdenotes the event thatΠ1cuts the horizontal segment[j−1, j]× {M K_n}of the top edge ofR_T^int.Suppose thatA_j∩LR^c_n occurs and suppose thatΠ1containsk≥Mlognoriented edges.

We count up and down arrows as in Durrett (1984) and obtain a subset Π2 of Π1

consisting of at least ₃₂^k edges, each cutting a boundary arrow that was independently terminated. Since the number of choices of Π1 is at most 4.3^k−1 and each boundary arrow was terminated with probability at most1−p²₀,we obtain that

P^or(Aj∩LR^c_n)≤4 X

k≥Mlogn

3^k−1 1−p²₀^k/32

≤e^−αMlogn

for allnsufficiently large and for some constantα >0,provided p₀>(1−3⁻³²)^1/2.Fixing such anp₀,we get that

Por(LR^c_n) = X

1≤j≤n−1

Por(A_j∩LR^c_n)≤ne^−αMlogn ≤ 1 n^δ+1,

providedM is large.

Acknowledgements

I thank Professors Rahul Roy, Thomas Mountford and the referee for crucial com- ments that led to an improvement of the paper. I also thank Professors Rahul Roy and Thomas Mountford for my fellowship.

References

[1] Bollobas and Riordan: Percolation.Cambridge Univ. Press, (2006).

[2] R. Durrett: Oriented Percolation in Two Dimensions.Annals Prob.,12, (1984), 999–1040.

[3] R. Durrett: Probability: Theory and Examples.Cambridge Univ. Press, (2001).

[4] H. Kesten: On the Speed of convergence in first-passage percolation.Annals Appl. Prob.,3, (1993), 296–338.

[5] R. T. Smythe and J. C. Wierman: First-Passage Percolation on the Square Lattice.Springer- Verlag, (2008).

Electronic Communications in Probability

Advantages of publishing in EJP-ECP

• Very high standards

• Free for authors, free for readers

• Quick publication (no backlog)

Economical model of EJP-ECP

• Low cost, based on free software (OJS

)

• Non profit, sponsored by IMS

, BS

, PKP

• Purely electronic and secure (LOCKSS

)

Help keep the journal free and vigorous

• Donate to the IMS open access fund

(click here to donate!)

• Submit your best articles to EJP-ECP

• Choose EJP-ECP over for-profit journals

1OJS: Open Journal Systemshttp://pkp.sfu.ca/ojs/

2IMS: Institute of Mathematical Statisticshttp://www.imstat.org/

3BS: Bernoulli Societyhttp://www.bernoulli-society.org/

4PK: Public Knowledge Projecthttp://pkp.sfu.ca/

5LOCKSS: Lots of Copies Keep Stuff Safehttp://www.lockss.org/