Random walks in random conductances: decoupling and spread of infection
Peter Gracar Alexandre Stauffer

Some surprises in the neutrino cross sections associated with neutrino spin
    İnanç  Şahin
    December 30, 2023
===========================================================================




Let (G,μ) be a uniformly elliptic random conductance graph on ℤ^d with a Poisson point process of particles at time t=0 that perform independent simple random walks. We show that inside a cube Q_K of side length K, if all subcubes of side length ℓ<K inside Q_K have sufficiently many particles, the particles return to stationarity after cℓ^2 time with a probability close to 1. We also show this result for percolation clusters on locally finite graphs. Using this mixing result and the results of <cit.>, we show that in this setup, an infection spreads with positive speed in any direction. Our framework is robust enough to allow us to also extend the result to infection with recovery, where we show positive speed and that the infection survives indefinitely with positive probability.
 

Keywords and phrases: mixing, decoupling, spread of infection, heat kernel




§ INTRODUCTION


We consider the graph G=(ℤ^d,E), d≥ 2 to be the d-dimensional square lattice, with edges between nearest neighbors: for x,y∈ℤ^d we have (x,y)∈ E iff x-y_1=1. Let {μ_x,y}_(x,y)∈ E be a collection of i.i.d. non-negative weights, which we call conductances. In this paper, edges will always be undirected, so μ_x,y=μ_y,x for all (x,y)∈ E. We also assume that the conductances are uniformly elliptic: that is,

    there exists C_M>0, such that μ_x,y∈[C_M^-1,C_M] for all (x,y)∈ E.


We say x∼ y if (x,y)∈ E and define μ_x=∑_y∼ xμ_x,y. At time 0, consider a Poisson point process of particles on ℤ^d, with intensity measure λ(x)=λ_0μ_x for some constant λ_0>0 and all x∈ℤ^d. That is, for each x∈ℤ^d, the number of particles at x at time 0 is an independent Poisson random variable of mean λ_0μ_x. Then, let the particles perform independent continuous-time simple random walks on the weighted graph so that a particle at x∈ℤ^d jumps to a neighbor y∼ x at rate μ_x,y/μ_x. It follows from the thinning property of Poisson random variables that the system of particles is in stationarity; thus, at any time t, the particles are distributed according to a Poisson point process with intensity measure λ.

We study the spread of an infection among the particles. Assume that at time 0 there is an infected particle at the origin, and all other particles are uninfected. Then an uninfected particle gets infected as soon as it shares a site with an infected particle. Our first result establishes that the infection spreads with positive speed.


	Let {μ_x,y}_(x,y)∈ E be i.i.d. satisfying (<ref>). For any time t≥ 0, let I_t be the position of the infected particle that is furthest away from the origin. Then
	
    lim inf_t→∞I_t_1/t>0  almost surely.



The above result has been established on the square lattice (i.e., μ_x,y=1 for all (x,y)∈ E) by Kesten and Sidoravicius <cit.> via an intricate multi-scale analysis; see also <cit.> for a shape theorem. In a companion paper <cit.>, we develop a framework which can be used to analyze processes on this setting without the need of carrying out a multi-scale analysis from scratch. We prove our <Ref> via this framework, showing the applicability of our technique from <cit.>. We also apply this technique to analyze the spread of an infection with recovery.
Let the setup be as before, but now each infected particle independently recovers and becomes uninfected at rate γ for some fixed parameter γ>0. After recovering, a particle becomes again susceptible to the infection and gets infected again whenever it shares a site with an infected particle. Our next result shows that if γ is small enough, then with positive probability there will be at least one infected particle at all times. When this happens, we also obtain that the infection spreads with positive speed.


	Let {μ_x,y}_(x,y)∈ E be i.i.d. satisfying (<ref>). For any λ_0>0, there exists γ_0>0 such that, for all γ∈(0,γ_0), with positive probability, the infection does not die out. Furthermore, there are constants c_1,c_2>0 such that
	
    ℙ[I_t_1≥ c_1t for all t≥0]≥ c_2,

	where I_t is the position of the infected particle that is furthest away from the origin at time t.


The challenge in this setup comes from the heavily dependent structure of the model. Though particles move independently of one another, dependencies do arise over time. For example, if a ball of radius R centered at some vertex x of the graph turns out to have no particles at time 0, then the ball B(x,R/2) of radius R/2 centered at x, will continue to be empty of particles up to time R^2, with positive probability. This means that the probability that the (d+1)-dimensional, space-time cylinder B(x,R/2)×[0,R^2] has no particle is at least exp{-cR^d} for some constant c, which is just a stretched exponential in the volume of the cylinder.
On the other hand, one expects that, after time t≫ R^2, the set of particles inside the ball will become “close” to stationarity.

To deal with dependences, one often resorts to a decoupling argument, showing that two local events behave roughly independently of each other, provided they are measurable according to regions in space time that are sufficiently far apart. We will obtain such an argument by extending a technique which we call local mixing, and which was introduced in <cit.>. The key observation is the following. Consider a cube Q⊆ℤ^d, tessellated into subcubes of side length ℓ>0. For simplicity assume for the moment that μ_x,y=1 for all (x,y)∈ E. Suppose that at some time t, the configuration of particles inside Q is dense enough, in the sense that inside each subcube there are at least cℓ^d particles, for some constant c>0. Regardless of how the particles are distributed inside Q, as long as the subcubes are dense, we obtain that at some time t+c'ℓ^2, not only particles had enough time to move out of the subcubes they were in at time t, but also we obtain that the configuration of particles inside “the core” of Q (i.e., away from the boundary of Q) stochastically dominates a Poisson point process of intensity (1-ϵ)cℓ^d that is independent of the configuration of particles at time t. Moreover, the value ϵ can be made arbitrarily close to 0 by setting c' large enough. In words, we obtain a configuration at time t+c'ℓ^2 inside the core of Q that is roughly independent of the configuration at time t, and is close to the stationary distribution. To the best of our knowledge, the idea of local mixing in such settings originated in the work of Sinclair and Stauffer <cit.>, and was later applied in <cit.>. This idea was then extended  with the introduction of soft local times by Popov and Teixeira <cit.> (see also <cit.>), and applied to other processes, such as random interlacements.

Our second main goal in this paper is to show that this local mixing result can be obtained in a larger setting, in which a local CLT result, which plays a crucial role in the proof[The results of <cit.> are in the setting of Brownian motions on ℝ^d, but can be adapted in a straightforward way to random walks on ℤ^d with μ_x,y=1 for all (x,y)∈ E by using the local CLT.] of <cit.>, might not hold or only holds in the limit as time goes to infinity, with no good control on the convergence rate. This is precisely the situation of our setting, where the weights μ_x,y are not all identical to 1. To work around that, we will show that local mixing can be obtained whenever a so-called Parabolic Harnack Inequality holds, and we have some good estimates on the displacement of random walks. 
 
For the result below, we can impose slightly weaker conditions on μ_x,y. Let p_c be the critical probability for bond percolation on ℤ^d. Assume that μ_x,y are i.i.d. and that, for each (x,y)∈ E, we have

    ℙ[μ_x,y=0]< p_c and μ_x,y satisfies (<ref>) whenever μ_x,y>0.


For two regions Q'⊆ Q⊂ℤ^d, we say that Q' is x away from the boundary of Q iof the distance between Q' and Q^c is at least x. 

	Let {μ_x,y}_(x,y)∈ E be i.i.d. satisfying (<ref>). There exist positive constants c_1, c_2, c_3, c_4, c_5 such that the following holds.
	Fix K>ℓ>0 and ϵ∈(0,1). Consider a cube Q of side-length K, tessellated into subcubes (T_i)_i of side length ℓ.
	Assume each subcube T_i contains at least β∑_x∈ T_iμ_x particles for some β>0, and let Δ≥ c_1ℓ^2ϵ^-c_2.
	If ℓ is large enough, then after the particles move for time Δ, we obtain that within a region Q'⊆ Q that is at least c_3ℓϵ^-c_4 away from the boundary of Q, the particles dominate an independent Poisson point process of intensity measure ν(x)=(1-ϵ)βμ_x, x∈ Q', with probability at least
	
    1-∑_y∈ Q'exp{-c_5βμ_yϵ^2Δ^d/2}.



We will prove a more detailed version of this theorem in <Ref> (see <Ref>). Although we only prove the result for the case of conductances on the square lattice, <Ref> holds for more general graphs. The theorem holds for any graph G and any region Q of G that can be tessellated into subregions of diameter at most ℓ whenever each such subregion is dense enough, the so-called parabolic Harnack inequality holds for G and we have estimates on the displacement of random walks on G. We discuss some extensions in <Ref>.

The structure of this paper is as follows. In <Ref>, we formally define the family of graphs we consider for local mixing and present results concerning the parabolic Harnack inequality, heat kernel bounds and exit times for random walks on such graphs. In <Ref>, we state a more precise version of <Ref> and prove it. In <Ref> we prove an extension of the local mixing result to random walks whose displacement is conditioned to be bounded, which is particularly useful in applications <cit.>. In <Ref>, we use the local mixing result and results from our companion paper <cit.> to prove Theorems <ref> and <ref> for graphs satisfying (<ref>).



§ HEAT KERNEL ESTIMATES AND EXIT TIMES


In this section, we consider a general graph G=(V,E), with uniformly bounded degrees. For x,y∈ V, let |x-y| denote the distance between x and y in G. For x∈ V, let B(x,r)={y∈ V: |x-y|≤ r} be the ball of radius r centered at x. We consider non-negative weights (conductances) (μ_x,y)_(x,y)∈ E, that are symmetric. As in <Ref>, we denote by x∼ y whenever x,y∈ V are neighbors in G, and define μ_x=∑_y∼ xμ_x,y. We also extend μ to a measure on V. For simplicity, the reader may think of V as ℤ^d and μ_x,y being i.i.d. random variables satisfying (<ref>).
We keep our notation in greater generality as we want to highlight the exact conditions we need for our results.

Assume the existence of d≥ 1 and C_U such that

    μ(B(x,r))≤ C_Ur^d,  for all r≥1, and x∈ V.


We consider a continuous time simple random walk on the weighted graph 𝒢:=(G,μ), which jumps from vertex x to vertex y at rate μ_x,y/μ_x. More formally, for any function f:V→ℝ, let

    ℒf(x)=μ_x^-1∑_y∼ xμ_x,y(f(y)-f(x)),

and define the random walk started at vertex x as the Markov process Y=(Y_t,t∈[0,∞),ℙ_x,x∈ V) with generator ℒ. Its heat kernel on the graph is defined as
	
    q_t(x,y)=ℙ_x(Y_t=y)/μ_y, for any x,y∈ V.
	
						
	We will say that a particle walks along 𝒢 if it is a Markov process with generator ℒ as defined above.
	We now state several definitions from <cit.> which we use throughout the paper.
						
	[Very good balls]
		Let C_V, C_P and C_W≥ 1 be fixed constants. We say B(x,r) is (C_V,C_P,C_W)-good if:
		
    μ(B(x,r))≥ C_Vr^d,

		and the weak Poincaré inequality
		
    ∑_y∈ B(x,r)(f(y)-f̅_B(x,r))^2μ_y≤ C_Pr^2∑_y,z∈ B(x,C_Wr),z∼ y(f(y)-f(z))^2μ_yz

		holds for every f:B(x,C_Wr)→ℝ, where f̅_B(x,r)=μ(B(x,r))^-1∑_y∈ B(x,r)f(y)μ_y is the weighted average of f in B(x,r). Furthermore, we say B(x,R) is (C_V,C_P,C_W)- very  good if there exists N_B=N_B(x,R)≤ R^1/(d+2) such that for all r≥ N_B,  B(y,r) is good whenever B(y,r)⊆ B(x,R). We assume that N_B≥ 1.
	
						
	For the remainder of the paper we assume that d≥ 2, fix C_U, C_V, C_P and C_W and take 𝒢=(V,E,μ) to satisfy (<ref>).
						
	We are now ready to present some key results from <cit.> that control the variation of the random walk density function. We will also present a result about random walk exit times which was initially shown in <cit.> for Bernoulli percolation clusters and then generalized to our setup in <cit.>. The first result gives Gaussian upper and lower bounds for the heat kernel for very good balls.
	
<cit.>
	Assume the weights μ_x,y are i.i.d. and (<ref>) holds. Fix a vertex x∈ V. Suppose there exists R_1=R_1(x) such that B(x,R) is very good with N_B(x,R)^3(d+2)≤ R for every R≥ R_1. Then there exist positive constants c_1, c_2, c_3, c_4 such that if t≥ R_1^2/3, we obtain
	
    q_t(x,y)≤ c_1t^-d/2e^-c_2|x-y|^2/t,  for all y∈ V with |x-y|≤ t

	and
	
    q_t(x,y)≥ c_3t^-d/2e^-c_4|x-y|^2/t,  for all y∈ V with |x-y|^3/2≤ t.



Now define the space-time regions
	
    Q(x,R,T)   =   B(x,R)× (0,T],
    
    	Q_-(x,R,T)   =   B(x,R2)×[T4,T2]
       and   
     
    	Q_+(x,R,T)   =   B(x,R2)×[3T4,T].

	
We denote by t+Q(x,R,T)=B(x,R)× (t,t+T). We call a function u:V×ℝ→ℝ caloric on Q if it is defined on Q=Q(x,R,T) and

    ∂/∂ tu(x,t)=ℒu(x,t)  for all (x,t)∈ Q.


We say the parabolic Harnack inequality (PHI) holds with constant C_H for Q=Q(x,R,T) if whenever u=u(x,t) is non-negative and caloric on Q, then

    sup_(x,t)∈ Q_-(x,R,T)u(x,t)≤ C_Hinf_(x,t)∈ Q_+(x,R,T)u(x,t).


It is well known that the heat kernel of a random walk on 𝒢 started at x is a caloric function; in fact taking x=0 and u(x,t)=q_t(0,x) we have

    d/dtq_t(0,x)   =   lim_dt→01/μ_x∑_y∈ Vℙ_0(Y_t=y)ℙ_y(Y_dt=x)-ℙ_0(Y_t=x)ℙ_x(Y_dt≠ x)/dt
       =   1/μ_x(∑_y∼ xℙ_0(Y_t=y)μ_y,x/μ_y-∑_y∼ xμ_x,y/μ_xℙ_0(Y_t=x))
       =   1/μ_x∑_y∼ xμ_x,y(q_t(0,y)-q_t(0,x))=ℒq_t(0,x).


The main result from <cit.> shows that the PHI holds in regions that are very good according to <Ref>.

	<cit.>	
	Let x_0∈ V. Suppose that R_1≥ 16 and B(x_0,R_1) is (C_V,C_P,C_W)- very  good with N_B(x_0,R_1)^2d+4≤ R_1/(2log R_1). Then there exists a constant C_H>0 such that the PHI holds for Q(x_1,R,R^2) for any x_1∈ B(x_0,R_1/3) and for R such that Rlog R=R_1.


A direct consequence of the PHI is the following known proposition, which when applied to the caloric function u(x,t)=q_t(0,x) gives that q_t(0,x) and q_t(0,y) are very similar to each other when x and y are close by. This property will be crucial for our proof of local mixing, so we give the proof of this proposition for completeness.


	Let x_0∈ V. Suppose that there exists s(x_0)≥ 0 so that for all R≥ s(x_0), the PHI holds with constant C_H for Q(x_0,R,R^2) and that the ball B(x_0,R) is (C_V,C_P,C_W)- very  good. Let Θ=log_2(C_H/(C_H-1)), and for x,y∈ V define
	
    ρ(x_0,x,y)=s(x_0)∨ |x_0-x|∨ |x_0-y|.

	There exists a constant c>0 such that the following holds. Let r_0≥ s(x_0) and suppose that u=u(x,t) is caloric in Q=Q(x_0,r_0,r_0^2). Then for any x_1,x_2∈ B(x_0,1/2r_0) and any t_1,t_2 such that r_0^2-ρ(x_0,x_1,x_2)^2≤ t_1,t_2≤ r_0^2 we have
	
    |u(x_1,t_1)-u(x_2,t_2)|≤ c(ρ(x_0,x_1,x_2)/r_0)^Θsup_(t,x)∈ Q_+(x_0,r_0,r_0^2)|u(t,x)|.




	For any integer k≥0, set r_k=2^-kr_0, and let
	
    Q(k)   =   (r_0^2-r_k^2)+Q(x_0,r_k,r_k^2),
    
    		Q_+(k)   =   (r_0^2-r_k^2)+Q_+(x_0,r_k,r_k^2)
       and   
    
    		Q_-(k)   =   (r_0^2-r_k^2)+Q_-(x_0,r_k,r_k^2).

	This gives that Q_+(k)=Q(k+1). Now take k≥ 1 small enough, so that r_k≥ s(x_0). If we apply the PHI to the non-negative caloric functions -u+sup_Q(k)u and u-inf_Q(k)u, we get the inequalities
	
    sup_Q(k)u-inf_Q_-(k)u   ≤    C_H(sup_Q(k)u-sup_Q_+(k)u)

	and
	
    sup_Q_-(k)u-inf_Q(k)u   ≤    C_H(inf_Q_+(k)u-inf_Q(k)u).

	Adding them together and using sup_Q_-(k)u-inf_Q_-(k)u≥ 0 gives
	
    sup_Q(k)u-inf_Q(k)u≤ C_H(sup_Q(k)u-inf_Q(k)u)-C_H(sup_Q_+(k)u-inf_Q_+(k)u)

							
							
							
	Denoting by Osc(u,A)=sup_Au-inf_Au and	setting δ=C_H^-1, this gives
							
	
    Osc(u,Q_+(k))≤(1-δ)Osc(u,Q(k)).

							
	Next, take the largest m such that r_m≥ρ(x_0,x_1,x_2). Then, applying (<ref>) repeatedly on Q(1)⊃ Q(2)⊃… Q(m) yields, since (x_i,t_i)∈ Q(m),
	
    |u(t_1,x_1)-u(t_2,x_2)|≤Osc(u,Q(m))≤ (1-δ)^m-1Osc(u,Q(1)).

	Since
	
    (1-δ)^m=2^-mΘ≤(2ρ(x_0,x_1,x_2)/r_0)^Θ,

	the result follows.



We will also need to control the exit time of the random walk out of a ball of radius r, which we define as

    τ(x,r)=inf{t: Y_t∉B(x,r)}.
 


	Let x_0∈ V and let B(x_0, R) be (C_V,C_P,C_W)- very  good with N_B^d+2<R. Let x∈ B(x_0,5/9R). There exist positive constants c_1, c_2, c_3, c_4 such that if t, r satisfy
	
    0<r≤ R  and   c_1 N_B^d(log N_B)^1/2r≤ t≤ c_2 R^2/log R,

	then we have
	
    ℙ_x(τ(x,r)<t)≤ c_3exp{-c_4r^2/t}.
		



	The proposition was proven for percolation clusters in <cit.>. The proof for more general 𝒢 is similar and can be found in <cit.>.


Since Propositions <ref>, <ref> and <ref> rely on very good balls and the related value N_B, we can assume a lower bound S such that if R>S, then the conditions of all three are satisfied. More formally, we assume the following. 


	The graph G has polynomial growth; i.e., it satisfies (<ref>). Furthermore, there exists a function S: V↦ℝ such that for all R_1 with R_1log R_1≥ S(x_0), the ball B(x_0,R_1) is (C_V,C_P,C_W)-very good with N_B(x_0,R_1)^2d+4≤ R_1.
	As a consequence, Propositions <ref>, <ref>, <ref> and <ref> all hold for any R>S(x).

For i.i.d. weights as defined in <Ref>, we obtain the following.

	If V=ℤ^d and the weights μ_x,y are i.i.d. and satisfy (<ref>) or (<ref>), then <Ref> holds. Furthermore, we have that there exist constants c,γ>0 such that 
	
    ℙ[S(x)≥ n]≤ cexp{-cn^γ} for all x∈ℤ^d and n≥ 0.

	If the weights μ_x,y are i.i.d. and satisfy (<ref>), then <Ref> holds with S(x)= 1 for all x∈ V.



	This has been shown in <cit.>, following from the framework developed in <cit.>. The tail estimate of S(x) was obtained in <cit.>. For the case where μ_x,y satisfy (<ref>), the function S can be set to 1 by <cit.> and the results of <cit.>.





	In <cit.> it has been shown that when the weights μ_x,y are i.i.d. but can assume values arbitrarily close to zero, so neither (<ref>) nor (<ref>) hold, it is possible to find distributions (at least in dimensions d≥ 5) for which <Ref> does not hold. Hence, even though we do not explicitly use uniform ellipticity of μ_x,y in our proofs, this property has a fundamental role in our analysis. Recent results (see, for example, <cit.>) have been derived to relax assumption (<ref>), but they do not establish all properties we need.




§ DECOUPLING VIA LOCAL MIXING


In this section, we will restrict to the case V=ℤ^d and (x,y)∈ E if and only if x-y_1=1, but we do not assume the μ_x,y are i.i.d. We define a cube of side length z>0 as Q_z:=[-z/2,z/2]^d.
In the remainder of the paper, we will work with the heat kernel q_t as defined in (<ref>). Since we allow μ_x,y=0, it is possible for two sites not to be connected. To address this we require the existence of an infinite component. Formally, we assume the following.


	For each (x,y)∈ E, either μ_x,y=0 or it satisfies (<ref>) for a uniform constant C_M. Moreover, the weights μ_x,y are such that an infinite connected component of edges of positive weight within 𝒢 exists and contains the origin.

With this let 𝒞_∞ be the infinite connected component of 𝒢 that contains the origin and define 
	
    Q̃_z:=Q_z∩𝒞_∞.

								
We note that if μ_x,y satisfy (<ref>), then <Ref> is automatically satisfied. We will continue to call Q̃_z as a “cube”. We are now ready to state the more detailed version of <Ref>.			
				

	Let μ_x,y satisfy Assumptions <ref> and <ref>. There exist constants c_0, c_1, C>0 such that the following holds.
	Fix K>ℓ>0 and ϵ∈(0,1). Consider the cube Q_K tessellated into subcubes (T_i)_i of side length ℓ and assume that ℓ>S^d+1(x) for all x∈Q̃_K. 
	Let (x_j)_j⊂Q̃_K be the locations at time 0 of a collection of particles, such that each subcube T̃_i contains at least ∑_y∈T̃_iβμ_y particles for some β>0.
	Let Δ≥ c_0ℓ^2ϵ^-4/Θ where Θ is as in <Ref>.
	For each j denote by Y_j the location of the j-th particle at time Δ. 
	Fix K'>0 such that K-K'≥√(Δ)c_1ϵ^-1/d. Then there exists a coupling ℚ of an independent Poisson point process ψ with intensity measure ζ(y)=β(1-ϵ)μ_y, y∈𝒞_∞, and (Y_j)_j such that within Q̃_K'⊂Q̃_K, ψ is a subset of (Y_j)_j with probability at least
	
    1-∑_y∈Q̃_K'exp{-Cβμ_yϵ^2Δ^d/2}.






				
Note that, due to <Ref>, <Ref> is a special case of <Ref>, which we prove below. In order to do so, we will use something called soft local times, which was introduced in <cit.> to analyze random interlacements, following the introduction of local mixing in <cit.>; see also <cit.> for an application of this technique to random walks on ℤ^d.


	Let (Z_j)_j≤ J be a collection of J independent random particles on V distributed according to a family of density functions g_j:V→ℝ, j≤ J. Define for all y∈ V the soft local time function H_J(y)=∑_j=1^Jξ_jg_j(y), where the ξ_j are i.i.d. exponential random variables of mean 1. Let ψ be a Poisson point process on V with intensity measure ρ:V→ℝ and define the event
	E={ψ is a subset of (Z_j)_j≤ J}.
	Then there exists a coupling such that,  
	
    ℙ[E]≥ℙ[H_J(y)≥ρ(y), ∀ y∈ V].
	
				

We are now ready to prove <Ref>.

	By <Ref>, there exists a coupling ℚ of an independent Poisson point process ψ with intensity measure ζ(y)=β(1-ϵ)μ_y1_{y∈Q̃_K'} and the locations of the particles Y_j, which are distributed according to the density functions f_Δ(x_j,y):=q_Δ(x_j,y)μ_y, y∈𝒞_∞, such that ψ is a subset of (Y_j)_j with probability at least
	
    ℚ[H_J(y)≥βμ_y(1-ϵ), ∀ y∈Q̃_K'],
	
	where H_J(y)=∑_j=1^Jξ_j f_Δ(x_j,y) and (ξ_j)_j≤ J are i.i.d. exponential random variables with parameter 1. We first observe that the probability of the converse event is
	
    ℚ[∃ y∈Q̃_K': H_J(y)<βμ_y(1-ϵ)]   ≤   ∑_y∈Q̃_K'ℚ[H_J(y)<βμ_y(1-ϵ)]
       ≤   ∑_y∈Q̃_K'e^κμ_yβ(1-ϵ)𝔼^ℚ[exp{-κ H_J'(y)}],

	where we used Markov's inequality in the last step, which is valid for any κ>0. Let c_1 be a positive constant which we will fix later and let 
	
    R=√(Δ)c_1ϵ^-1/d.
 
	Let J' be a subset of {1,2,…,J} such that for each T̃_i, J' contains exactly ⌈∑_y∈T̃_iβμ_y⌉ particles that are inside T̃_i.
	Define J'(y)⊆ J' to be the set of j∈ J' such that |x_j-y|≤ R and define H'(y) as H_J(y) but with the sum restricted to j∈ J'(y). Since H_J(y)≥ H'(y) we get that								
	
    𝔼^ℚ[exp{-κ H_J(y)}]≤𝔼^ℚ[exp{-κ H'(y)}].

	Next, we use that the ξ_j in the definition of H are independent exponential random variables to obtain
	
    𝔼^ℚ[exp{-κ H'(y)}]   =   ∏_j∈ J'(y)𝔼^ℚ[exp{-κξ_jf_Δ(x_j,y)}]
       =   ∏_j∈ J'(y)(1+κ f_Δ(x_j,y))^-1.

											 
	Using Taylor's expansion we have that log(1+x)≥ x-x^2 for |x|≤1/2. Since ℓ≥ S(x), we can apply <Ref>, to have q_Δ(x,y)≤ c_2Δ^-d/2 for a constant c_2>0 and all y∈Q̃_K' and x∈ J'(y).
	Hence if κ = CϵΔ^d/2 for the constant C=(4C_Uc_2)^-1, then
	
    sup_x∈ B(y,R+√(d)ℓ)κ f_Δ(x,y)=sup_x∈ B(y,R+√(d)ℓ)κμ_y q_Δ(x,y)≤ C_Uc_2κΔ^-d/2<ϵ/4.

	For such a value of κ we have
	
    ∏_j∈ J'(y)(1+κ f_Δ(x_j,y))^-1   ≤   ∏_j∈ J'(y)exp{-κ f_Δ(x_j,y)(1-κ f_Δ(x_j,y))}
       ≤   exp{-∑_j∈ J'(y)κ f_Δ(x_j,y)(1-sup_x∈ B(y,R+√(d)ℓ)κ f_Δ(x,y))}
       ≤   exp{-κ∑_j∈ J'(y) f_Δ(x_j,y)(1-ϵ/4)}.

	We claim that 
	
    ∑_j∈ J'(y)f_Δ(x_j,y)≥βμ_y(1-ϵ/2),

	which together with (<ref>), (<ref>) and (<ref>) give that	
	
    ℚ[∃ y∈Q̃_K': H_J(y)<βμ_y(1-ϵ)]    ≤   exp{κμ_yβ(1-ϵ)-κβμ_y(1-ϵ/2)(1-ϵ/4)}
       ≤   exp{-κβμ_yϵ/4}.

	Using the value of κ gives the theorem.
	
	It remains to show (<ref>). For each T̃_i and each particle x_j∈T̃_i, let x_j'∈T̃_i be such that x_j'=max_w∈T̃_if_Δ(w,y). 
	Then, write
	
    ∑_j∈ J'(y)f_Δ(x_j,y)   ≥   ∑_j∈ J'(y)(f_Δ(x_j',y)-|f_Δ(x_j',y)-f_Δ(x_j,y)|).
										
	
	We have for each T̃_i
	
    ∑_j∈ J'(y)
    x_j∈T̃_if_Δ(x_j',y)
    		   =   max_w∈T̃_if_Δ(w,y)∑_j∈ J'(y)
    x_j∈T̃_i1
       ≥   max_w∈T̃_if_Δ(w,y)∑_z∈T̃_iβμ_z
       ≥   ∑_z∈T̃_iβμ_z f_Δ(z,y).
	
	Set R(y) to be the set of all sites z such that |z-y|≤ R-√(d)ℓ. Note that if z∈ R(y) then for all particles x_j with x'_j=z and j∈ J' we have j∈ J'(y). 
	We observe that since μ_z f_Δ(z,y)=μ_y f_Δ(y,z), we have by using (<ref>) for each T̃_i that
	
    ∑_j∈ J'(y)f_Δ(x_j',y)   ≥   ∑_z∈ R(y)βμ_z f_Δ(z,y)
       =   βμ_y∑_z∈ R(y)f_Δ(y,z).

	Then, since ℓ>S^d+1(x) we have by <Ref> that there exist constants c_4 and c_5 such that 
	
    ∑_j∈ J'(y)f_Δ(x_j',y)   ≥   βμ_yℙ_y(τ(y,R-√(d)ℓ)≥Δ)
       ≥   βμ_y(1-c_4exp{-c_5c_1^2ϵ^-2/d})
       ≥   βμ_y(1-ϵ/4),

	where we set c_1 large enough with respect to c_4 and c_5 for the last inequality to hold.
											
	Now it remains to obtain an upper bound for the term ∑_j∈ J'(y)|f_Δ(x_j',y)-f_Δ(x_j,y)|.
	We define I to be the set of all i such that T̃_i contains a particle x_j from the set (x_j)_j∈ J'(y). Then, since ℓ>S(x), there exists positive constants C_PHI and C_BH such that if we apply the PHI (cf. <Ref>) with	
    r_0^2=Δ≥ c_0ℓ^2ϵ^-4/Θ

	for some constant c_0>d, we obtain
	
	
    ∑_j∈ J'(y)|f_Δ(x_j',y)-f_Δ(x_j,y)|   =   ∑_i∈ I∑_j∈ J'(y):
    x_j∈T̃_i|f_Δ(x_j',y)-f_Δ(x_j,y)|
       =   μ_y∑_i∈ I∑_j∈ J'(y):
    x_j∈T̃_i|q_Δ(x_j',y)-q_Δ(x_j,y)|
       ≤   μ_y∑_i∈ I∑_j∈ J'(y):
    x_j∈T̃_iC_PHIℓ^Θ/Δ^Θ/2C_BHΔ^-d/2
       ≤   μ_y∑_i∈ I∑_x∈T̃_i2βμ_x C_PHIℓ^Θ/Δ^Θ/2C_BHΔ^-d/2,

	where in the first inequality we replaced the supremum term coming from <Ref> by its upper bound C_BHΔ^-d/2 from <Ref>, and used that r_0=√(Δ) in the bound from <Ref>. Then
	
    ∑_j∈ J'(t)|f_Δ(x_j',y)-f_Δ(x_j,y)|   ≤   2βμ_y C_PHIC_BH∑_i∈ I∑_x∈T̃_iμ_xℓ^ΘΔ^-(d+Θ)/2
       ≤   2βμ_y C_PHIC_BHC_UR^dℓ^ΘΔ^-(d+Θ)/2
       ≤   βμ_yϵ/4,

	where the last inequality holds by using Δ≥ c_0ℓ^2ϵ^-4/Θ and setting c_0>(2C_PHIC_BHC_Uc_1^d)^-2/θ. Note that in order to use <Ref>, we need to have that each pair x_j,x_j' is contained in some ball B(x_0,r_0/2). This is satisfied since x_j-x_j'≤√(d)ℓ and r_0 is set sufficiently large by (<ref>).
	Plugging (<ref>) and (<ref>) into (<ref>) proves (<ref>).
	



§ EXTENSIONS

				
Although the estimate derived in <Ref> does not depend on the particles outside of Q_K at time 0 when K-K' is sufficiently large, it still depends on the geometry of the entire graph outside of Q_K. In some applications, as in our companion paper <cit.>, one needs to apply this coupling in many different regions of the graph simultaneously. In such cases, in order to control dependences between different regions, it is important that the coupling procedure depends only on the local structure of the graph. In order to do this, we will condition the particles to be inside some large enough, but finite region while they move for time Δ. Recall that, for any ρ>0, Q_ρ=[-ρ/2,ρ/2]^d is the cube of side length ρ. For any ρ>0, we say that a random walk has displacement in Q_ρ during [0,Δ] if the random walk never exits x+Q_ρ during the time interval [0,Δ], where x is the starting vertex of the random walk.
				

	Let μ_x,y satisfy Assumptions <ref> and <ref>. There exist constants c_1 and c_2 so that the following holds. Let V=ℤ^d, ℓ>0 and consider the cube Q_ℓ. Assume ℓ>S(x) for all x∈ Q_ℓ. Let Δ>c_1ℓ^2 and ρ≥ c_2√(ΔlogΔ). Consider a random walk Y that moves along 𝒢 for time Δ conditioned on having its displacement in Q_ρ during the time interval [0,Δ]. Let x,y∈ Q_ℓ with x being the starting point of the walk, and define 
	
    g(x,y):=ℙ_x[Y_Δ=y | Y has displacement in Q_ρ during [0,Δ]].

	Then there exists a constant C>2 such that for x,y,z∈ Q_ℓ we have
	
    |g(x,y)/μ_y-g(z,y)/μ_y|≤ Cℓ^ΘΔ^-(d+Θ)/2.




	Note that the above bound has the same form as the one for the heat kernel of unconditioned random walks in <Ref>, with the supremum being bounded above by the heat kernel bound from <Ref>. This allows us to extend <Ref> to random walks conditioned to have a bounded displacement during [0,Δ].


				

	Denote by p_E(ρ) the probability that a random walk started at x has displacement in Q_ρ during [0,Δ]. From <Ref> , we have that if Δ is sufficiently big, then
	
    1-p_E(ρ)   ≤ℙ_x[Y  exits B(x,ρ/2) during [0,Δ]]
       =ℙ_x(τ(x,ρ/2)<Δ)
       ≤ c_aexp{-c_bρ^2/Δ}.

											
	Next, using h(x,y):=ℙ_x[Y_Δ=y | Y exits x+Q_ρ during [0,Δ]] and f_Δ(x,y)=ℙ_x[Y_Δ=y], we can write
	
    f_Δ(x,y)=g(x,y)p_E(ρ)+h(x,y)(1-p_E(ρ)).

	With this we have
	
    g(x,y)≤ f_Δ(x,y)1/p_E(ρ).

											
	Then, we can write
	
    |g(x,y)/μ_y-g(z,y)/μ_y|   =   1_{g(x,y)>g(z,y)}(g(x,y)/μ_y-g(z,y)/μ_y)
          +1_{g(x,y)<g(z,y)}(g(z,y)/μ_y-g(x,y)/μ_y)
       ≤   1_{g(x,y)>g(z,y)}(f_Δ(x,y)/μ_yp_E(ρ)-f_Δ(z,y)/μ_yp_E(ρ)+h(z,y)(1-p_E(ρ))/p_E(ρ)μ_y)
          +1_{g(x,y)<g(z,y)}(f_Δ(z,y)/μ_yp_E(ρ)-f_Δ(x,y)/μ_yp_E(ρ)+h(x,y)(1-p_E(ρ))/p_E(ρ)μ_y)
       ≤   |q_Δ(y,x)-q_Δ(y,z)|/p_E(ρ)+max{h(x,y),h(z,y)}(1-p_E(ρ))/p_E(ρ)μ_y.

	
	Note that h(x,y) can be written as f_Δ-τ(w,y), where τ is the first time Y exists x+Q_ρ and w is the random vertex at the boundary of x+Q_ρ where Y is at time τ. Since the weights μ_x,y satisfy (<ref>) by <Ref>, we have that f_Δ-τ(w,y)/μ_y is at most some positive constant c. This holds because either Δ-τ is larger than |w-y|, which allows us to apply heat kernel bounds from <Ref>, or Δ-τ is smaller than |w-y| so f_Δ-τ(w,y) is bounded above by the probability that a random walk jumps at least |w-y| steps in time Δ-τ, which is small enough since |w-y| is large. This gives that max{h(x,y),h(z,y)}/μ_y is at most c. With this and (<ref>) we obtain that
	
    max{h(x,y),h(z,y)}(1-p_E(ρ))/μ_y p_E(ρ)   ≤c c_a/p_E(ρ)exp{-c_bρ^2/Δ}
       ≤c c_a/p_E(ρ)exp{-c_b c_2logΔ}.

	By (<ref>) we can just bound p_E(ρ)≥ 1/2 above. Then,  applying <Ref> to |q_Δ(y,x)-q_Δ(y,z)|, and using <Ref> to bound the resulting supremum term, concludes the proof.


The next theorem is an adaptation of <Ref> for conditioned random walks. Note that we need a stronger condition on K-K' below than in <Ref>.

	Let μ_x,y satisfy Assumptions <ref> and <ref>. There exist constants c_0, c_1, C>0 such that the following holds.
	Fix K>ℓ>0 and ϵ∈(0,1). Consider the cube Q_K tessellated into subcubes (T_i)_i of side length ℓ and assume that ℓ>S^d+1(x) for all x∈Q̃_K. 
	Let (x_j)_j⊂Q̃_K be the locations at time 0 of a collection of particles, such that each subcube T̃_i contains at least ∑_y∈T̃_iβμ_y particles for some β>0.
	Let Δ≥ c_0ℓ^2ϵ^-4/Θ, where Θ is as in <Ref>.
	Fix K'>0 such that K-K'≥ c_1√(ΔlogΔ). 
	For each j, denote by Y_j the location of the j-th particle at time Δ, conditioned on having displacement in Q_K-K' during [0,Δ]. 
	Then there exists a coupling ℚ of an independent Poisson point process ψ with intensity measure ζ(y)=β(1-ϵ)μ_y, y∈Q̃_K, and (Y_j)_j such that within Q̃_K'⊂Q̃_K, ψ is a subset of (Y_j)_j with probability at least
	
    1-∑_y∈Q̃_K'exp{-Cβμ_yϵ^2Δ^d/2}.


				

	Using <Ref> and (<ref>) when setting κ, the proof goes in the same way as the proof of <Ref>. The independence from G outside of Q̃_K follows from the fact that we only consider particles which have displacement in Q_K-K' and ended in Q̃_K', so that they never left Q̃_K during [0,Δ]. 

		


 §.§ Extension to other graphs

		
We have shown that the local mixing result of Theorems <ref> and <ref> work for ℤ^d, but they can easily be extended to the more general graphs defined in <Ref>, as long as Assumptions <ref> and <ref> hold.

We start with a region A⊆𝒞_∞ around the origin of G and tesselate it into tiles (T_i)_i∈ I of diameter at most ℓ. Let Δ be as in <Ref>. Let A'⊂ A be all the sites in A that are at least √(Δ)c_1ϵ^-1/d+cℓ away from the boundary of A. Then, if A' is not empty, using the same steps as in the proof of <Ref>, if each tile T_i of A contains at least β∑_y∈ T_iμ_y particles at time 0, it holds that in the region A', there is a coupling with an independent Poisson point process ψ of intensity measure ζ(y)=β(1-ϵ)μ_y such that at time Δ the particles inside A' are contained in ψ with probability at least

    1-∑_y∈ A'exp{-Cβμ_yϵ^2Δ^d/2},

for some constant C>0.

Furthermore, <Ref> can analogously be extended in the same way, if we require that A' contains only sites that are at least c_1√(ΔlogΔ) away from the boundary of A, for some constant c_1, and if we condition the random walks to have their displacement limited to a ball of radius c_1√(ΔlogΔ).



§ SPREAD OF THE INFECTION


Our goal in this section will be to use <Ref> in order to show that on the graph G=(V,E) with V=ℤ^d and E={(x,y):x-y_1=1}, and with μ_x,y, (x,y)∈ E being i.i.d. and satisfying (<ref>), information spreads with positive speed in any direction, as claimed in Theorems <ref> and <ref>. In this setting, <Ref> guarantees that <Ref> holds with S(x)≡ 1 and since μ_x,y≠ 0 for all (x,y)∈ E, we also have that <Ref> holds. 

Recall that we assume d≥ 2. Tessellate ℤ^d into cubes of side length ℓ, indexed by i∈ℤ^d. Next, tessellate time into intervals of length β, indexed by τ∈ℤ. With this we denote by the space-time cell (i,τ)∈ℤ^d+1 the region ∏_j=1^d[i_jℓ,(i_j+1)ℓ]×[τβ,(τ+1)β]. In the following, β is set as a function of ℓ so that the ratio β/ℓ^2 is fixed first to be a small constant, and then ℓ is set sufficiently large.

We will use a result from <cit.> that gives the existence of a Lipschitz connected surface (cf. Definitions <ref> and <ref> below) that surrounds the origin and which is composed of space-time cells, for which a certain local event holds. This will allow us to obtain an infinite sequence of space-time cells, such that the infection spreads from one cell to the next.

In order to obtain this result, we will need to consider overlapping space-time cells. Let η≥ 1 be an integer which will represent the amount of overlap between cells. For each cube i=(i_1,…,i_d) and time interval τ, define the super cube i as ∏_j=1^d[(i_j-η)ℓ,(i_j+η+1)ℓ] and the super interval τ as [τβ,(τ+η)β]. We define the super cell (i,τ) as the Cartesian product of the super cube i and the super interval τ.

In the following we will say a particle has displacement inside X' during a time interval [t_0,t_0+t_1], if the location of the particle at all times during [t_0,t_0+t_1] is inside x+X', where x is the location of the particle at time t_0. For each time s≥ 0, let Π_s be a point process on V, which represents the locations of the particles at time s. We say an event E is increasing for (Π_s)_s≥ 0 if the fact that E holds for (Π_s)_s≥ 0 implies that it holds for all (Π'_s)_s≥ 0 for which Π_s'⊇Π_s for all s≥ 0. We say an event E is restricted to a region X⊂ℤ^d and a time interval [t_0,t_1] if it is measurable with respect to the σ-field generated by all the particles that are inside X at time t_0 and their positions during [t_0,t_1]. For an increasing event E that is restricted to a region X and time interval [t_0,t_1], we have the following definition.


	ν_E is called the probability associated to a an increasing event E that is restricted to X  and a time interval [t_0, t_0+t_1] if, for an intensity measure ζ, ν_E(ζ,X,X',t_1) is the probability that E happens given that, at time t_0, the particles in X are given by a Poisson point process of intensity measure ζ and their motions from t_0 to t_0+t_1 are independent continuous time random walks on the weighted graph (G,μ), where the particles are conditioned to have displacement inside X'.


For each (i,τ)∈ℤ^d+1, let E_st(i,τ) be an increasing event restricted to the super cube i and the super interval τ. Here the subscript st refers to space-time. We say that a cell (i,τ) is bad if E_st(i,τ) does not hold and good otherwise.

We will need a different way to index space-time cells, which we refer to as the base-height index. In the base-height index, we pick one of the d spatial dimensions and denote it as height, using index h∈ℤ, while the remaining d space-time dimensions form the base, which we index by b∈ℤ^d. In this way, for each space-time cell (i,τ) there will be (b,h)∈ℤ^d+1 such that the base-height cell (b,h) corresponds to the space-time cell (i,τ)

We analogously define the base-height super cell (b,h) to be the space-time super cell (i,τ), for which the base-height cell (b,h) corresponds to the space-time cell (i,τ). Similarly, we define E_bh(b,h), the increasing event restricted to the super cell (b,h) that is the same as the event E_st(i,τ) for the space-time super cell (i,τ) that corresponds to the base-height super cell (b,h). Here, the subscript bh refers to the base-height index.

In order to prove Theorems <ref> and <ref>, we will need a theorem from <cit.>, which gives the existence of a two-sided Lipschitz surface F.


	A function F:ℤ^d→ℤ is called a Lipschitz function
	 if |F(x)-F(y)|≤ 1 whenever x-y_1 = 1.



	A two-sided Lipschitz surface F is a set of base-height cells (b,h)∈ℤ^d+1 such that for all b∈ℤ^d there are exactly two (possibly equal) integer values F_+(b)≥ 0 and F_-(b)≤0 for which (b,F_+(b)),(b,F_-(b))∈ F and, moreover, F_+ and F_- are Lipschitz functions.


We say a space-time cell (i,τ) belongs to F if there exists a base-height cell (b,h)∈ F that corresponds to (i,τ). We say a two-sided Lipschitz surface F is finite, if for all b∈ℤ^d, we have F_+(b)<∞ and F_-(b)>-∞. For a positive integer D, we say a two-sided Lipschitz surface surrounds a cell (b',h') at distance D if any path (b',h')=(b_0,h_0),(b_1,h_1),…,(b_n,h_n) for which (b_i,h_i)-(b_i-1,h_i-1)_1=1 for all i∈{1,… n} and (b_n,h_n)-(b_0,h_0)_1>D, intersects with F.

We now present the main result from our paper <cit.>, which holds for graphs where a local mixing result, such as the one in <Ref>, hold. More precisely, for a graph satisfying Assumption <ref> and (<ref>) (which implies <Ref> holds) we have that <Ref> holds (with S(x)=1 for all x∈ V), which in turn gives that the following result from <cit.> holds. Recall that, for any ρ≥ 2, Q_ρ stands for the cube [-ρ/2,ρ/2]^d, and  that λ is the intensity measure of the Poisson point process of particles as defined in <Ref>.




	Let 𝒢=(G,μ) be a graph satisfying Assumption <ref> and (<ref>) on the lattice ℤ^d for d≥ 2. There exist positive constants c_1 and c_2 such that the following holds. Tessellate G in space-time cells and super cells as described above for some ℓ,β,η>0 such that the ratio β/ℓ^2 is small enough. 
	
	Let E_st(i,τ) be an increasing event, restricted to the space-time super cell (i,τ). 
	Fix ϵ∈(0,1) and fix w such that
	
    w≥√(ηβ/c_2ℓ^2log(8c_1/ϵ)).
 
	Then, there exists a positive number α_0 that depends on ϵ, η and that ratio β/ℓ^2 so that if
	
    min{C_M^-1ϵ^2λ_0ℓ^d,log(1/1-ν_E_st((1-ϵ)λ,Q_(2η+1)ℓ,Q_wℓ,ηβ))}≥α_0,

	a two-sided Lipschitz surface F where E_st(i,τ) holds for all (i,τ)∈ F exists. Furthermore, the surface is finite almost surely and surrounds the origin at a finite distance almost surely.


Recall that we want to show that the infection spreads with positive speed. Given a space-time tessellation of G and a local increasing event E_st, <Ref> gives the existence of a Lipschitz surface F on which E_st holds. Let T=ℓ^5/3. We will define the increasing event E_st(i,τ) to represent a single infected particle in the middle of the super cube i at time τβ infecting a large number of particles in that super cube by time τβ+T, after which the infected particles move up to time (τ+1)β, spreading to all of the cubes contained in the super cube.

Let (i,τ) be a space-time cell as defined previously. We consider that there is an infected particle in the center cube of the super cube i at time τβ, that is,  the particle is inside ∏_j=1^d[i_jℓ,(i_j+1)ℓ]. Starting from time τβ, we let the infected particle move and infect sufficiently many other particles by time τβ+T. This is given in the lemma below.


	There exist positive constant C_1 such that the following holds for all large enough ℓ.
	Let Q^*=∏_j=1^d[(i_j-η)ℓ,(i_j+η+1)ℓ] and let (ρ(t))_τβ≤ t≤τβ+T be the path of an infected particle that starts in ∏_j=1^d[i_jℓ,(i_j+1)ℓ] and stays inside ∏_j=1^d[(i_j-η+1)ℓ,(i_j+η)ℓ] during [τβ,τβ+T]. Assume that at time τβ, the number of particles at each vertex x∈ Q^*∖ρ(τβ) is a Poisson random variable of mean λ_0/2μ_x.
	Let Υ be the subset of those particles that do not leave Q^* during [τβ,τβ+T], and let Υ'⊂Υ be the particles colliding with the path ρ, that is, for each particle of Υ' there exists a time t∈[τβ,τβ+T] such that the particle is located at ρ(t). Then, Υ' is a Poisson random variable of mean at least
	C_1λ_0ℓ^1/3.



	For each time t∈ [τβ,τβ+T], let Ψ_t be the Poisson point process on V giving the locations at time t of the particles that belong to Υ. Since the particles that start in Q^* move around and can leave Q^*, we need to find a lower bound for the intensity of Ψ_t for times in [τβ,τβ+T]. Note that the infected particle we are tracking is not part of Ψ, since Ψ does not include particles located at ρ(τβ) at time τβ. 
	
	We will need to apply heat kernel bounds from <Ref> to the particles in Q^*, so we need to ensure that the time intervals we consider are large enough for the proposition to hold. 
	
	We will only consider times t∈[ℓ^4/3,T] so that for large enough ℓ, t≥sup_x∈ Q^*
y∈ Q^*x-y_1 and so the heat kernel bounds from <Ref> hold. Then, we have that for all sites x∈ Q^* that are at least ℓ away from the boundary of Q^* and at any such time t the intensity of Ψ_τβ+t at vertex x∈ V is at least
	
    ψ(x,τβ+t)≥∑_y∈ Q^*
    y≠ρ(τβ)λ_02μ_y·μ_xq_t(y,x)
    		= λ_02μ_x∑_y∈ Q^*
    y≠ρ(τβ)ℙ_x[Y_t=y],

	where we used in the last step that the heat kernel q_t is symmetric. We now use the exit time bound from <Ref>  to get that 
	
    ∑_y∈ Q^*ℙ_x[Y_t=y]≥ 1-c_3exp{-c_4ℓ^2/t}.

	Next, we use that ℙ_x[Y_t=y]=μ_y q_t(x,y)≤ C_M q_t(x,y), and use <Ref> to account for the particles at ρ(τβ), yielding 
	
    ∑_y∈ Q^*
    y≠ρ(τβ)ℙ_x[Y_t=y]≥ 1-c_3exp{-c_4ℓ^2/t}-C_Mc_5t^-d/2.

	This gives that for any t∈[ℓ^4/3,T], the intensity of Ψ_τβ+t is at least
	
    ψ(x,τβ+t)≥λ_02μ_x(1-c_3exp{-c_4ℓ^2/T}-C_Mc_5ℓ^-2d/3).



	Let [τβ,τβ+T] be divided into subintervals of length W∈(0,T], where we set W=ℓ^4/3 so that it is large enough to allow the use of the heat kernel bounds from <Ref>. Let J={1,…, ⌊ T/W⌋} and t_j:=τβ+jW. Then the intensity of particles that share a site with the initially infected particle only at one time among {t_1, t_2, …, t_⌊ T/W⌋} is at least
	
    ∑_j∈ Jψ(ρ(t_j),t_j)ℙ_ρ(t_j)[X_r-t_j≠ρ(r)  ∀ r∈{t_j+1,…,t_⌊ T/W⌋}]
       ≥λ_02 C_M^-1(1-c_3exp{-c_4ℓ^2/T}-C_Mc_5ℓ^-2d/3)∑_j∈ J(1-∑_z>jℙ_ρ(t_j)[X_t_z-t_j= ρ(t_z)]).


	We want to make all of the terms of the sum over J positive, so we consider the term ∑_z>jℙ_ρ(t_j)[X_t_z-t_j= ρ(t_z)] and show that it is smaller than 1/2 for large enough ℓ. To do this, we use that ℙ_x[Y_t=y]=μ_y q_t(x,y) with the heat kernel bounds from <Ref>, which hold when W≥ℓ^4/3 and ℓ is large enough, to bound it from above by
	
    ∑_z>jℙ_ρ(t_j)[X_t_z-t_j= ρ(t_z)]
    		   ≤∑_z>jC_MC_HK(t_z-t_j)^-d/2
       ≤ C_M C_HKW^-d/2∑_z=1^T/W-jz^-d/2

	where C_HK is the constant coming from <Ref>. Then, (<ref>) can be bound from above by
	
    C_M C_HK W^-d/2(2+∑_z=3^T/W-jz^-d/2)
    		≤ C_M C_HKW^-d/2(2+∫_2^T/Wz^-d/2dz).

	Let C be a constant that can depend on C_HK, C_M and d. Then for d=2, (<ref>) it is smaller than CW^-1log(T/W), and for d≥ 3 the expression in (<ref>) is smaller than CW^-d/2. Thus, setting ℓ large enough, both terms are smaller than 1/2.

	Then, as a sum of Poisson random variables, we get that Υ' is a Poisson random variable with a mean at least
	
    λ_02 C_M^-1(1-c_3exp{-2c_4ℓ^2/T}-C_Mc_5ℓ^-2d/3)T2W.

	Using that T=ℓ^5/3 and setting ℓ large enough establishes the lemma, with C_1 being any constant satisfying C_1<C_M^-1/4.


Next we show that the particles from <Ref> move to nearby cells, spreading the infection.


	Let z=(z_1,…,z_d) with z_j∈{-η,-η+1,…,η} for all j∈{1,… d}, and fix the ratio β/ℓ^2. Let A(i,τ,N,z) be the event that given a set of N>0 particles in ∏_j=1^d[(i_j-η)ℓ,(i_j+η+1)ℓ] at time τβ+T,
	at least one of them is in ∏_j=1^d[(i_j+z_j)ℓ,(i_j+z_j+1)ℓ] at time (τ+1)β. Then, if ℓ is sufficiently large while keeping β/ℓ^2 fixed, we obtain
	
    ℙ[A(i,τ,N,z)]≥ 1-exp{-Nc_p},

	where c_p is a positive constant that is bounded away from 0 and depends only on d, η and the ratio β/ℓ^2.



	Let Q^*=∏_j=1^d[(i_j-η)ℓ,(i_j+η+1)ℓ] and Q^**=∏_j=1^d[(i_j+z_j)ℓ,(i_j+z_j+1)ℓ]. For t^2/3≥sup_x∈ Q^*
y∈ Q^**x-y_1, define p_t:=inf_x∈ Q^*∑_y∈ Q^**ℙ_x[Y_t=y]. Then, if we define bin(N,p_t) to be a binomial random variable of parameters N∈ℕ and p_t∈[0,1], it directly follows that
	
    ℙ[A(i,τ,N,z)]≥ℙ[bin(N,p_t)≥1]≥1-exp{-Np_t}.


	It remains to show that for t=β-T, we have that p_t≥ c_p>0 for some constant c_p. We will use the heat kernel bounds for the pair x,y, which hold if x-y_1^3/2≤β-T for all x∈ Q^*,y∈ Q^**. Given the ratio β/ℓ^2, d and η, this is satisfied if ℓ is large enough. Then we have that
	
    p_β-T   =inf_x∈ Q^*∑_y∈ Q^**ℙ_x[Y_β-T=y]
       ≥inf_x∈ Q^*C_M^-1∑_y∈ Q^**q_β-T(x,y)
       ≥inf_x∈ Q^*C_M^-1∑_y∈ Q^**c_1 β^-d/2exp{-c_2x-y_1^2/β-T}.

	Now we use that x and y can be at most c_ηℓ apart where c_η is a constant depending on d and η only, and that β-T≥β/2 for ℓ large enough. Hence,
	
	
	
	
    p_β-T   ≥inf_x∈ Q^*C_M^-1∑_y∈ Q^**c_1 β^-d/2exp{-c_22(c_ηℓ)^2/β}
       = C_M^-1c_1ℓ^d(1/β)^d/2exp{-c_22(c_ηℓ)^2/β}
       ≥ c_p.



In the next lemma, we will tie together the results from <Ref> and <Ref>. In order to precisely describe the behavior of the particles involved, we say a particle x collides with particle y during a time interval [t_0,t_1], if for at least one t∈[t_0,t_1], x and y are at the same site.


	Consider the super cell (i,τ). Assume that at each site x∈∏_j=1^d[(i_j-η)ℓ,(i_j+η+1)ℓ] the number of particles at x at time τβ is a Poisson random variable of intensity λ_0/2μ_x, and let Υ be the collection of such particles. Assume that, at time τβ, there is at least one infected particle x_0 inside ∏_j=1^d[i_jℓ,(i_j+1)ℓ]. Let E_st(i,τ) be the event that at time (τ+1)β, for all i'∈ℤ^d with i-i'_∞≤η, there is at least one particle  from Υ in ∏_j=1^d[(i_j')ℓ,(i_j'+1)ℓ] that collided with x_0 during [τβ,τβ+T]. If ℓ is sufficiently large for Lemmas <ref> and <ref> to hold,
	then there exists a positive constant C such that
	
    ℙ[E_st(i,τ)]≥1-exp{-Cλ_0ℓ^1/3}.




	We note that, by definition, the event E_st(i,τ) is restricted to the super cube ∏_j=1^d[(i_j-η)ℓ,(i_j+η+1)ℓ] and time interval [τβ,(τ+1)β].
	We define the following 3 events.
	
		
  F_1: The initial infected particle x_0 never leaves ∏_j=1^d[(i_j-η+1)ℓ,(i_j+η-1)ℓ] during [τβ,τβ+ T].
		
  F_2: Let C_1 be the constant from <Ref>. During the time interval [τβ,τβ+T] the initial infected particle x_0 collides with at least C_1λ_0ℓ^1/3/2 different particles from Υ that are in the supercube Q^**=∏_j=1^d[(i_j-η)ℓ,(i_j+η+1)ℓ] at time τβ+T.
		
  F_3: Out of the C_1λ_0ℓ^1/3/2 or more particles from F_2, at least one of them is in the cube ∏_j=1^d[(i_j+k_j)ℓ,(i_j+k_j+1)ℓ] at time (τ+1)β, for all k=(k_1,…,k_d) for which ∏_j=1^d[(i_j+k_j)ℓ,(i_j+k_j+1)ℓ]⊂ Q^**.
	
	By definition of the events, we clearly have that ℙ[E_st(i,τ)]≥ℙ[F_1∩ F_2∩ F_3].

Using <Ref> we have
	
    ℙ[F_1]≥ 1-C_2exp{-C_3ℓ^2/T}=1-C_2exp{-C_3ℓ^1/3}

	for some positive constants C_2 and C_3. We observe that F_1 is restricted to the super cube ∏_j=1^d[(i_j-η)ℓ,(i_j+η+1)ℓ] and the time interval [τβ,τβ+T].

	For the event F_2, we apply <Ref> to get that the intensity of the Poisson point process of particles that are in Q^** at time τβ and collide with x_0 during [τβ,τβ+T] is at least λ_0 C_1ℓ^1/3 for some positive constant C_1. Since every particle that collides with x_0 enters ∏_j=1^d[(i_j-η+1)ℓ,(i_j+η)ℓ] during [τβ,τβ+T], we can use <Ref> to bound the probability that the particle is inside of Q^** at time τβ+T by
	
    1-C_aexp{-C_bℓ^2/T}=1-C_aexp{-C_bℓ^1/3},

	for some positive constants C_a and C_b. This term can be made as close to 1 as possible by having ℓ sufficiently large. We assume ℓ is large enough so that this term is larger than 2/3. This gives that the intensity of the process of particles from Υ that collided with x_0 during [τβ,τβ+T] and are in Q^** at time τβ+T is at least 
	
    2λ_0 C_1ℓ^1/3/3.

	Using Chernoff's bound (see <Ref>) we have that
	
    ℙ[F_2]≥ 1-exp{-(2/3)^2C_1λ_0ℓ^1/3}.

	Note that, by construction, F_2 is restricted to the super cube Q^** and the time interval [τβ,τβ+T]. Furthermore, F_2 is clearly an increasing event. 
	
	We now turn to F_3. Using <Ref>, and a uniform bound across the number of cubes inside a super cube, we have that 
	
    ℙ[F_3]≥ 1-(2η+1)^dexp{-C_1λ_0ℓ^1/3/2c_p},

	where c_p is a small but positive constant. Again, the event is restricted to the super cube Q^** and the time interval [τβ+T,(τ+1)β] and is an increasing event. Taking the product of the probability bounds in (<ref>), (<ref>) and (<ref>), we see that the probability that E_st(i,τ) holds is at least
	
    1-	exp{-Cλ_0ℓ^1/3}

	for some constant C and all large enough ℓ.



	We start by using <Ref>. Set η∈ℕ such that η≥ d and set ϵ=1/2. Fix the ratio β/ℓ^2 small enough so that the lower bound for w is at most 2η+1, and then set w=2η+1.
	Assume ℓ is large enough so that <Ref> holds. 

	For each (i,τ)∈ℤ^d+1, define E_st(i,τ) as in <Ref>. This event is increasing in the number of particles, is restricted to the super cube i and time interval [τβ,(τ+1)β], and satisfies
	
    ℙ[E_st(i,τ)]≥ 1-exp{-Cλ_0ℓ^1/3},

	for some constant C. Hence, letting λ/2 stand for the measure λ/2(x)=λ_0μ_x/2, we have
	
    log(1/1-ν_E_st(λ2,Q_(2η+1)ℓ,Q_(2η+1)ℓ,ηβ))≥ Cλ_0ℓ^1/3,

	which increases with ℓ, as does the term ϵ^2λ_0ℓ^d in the condition of <Ref>.
	Thus, setting ℓ large enough, we apply <Ref> which gives the existence of a two-sided Lipschitz surface F, on which the event E_st(i,τ) holds. We also get that the surface is almost surely finite and that it surrounds the origin.
	
	We now proceed to argue that the existence of the surface F implies that the infection spreads with positive speed.
	Since the two-sided Lipschitz surface F is finite and surrounds the origin, we have that in almost surely finite time, an infected particle started from the origin will enter some cube ∏_j=1^d[i_jℓ,(i_j+1)ℓ] for which (i,τ) is in F. We call this the central cube of (i,τ). Once that holds, the starting assumption of E_st(i,τ) from <Ref> is satisfied for the super cell (i,τ), and the event E_st(i,τ) holds. By the definition of E_st(i,τ) this means that the initial infected particle for the super cell (i,τ) infects a large number of other particles, which spread the infection to the central cube of (i',τ+1) for all i'∈ℤ^d such that i'-i_∞≤η.
	
	Let (b,h) be the base-height index of the cell (i,τ)∈ F. Recall that h is one of the spatial dimensions. We will also select one of the d-1 spatial dimensions from b and denote it b_1. Let b'∈ℤ^d be obtained from b by increasing the time dimension from τ to τ+1, and by increasing the chosen spatial dimension from b_1 to b_1+1. Since b-b'_1=2, we can choose h'∈ℤ such that (b',h')∈ F and |h-h'|≤ 2, where the latter holds by the Lipschitz property of F. Therefore, there must exists i'∈ℤ^d such that (i',τ+1) is the space-time super cell corresponding to (b',h') and i-i'_∞≤ 1. Hence, at time (τ+1)β, there is an infected particle in the central cube of the super cell i'.
	
	We can then recursively repeat this procedure for the super cell (i',τ+1), since E_st(i',τ+1) holds. Repeating this process we obtain that the infection spreads by a distance of at least ℓ in time β in the chosen spatial direction. Consequently
	
    lim inf_t→∞I_t_1/t>0  almost surely.



In order to prove <Ref>, we can follow the same steps as in the proof of <Ref> with the additional consideration that we have to ensure that the relevant infected particles do not recover too quickly. For that, we will require that all the particles involved do not recover for at least β.


	Recall the definition of Υ and ρ from <Ref> and of E_st(i,τ) from <Ref>. Let E_st'(i,τ) be the event that E_st(i,τ) holds, and that the particles in Υ and the initial infected particle whose path is ρ do not recover during [τβ,(τ+1)β]. Since each such particle does not recover during [τβ,(τ+1)β] with probability exp{-γβ}, for <Ref> we consider that for each x∈ Q^*∖ρ(τβ) the number of particles at x at time τβ that do not recover during [τβ, (τ+1)β] is a Poisson random variable of intensity λ_0/2μ_xexp{-λβ}. Thus,
	 once η, β and ℓ are fixed, setting γ small enough gives that E'_st(i,τ) holds with probability at least 
	
    1-(1-exp{-γβ})-exp{-Cλ_0exp{-γβ}ℓ^1/3}

	for some positive constant C, where the term inside the parenthesis accounts of the probability that the initial infected particles recovers during [τβ,(τ+1)β].
	We now follow the same steps as in the proof of <Ref> to get that the two-sided Lipschitz surface F on which the increasing event E'_st(i,τ) holds exists, is finite and surrounds the origin almost surely. This gives that an initially infected particle that is at the origin at time 0 has a strictly positive probability of surviving long enough to enter a cell of the two-sided Lipschitz surface. Once on the surface, the infection survives indefinitely by the definition of E'_st(i,τ). Hence
	
    ℙ[I_t_1≥ c_1t for all t≥0]≥ c_2.





§ APPENDIX: STANDARD LARGE DEVIATION RESULTS


Let P be a Poisson random variable with mean λ. Then, for any 0<ϵ<1,

    ℙ[P<(1-ϵ)λ] < exp{-λϵ^2/2}

and

    ℙ[P > (1 + ϵ)λ] < exp{-λϵ^2/4}.



plaintocsectionReferences

