Sharp threshold for the ballisticity of the random walk on the exclusion process
Guillaume Conchon--Kerjan Daniel Kious Pierre-François Rodriguez

empty
Target Detection in Sea Clutter with Application to Spaceborne SAR Imaging 



    Shahrokh Hamidi

Department of Electrical and Computer Engineering

University of Waterloo

Waterloo, Ontario, Canada 

shahrokh.hamidi@uwaterloo.ca

    September 9, 2024
=========================================================================================================================================================







Guillaume Conchon-Kerjan^1, Daniel Kious^2 and Pierre-François Rodriguez^3 






§ ABSTRACT 
We study a non-reversible random walk advected by the symmetric simple exclusion process, so that the walk has a local drift of opposite sign when sitting atop an occupied or an empty site. We prove that the back-tracking probability of the walk exhibits a sharp transition as the density ρ of particles in the underlying exclusion process varies across a critical density ρ_c. Our results imply that the speed v=v(ρ) of the walk is a strictly monotone function and that the zero-speed regime is either absent or collapses to a single point, ρ_c, thus solving a conjecture of <cit.>.  The proof proceeds by exhibiting a quantitative monotonicity result for the speed of a truncated model, in which the environment is renewed after a finite time horizon L. The truncation parameter L is subsequently pitted against the density ρ to carry estimates over to the full model. Our strategy is somewhat reminiscent of certain techniques recently used to prove sharpness results in percolation problems. A key instrument is a combination of renormalisation arguments with refined couplings of environments at slightly different densities, which we develop in this article. Our results hold in fact in greater generality and apply to a class of environments with possibly egregious features, outside perturbative regimes. 









5cm0.4pt September 2024 

2

^1King's College London

Department of Mathematics

London WC2R 2LS

United Kingdom

<guillaume.conchon-kerjan@kcl.ac.uk>





^2University of Bath

Department of Mathematical Sciences 

Bath BA2 7AY 

United Kingdom

<daniel.kious@bath.ac.uk>





empty
^3Imperial College London

Department of Mathematics

London SW7 2AZ 

United Kingdom

<p.rodriguez@imperial.ac.uk> 












§ INTRODUCTION


Transport in random media has been an active field of research for over fifty years but many basic questions remain mathematically very challenging unless the medium satisfies specific (and often rather restrictive) structural assumptions; see for instance <cit.> and references therein. In this article we consider the problem of ballistic behavior in a benchmark setting that is both i) non-reversible, and ii) non-perturbative (in the parameters of the model). To get a sense of the difficulty these combined features entail, general results in case i) are already hard to come by in perturbative regimes, see, e.g., <cit.> regarding the problem of diffusive behavior.

Our focus is on a certain random walk in dynamic random environment, which lies outside of the well-studied `classes' and has attracted increasing attention in the last decade, see for instance <cit.> and references below. The interest in this model stems in no small part from the nature of the environment, which is driven by a particle system (e.g. the exclusion process)  that is typically conservative and exhibits slow mixing. Even in the (1+1)-dimensional case, unless one restricts its parameters to perturbative regimes, the features of the model preclude the use of virtually all 
classical techniques: owing to the dynamics of the environment, the model is genuinely non-reversible, and its properties make the search for an invariant measure of the environment as seen by the walker (in the spirit of <cit.>) inaccessible by current methods; see Section <ref> for a more thorough discussion of these and related matters.  

The model we study depends on a parameter ρ governing the density of particles in the environment, which in turn affects the walk, whose transition probabilities depend on whether the walk sits on top of a particle (advection occurs) or not. This may (or not) induce ballistic behaviour. Our aim in this article is to prove that ballisticity is a property of the walk undergoing a `sharp transition' as ρ varies, which is an inherently non-perturbative result. Our results answer a number of conjectures of the past fifteen years, and stand in stark contrast with (i.i.d.) static environments <cit.>, where the zero-speed regime is typically extended. The sharpness terminology is borrowed from critical phenomena, and the analogy runs deep, as will become apparent. Drawing inspiration from it is one of the cornerstones of the present work. 
 
  


 §.§ Main results




We present our main results with minimal formalism in the model case where the environment is the (simple) symmetric exclusion process, abbreviated (S)SEP in the sequel, and refer to Sections <ref> and <ref> for full definitions. We will in fact prove more general versions of these results, see Theorem <ref>, which hold under rather broad assumptions on the environment, satisfied for instance by the SEP. Another environment of interest that fulfils these conditions is discussed in  Appendix <ref>, and is built using a Poisson system of particles performing independent simple random walks (PCRW, short for Poisson Cloud of Random Walks).


The SEP is the continuous-time Markov process η=(η_t)_t≥ 0 taking values in {0,1}^ and describing the simultaneous evolution of continuous-time simple random walks subject to the exclusion rule. That is, for a given realization of η_0, one puts a particle at those sites x such that η_0(x)=1. Each particle then attempts to move at a given rate ν >0, independently of its previous moves and of the other particles, to one of its two neighbours chosen with equal probability. The move happens if and only if the target site is currently unoccupied; see Section <ref> for precise definitions. For the purposes of this article, one could simply set ν=1. We have kept the dependence on ν explicit in anticipation of future applications, for which one may wish to slow down/speed up the environment over time.

On top of the SEP η, a random walk X=(X_n)_n ≥ 0 starting from X_0=0 moves randomly as follows. Fixing two parameters p_∙,p_∘∈ (0,1) such that p_∙ >p_∘, the process X moves at integer times to a neighbouring site, the right site being chosen with probability p_∙, resp. p_∘, depending on whether X is currently located on an occupied or empty site. Formally, given a realization η of the SEP, and for all n≥ 1, 

    X_n+1-X_n= 
    +1,     with prob. p_∙1_η_n(X_n)=1+p_∘1_η_n(X_n)=0
    
    -1,     with prob. (1-p_∙)1_η_n(X_n)=1+(1-p_∘)1_η_n(X_n)=1

(notice that the transition probabilities depend on η since p_∘≠ p_∙ by assumption). For ρ∈ (0,1) we denote by ^ρ the annealed (i.e. averaged over all sources of randomness; see Section <ref> for details) law of (η,X)
whereby η_0 is sampled according to a product Bernoulli measure ((1-ρ)δ_0 + ρδ_1)^⊗, with δ_x a Dirac measure at x, which is an invariant measure for the SEP, see Lemma <ref>. Incidentally, one can check that except for the trivial cases ρ∈{0,1}, none of the invariant measures for the SEP (cf. <cit.>) is invariant for the environment viewed from the walker (to see this, one can for instance consider the probability that the origin and one of its neighbours are both occupied).   In writing ^ρ, we leave the dependence on ν,p_∙ and p_∘ implicit, which are regarded as fixed, and we will focus on the dependence of quantities on ρ, the main parameter of interest. For a mental picture, the reader is invited to think of X as evolving in a half-plane, with space being horizontal and time running upwards. All figures below will follow this convention.

We now describe our main results, using a language that will make analogies to critical phenomena apparent. Our first main result is simplest to formulate in terms of the fast-tracking probability, defined for n≥0 and ρ∈ (0,1) as

    θ_n(ρ)= ^ρ( H_n < H_-1 ),

where H_k= inf{ n ≥ 0: X_n =k }. In words θ_n(ρ) is the probability that X visits n before -1. Analogous results can be proved for a corresponding back-tracking probability, involving the event {H_-n< H_1 } instead; see the end of Section <ref> for more on this. The events in (<ref>) being decreasing in n, the following limit

    θ(ρ)def.=lim_n θ_n(ρ)

 is well-defined and constitutes an order parameter (in the parlance of statistical physics) for the
model. Indeed, it is not difficult to see from (<ref>)
and monotonicity properties of the environment (see  (<ref>) in Section <ref> and Lemma <ref>), that the functions θ_n(·), n ≥ 0, and hence θ(·) are non-decreasing, i.e. that θ(ρ) ≤θ(ρ') whenever ρ≤ρ'. One thus naturally associates to the function θ(·) a corresponding critical threshold

    ρ_c def.=sup{ρ∈ [0,1]: θ(ρ)=0 }.

The transition from the subcritical (ρ < ρ_c) to the supercritical (ρ > ρ_c) regime corresponds to the onset of a phase where the walk has a positive chance to escape to the right. In fact it will do so at linear speed, as will follow from our second main result. To begin with, in view of (<ref>) one naturally aims to quantify the behavior of θ_n(ρ) for large n. Our first theorem exhibits a sharp transition for its decay.




For all ρ∈(0,1), there exist constants c_1,c_2 ∈ (0,∞) depending on ρ such that, with ρ_c as in (<ref>) and for all n≥1,


  (i) θ_n(ρ) ≤ c_1 exp(-(log n)^3/2), if ρ<ρ_c;

  (ii) θ_n(ρ) ≥ c_2, if ρ>ρ_c.



The proof of Theorem <ref> appears at the end of Section <ref>.
Since θ = inf_n θ_n, item (ii) is an immediate consequence of (<ref>). The crux of Theorem <ref> is therefore to exhibit the rapid decay of item (i) in the full subcritical regime, and not just perturbatively in ρ≪ 1, which is the status quo, cf. Section <ref>. In the context of critical phenomena, this is the famed question of (subcritical) sharpness, see for instance <cit.> for sample results of this kind in the context of Ising and Bernoulli percolation models. Plausibly, the true order of decay in item (i) is in fact exponential in n (for instance, a more intricate renormalisation following <cit.> should already provide a stretched-exponential bound in n). We will not delve further into this question in the present article.


Our approach to proving Theorem <ref> is loosely inspired by the recent sharpness results <cit.> and <cit.> concerning percolation of the Gaussian free field and the vacant set of random interlacements, respectively, which both exhibit long-range dependence (somewhat akin to the SEP). Our model is nonetheless very different, and our proof strategy, outlined below in Section <ref>, vastly differs from these works. In particular, it does not rely on differential formulas (in ρ), nor does it involve the OSSS inequality or sharp threshold techniques, which have all proved useful in the context of percolation, see e.g. <cit.>. One similarity with <cit.>, and to some extent also with <cit.> (in the present context though, stochastic domination results may well be too much to ask for), is our extensive use of couplings. Developing these couplings represents one of the most challenging technical aspects of our work; we return to this in Section <ref>. It is also interesting to note that, as with statistical physics models, the regime ρ≈ρ_c near and at the critical density encompasses a host of very natural (and mostly open) questions that seem difficult to answer and point towards interesting phenomena; see Section <ref> and Corollary <ref> for more on this.




Our second main result concerns the asymptotic speed of the random walk, and addresses an open problem of <cit.> which inspired our work. In <cit.>, the authors prove the existence of a deterministic non-decreasing function v:(0,1) → such that, for all ρ∈ (0,1)∖{ρ_-, ρ_+ },
 
    ^ρ-a.s., X_n/n→ v(ρ)  as  n →∞,

where 

    ρ_-def.=sup{ρ : v(ρ) < 0 },
       ρ_+def.=inf{ρ : v(ρ) > 0 },

leaving open whether ρ_+>ρ_- or not, and with it the possible existence of an extended (critical) zero-speed regime. Our second main result yields the strict monotonicity of v(·) and provides the answer to this question. Recall that our results hold for any choice of the parameters 0<p_∘ <p_∙ <1 and ν>0.

  
With ρ_c as defined in (<ref>), one has

    ρ_- = ρ_+ = ρ_c.

Moreover, for every ρ,ρ'∈ (0,1) such that ρ >ρ', one has

    v(ρ)>v(ρ').


The proof of Theorem <ref> is given in Section <ref> below. It will follow from a more general result, Theorem <ref>, which applies to a class of environments η satisfying certain natural conditions. These will be shown to hold when η is the SEP. 

Let us now briefly relate Theorems <ref> and <ref>. Loosely speaking, Theorem <ref> indicates that v(ρ) >0 whenever ρ> ρ_c, whence ρ_+ ≤ρ_c in view of (<ref>), which is morally half of Theorem <ref>. One can in fact derive a result akin to Theorem <ref>, but concerning the order parameter θ̂(ρ)= lim_n ^ρ( H_-n < H_1 ) associated to the back-tracking probability instead. Defining ρ̂_c in the same way as (<ref>) but with θ̂ in place of θ, our results imply that ρ̂_c=ρ_c and that the transition for the back-tracking probability has similar sharpness features as in Theorem <ref>, but in opposite directions –
 the sub-critical regime is now for ρ>ρ̂_c(=ρ_c). Intuitively, this corresponds to the other inequality ρ_- ≥ρ_c, which together with ρ_+ ≤ρ_c, yields (<ref>). 
 
Finally, Theorem <ref> implies that v(ρ)≠ 0 whenever ρ≠ρ_c. Determining whether a law of large number holds at ρ=ρ_c holds or not, let alone whether the limiting speed v(ρ_c) vanishes when 0< ρ_c< 1, is in general a difficult question, to which we hope to return elsewhere; we discuss this and related matters in more detail below in Section <ref>. 

One noticeable exception occurs in the presence of additional symmetry, as we now explain. In <cit.> the authors could prove that, at the `self-dual' point p_∙=1-p_∘ (for any given value of p_∙∈ (1/2,1)), one has v(1/2)=0 and the law of large numbers holds with limit speed 0, but they could not prove that v was non-zero for ρ≠ 1/2, or equivalently that ρ_+=ρ_-=1/2. Notice that the value p_∙=1-p_∘ is special, since in this case (cf. (<ref>)) X has the same law under ^ρ as -X under ^1-ρ, and in particular Xlaw=-X when ρ=1/2. In the result below, which is an easy consequence of Theorem <ref> and the results of <cit.>, we summarize the situation in the symmetric case. We include the (short) proof here. The following statement is of course reminiscent of a celebrated result of Kesten concerning percolation on the square lattice <cit.>; see also <cit.> in related contexts.


If p_∘=1-p_∙, then 

    ρ_c=12   and  θ(12)=0.

Moreover, under ^1/2, X is recurrent, and the law of large numbers (<ref>) holds with vanishing limiting speed v(1/2)=0.



From the proof of <cit.> (and display (3.26) therein), one knows that v(1/2)=0 and that the law of large numbers holds at ρ=1/2. By Theorem <ref>, see (<ref>) and (<ref>), v is negative on (0,ρ_c) and positive on (ρ_c,1), which implies that ρ_c=1/2. As for the recurrence of X under ^1/2, it follows from the ergodic argument of <cit.> (Corollary 2.2, see also Theorem 3.2 therein; these results are stated for a random walk jumping at exponential times but are easily adapted to our case). Since θ(ρ) ≤^ρ(lim inf X_n ≥ 0) in view of (<ref>), recurrence implies that θ(1/2)=0, and (<ref>) follows. 



 
 
 









 §.§ Discussion


We now place the above results in broader context and contrast our findings with existing results. We then discuss a few open questions in relation with Theorems <ref> and <ref>.



  §.§.§ Related works


Random walks in dynamic random environments have attracted increasing attention in the past two decades, both in statistical physics - as a way to model a particle advected by a fluid <cit.>, and in probability theory - where they provide a counterpart to the more classically studied random walks in static environments <cit.>.


On ℤ, the static setting already features a remarkably rich phenomenology, such as transience with zero speed <cit.>, owing to traps that delay the random walk, and anomalous fluctuations <cit.> - which can be as small as polylogarithmic in the recurrent case <cit.>. On ℤ^d for d≥ 2, some fundamental questions are still open in spite of decades of efforts, for instance the conjectures around Sznitman's Condition (T) and related effective ballisticity criteria <cit.>, and the possibility that, for a uniformly elliptic environment, directional transience is equivalent to ballisticity. If true, these conjectures would have profound structural consequences, in essentially ascertaining that the above trapping phenomena can only be witnessed in dimension one. As with the model studied in this article, a circumstance that seriously hinders progress is the truly non-reversible character of these problems. This severely limits the tools available to tackle them.


New challenges arise when the environment is dynamic, requiring new techniques to handle the fact that correlations between transition probabilities are affected by time. In particular, the trapping mechanisms identified in the static case do not hold anymore and it is difficult to understand if they simply dissolve or if they are replaced by different, possibly more complex, trapping mechanisms. As of today, how the static and dynamic worlds relate is still far from  understood. Under some specific conditions however, laws of large numbers (and sometimes central limit theorems) have been proved in dynamic contexts: when the environment has sufficiently good mixing properties <cit.>, a spectral gap <cit.>, or when one can show the existence of an invariant measure for the environment as seen by the walk (<cit.>, again under some specific mixing conditions). One notable instance of such an environment is the supercritical contact process (see <cit.>, or <cit.> for a recent generalization).
We also refer to <cit.> for recent results in the time-dependent reversible case, for which the assumptions on the environment can be substantially weakened.

The environments we consider are archetypal examples that do not satisfy any of the above conditions. In the model case of the environment driven by the SEP, the mixing time over a closed segment or a circle is  super-linear (even slightly super-quadratic <cit.>), creating a number of difficulties, e.g. barring the option of directly building a renewal structure without having to make further assumptions (see <cit.> in the simpler non-nestling case). The fact that the systems may be conservative (as is the case for the SEP) further hampers their mixing properties. As such, they have been the subject of much attention in the past decade, see <cit.> among many others. All of these results are of two types: either they require particular assumptions, or they apply to some perturbative regime of parameters, e.g. high density of particles <cit.>, strong drift, or high/low activity rate of the environment <cit.>.

Recently, building on this series of work, a relatively comprehensive result on the Law of Large Numbers (LLN) in dimension 1+1 has been proved in <cit.>, see (<ref>) above, opening an avenue to some fundamental questions that had previously remained out of reach, such as the possible existence of transient regime with zero speed. Indeed, cf. (<ref>) and (<ref>), the results of <cit.> leave open the possibility of having an extended `critical' interval of ρ's for which v(ρ)=0, which is now precluded as part of our main results, see (<ref>). We seek the opportunity to stress that our strategy, outlined below in Section <ref>, is completely new and  rather robust, and we believe a similar approach will lead to progress on related questions for other models.




  §.§.§ Open questions





1) Existence and value of v(ρ_c). Returning to Theorems <ref> and <ref>, let us start by mentioning that ρ_c, defined by (<ref>) and equivalently characterized via (<ref>)-(<ref>), may in fact be degenerate (i.e. equal to 0 or 1) if v(·) stays of constant sign. It is plausible that ρ_c∈(0,1) if and only if
p_∘<1/2<p_∙, which corresponds to the (more challenging) nestling case, in which 
the walk has a drift of opposite signs depending on whether it sits on top of a particle or an empty site. Moreover, the function v(·), as given by <cit.>, is well-defined for all values of ρ∈(0,1) (this includes a candidate velocity at ρ_c), but whether a LLN holds at ρ_c with speed v(ρ_c) or the value of the latter is unknown in general, except in cases where one knows that v(ρ_c)=0 by other means (e.g. symmetry), in which case a LLN can be proved, see <cit.>. When ρ_c is non-degenerate, given Theorem <ref>, it is natural to expect that v(ρ_c)=0, but this is not obvious as we do not presently know if v is continuous at ρ_c. It is relatively easy to believe that continuity on (0,1)∖{ρ_c}, when the speed is non-zero, can be obtained through an adaptation of the regeneration structure defined in <cit.>, but continuity at ρ_c (even in the symmetric case) seems to be more challenging.

Suppose now that one can prove that a law of large numbers holds with vanishing speed at ρ=ρ_c, then one can ask whether X is recurrent or transient at ρ_c. A case in point where one knows the answer is the `self-dual' point p_∘=1-p_∙ where the critical density equals 1/2 and the walk is recurrent. In particular, this result and Theorem <ref> imply that v(ρ) is zero if and only if ρ=1/2, and thus there exists no transient regime with zero-speed in the symmetric case. This also answers positively the conjecture in <cit.> (end of Section 1.4), which states that in the symmetric case, the only density with zero speed is in fact recurrent. 




2) Regularity of v(·) near ρ_c and fluctuations at ρ_c.
In cases where v(ρ_c)=0 is proved, one may further wonder about the regularity of ρ↦ v(ρ) around ρ_c (and similarly of θ(ρ) as ρ↓ρ_c). Is it continuous, and if yes, is it Hölder-continous, or even differentiable? This could be linked to the fluctuations of the random walk when ρ=ρ_c, in the spirit of Einstein's relation, see for instance <cit.> in the context of reversible dynamics. Whether the fluctuations of X under ^ρ_c are actually diffusive, super-diffusive or sub-diffusive is a particularly difficult question. It has so far been the subject of various conjectures, both for the RWdRE (e.g. Conjecture 3.5 in <cit.>) and very closely related models in statistical physics (e.g. <cit.>, <cit.>, <cit.>). One aspect making predictions especially difficult is that the answer may well depend on all parameters involved, i.e. ρ, p_∘ and p_∙. At present, any rigorous upper or lower bound on the fluctuations at ρ=ρ_c would be a significant advance.






3) Comparison with the static setting.
In the past decade, there have been many questions as to which features of a static environment (when ν=0, so that the particles do not move) are common to the dynamic environment, and which are different. In particular, it is well-known that in the static case, there exists a non-trivial interval of densities for which the random walker has zero speed, due to mesoscopic traps that the random walker has to cross on its way to infinity (see for instance <cit.>, and above references). It was conjectured that if ν>0 is small enough, there could be such an interval in the dynamic set-up, see <cit.>. Theorem <ref> thus disproves this conjecture. 

Combined with the CLT from <cit.>, which is valid outside of (ρ_-,ρ_+), hence for all ρ≠ρ_c by Theorem <ref>, this also rules out the possibility of non-diffusive fluctuations for any ρ≠ρ_c, which were conjectured in <cit.>.  In light of this, one may naturally wonder how much one has to slow down the environment with time (one would have to choose ν=ν_t a suitably decreasing function of the time t) in order to start seeing effects from the static world. We plan to investigate this in future work.  










 §.§ Overview of the proof
 

We give here a relatively thorough overview of the proof, intended to help the reader navigate the upcoming sections. For concreteness, we focus on Theorem <ref> (see below its statement as to how Theorem <ref> relates to it), and specifically on the equalities (<ref>), in the case of SEP (although our results are more general; see Section <ref>). The assertion (<ref>) is somewhat reminiscent of the chain of equalities u̅=u_*=u_** associated to the phase transition of random interlacements that was recently proved in <cit.>, and draws loose inspiration from the interpolation technique of <cit.>, see also <cit.>. Similarly to <cit.> in the context of interlacements, and as is seemingly often the case in situations lacking key structural features (in the present case, a notion of reversibility or more generally self-adjointness, cf. <cit.>), our methods rely extensively on the use of couplings. 



The proof essentially consists of two parts, which we detail individually below. In the first part, we compare our model with a finite-range version, in which we fully re-sample the environment at times multiple of some large integer parameter L (see e.g. <cit.> for a similar truncation to tame the long-range dependence). One obtains easily that for any L and any density ρ∈ (0,1), the random walk in this environment satisfies a strong Law of Large Numbers with some speed v_L(ρ) (Lemma <ref>), and we show that in fact, 

    v_L(ρ-ε_L)-δ_L≤ v(ρ)≤ v_L(ρ+ε_L) +δ_L,

 for some δ_L, ε_L that are quantitative and satisfy δ_L, ε_L  =o_L(1) as L →∞ (see Proposition <ref>). 


In the second part, we show that for any fixed ρ,ρ+ε∈ (0,1), we have 

    v_L(ρ+ε) > v_L(ρ)+3δ_L,

 for L large enough (Proposition <ref>). Together, (<ref>) and (<ref>) readily imply that v(ρ+ε)>v(ρ), and (<ref>) follows. Let us now give more details. 




First part: from infinite to finite range. For a density ρ∈ (0,1) the environment η of the range-L model is the SEP starting from η_0∼Ber(ρ)^⊗ during the time interval [0,L). Then for every integer k ≥1, at time kL we sample η_kL again as Ber(ρ)^⊗, independently from the past, and let it evolve as the SEP during the interval [kL,(k+1)L). The random walk X on this environment is still defined formally as in (<ref>), and we denote ^ρ,L the associated annealed probability measure. Clearly, the increments (X_kL-X_(k-1)L)_k≥ 1 are i.i.d. (and bounded), so that by the strong LLN, X_n/n→ v_L(ρ) :=𝔼^ρ[X_L/L], a.s. as n→∞. 

Now, to relate this to our original 'infinite-range' (L=∞) model, the main idea is to compare the range-L with the range-2L, and more generally the range-2^kL with the range-2^k+1L model for all k ≥ 0 via successive couplings. The key is to prove a chain of inequalities of the kind

    v_L(ρ)≤ v_2L(ρ+ε_1,L)+δ_1,L≤…≤  v_2^kL(ρ+ε_k,L)+δ_k,L≤…,

where the sequences (ε_k,L)_k≥ 1 of and (δ_k,L)_k≥ 1 are increasing, with ε_L:=lim_k→∞ε_k,L=o_L(1) and δ_L:=lim_k→∞δ_k,L=o_L(1). In other words, we manage to pass from a scale 2^kL to a larger scale 2^k+1L, at the expense of losing a bit of speed (δ_k+1,L-δ_k,L), and using a little sprinkling in the density (ε_k,L-ε_k-1,L), with δ_0,L= ε_0,L=0. From (<ref>) (and a converse inequality proved in a similar way), standard arguments allow us to deduce (<ref>). 
Let us mention that such a renormalization scheme, which trades scaling against sprinkling in one or several parameters, is by now a standard tool in percolation theory, see for instance <cit.>.


We now describe how we couple the range-L and the range-2L models in order to obtain the first inequality, the other couplings being identical up to a scaling factor. We do this in detail in Lemma <ref>, where for technical purposes, we need in fact more refined estimates than only the first moment, but they follow from this same coupling. The coupling works roughly as follows (cf. Fig. <ref>). We consider two random walks X^(1)law=^ρ,L and X^(2)law=^ρ+ε_L,2L coupled via their respective environments η^(1) and η^(2) such that we retain good control (in a sense explained below) on the relative positions of their respective particles during the time interval [0,2L], except during a short time interval after time L after renewing the particles of η^(1). In some sense, we want to dominate η^(1) by η^(2) `as much as possible', and use it in combination with the following monotonicity property of the walk:  since p_∙ >p_∘, X^(2) cannot be overtaken by X^(1) if η^(2) covers η^(1) (cf. (<ref>); see also Lemma <ref> for a precise formulation). Roughly speaking, we will use this strategy from time 0 to L, then lose control for short time before recovering a domination and using the same argument but with a lateral shift (in space), as illustrated in Figure <ref>.
The key for recovering a domination in as little time as possible is a property of the following flavour. 

    0.8
    Let L,t,ℓ≥ 1 be such that L≫ t^2≫ℓ^4, and let η_0, η'_0 ∈{0,1}^ℤ be such that over [-3L,3L], η_0 (resp. η'_0) has empirical density ρ+ε (resp. ρ) on segments of length ℓ. Then one can couple the time evolutions of η,η' as SEPs during [0,t] such that 
    
        (η_t(x)≥η_t'(x), ∀ x ∈ [-L+ct,L-ct]) ≥ 1-c'tLexp(-c”ε^2 t^1/4),
    
    for some constants c,c',c”>0.

Roughly, for t poly-logarithmic in L the right-hand side of (<ref>) will be as close to 1 as we need. 
We do not give precise requirements on the scales ℓ,t,L (nor a definition of empirical density), except that they must satisfy some minimal power ratio due to the diffusivity of the particles. We will formalize this statement in Section <ref>, see in particular condition <ref>, with exponents and constants that are likely not optimal but sufficient for our purposes. Even if the environment were to mix in super-quadratic (but still polynomial) time, our methods would still apply, up to changing the exponents in our conditions <ref>-<ref>.

The only statistic we control is the empirical density, i.e. the number of particles over intervals of a given length. The relevant control is formalised in Condition <ref>. In particular, our environment couplings have to hold with a quenched initial data, and previous annealed couplings in the literature (see e.g. <cit.>) are not sufficient for this purpose (even after applying the usual annealed-to-quenched tricks), essentially due to the difficulty of controlling the environment around the walker in the second part of the proof, as we explain in Remark <ref>; cf. also <cit.> for related issues in other contexts.


Let us now track the coupling a bit more precisely to witness the quantitative speed loss δ_L incurred by (<ref>). We start by sampling η^(1)_0 and η^(2)_0 such that a.s., η^(1)_0(x)≤η^(2)_0(x) for all x∈ℤ, which is possible by stochastic domination. In plain terms, wherever there is a particle of η^(1), there is one of η^(2). Then, we can let η^(1) and η^(2) evolve during [0,L] such that this domination is deterministically preserved over time (this feature is common to numerous particle systems,  including both SSEP and the PCRW). As mentioned above, conditionally on such a realization of the environments, one can then couple X^(1) and X^(2) such that X^(2)_s≥ X^(1)_s for all s∈ [0,L]. The intuition for this is that 'at worst', X^(1) and X^(2) sit on the same spot, where X^(2) might see a particle and X^(1) an empty site (hence giving a chance for X^(2) to jump to the right, and for X^(1) to the left), but not the other way around (recall to this effect that p_∙ >p_∘).

At time L, we have to renew the particles of η^(1), hence losing track of the domination of η^(1) by η^(2). We intend to recover this domination within a time t:=(log L)^100 by coupling the particles of η^(1)_L with those of η^(2)_L using (<ref>) (at least over a space interval [-3L,3L], that neither X^(1) nor X^(2) can leave during [0,2L]). Since during that time, X^(1) could at worst drift of t steps to the right (and X^(2) make t steps to the left), we couple de facto the shifted configurations η^(1)(·) with η^(2)(· -2t). Hence, we obtain that η^(1)_L+t(x)≤η^(2)_L+t(x -2t) for all x∈ [-3L+ct,3L+ct] with high probability as given by (<ref>). As a result, all the particles of η^(1)_L+t are covered by particles of η^(2)_L+t, when observed from the worst-case positions of X^(1)_L+t and X^(2)_L+t, respectively.

Finally, during [L+t,2L] we proceed similarly as we did during [0,L], coupling η^(1) with η^(2)(· -2t) so as to preserve the domination, and two random walks starting respectively from the rightmost possible position for X^(1)_L+t, and the leftmost possible one for X^(2)_L+t. The gap between X^(1) and X^(2) thus cannot increase, and we get that X^(1)_2L≤ X^(2)_2L+2t, except on a set of very small probability where (<ref>) fails. Dividing by 2L and taking expectations, we get 

    v_L(ρ)≤ v_2L(ρ +ε)+δ, where δ=O((log L)^100L),

for suitable ε > 0. The exponent 100 is somewhat arbitrary, but importantly, owing to the coupling time of the two processes (and the diffusivity of the SEP particles), this method could not work with a value of δ smaller than (log^2L)/L. In particular, the exponent of the logarithm must be larger than one, and this prevents potentially simpler solutions for the second part. 




Second part: quantitative speed increase at finite range. We now sketch the proof of (<ref>), which is a quantitative estimate on the monotonicity of v_L, equivalently stating that for ρ∈ (0,1) and ε∈ (0,1-ρ), 

    𝔼^ρ+ε[X_L]>𝔼^ρ[X_L]+3Lδ_L,

with δ_L explicit and supplied by the first part. This is the most difficult part of the proof, as we have to show that a denser environment actually yields a positive gain for the displacement of the random walk, and not just to limit the loss as in the first part. The main issue when adding an extra density ε of particles is that whenever X is on top of one such particle, and supposedly makes a step to the right instead of one to the left, it could soon after be on top of an empty site that would drive it to the left, and cancel its previous gain. 


We design a strategy to get around this and preserve gaps, illustrated in Figure <ref> (cf. also Figure <ref> for the full picture, which is more involved). When coupling two walks X^ρlaw=^ρ, X^ρ+εlaw=^ρ+ε with respective environments η^ρ, η^ρ+ε, our strategy is to spot times when i) X^ρ+ε sees an extra particle (that we call sprinkler) and jumps to the right, while X^ρ sees an empty site and jumps to the left, and ii) this gap is extended with X^ρ then drifting to the left and X^ρ+ε drifting to the right, for some time t that must necessarily satisfy t  ≪log L – so that this has a chance of happening often during the time interval [0,L]. 


Once such a gap is created, on a time interval say [s_1,s_2] with s_2-s_1=t, we attempt to recouple the environments η^ρ, η^ρ+ε around the respective positions of their walker, so that the local environment seen from X^ρ+ε again dominates the environment seen from X^ρ, 
which then allows us to preserve the gap previously created, up to some time T which is a polynomial in log L. As we will explain shortly, this gap arises with not too small a probability, so that repeating the same procedure between times iT and (i+1)T (for i≤ L/T-1) will provide us with the discrepancy  3δ_L needed.

The re-coupling of the environments mentioned in the previous paragraph must happen in time less than O(log L) (in fact less than t), in order to preserve the gap previously created. This leads to two difficulties:


  * in such a short time, we cannot possibly recouple the two environments over a space interval of size comparable to L (≈ the space horizon the walk can explore during [0,L]), and

  * the coupling will have a probability ≫ L^-1 to fail, hence with high probability, this will actually happen during [0,L]! In this case, we lose track of the domination of the environments completely, hence it could even be possible that X^ρ overtakes X^ρ+ε. 

We handle the first of these difficulties with a two-step surgery coupling: 



  1) (Small coupling). We perform a first coupling of η^ρ and η^ρ+ε on an interval of stretched exponential width (think exp(t^1/2) for instance) during a time s_3-s_2=t/2 (cf. the orange region in Fig. <ref>), so as to preserve at least half of the gap created. We call this coupling “small” because t is small (compared to L). If that coupling is successful, X^ρ+ε now sees an environment that strictly covers the one seen by X^ρ, on a spatial interval I of width ≍exp(t^1/2) ≫ t. Due to the length of I, this domination extends in time, on an interval [s_3,T] of duration say t^200 (it could even be extended to timescales ≍exp(t^1/2)): it could only be broken by SEP particles of η^ρ_s_3 lying outside of I, who travel all the distance  to meet the two walkers, but there is a large deviation control on the drift of SEP particles. The space-time zone in which the environment as seen from X^ρ+ε dominates that from X^ρ is the green trapezoid depicted in Figure <ref>. 


  2) (Surgery coupling). When the coupling in 1) is successful, we use the time interval [s_3,T] to recouple the environments η^ρ and η^ρ+ε on the two outer sides of the trapezoid, on a width of length 10L say, so that η^ρ+ε_T(· +t/2) dominates η^ρ_T(· -t/2) on the entire width, all the while preserving the fact that η^ρ+ε(· +t/2) dominates η^ρ(· -t/2) inside the trapezoid at all times (for simplicity and by monotonicity, we can suppose assume that X^ρ+ε_s_3-X^ρ_s_3 is exactly equal to t, as pictured in Figure <ref>). This step is quite technical, and formulated precisely as Condition <ref> in Section <ref>. It requires that different couplings  can be performed on disjoint contiguous intervals and glued in a `coherent' fashion, whence the name surgery coupling. Again, we will prove this specifically for the SEP in a dedicated section, see Lemma <ref>. Since this second coupling operates on a much longer time interval, we can now ensure its success with overwhelming probability, say 1-O(L^-100). 




We still need to address the difficulty described in the second bullet point above, which corresponds to the situation where the small coupling described at 1) fails. As argued, will happen a number of times within [0,L] because t is small. If this occurs, we lose control of the domination of the environments seen by the two walkers. This leads to:



  3) (Parachute coupling). If the coupling in 1) is unsuccessful, instead of the surgery coupling, we perform a (parachute) coupling of η^ρ and η^ρ+ε  in [s_3,T] so that η^ρ+ε(· -(T-s_3)) covers η^ρ(· +(T-s_3)), as we did in the first part of the proof. This again happens with extremely good probability 1-O(L^-100). The price to pay is that on this event, the two walks may have drifted linearly in the wrong direction during [s_3,T] (see the dashed blue trajectories in Figure <ref>), but we ensure at least that X^ρ+ε_T-X^ρ_T≥ -2(T-s_3), and we have now re-coupled the environments seen from the walkers, hence we are ready to start a new such step during the interval [T,2T], etc. This last point is crucial, as we need to iterate to ensure an expected gain 𝔼^ρ+ε[X_L]-𝔼^ρ[X_L] that is large enough, cf. (<ref>). 
 


We now sketch a back-of-the-envelope calculation to argue that this scheme indeed generates the necessary discrepancy between 𝔼^ρ+ε[X_L] and 𝔼^ρ[X_L]. During an interval of the form [iT,(i+1)T] for i=0, 1,… , ⌊ L/T⌋ -1 (we take i=0 in the subsequent discussion for simplicity), with probability ≃ 1-e^-ct, we do not have the first separating event (around time s_1) between X^ρ+ε and X^ρ, and we simply end up with X^ρ+ε_T - X^ρ_T≥ 0, which is a nonnegative expected gain. 

Else, with probability ≃ e^-ct we have the first separation happening during [s_1,s_2]. On this event, the coupling in 1) (and the subsequent impermeability of the green trapezoid) succeeds with probability ≥ 1- e^-t^1/100, and we end up with X^ρ+ε_T - X^ρ_T≥ t, resulting in an expected gain of order ≃  t. If the first coupling fails, and we resort to the parachute coupling, we have a (negative) expected gain ≃ -2T e^-t^1/100. Multiplying by the probability of the first separation, we obtain a net expected gain ≃ e^-ct(t-2T e^-t^1/100). 

Finally, we evaluate the possibility that the surgery coupling (in step 2) above) or the parachute coupling 3) fails, preventing us to restore the domination of η^ρ(·+X^ρ) by η^ρ+ε(·+X^ρ+ε) at time T, and we do not control anymore the coupling of the walks. This has probability O(L^-100), and in the worst case we have deterministically X^ρ+ε_L-X^ρ_L =-2L, so the expected loss is O(L^-99). 


Putting it all together, we get, for L large enough by choosing e.g. t=√(log L) and T=(log L)^100 (it turns out that our couplings work with this choice of scales), that

    𝔼^ρ+ε[X^ρ+ε_T]-𝔼^ρ[X^ρ_T]≥ e^-ct(t-2T e^-t^1/100)+O(L^-99)≥ L^-o(1)

As long as the surgery coupling or the parachute succeed, we can repeat this coupling for up to ≃ L/T times during [0,L], thus obtaining 

    𝔼^ρ+ε[X^ρ+ε_L]-𝔼^ρ[X^ρ_L]≥ L^1-o(1)/T≥ L^1-o(1),

which establishes (<ref>), with a sizeable margin. 












 §.§ Organization of the paper

In Section <ref>, we give rigorous definitions of general environments with a minimal set of properties (<ref>)-(<ref>), and of the random walk X. 
In Section <ref>, we impose the mild coupling conditions <ref>-<ref> on the environments, state our general result, Theorem <ref>, and deduce Theorems <ref> and <ref> from it. We then define the finite-range models and give a skeleton of the proof. 
In Section <ref>, we proceed to the first part of the proof, and in Section <ref>, we proceed to the second part (cf. Section <ref> reagrding the two parts). In Section <ref>, we define rigorously the SEP and show that it satisfies all the conditions mentioned above. The (short) Appendix <ref> contains a few tail estimates in use throughout this article.
In Appendix <ref>, we introduce the PCRW environment and show that it equally satisfies the above conditions, which entails that our results also apply to this environment. Throughout this article all quantities may implicitly depend on the two parameters  p_∙, p_∘∈ (0,1) that are assumed to satisfy p_∙ >p_∘, cf. above (<ref>) (and also Section <ref>). 







§ SETUP AND USEFUL FACTS


In this section, after introducing a small amount of notation (Section <ref>), we proceed to define in Section <ref> a class of (dynamic) random environments of interest, driven by a Markov process η characterized by properties (<ref>)–(<ref>) below. We will primarily be interested in environments driven by the exclusion process, which is introduced in Section <ref> and shown to satisfy these properties. The framework developed in Section <ref> and further in Section <ref> will allow our results to apply directly to a second environment of interest, considered in Appendix <ref>. We conclude by introducing in Section <ref> the relevant walk in random environment along with its associated quenched and annealed laws and collect a few basic features of this setup. 





 §.§ Notation
  

We write ℤ_+, resp. ℝ_+, for the set of nonnegative integers, resp. real numbers. We use the letter z ∈×_+ exclusively to denote space-time points z=(x,t), and typically x,y, x', y' … for spatial coordinates and s,t,s',t',… for time coordinates. We usually use m,n, … for non-negative integers. 
 With a slight abuse of notation, for two integers a≤ b, we will denote by [a,b] the set of integers {a,…, b} and declare that the length of [a,b] is |{a,…, b}| =b-a+1. Throughout, c,c',… and C,C',… denote generic constants in (0,∞) which are purely numerical and can change from place to place. Numbered constants are fixed upon first appearance.





 §.§ A class of dynamic random environments
  
We will consider stationary Markov (jump) processes with values in Σ = (ℤ_+)^ℤ. The state space Σ carries a natural partial order: for two configurations η, η' ∈Σ, we write η≼η' (or η'≽η) if, for all x∈ℤ, η(x)≤η'(x). More generally, for I ⊂ℤ, η|_I≼η'|_I (or η'|_I≽η|_I) means that η(x)≤η'(x) for all x ∈ I.
For a finite subset I⊂ℤ, we use the notation η(I)=∑_x∈ Iη(x). We will denote ≥_st. and ≤_st. the usual stochastic dominations for probability measures. Let J be a (fixed) non-empty open interval of ℝ^+. An environment is specified in terms of two families of probability measures (𝐏^η_0: η_0 ∈Σ) governing the process (η_t)_t ≥ 0 and (μ_ρ : ρ∈ J), where μ_ρ is a measure on Σ, which are required satisfy the following conditions: 

    P.114cm(Markov property and invariance). For every η_0∈Σ, the process (η_t)_t ≥ 0 defined under 𝐏^η_0 is a time-homogeneous Markov process, such that for all s≥ 0 and x∈ℤ, the process (η_s+t(x+·))_t≥ 0 has law 𝐏^η_s(x+·); moreover, the process (η_t)_t ≥ 0 exhibits `axial symmetry' in the sense that (η_t(x-·))_t≥ 0 has law 𝐏^η_0(x-·).


    P.214cm(Stationary measure). The initial distribution μ_ρ is a stationary distribution for the Markov process 𝐏^η_0. More precisely, letting 
        𝐏^ρ= ∫μ_ρ(dη_0) 𝐏^η_0,   ρ∈ J,
     
    the 𝐏^ρ-law of (η_t+s)_t≥0 is identical to the 𝐏^ρ-law of (η_t)_t≥0 for all s≥ 0 and ρ∈ J. In particular, the marginal law of η_t under 𝐏^ρ is μ_ρ for all t ≥ 0. 
    
       P.314cm(Monotonicity).  The following stochastic dominations hold:
    
      i) (quenched) For all η'_0 ≼η_0, one has that 𝐏^η'_0≤_st.𝐏^η_0 , i.e. there exists a coupling of (η'_t)_t ≥0 and (η_t)_t ≥ 0 such that  η'_t≼η_t for all t≥ 0. 
     
      ii) (annealed) For all ρ'≤ρ, one has that μ_ρ'≤_st.μ_ρ. Together with i), this implies that 𝐏^ρ'≤_st.𝐏^ρ.
    
       P.414cm(Density at stationarity). There exists a constant [c]densitydev >0  such that for all ρ∈ J, for all ε∈ (0,1) and every positive integer ℓ, 
    
        𝐏^ρ({η_0∈Σ:  |η_0([0,ℓ-1 ])-ρℓ|≥εℓ})≤ 2exp(-densitydevε^2ℓ).




A prime example satisfying the above conditions is the simple exclusion process, introduced and discussed further in Section <ref>; see in particular Lemma <ref> regarding the validity of properties (<ref>)–(<ref>). We refer to 
Appendix <ref> for another example.








 §.§ Random walk
 

We now introduce the random walk in dynamic environment (RWdRE) that will be the main object of interest in this article.
To this effect, we fix two constants p_∙,p_∘∈ (0,1) such that p_∙>p_∘ and an environment configuration η=(η_t)_t≥ 0 with η_t ∈Σ (= ℤ_+^ℤ, see Section <ref>). 
Given this data, the random walk evolving on top of the environment η is conveniently defined in terms of a family (U_n)_n≥ 0 of i.i.d. uniform random variables on  [0,1], as follows. 
For an initial space-time position z=(x,m)∈ℤ×ℤ_+, let P^η_z be the law of the discrete-time Markov chain X=(X_n)_n≥ 0 such that X_0=x and for all integer n≥0,

    X_n+1=X_n+2×{ U_n≤ (p_∘-p_∙)1{η_n +m
    (X_n)=0 } + p_∙}-1.

Let us call x∈ℤ an occupied site of η_t ∈Σ if η_t(x)>0, and empty otherwise.
With this terminology, (<ref>) implies for instance that when X_n, started at a point z=(x,t=0), is on an occupied (resp. empty) site of η_n,  it jumps to its right neighbour with probability p_∙ (resp. p_∘) and to its left neighbour with probability 1-p_∙ (resp. 1-p_∘). We call P^η_z the quenched law of the walk started at z and abbreviate P^η=P^η_(0,0); here quenched refers to the fact that the environment η is deterministic.


We now discuss annealed measures, i.e. including averages over the dynamics of the environment η. We assume from here on that η=(η_t)_t≥ 0 satisfies the assumptions of Section <ref>. Recall
that 𝐏^η_0 denotes the law of η starting from the configuration η_0 ∈Σ and that 𝐏^ρ is declared in (<ref>). Correspondingly,  one introduces the following two annealed measures for the walk

    ℙ^ρ_z[ ·  ]=∫𝐏^ρ(dη)P^η_z[ ·  ],   ρ∈ J, 
       ℙ^η_0_z[ ·  ]=∫𝐏^η_0(dη)P^η_z[ ·  ],  η_0 ∈Σ,
 
for arbitrary z ∈ℤ×ℤ_+. Whereas the latter 
averages over the dynamics of η for a fixed initial configuration η_0, the former includes η_0, which is sampled from the stationary distribution μ_ρ for η. Observe that
ℙ^ρ_z =  ∫μ_ρ(dη_0) ℙ^η_0_z.  For ⋆∈{η,ρ}, write ^⋆_x for ^⋆_(x,0), for all x∈ℤ, and write simply ^⋆ for ^⋆_0. 



We introduce a joint construction for the walk X when started at different space-time points. This involves a graphical representation using arrows similar to that used in <cit.>, but simpler, which will be sufficient for our purposes. For a point w=(x,n)∈ℤ×ℤ_+, we let π_1(w)=x and π_2(w)=n denote the projection onto the first (spatial) and second (temporal) coordinate. We consider the discrete lattice

    𝕃= (2ℤ× 2ℤ_+) ∪( (1,1)+(2ℤ× 2ℤ_+)).

Note that the process (X_n,n)_n ≥ 0 evolves on the lattice 𝕃⊂ (ℤ×ℤ_+) defined by (<ref>) when X=(X_n)_n ≥ 0 is started at z=(0,0) under any of P_z^η and the measures in (<ref>)-(<ref>).

We proceed to define a family of processes (X^w=(X^w_n)_n ≥ 0 : w∈𝕃), such that X^w_0=π_1(w) almost surely and (X^(0,0)_n)_n ≥ 0 has the same law as X under P_(0,0)^η. Furthermore, X^w' and X^w have the property that they coalesce whenever they intersect, that is if X^w'_m=X^w_n  for some w,w'∈𝕃 and n,m≥0, then X^w'_m+k=X^w_n+k for all k≥0.

Let U= (U_w)_w∈𝕃 be a collection of i.i.d. uniform random variables on [0,1]. Given the environment η, we define a field A=(A_w)_w∈𝕃∈{-1,1}^𝕃 of arrows (see Figure <ref>), measurably in (η,U ) as follows:

    A_w = A(η_n(x), U_w) =2×{ U_w≤ (p_∘-p_∙)1{η_n(x)= 0 } + p_∙}-1,    w=(x,n)∈𝕃.

For any  w=(x,n)∈𝕃, we then set X^w_0=x and, for all integer k ≥0, we define recursively

    X^w_k+1 = X^w_k+A_(X^w_k,    n+k).




This defines the coupled family ((X^w_k)_k ≥ 0: w∈𝕃), and we note that trajectories the process (X_k^w , k+n)_k ≥ 0, where π_2(w)=n, are embedded in (i.e. subsets of) 𝕃. In view of (<ref>) and (<ref>)-(<ref>), it follows plainly that the law of X^(0,0)= (X^(0,0)_n)_n ≥ 0 when averaging over U while keeping η fixed is the same as that of X under P^η_(0,0)= P^η. 
 

We now discuss a variation of the construction specified around (<ref>)-(<ref>), which will be practical in Section <ref>. 


Let η_0∈Σ and suppose that (η,U) are coupled under the probability measure Q, with η having marginal law 𝐏^η_0 and (U_w)_w∈𝕃 a collection of i.i.d. uniform random variables on [0,1], in such a way that under Q, for all integers t ≥ 0,

    (U_w: π_2(w)=t) is independent from ℱ_t,

where

    ℱ_t:=σ ((η_s)_0 ≤ s ≤ t, (U_w: π_2(w)≤ t-1)).

Then, defining X^w= X^w(η,U) as in (<ref>)-(<ref>), it follows that X^(0,0) has law  ℙ^η_0 (cf. (<ref>)) under Q. 



We show by induction over k ≥ 1 integer that for all such k, the pair ((η_t)_0≤ t≤ k-1,(X_t)_0≤ t≤ k) has the same law under both Q and ℙ^η_0 (which, for the duration of the proof, we extend here to denote the joint distribution of (X, η), by a slight abuse of notation). The initialisation at k=1 is immediate, since Q(X_1=1)=p_∙{η_0(0)=1}+p_∘{η_0(0)=0} and η_0 is deterministic. 

As for the induction step, assume the induction hypothesis for some k≥ 1, and condition on the σ- algebra Σ_k:=σ((η_t)_0≤ t≤ k-1,(X_t)_0≤ t≤ k).  We first let η evolve between times k-1 and k. Under both Q and ℙ^η_0 and conditionally on Σ_k, we have that (η_t)_k-1≤ t≤ k is distributed as (η_t)_0≤ t≤ 1 under 𝐏^η_k-1, given the marginal distribution of η and by the Markov property (<ref>). Therefore, ((η_t)_0≤ t≤ k,(X_t)_0≤ t≤ k) has the same law under both Q and ℙ^η_0. Now, conditioning on ℱ_k as defined in (<ref>), and noticing that (η_t)_0≤ t≤ k, (X_t)_0≤ t≤ k) (hence also η_k(X_k)) are all ℱ_k-measurable (for (X_t)_0≤ t≤ k this follows from (<ref>)-(<ref>)), we obtain that

    Q(X_k+1-X_k=1 | ℱ_k) 
    (<ref>),(<ref>)=(U_(X_k,k)≤ p_∙ | ℱ_k) {η_k(X_k)=1}+(U_(X_k,k)≤ p_∘ | ℱ_k) {η_k(X_k)=0}.

Now, by (<ref>), and using that X_k is ℱ_k-measurable, we can evaluate the conditional probabilities in (<ref>) to find that

    Q(X_k+1-X_k=1 | ℱ_k) = p_∙{η_k(X_k)=1}+p_∘{η_k(X_k)=0}
    =ℙ^η_0(X_k+1-X_k=1 | ℱ_k),

where the second equality comes from the independence of ℱ_k and U_k under ℙ^η_0, see (<ref>) and (<ref>). Integrating both sides of (<ref>) under Q and ℙ^η_0, respectively, against a suitable (ℱ_k-measurable) test function of ((η_t)_0≤ t≤ k,(X_t)_0≤ t≤ k), it follows that ((η_t)_0≤ t≤ k,(X_t)_0≤ t≤ k+1) have the same distribution under Q and ℙ^η_0. This concludes the proof of the induction step. 



We conclude this section by collecting a useful monotonicity property for the collection of random walks defined above, similar to <cit.>. 
Its proof hinges on the fact that the trajectories considered cannot cross without first meeting at a vertex, after which they merge. In the sequel, for a given environment configuration η =(η_t)_t ≥ 0, we refer to X^w = (X_n^w)_n ≥ 0 the process defined as in (<ref>) but with η in place of η entering the definition of the arrows in (<ref>). We will be interested in the case where η and η are such that

    η_n(x)≤η_n(x), for all  (x,n)∈𝕃∩ K,

for some K⊆ℤ×ℤ_+.
The following result is already interesting for the choice η=η, in which case X^w= X^w below.



 
If η,η∈Σ and K⊆ℤ×ℤ_+ are such that (<ref>) holds, then for every w,w'∈ K with π_1(w')≤π_1(w) and π_2(w)= π_2(w'),and for every n ≥ 0 such that [π_1(w)-k,  π_1(w')+k]× [π_2(w), π_2(w)+k] ⊆ K for all 0 ≤ k ≤ n, one has that

    X^w'_n≤X^w_n.
  


  We only treat the case K= ℤ×ℤ_+ to lighten the argument. The adaptation to a general K is straightforward, as all possible trajectories considered for X and X lie in K by assumption. The proof proceeds by a straightforward induction argument. Indeed, since X_0^w'= π_1(w') and X_0^w= π_1(w), one has that
X^w_0- X^w_0≥ 0 by assumption. To carry out the induction step, one notes that X^w_n-X^w'_n is even for any n ≥ 0 with increments ranging in -2, 0 or +2, and combines this with the following observation: if X^w_n-X^w'_n=0, then

    X^w_n+1-X^w'_n+1(<ref>)= A_(X_n^w, π_2(w)+n) -  A_(X_n^w', π_2(w')+n)(<ref>)=  A(η_n(X^w_n), U_w)- A(η_n(X^w_n), U_w)≥0,

where the second equality follows using that π_2(w)=π_2(w') (along with X^w_n=X^w'_n) and the inequality is due to (<ref>) and the fact that A(·, ξ) is increasing for any ξ∈ [0,1], which is straightforward from (<ref>).


For later reference, we also record that for any w∈𝕃 and n≥ m≥ 0, 

    |X^w_n - X^w_m| ≤ n - m,

as follows clearly from (<ref>). 





§ MAIN RESULTS


In this section, we start by formulating in Section <ref>  precise coupling conditions that we require from the environments, and which are of independent interest. These are given by conditions <ref>-<ref> below (a flavor of the second of these was given in (<ref>) in the introduction). Our main result, Theorem <ref>, appears in Section <ref>. It concerns the generic random walk in random environment defined in Section <ref>-<ref>, subject to the conditions of Section <ref>. Our standing assumptions will thus be that all of properties (<ref>)-(<ref>) and the conditions <ref>-<ref> hold. We will verify separately in Section <ref> that all of these conditions hold for SEP. From Theorem <ref> we then readily deduce Theorems <ref>and <ref> at the end of Section <ref>.

Towards the proof of Theorem <ref>, and following the outline of Section <ref>, we proceed to introduce in Section <ref> a finite-range approximation of the model, in which the environment is renewed after L time steps and gather its essential features that will be useful for us. We then state two 
key intermediate results, Propositions <ref> and <ref>, which correspond to the first and second parts from the discussion in Section <ref>; cf. also (<ref>) and (<ref>). From these, we deduce Theorem <ref> in Section <ref>. The proofs of the two propositions appear in forthcoming sections.





 §.§ Coupling conditions on the environment


Recall the framework of Section <ref>-<ref>, which we now amend with three further conditions. These involve an additional parameter ν>0 which quantifies the activity of the environment (in practice it will  correspond to the rate parameter appearing in (<ref>) in the case of SEP). We keep the dependence on ν explicit in the following conditions for possible future applications, for which one may wish to tamper with the speed of the environment (for instance, by slowing it down). 


For the purposes of the present article however, one could simply set ν=1 in what follows.

The first two conditions <ref> and <ref> below regard the environment (η_t)_t ≥ 0 alone, which, following the setup of Section <ref>, is assumed to be specified in terms of the measures (𝐏^η_0: η_0 ∈Σ) and (μ_ρ : ρ∈ J) that satisfy (<ref>)-(<ref>). The first condition, <ref>, concerns the empirical density of the environment. Roughly speaking, it gives a quantitative control on how  (<ref>) is conserved over time. The second condition, <ref>, is more technical.
In a nutshell, it states that if one environment η covers another environment η' on a finite interval I at a given time, and if η has a larger empirical density than η' outside I at the same time, the evolutions of η and η' can be coupled in a way that η covers η' on a larger interval after some time. 

We proceed to formalize these two properties:


  *  
(Conservation of density). There exists constants densitystable,[c]densitystableexpo∈ (0,∞) such that for all ρ∈ J and ε∈ (0,1) (with ρ+ε∈ J), and for all 
ℓ, ℓ', H,t≥ 1 satisfying H>4ν t > densitystableℓ^2ε^-2(1+|log^3 (ν t)|) and ℓ'≤√(t), the following two inequalities hold. Let η_0 be such that on every interval I of length ℓ included [-H,H], one has η_0(I)≤ (ρ+ε)ℓ (resp. η_0(I)≥ (ρ-ε)ℓ).  Then

    𝐏^η_0([ for all intervals I' of length ℓ' included in;         [-H+2ν t,H-2ν t]: η_t(I') ≤ (ρ+3ε) ℓ';                (resp. η_t(I')  
     ≥ (ρ-3ε) ℓ') ]) ≥ 1 - 4  H exp(-densitystableexpoε^2ℓ').


  *  (Couplings). There exists compatible, SEPcoupling2∈ (0,∞) such that the following holds. Let ρ∈ J, ε∈ (0,1) (with ρ+ε∈ J), and H_1, H_2,t,ℓ≥ 1 be integers  such that min{H_1, H_2-H_1-1}> 10νt>4νℓ^100>compatible, ν^ℓ>compatibleε^-2(1+|log^3(νℓ^4)|) and ℓ>80νε^-1+ν^-2. Let η_0,η'_0∈Σ be such that η_0|_[-H_1, H_1]≽η_ 0 '|_[-H_1, H_1] and such that for every interval I⊆ [-H_2,H_2] of length ⌊ℓ/2 ⌋≤ |I| ≤ℓ , we have η_0(I)≥ (ρ+3ε/4)| I | and η'_0(I)≤ (ρ+ε/4)| I |. Then there exists a coupling  of two environments η,η' with respective marginals 𝐏^η_0,𝐏^η'_0 such that 

    (∀ s∈ [0,t],  η_s|_[-H_1+4νt, H_1-4νt]≽η'_s|_[-H_1+4νt, H_1-4νt])≥ 1 - 20texp (-νt/4)

and 

    (η_t |_[-H_2+6νt, H_2-6νt]≽η'_t|_[-H_2+6νt, H_2-6νt])≥ 1 -5SEPcoupling2ℓ^4 H_2exp(- SEPcoupling2^-1ν/ν+1ε^2ℓ).




For later reference, we record the following two particular instances of <ref>, which correspond to the cases where H_2=0 and H_1=0, respectively. For convenience, we state them with better constants and exponents than in <ref>. In fact, when verifying condition <ref> for the SEP in Section <ref>, we will first prove that these two conditions hold, and use them to prove <ref>.






  *  (No particle drifting in from the side). 
Let t,H ≥ 0 and k≥ 1 be integers, and let η_0,η'_0∈Σ be such that η_0 |_[-H, H]≽η_0' |_[-H, H].   
There exists a coupling  of environments η,η' with respective marginals 𝐏^η_0 and 𝐏^η'_0 such that

    ℚ(∀ s∈ [0,t],  η_s|_[-H+2νkt, H-2νkt]≽η'_s|_[-H+2νkt, H-2νkt])≥ 1- 20exp(-kν t/4).

Informally, with high probability no particle of η' outside of [-H,H] can drift into [-H+2νt, H-2νt] (when k=1 for instance) before time t to perturb the domination of η' by η.



  *  (Covering η' by η).
There exists SEPcoupling >0 such that for all ρ∈ J and ε∈ (0,1) (with ρ+ε∈ J), the following holds. If  H,t≥ 1 satisfy H>4ν t, ν^8t>1 and ν t^1/4 >SEPcouplingε^-2(1+|log^3(ν t) |), then for all η_0,η'_0∈Σ such that on each interval I ⊂ [-H,H] of length ⌊ℓ/2 ⌋≤ |I| ≤ℓ, where ℓ:=⌊ t^1/4⌋, η_0(I)≥ (ρ+3ε/4)|I| and η'_0(I) ≤ (ρ+ε/4)|I|, there exists a coupling ℚ of η,η'  with marginals 𝐏^η_0, 𝐏^η'_0 so that 
    ℚ( η_t | _[-H+4ν t, H-4ν t]≽η_t' | _[-H+4ν t, H- 4ν t])≥ 1- SEPcoupling2 tHexp(-(SEPcoupling2(1+ν^-1))^-1ε^2t^1/4).

In words, the coupling ℚ achieves order between η and η' at time t under suitable regularity assumptions on the empirical density of their initial configurations η_0 and η_0'.







The third and last property ensures that if an environment η covers another environment η' and has at least one extra particle at distance ℓ of the origin (which typically happens if η has higher density than η'), then with probability at least exponentially small in ℓ, by time ℓ, this particle can reach the origin which will be empty for η', while preserving the domination of η' by η. 
We will combine this property with the uniform ellipticity of the random walk on top of the environment to show that the walker has at least an exponentially small probability to reach a position where η has a particle but not η', which in turn yields a probability bounded away from zero that a walker on η steps to the right while a walker on η' steps to the left (under the coupling mentioned in Section <ref>), hence creating the desired initial gap that we will then exploit in our constructions.


 





  *  (Sprinkler). 
For all ρ∈ J, for all integers H, ℓ,k≥ 1 with H≥ 2νℓ k and k ≥ 48ν^-1(ν +log(40)-log(p_∘(1-p_∙)ν/2)), the following holds. If η_0,η'_0 ∈Σ satisfy η_0(x)≥η'_0(x) for all x∈ [-H,H], η_0([0,ℓ])≥η'_0([0,ℓ])+1 and η'_0([-3ℓ+1, 3ℓ])≤ 6(ρ+1)ℓ,  then there is a coupling ℚ of  η' under 𝐏^η_0' and η under 𝐏^η_0 such that, with 
δ =  (
ν/2e^ν )^6(ρ+1)ℓ,

    ℚ(η_ℓ(x )>0  ,  η'_ℓ( x )=0)≥ 2δ

 for x ∈{0,1}, and with δ'= δ (p_∘(1-p_∙))^6(ρ+1)ℓ,

    ℚ({∀ s∈ [0, ℓ],   η_s|_[-H+2νkℓ, H-2νkℓ]≽η'_s|_[-H+2νkℓ, H-2νkℓ]}^c)   ≤ 20e^-kνℓ/4≤δ'.
























 §.§ Main result
 Following is our main theorem.

[Sharpness of v(·)]  Let η be an environment as in Section <ref> satisfying <ref>-<ref>. Assume that for all ρ∈ J, there exists v(ρ) such that

    ℙ^ρ-a.s., lim_n  n^-1X_n= v(ρ) .

Then, for all ρ, ρ'∈ J such that ρ>ρ', one has  that

    v(ρ)>v(ρ').




With Theorem <ref> at hand, we first give the proofs of Theorems <ref> and <ref>. We start with the latter.

 Theorem <ref> concerns the particular case where ℙ^ρ refers to the walk of Section <ref> evolving on top of the exclusion process η started from product Bernoulli(ρ) distribution, for ρ∈ J ⊂ (0,1). The properties (<ref>)-(<ref>) and <ref>-<ref> are indeed all satisfied in
this case, as is proved separately in Section <ref> below, see Lemma <ref> and Proposition <ref>. 

In the notation of (<ref>), we now separately consider the intervals J∈{J_-, J_0, J_+}, where J_-=(0,ρ_-), J_0=(ρ_-,ρ_+) and J_+=(ρ_+,1). The fact that the law of large numbers (<ref>) holds for any choice of J is the content of <cit.>. Thus Theorem <ref> is in force, and v is strictly increasing on J for any  J∈{J_-, J_0, J_+}. Since by direct application of (<ref>) and Lemma <ref>, v is already non-decreasing on J_-∪ J_0∪ J_+, it must be (strictly) increasing on J_-∪ J_0∪ J_+ altogether, and (<ref>) follows. In view of (<ref>), the first equality in (<ref>) is an immediate consequence of (<ref>) with J=J_0.



As to the second equality in (<ref>), recalling the definition of ρ_c from (<ref>), we first argue that ρ_- ≤ρ_c. If ρ < ρ_-, then by (<ref>)-(<ref>), X_n/n → v(ρ)<0 ^ρ-a.s. and thus in particular ^ρ(lim sup X_n <0)=1 (in fact it equals -∞ but we will not need this). On the other hand, { H_n < H_-1}⊂{ H_-1>n}⊂{X_k ≥ 0,  ∀ k ≤ n}, and the latter has probability tending to 0 as n →∞ under ^ρ. It follows that θ(ρ)= 0 in view of (<ref>), whence ρ≤ρ_c, and thus ρ_- ≤ρ_c upon letting ρ↑ρ_-. 

Since ρ_-=ρ_+, in order to complete the proof it is enough to show that ρ_+ ≥ρ_c. Let ρ> ρ_+. We aim to show that θ(ρ) > 0. Using the fact that v(ρ)>0 and (<ref>), one first picks n_0=n_0(ρ) ≥ 1 such that ^ρ_z(X_n >0,  ∀ n ≥ n_0) ≥ 1/2 for any z=(m,m) with m ≥ 0 (the worst case is m=0, the other cases follow from the case m=0 using invariance under suitable space-time translations). Now, observe that for all n ≥ 0, under ^ρ,

    { H_n < H_-1}⊃( { X_k-X_k-1= +1,  ∀ 1 ≤ k ≤ n_0}
    ∩{ X_2n_0+k' >0,  ∀ k' ≥ n_0}∩{lim sup_n→∞X_n=+∞});

for, on the event on the right-hand side, one has that X_n_0= n_0 and the walk can in the worst case travel n_0 steps to the left during the time interval (n_0, 2n_0], whence in fact X_k ≥ 0 for all k ≥ 0, and H_n<∞ since lim sup_n→∞X_n=+∞. Combining (<ref>), the fact that the last event on the RHS has  full probability due to (<ref>)-(<ref>), the fact that P^η_(0,0)(X_k-X_k-1= +1,  ∀ 1 ≤ k ≤ n_0) ≥ (p_∙∧ p_∘)^n_0 on account of (<ref>)-(<ref>) and the Markov property of the quenched law at time n_0, one finds that 

    θ_n(ρ) (<ref>)≥  (p_∙∧ p_∘)^n_0·_(n_0, n_0)^ρ(X_n_0+k' >0,  ∀ k' ≥ n_0 ) ≥ 2^-1 (p_∙∧ p_∘)^n_0 >0,

where the second inequality follows by choice of n_0. Thus, θ(ρ)>0 (see (<ref>)), i.e. ρ≥ρ_c. Letting ρ↓ρ_+ one deduces that ρ_+ ≥ρ_c, and this completes the verification of (<ref>).


 

Only item (i) requires an explanation. This is an easy consequence of <cit.>, e.g. with the choice ε=(ρ_c-ρ)/4 for a given ρ<ρ_c, and Theorem <ref> (see (<ref>)), as we now explain. Indeed one has that { H_n < H_-1}⊂{X_n≥ v(ρ_c-ε)n} under ^ρ as soon as n is large enough (depending on ρ); to see the inclusion of events recall that ρ_c=ρ_- on account of (<ref>), which has already been proved, and therefore v(ρ_c-ε)<0. The conclusion of item (i) now readily follows using the second estimate in <cit.>.






 §.§ The finite-range model 𝐏^ρ,L


Following the strategy outlined in Section <ref>, we will aim at comparing the random walk in dynamic random environment, which has infinite-range correlations, to a finite-range model, which enjoys regeneration properties, and which we now introduce.


For a density ρ∈ J (recall that J is an open interval of ℝ_+) and an integer L≥1, we define a finite-range version of the environment, that is, a probability measure 𝐏^ρ,L on Σ∋η=(η _t(x):  x ∈ℤ,   t∈ℝ_+) (see Section <ref> for notation) such that the following holds. At every time t multiple of L, η_t is sampled under 𝐏^ρ,L according to μ_ρ (recall (<ref>)), independently of (η _s)_0≤ s<t and, given η_t, the process (η_t+s)_0≤ s<L has the same distribution under 𝐏^ρ,L as (η_s)_0≤ s<L under P^η_t, cf. Section <ref> regarding the latter. We denote 𝐄^ρ,L the expectation corresponding to 𝐏^ρ,L. It readily follows that η is a homogenous Markov process under 𝐏^ρ,L, and that 𝐏^ρ,L inherits all of Properties (<ref>)-(<ref>) from 𝐏^ρ. In particular μ_ρ is still an invariant measure for the time-evolution of this environment. Note that 𝐏^ρ,∞ is well-defined and 𝐏^ρ,∞= 𝐏^ρ.


Recalling the quenched law P_z^η of the walk X in environment η started at z∈ℤ from Section <ref>, we extend the annealed law of the walk from (<ref>) by setting _z^ρ,L[·] = ∫𝐏^ρ,L(dη) P_z^η[·] so that ^ρ,∞_z=^ρ_z corresponds to the annealed law defined in (<ref>). We also abbreviate ^ρ,L=^ρ,L_0.

We now collect the key properties of finite-range models that will be used in the sequel. A straightforward consequence of the above definitions is that

    [        under ^ρ,L, {(X_kL+s-X_kL)_0≤ s≤ L: k∈ℕ} is an i.i.d. family,; with common distribution identical to the ℙ^ρ-law of  (X_s)_0≤ s≤ L. ]

Moreover, by direct inspection one sees that 𝐏^ρ,L inherits the properties listed in (<ref>) from 𝐏^ρ; that is, whenever 𝐏^ρ does,

    𝐏^ρ,L satisfies <ref>, <ref>, <ref>, <ref>
     (all for L≥ t) and <ref> (for L≥ℓ).

(more precisely, all of these conditions hold with 𝐏^η,L in place of 𝐏^η everywhere, where 𝐏^η,L refers to the evolution under 𝐏^ρ,L with initial condition η_0=η).
The next result provides a well-defined monotonic speed v_L(·) for the finite-range model. This is an easy fact to check. A much more refined quantitative monotonicity result will follow shortly in Proposition <ref> below (implying in particular strict monotonicity of v_L(·)).

[Existence of the finite-range speed v_L]
For ρ∈ J and an integer L≥ 1, let

    v_L(ρ)def.=𝔼^ρ,L[X_L/L]=𝔼^ρ[X_L/L].

Then

    ℙ^ρ,L-a.s.lim_n→ +∞ n^-1X_n=v_L(ρ).

Moreover, for any fixed L, we have that

    the map ρ↦ v_L(ρ) is non-decreasing on J.




The second equality in (<ref>) is justified by (<ref>).  The limit in (<ref>) is an easy consequence of (<ref>), (<ref>), the definition (<ref>) of v_L and the law of large numbers.
The monotonicity (<ref>) is obtained  by combining (<ref>) and Lemma <ref>.








 §.§ Key propositions and proof of Theorem <ref>



In this section, we provide two key intermediate results, stated as Propositions <ref> and <ref>, which roughly correspond to the two parts of the proof outline in Section <ref>.
Theorem <ref> will readily follow from these results, and the proof appears at the end of this section. As explained in the introduction, the general strategy draws inspiration from recent interpolation techniques used in the context of sharpness results for percolation models with slow correlation decay, see in particular <cit.>, but the proofs of the two results stated below are vastly different.




Our first result is proved in Section <ref> and allows us to compare the limiting speed of the full-range model to the speed of the easier finite-range model with a slightly different density. Note that, even though both v(·) and v_L(·) are monotonic, there is a priori no clear link between v and v_L.
 

[Approximation of v by v_L]

Under the assumptions of Theorem <ref>, there exists C:approx=C:approx(ν) ∈ (0,∞) such that for all L ≥ 3 and ρ such that [ρ -1/log L,ρ +1/log L]⊆ J, 

    v_L(ρ -1/log L)-C:approx(log L)^100/L≤ v(ρ)≤ v_L(ρ +1/log L) +C:approx(log L)^100/L.




With Proposition <ref> above, we now have a chance to deduce the strict monotonicity of v(·) from that of v_L(·). Proposition <ref> below, proved in Section <ref>, provides a quantitative strict monotonicity for the finite-range speed v_L(·). Note however that it is not easy to obtain such a statement, even for the finite-range model: indeed, from the definition of v_L(·) in (<ref>), one can see that trying to directly compute the expectation in (<ref>) for any L boils down to working with the difficult full range model. One of the main difficulties is that the environment mixes slowly and creates strong space-time correlations. Nonetheless, using sprinkling methods, it turns out that one can speed-up the mixing dramatically by increasing the density of the environment. This is the main tool we use in order to obtain the result below. 


[Quantitative monotonicity of v_L]
 Assume (<ref>)  
 holds and let ρ∈ J. For all ϵ>0 such that ρ+ϵ∈ J, there exists L_1=L_1(ρ,ϵ, ν)≥ 1 such that, for all L≥ L_1,

    v_L(ρ+ϵ) - v_L(ρ) ≥3 
    C:approx (log L)^100/L.







Propositions <ref> and <ref> imply Theorem <ref>, as we now show.
  
Let ρ, ρ'∈ J with ρ>ρ', and define ε=ρ-ρ'. 
Consider L≥ 3 ∨ L_1(ρ+ε/3, ε/3), so that the conclusions of Propositions <ref> and <ref> both hold. By choosing L sufficiently large in a manner depending on ρ and ρ', we can further ensure that (log L)^-1<ε/3 and [ρ-(log L)^-1, ρ+(log L)^-1]∪ [ρ'-(log L)^-1, ρ'+(log L)^-1]⊆ J. Abbreviating α_L = L^-1(log L)^100, it follows that 

    v(ρ)(<ref>)≥ v_L(ρ -(log L)^-1)-C:approxα_L (<ref>)≥  v_L(ρ -ε/3)-C:approxα_L (<ref>)≥
     v_L(ρ'+2ε/3) - C:approxα_L
    
    (<ref>)≥ v_L(ρ'+ε/3) +2 C:approxα_L
    (<ref>)≥ v_L(ρ'+(log L)^-1) +2C:approxα_L (<ref>)≥ v(ρ')+C:approxα_L
    >v(ρ'),

yielding (<ref>).





§ FINITE-RANGE APPROXIMATION OF ^Ρ

In this section, we prove Proposition <ref>, which allows us to compare the speed v(·) of the full-range model to the speed v_L(·) (see (<ref>)) of the finite-range model introduced in <ref>. The proof uses a dyadic renormalisation scheme. By virtue of the law(s) of large numbers, see (<ref>) and (<ref>), and for L_0 and ρ fixed, the speed v(ρ) ought to be close to the speed v_2^KL_0(ρ), for some large integer K. Hence, if one manages to control the discrepancies between v_2^k+1L_0(ρ) and v_2^kL_0(ρ) for all 0≤ k≤ K-1 and prove that their sum is small, then the desired proximity between v(ρ) and v_L_0(ρ) follows. This is roughly the strategy we follow except that at each step, we slightly increase or decrease the density ρ (depending on which bound we want to prove), in order to weaken the (strong) correlations in the model. This is why we only compare v(·) and v_L(·) for slightly different densities at the end. This decorrelation method is usually referred to as sprinkling; see e.g. <cit.> for similar ideas in other contexts.


As a first step towards proving Proposition <ref>, we establish in the following lemma a one-step version of the renormalization, with a flexible scaling of the sprinkling (f(L) below) in anticipation of possible future applications. For x∈ℝ, let x_-=max(-x,0) denote the negative part of x. Throughout the remainder of this section, we are always tacitly working under the assumptions of Theorem <ref>.



 
There exists L_0=L_0(ν) ≥ 1 such that for all L ≥ L_0, all f(L)∈ [(log L)^90, L^1/10] and all ρ such that (ρ-f(L)^-1/40,ρ+f(L)^-1/40)⊆ J, the following holds: there exists a coupling _L of (X^(i)_s)_ 0 ≤ s ≤ 2L, i=1,2, such that X^(1)∼^ρ,L, X^(2)∼^ρ + ε,2L with ε= f(L)^-1/40,  and

    _L(min_0≤ s≤ 2L(X^(2)_s-X^(1)_s)≤ -f(L))≤  e^-f(L)^1/40.

Consequently,

    𝔼^_L[max_0≤ s≤ 2L(X^(2)_s-X^(1)_s)_-]≤ 2f(L),

and

    Var^_L(max_0≤ s≤ 2L(X^(2)_s-X^(1)_s)_-)≤ 2f(L)^2.

The same conclusions hold with marginals X^(1)∼^ρ,2L and X^(2)∼^ρ + ε,L instead.





 Towards showing (<ref>), let us first assume that

    there exists L_0>3 such that for all L≥ L_0, (ρ+log^-2L) ∈ J and there exists a
       coupling ℚ_L of η^(1)∼𝐏^ρ,L and η^(2)∼𝐏^ρ+ε,2L s.t. _L[G] ≥ 1 - exp(-f(L)^1/40),

where, setting t=⌊f(L)/2⌋, the `good' event G is defined as

    G={η^(1)_s(x) ≤η^(2)_s(x),  ∀ (x,s)∈ [-3L,3L] × [0,L) }
    ∩{η^(1)_s(x) ≤η^(2)_s(x-2t),  ∀ (x,s)∈ [-3L, 3L]× [L+t, 2L)}.

Given the above, we now extend the coupling ℚ_L to the random walks X^(1)∼ P^η^(1) and X^(2)∼ P^η^(2), defined as in Section <ref>, up to time 2L. To do that, we only need to specify how we couple the collections of independent uniform random variables (U^(1)_w)_w∈𝕃 and (U^(2)_w)_w∈𝕃 (recall that 𝕃 denotes space-time, see (<ref>)) used to determine the steps of each random walk; the walks X^(i), i=1,2, up to time 2L are then specified in terms of (U^(i), η^(i)) as in (<ref>)-(<ref>). Under _L, we let (U^(1)_w)_w∈𝕃 be i.i.d. uniform random variable on [0,1] and define, for (x,s)∈𝕃,

    U^(2)_(x,s)=
          U^(1)_(x,s),    if  0≤ s<L 
    
          U^(1)_(x-2t,s),    if  L≤ s<2L

(for definiteness let U^(2)_(x,s)=U^(1)_(x,s) when s ≥ 2L). Clearly (U^(2)_w)_w∈𝕃 are i.i.d. uniform variables, hence X^(2) also has the desired marginal law.
Now, we will explain why, on this coupling, (<ref>) holds, and refer to Figure <ref> for illustration. We will only consider what happens on the event G defined in (<ref>).

On G, by Lemma <ref> with K=[-3L,3L]× [0,L], we have that X^(2)_s≥ X^(1)_s for all 0≤ s≤ L. This implies that X^(2)_L+t≥ X^(1)_L+t-2t owing to (<ref>). Let η=η^(1), define η  by η_n(x)=η^(2)_n(x-2t) and w=(X^(1)_L+t, L+t). Let X^w and X^w be random walks evolving on top of η and  η respectively, and both using the collection of uniform random variables U^(1). Then, conditionally on η^(1)_L+t, η^(2)_L+t and X^(1)_L+t, and on the event {X^(1)_L+t= x_1}, X^w_L-t has the law of X^(1)_2L and  X^w_L-t-2t has the law of the position at time 2L of a random walk started at (x_1-2t,L+t) and evolving on top of η^(2), using the collection U^(2). In particular, it evolves on the same environment as X^(2) and starts on the left of X^(2)_L+t, so that X^w_L-t≤ X^(2)_2L (by Lemma <ref> applied with K=ℤ×ℤ^+ and η=η). 
On G, using the second event in the intersection on the right-hand side of (<ref>), we can again apply Lemma <ref>, now at time L+t, with X and X as described and K=[-3L+2t,3L-2t]× [L+t,2L]. We obtain that X^w_s-t≤X^w_s-t for all s∈[t,L]. Thus, subtracting 2t on both sides and using the previous facts, we have on G that X^(1)_s-2t≤ X^(2)_s, for all 0≤ s≤ 2L. All in all, we have proved that

    G ⊆{max_0≤ s≤ 2L(X^(2)_s-X^(1)_s)_-≤ 2t },

and therefore (<ref>) follows from our assumption (<ref>). The fact that (<ref>) and (<ref>) hold is a simple consequence of (<ref>) and a straightforward computation using the deterministic inequality (X^(2)_s-X^(1)_s)_-≤ 4L valid for all 0≤ s≤ 2L and the fact that L≥ L_0> 3 (note that for L large enough, we have (2L)^2e^-f(L)^1/40≤ f(L) for all f(L)∈ [log^90L,L^1/10]).


It remains to show that (<ref>) holds, which brings into play several of the properties gathered in <ref> and which hold by assumption. Let L_0>3 be such that for every L≥ L_0 and any choice of f(L)≥log^90L, with ε=f(L)^-1/40 we have that ρ+ε∈ J and

    L> t>10^100ν^-1+ν^-8+ν^-7SEPcoupling^8ε^-16,

where t=⌊ f(L)/2⌋ as defined above (<ref>).


We will provide a step-by-step construction of _L, in four steps. First, note that by (<ref>)-ii), there exists a coupling _L of environments (η^(1)_t(x) : x∈ℤ,t∈ [0,L)) and (η^(2)_t(x) : x∈ℤ,t∈ [0,L]) such that under _L, η^(1)∼𝐏^ρ,L on the time interval [0,L), η^(2)∼𝐏^ρ+ε,2L on the time interval [0,L] and such that _L-a.s., η^(1)_t(x)≤η^(2)_t(x) for all x∈ℤ and t∈ [0,L). 
We then extend _L to time L for η^(1) by sampling η^(1)_L∼μ_ρ, independently of (η^(1)_t)_0≤ t<L and (η^(2)_t)_0≤ t≤ L.
In particular the above already yields that the inequalities required as part of the event G in (<ref>) which involve (η^(i)_t)_0≤ t<L actually hold ℚ_L-a.s.

Second, letting ℓdef.=⌊ t^1/4⌋, we define G_1 to be the event that for every interval I⊆ [-10L(1+ν), 10L(1+ν)] of length ⌊ℓ/2 ⌋≤ |I|≤ℓ, the inequalities η^(1)_L(I)≤ (ρ+ε/4)ℓ and η^(2)_L(I)≥ (ρ+3ε/4)ℓ hold (see the beginning of <ref> for notation). By (<ref>) and a union bound over the choices of such intervals I, we get that 

    _L(G_1^c)≤ 40ℓ L(1+ν) exp(-densitydevε^2ℓ/32).

At time L and on G_1^c, extend _L to the time interval [L,2L] by letting η^(1) and  η^(2) follow their dynamics P^η^(1)_L and P^η^(2)_L independently of each other (using (<ref>)).


Third, we continue the construction of the coupling on G_1 by applying <ref> with H=10L(1+ν), η_0=η^(2)_L(· -2t) and η'_0=η^(1)_L, checking the assumptions using (<ref>) (note indeed that we have 1+|log^3(ν t)|≤ (ν t)^1/8 since ν t>10^100, and then that SEPcouplingε^-2(ν t)^1/8≤ν t^1/4). This implies that, given η^(1)_L and η^(2)_L, on G_1, there exists an extension of the coupling _L on the time interval [L,L+t] such that, defining

    G_2={∀ x∈ [-8L-6νL , 8L+6νL ],  η^(1)_L+t(x)≤η^(2)_L+t(x-2t)  },

we have  

    _L(G_2^c)≤ 10SEPcoupling2t L(1+ν) exp( -SEPcoupling2^-1ν/ν +1ε^2t^1/4).
 
At time L+t and on G_2^c, we extend _L on the time interval [L+t,2L] by letting η^(1) and  η^(2) follow their dynamics P^η^(1)_L+t and P^η^(2)_L+t independently of each other.

Fourth, we continue the construction of the coupling on G_2 by applying <ref> with η_0=η^(2)_L+t(· -2t) and η'_0=η^(1)_L+t, H=8L+6νL, k=1 and t in <ref> equal to L-t. This implies that, given η^(1)_L+t and η^(2)_L+t, on G_2, there exists an extension of the coupling _L on the time interval [L+t,2L] such that, defining

    G_3={∀ x∈ [-8L , 8L ],  s∈[L+t,2L],  η^(1)_s(x)≤η^(2)_s(x-2t)  },

we have

    _L(G_3^c)≤ 20exp(-ν(L-t)/4).
 
Finally, note that G_1∩ G_2∩ G_3  ⊆   G, so that (<ref>) is a straightforward consequence of  (<ref>), (<ref>) and (<ref>) provided that L_0 is chosen large enough, depending only on ν (as well as SEPcoupling2,  densitydev and SEPcoupling). Note in particular that with our choices of f(L), ε above (<ref>) and ℓ (≥ c f(L)^1/4), we have that min (L-t,ε^2t^1/4,ε^2ℓ)≥ f(L)^1/20. All in all (<ref>) follows. The case X^(1)∼𝐏^ρ,2L and X^(2)∼𝐏^ρ + ε,L can be treated in the same way, by means of an obvious analogue of (<ref>). The remainder of the coupling (once the environments are coupled) remains the same.





















We are now ready to prove Proposition <ref>. The proof combines the law of large numbers for the speed together
with Lemma <ref> applied inductively over increasing scales.
The rough strategy is as follows. We aim to compare the speed of the full-range model v(ρ) to the speed of the finite-range model v_L(ρ) for some possibly large, but finite L, and prove that these two are close. For δ<v_L(ρ), we know that the probability for the finite-range model to go slower than speed δ goes to 0 on account of Lemma <ref>. Thus, in a large box of size 2^K L_0, the L_0-range model will most likely be faster than δ as soon as K is large enough. Lemma <ref> is used over dyadic scales to control the discrepancies between the 2^k L_0-range model and the 2^k+1 L_0-range model for all k from 0 to K-1, and to prove that they are small. It will be seen to imply that with high probability, in a box of size 2^K L_0, the 2^K L_0-range model will be faster than δ. Now, we only need to observe that when observed in a box of size 2^K L_0, the 2^K L_0-range model is equivalent to the full-range model. As Lemma <ref> already hints at, this is but a simplified picture and the actual argument entails additional complications. This is because each increase in the range (obtained by application of Lemma <ref>) comes not only at the cost of slightly `losing speed,' but also requires a compensation in the form of a slight increase in the density ρ, and so the accumulation of these various effects have to be tracked and controlled jointly.




We only show the first inequality in Proposition <ref>, i.e. for L ≥ C(ν) and ρ such that [ρ -(log L)^-1,ρ +(log L)^-1]⊆ J, abbreviating α_L= (log L)^100/L, one has

    v_L(ρ - (log  L)^-1)-α_L≤ v(ρ).

The first inequality in (<ref>) then follows for all L ≥ 3 by suitably choosing the constant C:approx since v,v_L ∈ [-1,1]. 
The second inequality of (<ref>) is obtained by straightforward adaptation of the arguments below, using the last sentence of Lemma <ref>.

For L ≥ 1, define L_k= 2^kL for k ≥ 0. As we now explain, the conclusion (<ref>) holds as soon as for L ≥ C(ν) and ρ as above, we show that

    ℙ^ρ((X_L_K/ L_K) ≤ v_L(ρ -( log L)^-1)-α_L)→ 0, as K→∞.

Indeed under the assumptions of Proposition <ref>, the law of large numbers (<ref>) holds, and therefore in particular, for all δ>v(ρ), we have that ℙ^ρ(X_L_K≤δL_K) tends to 1 as K →∞. Together with (<ref>) this is readily seen to imply (<ref>).

We will prove (<ref>) for L ≥ C(ν), where the latter is chosen such that the conclusions of Lemma <ref> hold for L, and moreover such that

    (log L)^-9/4+100/(log L)^5/4≤1/log L, log L≥ 5  and (3/2)^-k(klog2/log L + 1)^99≤ 1, for all  k≥0.

For such L we define, for all integer K,k ≥ 0, all ρ>0 and all δ∈, recalling the finite-range annealed measures ℙ^ρ, L from  <ref>,

    p_ρ,K,δ^(k)=^ρ,L_k(X_L_K≤δL_K), 
       p_ρ,K,δ^(∞)=^ρ(X_L_K≤δL_K)

(observe that the notation is consistent with <ref>, i.e. ℙ^ρ,∞= ℙ^ρ).
In this language (<ref>) requires that p_ρ,K,δ^(∞) vanishes in the limit K →∞ for a certain value of δ. We start by gathering a few properties of the quantities in (<ref>).
For all ρ'∈ J, the following hold:

    lim_K→ +∞p_ρ',K,δ^(0)=0 for all δ< v_L(ρ')  (by (<ref>)),
        p_ρ',K,δ^(∞)=p_ρ',K,δ^(k), for all δ∈[-1,1], K≥0  and k≥ K,
        p_ρ',K,δ^(∞) and  p_ρ',K,δ^(k) are non-increasing in ρ' and non-decreasing in δ.

As explained atop the start of the proof, owing to the form of Lemma <ref> we will need to simultaneously sprinkle the density and the speed we consider in order to be able to compare the range-L_k+1 model to the range-L_k model. To this effect, let

    ρ_0=ρ-(log L)^-1 and ρ_k+1=ρ_k+(log L_k)^-9/4, for all k≥0,

as well as

    δ_0=v_L(ρ_0)-L^-2 and δ_k+1=δ_k- log^99(L_k)/L_k, for all k≥0.

A straightforward computation, bounding the sum below for k≥1 by the integral ∫_0^∞ dx/(xlog 2 +log L)^9/4, yields that

    lim_k ρ_k = ρ_0 + ∑_k≥0 (log L_k)^-9/4≤ρ_0 + (log L)^-9/4+100/(log L)^5/4(<ref>)≤ρ_0 +1/log L(<ref>)≤ρ.

Another straightforward computation yields that

    ∑_k≥0(log L_k)^99/L_k = 
    ∑_k≥0(3/2)^-k(klog2/log L + 1)^99×(log L)^99/L(3/4)^k
    (<ref>)≤(log L)^99/L∑_k≥0(3/4)^k 
    (<ref>)≤(log L)^100/L-1/L^2.

In particular, since (ρ_k) is increasing in k, (<ref>) implies that for all K≥0, we have ρ≥ρ_K, and (<ref>) yields in view of (<ref>) that δ_K >v_L(ρ_0)-α_L, with α_L (=L^-1(log L)^100) as above (<ref>).
Using this, it follows that, for all K≥ 0,

    p^(∞)_ρ,K,v_L(ρ_0)-α_L(<ref>)=p_ρ,K,v_L(ρ_0)-α_L^(K)
    (<ref>)≤ p_ρ_K,K,δ_K^(K)     = p_ρ_0,K,δ_0^(0)+∑_0 ≤ k < K(p_ρ_k+1,K,δ_k+1^(k+1) - p_ρ_k,K,δ_k^(k)).

As the left-hand side in (<ref>) is precisely equal to the probability appearing in (<ref>), it is enough to argue that the right-hand side of (<ref>) tends to 0 as K →∞ in order to conclude the proof.
By recalling that δ_0<v_L(ρ_0) from (<ref>) and using (<ref>), we see that lim_K→∞ p_ρ_0,K,δ_0^(0)=0, which takes care of the first term on the right of (<ref>). 

We now aim to show that the sum over k in (<ref>) vanishes in the limit K →∞, which will conclude the proof. Lemma <ref>
now comes into play. Indeed recalling the definition (<ref>), the difference for fixed value of k involves walks with range L_k and L_k+1, and Lemma <ref> supplies a coupling allowing good control on the negative part of this difference (when expressed under the coupling). Specifically, for a given K ≥ 1 and
0≤ k ≤ K-1, let X^(1)∼ℙ^ρ_k+1,L_k+1 and X^(2)∼ℙ^ρ_k,L_k. Note that for i∈{1,2}, one has the rewrite

    X^(i)_L_K=∑_0 ≤ℓ< 2^K-k-1( X^(i)_(ℓ+1)L_k+1-X^(i)_ℓ L_k+1).

Therefore, due to the regenerative structure of the finite-range model, explicated in (<ref>), it follows that, for i∈{1,2}, under ℙ^ρ_k+2-i,L_k+2-i,

    X^(i)_L_Klaw=∑_0 ≤ℓ< 2^K-k-1 X^(i,ℓ)_L_k+1,

 where X^(i,ℓ)_L_k+1, ℓ≥0, is a collection of independent copies of X^(i)_L_k+1 under ℙ^ρ_k+2-i,L_k+2-i.

 Now recall the coupling measure ℚ_L provided by Lemma <ref> with f(L)=(log L)^90 and  let us denote by ℚ the product measure induced by this couplingfor the choices L=L_k and ε= ρ_k+1-ρ_k in Lemma <ref>, so that ℚ supports the i.i.d. family of pairs (X^(1,ℓ)_L_k+1,X^(2,ℓ)_L_k+1), ℓ≥0, each sampled under ℚ_L_k. In particular, under ℚ, for all ℓ≥0, X^(1,ℓ)_L_k+1 and X^(2,ℓ)_L_k+1 have law ℙ^ρ_k+1,L_k+1 and ℙ^ρ_k,L_k, respectively. Now, one can write, for any K≥1 and 0≤ k≤ K-1, with the sum over ℓ ranging over 0 ≤ℓ< 2^K-k-1 below, that

    p_ρ_k+1,K,δ_k+1^(k+1) - p_ρ_k,K,δ_k^(k)(<ref>)=ℚ(∑_ℓ X^(1,ℓ)_L_k+1≤ L_K δ_k+1) -  ℚ(∑_ℓ X^(2,ℓ)_L_k+1≤ L_K δ_k)
    ≤ℚ(∑_ℓ X^(1,ℓ)_L_k+1≤ L_K δ_k+1, ∑_ℓ X^(2,ℓ)_L_k+1> L_K δ_k)
    (<ref>)≤ℚ(∑_ℓ (X^(1,ℓ)_L_k+1- X^(2,ℓ)_L_k+1)≤ -2^K-klog^99(L_k)).

Now, using Chebyshev's inequality together with Lemma <ref> (recall that f(L)=log^90L), it follows that for K≥1 and 0≤ k≤ K-1,

    p_ρ_k+1,K,δ_k+1^(k+1) - p_ρ_k,K,δ_k^(k)   ≤2^K-k(log L_k)^190/( 2^K-k(log L_k)^99-2^K-k(log L_k)^90)^2
       ≤7/2^K-k(k+5)^8≤ 2^-K2+224K^-8,

where the second line is obtained by considering the cases when k< K/2 or k≥ K/2 separately, together with straightforward computations. The bound (<ref>) implies in turn that

    ∑_k=0^K-1(p_ρ_k+1,K,δ_k+1^(k+1) - p_ρ_k,K,δ_k^(k))≤ K2^-K2+224K^-7K→∞⟶ 0,

which concludes the proof.





§ QUANTITATIVE MONOTONICITY FOR THE FINITE-RANGE MODEL

The goal of this section is to prove Proposition <ref>. For this purpose, recall that J is an open interval, and fix ρ∈ J and ϵ>0 such that (ρ+ϵ)∈ J. Morever, in view of (<ref>), we can assume that ϵ<1/100. The dependence of quantities on ρ and ϵ will be explicit in our notation. As explained above Proposition <ref>, even if we are dealing with the finite-range model, the current question is about estimating the expectation in (<ref>), which is actually equivalent to working on the full-range model. Thus, we retain much of the difficulty, including the fact that the environment mixes slowly. The upshot is that the speed gain to be achieved is quantified, and rather small, cf. the right-hand side of (<ref>).

The general idea of the proof is as follows. First, recall that we want to prove that at time L, the expected position of X^ρ+ϵ∼ℙ^ρ+ϵ (where ∼ denotes equality in law in the sequel) is larger than the expected position of X^ρ∼ℙ^ρ by 3(log L)^100. The main conceptual input is to couple X^ρ and X^ρ+ϵ in such a way that, after a well-chosen time T ≪ L, we create a positive discrepancy between them with a not-so-small probability, and that this discrepancy is negative with negligible probability, allowing us to control its expectation. We will also couple these walks in order to make sure that the environment seen from X^ρ_T is dominated by the environment seen from X^ρ+ϵ_T, even if these walks are not in the same position, and we further aim for these environments to be `typical'. The last two items will allow us to repeat the coupling argument several times in a row and obtain a sizeable gap between X^ρ_L and X^ρ+ϵ_L. In more quantitative terms, we choose below T=5(log L)^1000 and create an expected discrepancy of exp(-(log L)^1/20) at time T. Repeating this procedure L/T times provides us with an expected discrepancy at time L larger than 3(log L)^100 (and in fact larger than L^1+o(1)). We refer to the second part of Section <ref> for a more extensive discussion of how the expected gap size comes about.


We split the proof of Proposition <ref> into two parts. The main part (Section <ref>) consists of constructing a coupling along the above lines. In Section <ref>, we prove Proposition <ref>. 




 §.§ The trajectories Y^±




In this section, we define two discrete-time processes Y_t^- and Y^+_t, t ∈ [0,T], for some time horizon T, see (<ref>) below, which are functions of two deterministic environments η^- and η^+ and an array U=(U_w)_w∈  (see Section <ref> for notation) of numbers in [0,1]. This construction will lead to a deterministic estimate of the difference Y^+_t-Y^-_t, stated in Lemma <ref>. In the next section, see Lemma <ref>, we will prove that there exists a measure  on (η^±, U) such that under , Y^- dominates stochastically the law of a random walk X^ρ∼ℙ^ρ (see below (<ref>) for notation), Y^+ is stochastically dominated by the law of a random walk X^ρ+ϵ∼ℙ^ρ+ϵ, and we have a lower bound on 𝔼^[Y^+_T-Y^-_T], thus yielding a lower bound on 𝔼^ρ+ϵ[X^ρ+ϵ] -𝔼^ρ[X^ρ].



The construction of the two processes Y^± will depend on whether some events are realized for η^± and U. We will denote E_1, E_2,… these events, which will occur (or not) successively in time. We introduce the convenient notation

    E_i-jdef.=E_i∩ E_i+1∩…∩ E_j,  for all j>i≥ 1,

and write E_i-j^c for the complement of E_i-j. We refer to Figure <ref> (which is a refined version of Figure <ref>) for visual aid for the following construction of  Y^±, and to the discussion in Section <ref> for intuition. Let us give a brief outlook on what follows. The outcome of the construction will depend on whether a sequence of events E_1-E_9 happens or not: when all of these events occur, which we call a success, then Y_T^+ and Y^-_T  have a positive discrepancy and we retain a good control on the environments at time T, namely η^+ dominates η^- (or, more precisely, η^- shifted by  Y_T^+-Y^-_T). When at least one of these nine events does not happen, this can either result in a neutral event, where the trajectories end up at the same position and we still have control on the environments, or it could result in a bad event, where we can have Y_T^+<Y^-_T (but we will show in Lemma <ref> that we keep control on the environments with overwhelming probability, owing to the parachute coupling evoked at the end of Section <ref>). Whenever we observe a neutral or a bad event, we will exit the construction and define the trajectories Y^± at once from the time of observation all the way up to time T. Finally, we note that the walks Y^+ and Y^- are actually not Markovian. This is however not a problem as we use them later to have bounds on the expected displacements of the actual walks X^ρ and X^ρ+ε.









We now proceed to make this precise. For L≥ 3, define 

    ℓ_G=⌊ (log L)^1000⌋, ℓ_g = ⌊ (log L)^1/1000⌋ and T=5ℓ_G,

as well as

    s_0= ℓ_G,   s_1= s_0+ℓ_g,    s_2= s_1+2ℓ_g^20 and s_3=s_2+ℓ_g^20.

Let M≥ 10(ν+1)L, which will parametrize the spatial length of a space-time box in which the entire construction takes place, and let Y_0^±=0. The definition of Y^± depends on the values of M and L, but we choose not to emphasize it in the notation. Given processes 

    γ = (η^+, η^-,  U)

 on a state space Ω such that the first two coordinates take values in ( ℤ_+ )^[0,T] ×ℤ and the last one in [0,1]^, we will define the events E_i=E_i(γ) below measurably in γ and similarly Y^± =(Y^±_t(γ))_ 0 ≤ t ≤ T with values in the set of discrete-time trajectories starting at 0. Unlike the sample paths of  X^ρ, X^ρ+ε, the trajectories of Y^± may perform jumps that are not to nearest neighbors.   Probability will not enter the picture until Lemma <ref> below, see in particular (<ref>), which specifies the law of γ. We now properly define the aforementioned three scenarii of success, neutral events and bad events, which will be mutually exclusive, and we specify Y^± in all cases.
 
 



Below s and t always denote integer times. Define the event (see Section <ref> regarding the notation ≽) 

    E_1=   {∀ s∈ [0,s_0],  η^+_s|_[-M+2νs_0, M-2νs_0]≽η^-_s|_[-M+2νs_0, M-2νs_0)]}.

The event E_1 guarantees the domination of the environment η^- by η^+ and is necessary for a success, while E_1^c will be part of the bad event.
On E_1, for all 1≤ t≤ s_0, let recursively

    Y^-_t=Y^+_t=Y^-_t-1+A(η^-_t-1(Y^-_t-1), U_(Y^-_t-1,t-1))

where A was defined in (<ref>), so that we let the walks evolve together up to time s_0. On the bad event E_1^c, we exit the construction by defining

    Y^-_t=t  and  Y^+_t=-t, for all  1≤ t≤ T.

Next, define the events

    E_2=   {η^+_s_0([Y^-_s_0, Y^-_s_0+ℓ_g])>η^-_s_0([Y^-_s_0, Y^-_s_0+ℓ_g])  }
       ∩{η^-_s_0([Y^-_s_0-3ℓ_g+1, Y^-_s_0+3ℓ_g]) ≤ (ρ+1)· 6ℓ_g},
    
    E_3=    {∀ s∈ [s_0, s_1],  η^+_s|_[-M+(4ν+1) s_1, M-(4ν+1) s_1]≽η^-_s|_[-M+(4ν+1) s_1, M-(4ν+1) s_1]}.

The event E_3 again ensures the domination of η^- by η^+ on a suitable spatial interval while E_2 creates favourable conditions at time s_0 to possibly see a sprinkler at time s_1.
On the event E_1-3 (recall (<ref>) for notation), for all s_0+1≤ t≤ s_1, let recursively

    Y^-_t=Y^+_t=Y^-_t-1+A(η^-_t-1(Y^-_t-1), U_(Y^-_t-1,t-1)),

so that the walks, from time s_0, continue to evolve together up to time s_1 and, in particular, we have that

    on  E_1-3,    Y^-_s_1=Y^+_s_1.

In order to deal with the case where E_2 or E_3 fail, we will distinguish two mutually exclusive cases, that will later contribute to an overall neutral and bad event, respectively; cf. (<ref>) and (<ref>). To this end, we introduce

    E_2,bis={∀ s∈ [s_0,T],  η^+_s|_[-M+2νT, M-2νT]≽η^-_s|_[-M+2νT, M-2νT]}.

On E_1∩ E_2^c∩ E_2,bis, which will be a neutral event, we exit the construction by letting the walk evolve together up to time T, that is,  we define

    Y^-_t=Y^+_t=Y^-_t-1+A(η^-_t-1(Y^-_t-1), U_(Y^-_t-1,t-1)), for all  s_0+1≤ t≤ T.

On the bad event (E_1∩ E_2^c∩ E_2,bis^c)∪(E_1-2∩ E_3^c), we exit the construction by defining

    Y^-_t=t  and  Y^+_t=-t, for all  s_0+1≤ t≤ T.

In the above, Y^+ and Y^- may take a non-nearest neighbour jump at time s_0, which is fine for our purpose. Next, define

    E_4=   {η^+_s_1(Y_s_1^ + )≥ 1,η^-_s_1(Y_s_1^ - )=0},
    
    E_5=   {∀ s∈ [s_1,s_2],  η^+_s|_[-M+(6ν+1) s_2, M-(6ν+1) s_2]≽η^-_s|_[-M+(6ν+1) s_2, M-(6ν+1) s_2]},

where E_4 states that the walkers  see a sprinkler at time s_1 and E_5 guarantees domination of the environments from time s_1 to s_2.  We will first define what happens on the neutral and the bad events. For this purpose, define

    E_4,bis={∀ s∈ [s_1,T],  η^+_s|_[-M+(4ν+1) T, M-(4ν+1) T]≽η^-_s|_[-M+(4ν+1) T, M-(4ν+1) T]}.

Recall that on E_1-3, we have defined Y^± up to time s_1. On the neutral event E_1-3∩ E_4-5^c∩ E_4,bis, we define

    Y^-_t=Y^+_t=Y^-_t-1+A(η^-_t-1(Y^-_t-1), U_(Y^-_t-1,t-1)), for all  s_1+1≤ t≤ T.

On the bad event E_1-3∩ E_4-5^c∩ E_4,bis^c, we exit the construction by defining

    Y^-_t=t  and  Y^+_t=-t, for all  s_1+1≤ t≤ T.

On the event E_1-5, because of the sprinkler, the walkers have a chance to split apart hence, for t∈ [s_1+1,s_2], we let

    Y^-_t=Y^-_t-1 +A(η^-_t-1(Y^-_t-1), U_ ( Y^-_t-1 ,t-1)      )  and  Y^+_t=Y^+_t-1 +A(η^+_t-1(Y^+_t-1), U_ ( Y^+_t-1 ,t-1)      ).

Above, Y^+ and Y^- evolve on top of their respective environments η^+ and η^- from time s_1+1 to time s_2. To be able to continue the construction from time s_2 to s_3, we define two events E_6 and E_7 concerning the environments from times s_1 to s_2. If we are on E_1- 6, between times s_1+1 and s_2 we will require that Y^+ and Y^- drift away, regardless of the states of η^+ and η^-, using only the information provided by U. For this purpose, define

    E_6= ⋂_s_1≤ t≤ s_2-1 E_6^t,

where we set 

    E^s_1_6={U_(Y^-_s_1,s_1)∈ (p_∘, p_∙)} (recall that p_∙ >p_∘) and
       E^t_6={ U_ (  Y_s_1^- -(t-s_1)   ,t) >  p_∙}∩{  U_ (  Y^-_s_1+ t-s_1  ,t)< p_∘} for  s_1+1≤ t ≤ s_2-1.

On E_4∩ E_6^s_1, Y^- steps to the left and Y^+ steps to the right from their common position, thus creating a gap at time s_1+1. Then for all s_1<t< s_2, as long as E_4 and E_6^s_1 to E_6^t-1 happen, Y^-_t and Y^+_t are at distinct positions and E_6^t allows Y^- to take one more step to the left and Y^+ one more step to the right. Hence, using what we have constructed so far on E_1-5, we have that

    on  E_1-6,    Y^+_s_2=Y^-_s_2+2(s_2-s_1),

and we still have the domination of η^- by η^+ at time s_2, cf. (<ref>).

Since Y^+ and Y^- are no longer at the same position, we are going to momentarily allow to lose this domination in order to recreate it at time s_3 but in a suitably shifted manner, namely, achieve that η^+(Y^+_s_3+·)|_I ≽η^-(Y^-_s_3+·) |_I for a suitable interval I, see (<ref>). To do so, we first need favourable conditions at time s_2 encapsulated by the event

    E_7={[               for all intervals  I⊆ [Y^-_s_1 - 3(ν+1)T,  Y^-_s_1 + 3(ν+1)T] with; ⌊ℓ_g^2 /2⌋≤| I|≤ℓ_g^2,  η^+_s_2(I)≥ (ρ+3ϵ/4) | I | and η^-_s_2(I)≤ (ρ+ϵ/4) | I | ]}

The above requires good empirical densities at time s_2 on an interval of length of order T centred around the common position of the walkers Y^± at time s_1. On E_1-7, we do not precisely control the position of the walkers from time s_2 to s_3 and define, for all s_2< t≤ s_3,

    Y_t^- -Y_t-1^- = 1,    Y_t^+ - Y_t-1^+ = -1,

which corresponds to the worst case scenario assuming nearest-neighbour jumps. In particular, using (<ref>), (<ref>) and (<ref>), we have that

    on  E_1-7,    Y^+_s_3-Y^-_s_3=2ℓ_g^20.

We now need to consider the case where E_6-7 fails, and we will again distinguish two types of failure. For this purpose, define

    E_6,bis={∀ s∈ [s_2,T],  η^+_s|_[-M+(6ν+1) T, M-(6ν+1) T]≽η^-_s|_[-M+(6ν+1) T, M-(6ν+1) T]},

and, on the neutral event E_1-5∩ E_6,7^c∩ E_6,bis, we merge Y^+ with Y^- at time s_2+1 and then let them walk together, by defining

    Y_s_2+1^+   =Y_s_2+1^-= Y_s_2^- + A(η_s_2^-(Y^-_s_2), U_(Y^-_s_2,s_2)),  and 
    
     Y^-_t   =Y^+_t=Y^-_t-1+A(η^-_t-1(Y^-_t-1), U_(Y^-_t-1,t-1)), for all  s_2+2≤ t≤ T

(above one line would be sufficient but we single out (<ref>) because the merging will typically occasion a jump for Y^+). On the remaining bad event E_1-5∩ E_6-7^c∩ E_6,bis^c, we exit the construction in the now usual way by defining

    Y^-_t=t  and  Y^+_t=-t, for all  s_2+1≤ t≤ T.

It remains to define Y^± from time s_3 to T on the event E_1-7. The good event will require

    E_8def.={η^+_s_3(·+ℓ_g^20)|_[Y^-_s_1-2(ν+1)T,Y^-_s_1+2(ν+1)T]≽η^-_s_3(·-ℓ_g^20)|_[Y^-_s_1-2(ν+1)T,Y^-_s_1+2(ν+1)T]},

that is, we want that the environment η^+ seen from Y^+_s_3 covers η^- seen from Y^-_s_3 on an interval of length of order T, which will enable us to let the walkers move in parallel (i.e. taking the same steps at the same time), even if they are at different positions. Moreover, we want this domination to persist from time s_3 to time T, hence we require

    E_9def.={∀ s∈ [s_3,T], η^+_s(·+ℓ_g^20)|_[Y^-_s_1-2 T,Y^-_s_1+2T]≽η^-_s(·-ℓ_g^20)|_[Y^-_s_1-2 T,Y^-_s_1+2T]}.

On the good event E_1-9, we let, for t∈ [s_3+1,T],

    Y^-_t=Y^-_t-1+A(η^-_t-1(Y^-_t-1),U_(Y^-_t-1,t-1)) and 
    Y^+_t=Y^+_t-1+A(η^+_t-1(Y^+_t-1),U_(Y^+_t-1-2ℓ_g^20,t-1)).

Note that above, we choose to shift spatially the collection (U_w) by 2ℓ_g^20 spatially for Y^+, which corresponds to the difference between Y^- and Y^+. Therefore, both walks are using the same U_w to determine their next step. Using (<ref>), (<ref>) and (<ref>), one thus proves recursively that

    on  E_1-9,   Y^+_t-Y^-_t=2ℓ_g^20, for all s_3≤ t≤ T.

Finally, on the bad event E_1-7^c∩ E_8-9^c, we finish the construction by defining

    Y^-_t=Y^-_t-1+1,  Y^+_t=Y^+_t-1-1, for all  s_3+1≤ t≤ T-1, and  Y^-_T=T,Y^+_T=-T.

This ends the definition of the trajectories Y^+ and Y^-. Let us emphasize once more that these trajectories are not nearest-neighbour and not Markovian w.r.t. the canonical filtration associated to (η^+,η^-,U), but that this will not prevent us from obtaining the desired bounds.


Below, we proceed to define our three key events and summarise in Lemma <ref> some of the important (deterministic) properties we will use.



  * Scenario I: Good event. We define

    E_gooddef.= E_1-9.
 
Notice that by (<ref>), on the event E_good we have that

    Y^+_T-Y^-_T=2ℓ_g^20>0,

and also that

    ∀ s∈ [0,s_2], η^+_s|_[-T,T]≽η^-_s|_[-T,T],

which follows by (<ref>), (<ref>) and (<ref>), provided that M-(6ν+1)s_2≥ T. Finally, (<ref>) and the fact that on E_good, | Y^-_s_1|≤ s_1 (by (<ref>) and (<ref>)) imply that

    ∀ s∈ [s_3,T], η^+_s(·+2ℓ_g^20)|_[-T-2ℓ_g^20,T-2ℓ_g^20]≽η^-_s|_[-T,T].


  * Scenario II: Neutral event. We define

    E_neutraldef.=(E_1∩ E_2^c∩ E_2,bis) ∪(E_1-3∩ E_4-5^c∩ E_4,bis) 
     ∪(E_1-5∩ E_6-7^c∩ E_6,bis).
 
Note that on E_neutral, (<ref>)-(<ref>), (<ref>) and (<ref>) imply that  

    Y^+_T=Y^-_T

and (<ref>), (<ref>), (<ref>), (<ref>), (<ref>), (<ref>) and (<ref>)
imply that 

    Y^-_t=Y^-_t-1+A(η^-_t-1(Y^-_t-1), U_(Y^-_t-1,t-1)), for all  1≤ t≤ T.

From (<ref>), (<ref>), (<ref>), (<ref>), (<ref>) and (<ref>), we also have 

    ∀ s∈ [0,T],  η^+_s|_[-T, T]≽η^-_s|_[-T,T],

provided that M-(6ν+1)T≥ T.


  * Scenario III: Bad event. We finally define the event

    E_bad   def.=( E_good∪ E_neutral)^c=E_1^c ∪(E_1∩ E_2^c∩ E_2,bis^c) ∪(E_1-2∩ E_3^c) ∪
       (E_1-3∩ E_4-5^c∩ E_4,bis^c)  ∪(E_1-5∩ E_6-7^c∩ E_6,bis^c) ∪(E_1-7∩ E_8-9^c ).

In particular, (<ref>), (<ref>), (<ref>), (<ref>), and (<ref>) yield  

    Y^+_T = Y^-_T-2T=-T  on the event  E_bad.


 
 
 
 
 
 
 
 
 
 
 
 
 
 The next deterministic lemma is a restatement of (<ref>), (<ref>) and (<ref>).
 
 
The event E_good, E_neutral and E_bad defined in (<ref>), (<ref>)
 and (<ref>), respectively, form a partition of Ω  such that

    Y_T^+   = Y_T^-+2ℓ_g^20 on E_good; 
    Y^+_T   =Y_T^-  on E_neutral; 
    Y_T^+    = Y^-_T -2T   on E_bad.



  

 §.§ The coupling ℚ

We now aim to compare Y^± to X^ρ and X^ρ+ε, and to integrate over the dynamics of the environments when started from a typical initial configuration. We will derive from this a bound  on the expected discrepancy between Y^+ and Y^-, and thus on the one between X^ρ and X^ρ+ε. The main result of this section is Lemma <ref>, which entails a coupling ℚ with these features. Lemma <ref> is the key ingredient in the proof of Proposition <ref>, which appears in the next subsection.

We will require the environments η^+ and η^- to have a typical initial configuration under 𝐏^ρ+ϵ and 𝐏^ρ in the following sense. Recall that ρ∈ J and ϵ∈ (0,1/100) have been fixed at the start of this section, and that (ρ+ϵ)∈ J. For M,L∈ℕ, we say that (η^+_0,η^-_0)∈Σ^2 (recall that Σ= (_+)^ from Section <ref>) is (M,L)-balanced if all of the following occur:


  *  η^+_0(x)≥η^-_0(x) for all x∈ [-M,M],

  *  η^+_0([x,x+⌊(log L)^2⌋ -1])≥ (ρ +99ϵ100) ⌊(log L)^2⌋ for all x∈ [-M,M-⌊(log L)^2⌋ +1], 

  *   η^-_0([x,x+⌊(log L)^2⌋ -1])≤ (ρ +ϵ100) ⌊(log L)^2⌋ for all x∈ [-M,M-⌊(log L)^2⌋ +1].




There exists L_2=L_2(ρ,ϵ, ν) 
≥ 1 such that for all L≥ L_2, the following holds.  For all M∈ [10(ν+1)L,20(ν+1)L] and for every (M,L)-balanced choice of (η^+_0,η^-_0), there exists a coupling = _(η^+_0,η^-_0) of (η^+, η^-, U) with the following properties:

    0.8η^-∼𝐏^η^-_0,  η^+∼𝐏^η^+_0, and (U_w)_w∈𝕃 are i.i.d. uniform variables on [0,1]; 
    
       0.85 
    There exist X^±=X^±(η^±,U) such that X^±∼ℙ^η^±_0 and ℚ-a.s., the inequalities X^-_T ≤ Y^-_T and Y^+_T ≤ X^+_T hold,  with Y^±= Y^± (η^+,η^-,U) as in Section <ref>;
    
       𝔼^ℚ[Y^+_T - Y^-_T] ≥exp(- (log L)^1/20);
       ( E_restart) ≥ 1- L^-100,  where 
       E_restartdef.={∀ x∈ [-(M-(8ν+3)T),M-(8ν+3)T], η^+_T(x +Y^+_T) ≥η^-_T(x +Y^-_T)   }.







 
Let L_2≥ 1 to be chosen later, and L≥ L_2. Fix M∈ [10(ν+1)L, 20(ν +1)L], and let (η_0^+, η_0^-) be (M, L)-balanced. 
We construct the coupling ℚ below. We will then define X^- and X^+ such that 
 (<ref>) is satisfied. To prove the main estimate (<ref>), we will control the probabilities of the events E_good, E_neutral and E_bad emerging from the construction of Y^±, and use Lemma <ref>. Finally, proving (<ref>) will require to bound the probability of losing the synchronisation of η^+ and η^- by time T.
 
We split the proof into five parts: the construction of ℚ and the proofs of (<ref>)-(<ref>).



Part I: Construction of .


 We will denote the natural filtration generated by the triplet (η^+,η^-,U) by

    ℱ_t=σ{(η^+_t')_0≤ t'≤ t,(η^-_t')_0≤ t'≤ t, (U_w)_w∈, π_2(w)≤ t-1}, for  t≥0.

Under ℚ, we first let U=(U_w)_w∈ be a collection of i.i.d. uniform random variables on [0,1]. We now define the coupling of η^- and η^+ under ℚ in such a way that given ℱ_t, the evolution of (η^±_s)_t≤ s≤ t+1 has the right marginal 𝐏^η^±_t (up to time one), cf. (<ref>). Moreover, throughout the construction of ℚ, i.e. from (<ref>) to (<ref>) below, we will in fact ensure that for all integer t ∈ [0,T], under ℚ,

    (U_w: π_2(w)=t) is independent from ℱ_t.

  We now proceed to specify η^± under ℚ, and refer again to Figure <ref> for visual aid. On the time-interval [0,s_0], we

    couple (η^+,η^-) as (η,η') in <ref> with η_0=η^+_0, η'_0=η^-_0, H=M, t=s_0 and k=1;

in particular, the domination η_0 |_[-H, H]≽η_0' |_[-H, H] required by <ref> is ensured by the fact that (η^+_0,η^-_0) is (M,L)-balanced; see item (i) in the corresponding definition above Lemma <ref>.
Since E_1 ∈ℱ_s_0 by (<ref>) and (<ref>), we can observe at time s_0 whether E_1 occurred. Conditionally on ℱ_s_0 and on E_1^c, during [s_0,T], we

    let η^- and η^+ evolve independently  with respective marginals ^η^-_s_0 and ^η^+_s_0.

Recalling the definition (<ref>), we have that E_2∈ℱ_s_0. 
Conditionally on ℱ_s_0 and on E_1∩ E_2^c,  we couple (η^+,η^-) during the interval [s_0,T] as 

    (η,η') in <ref> with η_0=η^+_s_0, η'_0=η^-_s_0, H=M-2ν s_0, t=T-s_0 and k=1.

On E_1-2, note that | Y^-_s_0|≤ s_0 <s_1. Hence, as we now explain, during the time-interval [s_0, s_1], conditionally on ℱ_s_0 and on E_1-2, we can 

    apply the coupling of <ref> to η_ t(·)=η^+_s_0+ t (·+Y^-_s_0) and η_ t '(·)=η^-_ s_0+ t (·+Y^-_s_0), t ≥0,
        with ℓ=ℓ_g, H=M-(2ν+1) s_1, k=⌊ s_1/ℓ_g⌋ and x= ℓ mod  2.

Note indeed that by (<ref>) and (<ref>), k≥ℓ_g> 48ν^-1(ν +log (40) - p_∘(1-p_∙)ν/2) for L large enough and H= M-(2ν+1)  s_1≥ 2ν s_1≥  2ν kℓ_g = 2 νℓ k for all L≥ 3, as required in <ref>. Together with the definition of E_2 in (<ref>), this allows us to apply the coupling of <ref>.

So far we have specified η^± for all of [0,T] on E_1-2^c and up to time s_1 on E_1-2. As we now briefly elaborate, it is also plain from the construction above that the independence property postulated in (<ref>) holds for all t ≤ s_1. This is a trivial matter for t<s_0 in view of (<ref>), which does not involve U at all. For s_0 ≤ t ≤ s_1, the only dependence on U arises through Y^-_s_0 via E_2 and (<ref>). However, on account of (<ref>), (<ref>), (<ref>), (<ref>) and (<ref>), Y^-_s_0 only relies on variables in U with time label at most s_0-1, whence the claim. In the sequel (more precisely, up to (<ref>)), considerations along similar lines allow to extend (<ref>) to larger times t. These will not be made explicit.


Returning to the construction of ℚ, it remains to specify η^±
after time s_1 on the event E_1-2. Recall that by (<ref>) and (<ref>), both E_3 and E_4 are in ℱ_s_1. Over the time interval [s_1, T], conditionally on ℱ_s_1 and on E_1-2∩ E_3^c, we choose to

    let η^- and η^+ evolve independently  with respective marginals ^η^-_s_1 and ^η^+_s_1.

On the other hand, conditionally on ℱ_s_1 and on E_1-3∩ E_4^c, during [s_1,T], we

    couple (η^+,η^-)  as (η, η') in <ref>,
    with     H=M-(4ν+1) s_1,   t=t=T-s_1,   k= 1 .

Conditionally on ℱ_s_1 and on E_1-4, during the time-interval [s_1, s_2], we

    couple (η^+,η^-)  as (η, η') in <ref>,
    with     H=M-(4ν+1) s_1,   t=s_2-s_1,   k= ⌊ s_1/(s_2-s_1)⌋.

Note that k ≥ 1 in (<ref>) by (<ref>)  and since L ≥ L_2 by assumption (upon possibly enlarging L_2). Moreover, note that the conditions on the environments at time s_1 needed for  <ref> to apply in both (<ref>) and (<ref>) are met owing to the occurrence of E_3, see (<ref>).

We still have to specify η^± from time s_2 onwards on the event E_1-4. By definition (<ref>), we have that E_5∈ℱ_s_2. Hence, conditionally on ℱ_s_2 and on E_1-4∩ E_5^c, during [s_2, T], we 

    let η^- and η^+ evolve independently  with respective marginals ^η^-_s_2 and ^η^+_s_2.

Using the definitions (<ref>) and (<ref>), we have that both E_6 and E_7 are in ℱ_s_2. During [s_2,T], conditionally on ℱ_s_2 and on E_1-5∩ E_6-7^c, observing that the defining features of E_5 (see (<ref>)) allow to apply <ref>, we 

    couple (η^+,η^-) as (η, η') in <ref> with H=M-(6ν+1) s_2, t=T-s_2 and k=1.

Conditionally on ℱ_s_2 and on E_1-7, during [s_2,s_3], as we now explain, we

    couple (η^+(·+Y^-_s_2+ℓ_g^20),η^-(·+Y^-_s_2-ℓ_g^20 )) as (η, η') in <ref>
       with H=3(ν+1)T, t=s_3-s_2 and (ρ,ε)=(ρ,ϵ).

Indeed, one checks that the conditions needed for <ref> to apply are all satisfied on the event E_7 whenever L_2 (ρ,ϵ,ν) is large enough. First, by choice of L_2 and for all L ≥ L_2, one readily ensures (recall (<ref>)-(<ref>)) that all of 3(ν+1)T > 4ν(s_3-s_2), ν^8(s_3-s_2)>1 and ν(s_3-s_2)^1/4>SEPcouplingϵ^-2(1+|log^3(ν(s_3-s_2)) |) hold. Moreover, the conditions on the empirical densities of η_0 and η_0' appearing above (<ref>) hold by definition of E_7 at (<ref>), since ⌊ (s_3-s_2)^1/4⌋≥ℓ_g^2 by (<ref>). Note that the relevant intervals I in the context of <ref>, which have length ⌊ℓ/2 ⌋≤ |I| ≤ℓ with ℓ= ⌊ (s_3-s_2)^1/4⌋, may in practice be much larger than those appearing in the definition of E_7, but they can be paved by disjoint contiguous intervals as entering E_7. The required controls on the corresponding empirical densities η_0(I) and η_0'(I) are thus inherited from those defining E_7. Similar considerations also apply below (whenever either of <ref> or <ref> are used).

 It remains to specify η^± on the event E_1-7 for the time interval [s_3,T]. We now define an additional event whose realisation will allow us to couple η^± on the whole window of width order M at time T, regardless of whether the coupling at (<ref>) succeeds or not; here, by “succeed” we mean that the (high-probability) event appearing in (<ref>) is realized. The following will play a key role when establishing (<ref>). We set

    E_10def.={[ ∀ I ⊆ [-M+2ν s_3,M-2ν s_3] with ⌊⌊ (log L)^2⌋/2⌋≤| I |≤⌊ (log L)^2⌋,;              η^-_s_3(I)≤ (ρ+ϵ/4)| I| and η^+_s_3( I )≥ (ρ+3ϵ/4)| I | ]}.

The event E_10 above and E_8 defined in (<ref>) are both ℱ_s_3-measurable. Conditionally on ℱ_s_3 and on E_1-8∩ E_10, during [s_3,T], we couple

    (η^+(· +Y^-_s_1+ℓ_g^20 ),η^-(· +Y^-_s_1-ℓ_g^20 )) as in <ref> with  H_1=2(ν+1)T,
    
        H_2=M-2ν s_3-s_1, t=T-s_3, ℓ=ℓ_G^1/200 and (ρ,ε)=(ρ,ϵ).

To this effect, we verify that for L large enough, by (<ref>), (<ref>) and since M ≥ 10(ν+1)L, we indeed have that
min{H_1, H_2-H_1-1}> 10νt>4νℓ^100>compatible, νℓ>compatibleϵ^-2(1+|log^3(νℓ^4)|) and ℓ>80νϵ^-1+ν^-2 .
Also, the domination on [-H_1,H_1] and the empirical density condition are respectively guaranteed by definition of E_8 at (<ref>) and E_10 at (<ref>).


If E_8 does not occur (hence we temporarily lose the domination of η^- by η^+) but E_10 does, we proceed to what was referred to as the parachute coupling in Section <ref>, in order to recover this domination by time T. Precisely, conditionally on ℱ_s_3 and on E_1-7∩ E_8^c∩ E_10, we

    couple (η^+(· -T),η^-(· +T)) as (η, η') in <ref>
       with H=M-T-2ν s_3, t=T-s_3 and (ρ,ε)=(ρ,ϵ).

One checks indeed that the conditions of <ref> hold, since for L large enough (recalling (<ref>) and (<ref>)) we have that
H>4ν t,ν^8t>1, ν t^1/4 >SEPcouplingϵ^-2(1+|log^3(ν t) |) and t^1/4>⌊ (log L)^2 ⌋, so that on E_10 the condition on the empirical density holds. 

The remaining cases are straightforward to specify. Conditionally on ℱ_s_3, on E_1-8∩ E_10^c, we

    couple (η^+(· +Y^-_s_1+ℓ_g^20 ),η^-(· +Y^-_s_1-ℓ_g^20 )) as in <ref>
       with H=2(ν+1)T-ℓ_g^20, t=T-s_3, and k=1.

Finally, conditionally on ℱ_s_3 and on E_1-7∩ E_8^c∩ E_10^c, during [s_3,T], we

    let η^- and η^+ evolve independently  with respective marginals ^η^-_s_3 and ^η^+_s_3.

We have now fully defined the measure ℚ and with it the triplet (η^+,η^-,U) (in the time interval [0,T]). The task is now to verify that with these choices, all of (<ref>)-(<ref>) hold. For concreteness we extend all three processes (η^+,η^-,U) independently at times t >T, using the Markov property at time T for η^±. These extensions will de facto play no role because all of (<ref>)-(<ref>) only concern matters up to time T.

















































Part II: Proof of  (<ref>).
 

The fact that U has the desired law is immediate, see below (<ref>). We proceed to show that η^-∼𝐏^η_0^-. Since the construction of η^- only consists of successive couplings at times 0,s_0,s_1,s_2 and s_3 where the marginals have the desired distributions (recall <ref>, <ref>, <ref> and <ref>), by virtue of the Markov property (<ref>), it is enough to check that the events deciding which coupling to apply at time s_i are ℱ_s_i-measurable for i∈{0,1,2,3}, which we already did at (<ref>)-(<ref>), (<ref>), (<ref>), (<ref>) 
and (<ref>). Therefore, η^-∼𝐏^η_0^-. In the same way we deduce that η^+∼𝐏^η_0^+. 





Part III: Proof of (<ref>).



We now use (η^+,η^-,U) to construct explicit functions X^+=X^+(η^+,U) and X^-= X^-(η^-,U) with the correct marginal laws X^±∼ℙ^η_0^±. The case of X^- is easily dispensed with: we define  X^- as in (<ref>) and (<ref>) with (η^-,U) instead of (η,U). Since we have already established that η^-∼𝐏^η_0^- as part of (<ref>), it follows using (<ref>) and Lemma <ref> that X^-∼ℙ^η_0^-.  
 


As for X^+, we also define it via (<ref>) and (<ref>) using the construction specified around (<ref>), replacing (η,U) by (η^+,U^+) where U^+ is defined as follows: for all w∈𝕃 with π_2(w)≤ s_3-1, U^+_w=U_w, and for all w∈𝕃 with π_2(w)≥ s_3, 

    U^+_w=
     
    U_w-(2ℓ_g^20,0) on E_1-8, 
    
    U_w on E_1-8^c.

Recalling that E_1-8∈ℱ_s_3, and hence is independent of (U_w; w∈𝕃, π_2(w)≥ s_3), it follows that X^+∼ℙ^η_0^+ again by combining the established fact that η^+∼𝐏^η_0^+ and (<ref>). The rationale behind (<ref>) will become clear momentarily. 




We show that X^± as defined above satisfy Y^-_T≥ X^-_T and Y^+_T≥ X^+_T ℚ-a.s. To this end, note first that on E_bad and by (<ref>), Y^-_T=T and Y^+_T=-T, hence ℚ-a.s. on E_bad we have using the trivial bounds X^±_T ∈ [-T,T] that X^-_T≤ Y^-_T and Y^+_T≤ X^+_T.

Second, on E_neutral and by (<ref>), under ℚ, the process (Y^-_t:  0≤ t≤ T) simply follows the environment (η^-,U) as per (<ref>) and (<ref>), and so does (X_t^-: 0≤ t≤ T) by above definition of X^-. Hence Y^-_T=X^-_T. Moreover, since E_neutral⊂ E_1-8^c by (<ref>), the process (X^+_t: 0≤ t≤ T) follows the environment (η^+,U) by (<ref>). By Lemma <ref> applied with (X,X)=(Y^-,X^+), (η,η̃)=(η^-,η^+) and K=[-T,T]× [0,T], recalling (<ref>), we get that X^+_T≥ Y^-_T. Using (<ref>), we finally obtain X^+_T≥ Y^+_T=Y^-_T=X^-_T ℚ-a.s. on E_neutral.


Third, on E_good⊂ E_1-6, the process (Y^-_t:  0≤ t≤ s_2) follows the environment (η^-,U) by (<ref>), (<ref>) and (<ref>), as is the case of X^-, so that X^-_s_2=Y^-_s_2. Then by (<ref>) we have that Y^-_s_3=Y^-_s_2+(s_3-s_2) which guarantees that X^-_s_3≤ Y^-_s_3. From time s_3 to time T, X^- and Y^- follow the same environment (η^-,U) by (<ref>) and thus, by Lemma <ref> with (X,X)=(Y^-,X^-), (η,η̃)=(η^-,η^-) and K=ℤ× [s_3,T], we have that X^-_T≤ Y^-_T. 

Similarly for X^+ and Y^+, on E_good⊂ E_1-3, during [0,s_1] the process X^+ follows the environment (η^+,U) while Y^+ follows (η^-,U) by (<ref>), (<ref>). By (<ref>) we can apply Lemma <ref> with (X,X)=(Y^+,X^+), (η,η̃)=(η^-,η^+) and K=[-T,T]× [0,s_1] to deduce that Y^+_s_1≤ X^+_s_1.  Then during [s_1,s_2], both Y^+ and X^+ follow (η^+,U) (recall (<ref>), and that E_good⊂ E_1-5). Thus Lemma <ref> with (X,X)=(Y^+,X^+), (η,η̃)=(η^+,η^+) and K=ℤ× [s_1,s_2] ensures that Y^+_s_2≤ X^+_s_2 ℚ-a.s. on E_good. Next, (<ref>), which holds on E_1-7⊃ E_good, implies that Y^+_s_3≤ X^+_s_3, given that X^+ only takes nearest-neighbour steps. Finally, since E_good⊂ E_1-9, from time s_3 to T, both Y^+ and X^+ follow the environment (η^+,U^+), where U^+ is as in (<ref>) (recall (<ref>); this explains the choice in (<ref>)). Applying Lemma <ref> with (X,X)=(Y^+,X^+), (η,η̃)=(η^+,η^+) and K=ℤ× [s_3,T] therefore yields Y^+_T≤ X^+_T on E_good. This concludes the proof of (<ref>).



















Part IV: Proof of (<ref>). 


By Lemma <ref>, we have that 

    𝔼^[Y^+_T-Y^-_T]=2ℓ_g^20(E_good)-2T(E_bad).

Recalling the definitions of E_good and E_bad from (<ref>) and (<ref>), as well as (<ref>) and (<ref>), it is thus enough to show that

    ((E_good)=)  (E_1-9)≥exp(-ℓ_g^22)

and

    Sdef.=(E_1^c) +(E_1∩ E_2^c∩ E_2,bis^c ) +(E_1-2∩ E_3^c)
    +(E_1-3∩ E_4,5^c∩ E_4,bis^c ) 
     +(E_1-5∩ E_6-7^c∩ E_6,bis^c) +(E_1-7∩ E_8-9^c ) ≤(E_1-9)/(10T).

Proof of (<ref>). Recall E_1 from (<ref>). By (<ref>) and (<ref>), which is in force, we get

    ℚ(E_1^c)≤ 20 exp (-ν s_0/4) ≤exp(-ℓ_g^10^5),

the last inequality being true for L large enough by (<ref>) and (<ref>). 
Next, recalling (<ref>), that 4s_0>s_0+3ℓ_g by (<ref>) and that ϵ<1/100, and using that | Y^-_s_0|≤ s_0, we note that

    E_2^c⊆   ⋃_ x∈ [-4s_0+1,4s_0],
    ⌊ℓ_g/2⌋≤ℓ'≤ℓ_g{η^-([x,x+ℓ'-1])≤ (ρ+ϵ/2)ℓ' <η^+([x,x+ℓ'-1])≤  (ρ+2ϵ)ℓ'}^c.

We note in passing that we cannot locate precisely Y^-_s_0 without (possibly heavily) conditioning the evolution of η^- on [0,s_0]. By <ref> applied with either (η_0,ρ,ε)=(η^-_0,ρ ,ϵ/20) or (η_0,ρ,ε)=(η^-_0,ρ+ϵ ,ϵ/20), both times with (ℓ, H,t)= (⌊log ^2 L⌋,(4ν+8)s_0,s_0) and ℓ' ranging from ⌊ℓ_g/2⌋ to ℓ_g we have by a union bound on x and ℓ': 

    ℚ(E_2^c)≤ (2× 8s_0×ℓ_g) 4 (4ν+8)s_0exp (-densitystableexpoϵ^2 ⌊ℓ_g/2⌋/400)≤ 1/4,

the last inequality holding for L large enough by (<ref>) and (<ref>). Note that we can indeed apply <ref> since (η^+_0,η^-_0) is (M,L)-balanced (see items (ii) and (iii) above Lemma <ref>), and M>(4ν+8)s_0> 4ν s_0 >densitystableϵ^-2⌊ (log L)^2⌋^2(1+|log^3(ν s_0)|) and ℓ_g≤√(s_0) for L large enough. 


Next, we aim to derive a suitable deterministic lower bound on ℚ(E_3-4 |ℱ_s_0), on the event E_1-2, which is ℱ_s_0-measurable. We aim to apply <ref>, cf. (<ref>), and dealing with E_3 is straightforward, see (<ref>), but E_4 requires a small amount of work, cf. (<ref>) and (<ref>). To this effect, we first observe that under ℚ, with η, η' as defined in (<ref>), one has the inclusions

    E_1-4(<ref>), (<ref>)⊃{η^+_s_1(Y_s_1^ - )≥ 1,η^-_s_1(Y_s_1^ - )=0}∩  E_1-3
    ⊃{η_ℓ(x)≥ 1,η'_ℓ(x)=0}∩{Y_s_1^– Y_s_0^-=x }∩  E_1-3,

where ℓ=ℓ_g=s_1-s_0 and x= ℓ mod  2 on account of (<ref>) and (<ref>). Now recalling that the evolution of Y^- on the time interval [s_0,s_1] follows (<ref>) on E_1-3, and in view of (<ref>), one readily deduces that the event  {Y_s_1^– Y_s_0^-=x } is implied by the event E_1-3∩ F, where F refers to the joint occurrence of
{ U_(Y^-_s_0,s_0+ n) < p_∘} for even integer n satisfying 0 ≤ n ≤ℓ-1 and { U_(Y^-_s_0,s_0+ n) > p_∙} for odd integer n satisfying 0 ≤ n ≤ℓ-1.
(Observe indeed that, if ℓ is odd, whence x=1, there will be one more step to the right than to the left in the resulting trajectory for Y^+). Feeding this into (<ref>), applying a union bound, using (<ref>) and (<ref>) (which are in force on account of (<ref>)), it follows that on E_1-2,

    ℚ(E_3-4 |ℱ_s_0)≥ℚ({η_ℓ(x)≥ 1,η'_ℓ(x)=0}∩ F  |ℱ_s_0) -δ' ≥ 2δ(p_∘(1-p_∙))^ℓ -δ' ≥δ'

(see above <ref> regarding δ and δ');
in the penultimate step above, we have also used that, conditionally on ℱ_0, the events {η_ℓ(x)≥ 1,η'_ℓ(x)=0} and F are independent. Combining this with (<ref>) and (<ref>), we deduce that for L large enough, using (<ref>),

    ℚ(E_1-4)≥ 3δ'/4-  20  e^-ℓ_g^10^5≥δ'/2.



Next, recalling the definition (<ref>) of E_5 and that E_1-4∈ℱ_s_1, by  (<ref>) and the bound given in <ref>,  we have that, ℚ-a.s. on E_1-4,

    ℚ(E_5^c |ℱ_s_1)≤ 20exp(- ⌊ s_1/(s_2-s_1)⌋ (s_2-s_1)ν4 )≤exp(- ν4ℓ_G )≤exp(- ν8ℓ_g^10^6),

for all L large enough by (<ref>). 

We will return to E_6 momentarily and first consider E_7. To compute the probability of E_7^c, we take a union bound over ℓ' such that ⌊ℓ_g^2/2⌋≤ℓ'≤ℓ_g^2, use the definition (<ref>) and the fact that (η_0^-,η_0^+) is (M,L)-balanced in order to apply <ref> twice, once for η^- and once for η^+, choosing in both cases (ℓ,H,t)=(⌊ (log L)^2⌋, 38(ν+1)ℓ_G, s_2) and, for η^-, with (η_0,ρ, ε)=(η^-_0,ρ ,ϵ/100 ) and, for η^+, with (η_0,ρ, ε)=(η^+_0,ρ+ϵ ,ϵ/100 ). Note that for L large enough by (<ref>) and (<ref>), we have indeed M>H>4ν t>densitystableℓ^2ε^-2(1+|log^3(ν t)|) and ℓ'≤ℓ_g^2≤√(t), as required in <ref>. We thus obtain that

    ℚ(E_7^c)≤ 400(ν+1)ℓ_g^2ℓ_G exp(-densitystableexpoϵ^2⌊ℓ_g^22⌋/10^4)≤exp(  -densitystableexpoϵ^210^5ℓ_g^2 ),

where the last inequality holds for L large enough (depending on ν, ρ and ϵ). 
Putting (<ref>), (<ref>) and (<ref>) together and taking L (hence ℓ_g) large enough, it follows that 

    (E_1-5∩ E_7) ≥(E_1-5)-(E_7^c) ≥δ'/4.



 Concerning E_6, we first observe that under ℚ, the field (U_w: s_1 ≤π_2(w) ≤ s_2) is independent from the σ-algebra generated by ℱ_s_1 and (η^±_t)_s_1≤ t≤ s_2; this can be seen by direct inspection of the coupling construction until time s_2, paying particular attention (with regards to the evolution of η^± during [s_1,s_2]) to (<ref>), (<ref>), (<ref>) (and (<ref>)), which all involve only either i) trivial couplings or ii) couplings relying on <ref>. In particular these couplings do not involve U at all. Using the previous observation and recalling (<ref>)-(<ref>), it follows that ℚ-a.s., 

    (. E_6| ℱ_s_1, (η^±_t)_s_1≤ t≤ s_2)=(p_∙ -p_∘)( p_∘ (1-p_∙))^s_2-s_1-1≥ (p_∙ -p_∘)( p_∘ (1-p_∙))^2ℓ_g^20.

Next, observe that E_1-5 and E_7 are measurable with respect to the σ
-algebra generated by ℱ_s_1 and (η^±_t)_s_1≤ t≤ s_2 owing to (<ref>), (<ref>),
 (<ref>), (<ref>),
 (<ref>) and (<ref>). Combining this with (<ref>), and recalling the value of δ' from <ref>, we obtain that 

    (E_1-7)
       ≥( p_∘ (1-p_∙))^2ℓ_g^20δ'/4 ≥( p_∘ (1-p_∙))^3ℓ_g^20≥exp(-ℓ_g^21),

where, in the last two inequalities, we took L (hence ℓ_g) large enough. 

Recalling E_8 from (<ref>) along with the coupling defined in (<ref>) and using that E_1-7∈ℱ_s_2, we can apply <ref>, and obtain that, -a.s. on E_1-7, for large enough L (owing to (<ref>) and (<ref>)),

    ( . E_8^c| ℱ_s_2)≤SEPcoupling2× 3(ν+1)T(s_3-s_2)exp(-(SEPcoupling2(1+ν^-1))^-1ϵ^2 (s_3-s_2)^1/4)≤exp(-ℓ_g^4),

which implies that

    ( . E_8^c| E_1-7)≤exp(-ℓ_g^4).

Next, we control the probability of E_10 defined at (<ref>). To do so, we take a union bound over ℓ'∈ [⌊⌊ (log L)^2⌋/2⌋,⌊ (log L)^2⌋] and, using that (η_0^-,η_0^+) is (M,L)-balanced, we apply <ref> twice for any fixed ℓ' in this interval: once with (η_0, ρ, ε)=(η^-_0,ρ,ϵ/20 ), once with (η_0, ρ, ε)=(η^+_0,ρ+ϵ,ϵ/20 ) and both times with (ℓ,H,t)=(⌊ (log L)^2⌋, M, s_3). Note once again that for L large enough by (<ref>) and (<ref>), we have M>H>4ν t>densitystableℓ^2ε^-2(1+|log^3(ν t)|) and ℓ'≤ℓ_g^2≤√(t), as required for <ref> to apply. This yields, applying a union bound over the values of ℓ', that for large enough L (recalling that M≤ 20(ν+1)L),

    (E_10^c) ≤ 8M⌊ (log L)^2⌋exp(-densitystableexpoϵ^2 ⌊log^2 L⌋ /400)≤exp(-ℓ_g^1500).
 
Finally, recalling the coupling (<ref>) (together with (<ref>), (<ref>) and (<ref>)), we have by <ref>, more precisely by (<ref>), for large enough L,

    (E_9^c |  E_1-8∩ E_10)≤ 20Texp(-ν(T-s_3)/4)≤exp(-ℓ_g^10^5).

Putting together (<ref>), (<ref>), (<ref>) and (<ref>), we obtain (<ref>), as desired. 




Proof of (<ref>). We bound individually the six terms comprising S on the left-hand side of (<ref>). The first of these is already controlled by (<ref>). Recall the coupling defined in (<ref>) together with the definitions of E_1, E_2 and E_2,bis in (<ref>), (<ref>) and (<ref>). Observe that by (<ref>) and <ref>, we have -a.s. on E_1∩ E_2^c that ( E_2,bis^c| ℱ_s_0)≤ 20exp( -ν (T-s_0)/4 ). Hence for large enough L, by (<ref>) and (<ref>), this yields

    (E_1∩ E_2^c∩ E_2,bis^c)≤exp(-ℓ_g^10^5).

Recall now the coupling (<ref>) and the definition (<ref>) of E_3. By (<ref>) which is in force, we have

    (E_1-2∩ E_3^c)≤ 20exp(-νℓ_g ⌊ s_1/ℓ_g ⌋ /4 )≤exp(-ℓ_g^10^5),

for L large enough due to (<ref>) and (<ref>). Next, remark that 

    E_1-3∩ E_4-5^c∩ E_4,bis^c ⊆{E_1-4∩ E_5^c }∪{E_1-3∩ E_4^c∩ E_4,bis^c }.

On one hand, by (<ref>) and <ref> (recalling (<ref>)) we have

    (E_1-4∩ E_5^c)≤ 20exp(-ν (s_2-s_1)⌊ s_1/(s_2-s_1)⌋/4).

On the other hand, by (<ref>) and <ref> (recalling (<ref>)), we have

    (E_1-3∩ E_4^c∩ E_4,bis^c )≤ 20exp(-ν (T-s_1)/4)

Together, (<ref>), (<ref>) and (<ref>) yield that

    (E_1-3∩ E_4-5^c∩ E_4,bis^c)≤exp(-ℓ_g^10^5),

for L large enough, again via (<ref>) and (<ref>). Similarly, by (<ref>), <ref> and (<ref>), for L large enough we have that

    (E_1-5∩ E_6-7^c∩ E_6,bis^c)≤exp(-ℓ_g^10^5).






In view of (<ref>), putting together (<ref>), (<ref>), (<ref>), (<ref>) and (<ref>) yields that

    S≤(E_1-7∩ E_8-9^c)+5exp(-ℓ_g^10^5).

By (<ref>), which has been already established, we know that 5exp(-ℓ_g^10^5)≤(E_1-9)/(20T) for L large enough by (<ref>). Hence, in order to conclude the proof, it is enough to show that
(E_1-7∩ E_8-9^c)≤(E_1-9)/(20T),  or equivalently that

    (E_8-9 |  E_1-7)≥ 1-(20T)^-1.

Indeed,

    (E_8-9 |  E_1-7)= (E_8 |  E_1-7)(E_9 |  E_1-8)=(E_8 |  E_1-7)( E_1-9 |  E_1-8∩ E_10 )( E_1-8∩ E_10 )/( E_1-8)
    ≥(E_8 |  E_1-7)( E_1-9 |  E_1-8∩ E_10 )(1- (E_10^c)/( E_1-9)) 
    ≥(1-exp(-ℓ_g^4))(1-exp(-ℓ_g^10^5))(1-exp(-ℓ_g^1500)exp(ℓ_g^22)),

by virtue of (<ref>), (<ref>), (<ref>) and (<ref>) in the last line. For large enough  L (recalling (<ref>) and (<ref>)), this readily yields (<ref>) and concludes the proof of (<ref>).












Part V: Proof of (<ref>). 


Recall the event E_restart from (<ref>). The proof of (<ref>) is relatively straightforward at this point, we just need to keep careful track of those events in the above construction that can force us out of the event E_restart; this is key to get the rapid decay in (<ref>). First note that E_neutral⊆ E_2,bis∪ E_4,bis∪ E_6,bis by (<ref>), so that by (<ref>), (<ref>), (<ref>)  and (<ref>) (and using that |Y_T^±| ≤ T along with (<ref>)), E_restart holds on E_neutral for large enough L (tacitly assumed in the sequel), hence E_restart^c can only happen on E_good∪ E_bad. As we now explain, looking at the decomposition of E_good and E_bad at (<ref>) and (<ref>), and inspecting closely the construction η^± (and Y^±), especially in Part I of the proof, starting with the paragraph of (<ref>) until (<ref>), one notices that E_restart^c can in fact only happen:


  (i) on all but the last event (i.e. all but E_1-7∩ E_8-9^c) defining E_bad at (<ref>), or

  (ii) on E_1-7∩ E_10^c (see (<ref>)), or

  (iii) on E_1-7∩ E_8^c∩  E_10 if the coupling <ref> applied at (<ref>) fails, i.e. if the event

    E_11def.={η^+_T (· -T)|_[-M+T+4ν T,M-T-4ν T ]≽η^-_ T (· +T)|_[-M+T+4ν T,M-T-4ν T ]}

(cf. (<ref>)) does not occur, or

  (iv) on E_1-8∩ E_9^c∩ E_10, or

  (v) on E_1-10 if the coupling <ref> (more precisely (<ref>)) applied at (<ref>) fails, i.e. if the event

    E_12def.={η^+_ T (· +Y^-_s_1+ℓ_g^20)|_I≽η^-_ T (· +Y^-_s_1-ℓ_g^20)|_I }

with I= [-M+T+6ν T,M-T-6ν T ] does not occur.

We now detail how the cases (i)-(v) arise. First note that, since E_restart⊂ (E_bad∪ E_good) as established above, and since E_good= E_1-9 by definition (see (<ref>)), after discarding item (i) from the above list it only remains to investigate matters on the event E_1-7, and the cases considered in items (ii)-(v) indeed form a partition of this event, save for the additional specifications (“if the coupling...”) in items (iii) and (v), which we now discuss. For item (iii), note indeed that if E_1-7∩ E_8^c∩  E_10⊆ E_bad holds (see (<ref>)) then Y^+_T=Y^-_T-2T by Lemma <ref>, and that since | Y^-_T|≤ T, if in addition E_11 holds then so does E_restart in view of (<ref>). Similarly, regarding item (v), we have by (<ref>) that E_1-10⊆ E_good so that if E_1-10 holds, Y^+_T=Y^-_T+2ℓ_g^20 by Lemma <ref>. Since | Y^-_T-(Y^-_s_1-ℓ_g^20)|≤ T-s_1+ℓ_g^20≤ T, if in addition E_12 occurs then E_restart occurs as well.

Combining items (i)-(v) above and recalling (<ref>) in the context of item (i), by a union bound we have that 

    (E_restart^c)≤(E_1^c) +(E_1∩ E_2^c∩ E_2,bis^c )  
    +(E_1-2∩ E_3^c) +(E_1-3∩ E_4,5^c∩ E_4,bis^c )
     +(E_1-5∩ E_6-7^c∩ E_6,bis^c)   + (E_10^c)
    
    +(E_1-8∩ E_9^c∩ E_10)+(E_1-7∩ E_8^c∩ E_10∩ E_11^c)+(E_1-8∩ E_10∩ E_12^c).

By (<ref>), (<ref>), (<ref>), (<ref>), (<ref>),
 (<ref>) and (<ref>), for large enough L we obtain that

    (E_restart^c)≤ 7exp(-ℓ_g^1500)+Q(E_1-7∩ E_10∩ E_8^c∩ E_11^c)+(E_1-8∩ E_10∩ E_12^c).

As to the last two terms in (<ref>), using the coupling defined in (<ref>) and <ref>, we get 

    Q( E_11^c | E_1-7∩ E_8^c∩ E_10)≤SEPcoupling2 TMexp(-(SEPcoupling2(1+ν^-1))^-1ϵ^2(T-s_3)^1/4)
    ≤ C_3 2ℓ_g^10^6· 20(ν+1) L ·exp(-(SEPcoupling2(1+ν^-1))^-1ϵ^2ℓ_g^2· 10^5) ≤exp(-ℓ_g^10^5),

where we used (<ref>)-(<ref>), the fact that M≤ 20(ν +1) L and took L large enough.
Similarly, using the coupling defined in (<ref>) and <ref> (more precisely (<ref>)), we obtain that

    Q( E_12^c | E_1-8∩ E_10)≤ 5SEPcoupling2ℓ_G^1/20 Mexp(- (SEPcoupling2(1+ν^-1))^-1ϵ^2 ℓ_G^1/100)≤exp(-ℓ_g^2· 10^3).

Finally, putting (<ref>), (<ref>) and (<ref>) together, and using (<ref>) with L large enough, leads to (E_restart^c)≤ L^-100.
This concludes the proof of (<ref>) and thus of Lemma <ref>, taking L_2 large enough so that (<ref>)-(<ref>) (which represent a finite number of constraints) hold.



In the coupling ℚ constructed in Lemma <ref>, U is a priori not independent from (η^+,η^-); for instance a synchronous evolution of η^+(·+2ℓ_g^20) and η^- after s_3 could indicate that E_6, which depends on U during [s_1,s_2], has happened.








































































 §.§ Proof of Proposition <ref>




Let L≥ 1 be an integer satisfying L≥ L_2(ρ,ϵ,ν), where L_2 is given by Lemma <ref>. Let k:=⌊ L/T⌋, with T as defined in (<ref>). We start with a brief overview of the proof. To deduce (<ref>), we will couple two walks X^+∼ℙ^ρ+ϵ and X^-∼ℙ^ρ on the time interval [0,iT], 1≤ i ≤ k, recursively in i. The processes X^± will be specified in terms of  associated environments η̂^+∼𝐏^ρ+ϵ, η̂^-∼𝐏^ρ, and an i.i.d. array U=(U_w)_w∈𝕃 using Lemma <ref> repeatedly, cf. (<ref>)-(<ref>). We will denote  the associated coupling measure defined below, which will also comprise associated auxiliary walks Y^± that will be defined using the construction of Y^± in Section <ref>, iterated over i and allow to keep control on the gap between X^+ and X^- via a combination of (<ref>)-(<ref>). The very possibility of iteration is guaranteed by the high-probability event E_restart in (<ref>).


We now proceed to make the above precise.  For later reference we set M_i=20(ν+1) L-(8ν+3)i, for i∈{0,…,k-1}. We further recall the filtration ℱ_t defined in (<ref>) and write ℱ_t below when adding hats to all processes involved. Finally, for all i∈{0,…,k-1}, let

    B_idef.=⋂_j=0^i {  ( η̂^+_jT(· +Y^+_jT),η̂^-_jT( · + Y^-_jT)   is (M_j,L)-balanced}

(see items (i)-(iii) above Lemma <ref> for notation).

 By successive extensions of , we will construct a coupling such that the following hold for all L ≥ L_2 (as supplied by Lemma <ref>) and i∈{0,…, k}:



  (-1) The processes (η̂^+_t, η̂^-_t)_0≤ t≤ iT, (U_w)_w∈𝕃, π_2(w)≤ iT-1 (absent when i=0) and (X^±_t)_0≤ t≤ iT are defined under  with the correct marginal laws. That is, η̂^+_0∼μ_ρ+ϵ, η̂^-_0∼μ_ρ and (η̂^±_t)_0< t≤ iT has the same law as (the restriction to [0,iT]) of η^± under 𝐏^η̂_0^±. Moreover, (U_w)_w∈𝕃, π_2(w)≤ iT-1 are i.i.d. uniform variables on [0,1], and given η̂_0^±, (X^±_t)_0≤ t≤ iT is ℱ_iT-measurable and has the law of (the restriction to [0,iT] of) X^± under ℙ^η̂_0^±.

  (-2) The processes (Y^±_t)_0≤ t≤ iT are ℱ_iT-measurable and X^-_iT≤Y^-_iT and X^+_iT≥Y^+_iT hold -a.s.

  (-3) Y^+_0= Y^-_0=0, and if i ≥1, with B_i as in (<ref>),

    𝔼^[  . (Y^+_iT- Y^+_(i-1)T)-(Y^-_iT- Y^-_(i-1)T)| ℱ_(i-1)T] 1_B_i-1≥exp(-(log L)^1/20).


  (-4) (B_0^c)=0 and if i ≥ 1, (B_i^c | B_i-1) ≤ L^-100.





For i=0, we simply couple under  two configurations η̂^+_0∼μ_ρ+ϵ and η̂^-_0∼μ_ρ such that a.s. η̂^+_0(x)≥η̂^-_0(x) for all x∈ℤ, which we can do with probability one by (<ref>). We set X^+_0=X^-_0=Y^+_0=Y^-_0=0. Thus (-1) and (-2) are satisfied, and (-3) is trivial. Finally (B_0^c)=0 since 
η̂^±_0 are in particular (M_0,L)-balanced, whence (-4) holds.


Assume by induction that for some i∈{0,…, k-1}, we have constructed a coupling  with the above properties. We now proceed to extend  so as to have (-1)-(-4) with (i+1) in place of i.
We first specify matters on  the event B_i^c. Conditionally on ℱ_iT, if B_i^c occurs, we let η̂^+_t and η̂^-_t evolve independently for iT< t≤ (i+1)T according to 𝐏^η̂^+_iT and 𝐏^η̂^-_iT respectively, and independently of this, we choose U_w as uniform random variables on [0,1] in an i.i.d. manner, for w such that iT≤π_2(w)≤ (i+1)T -1. On B_i^c, we further let Y^+_iT+t=Y^+_iT-t and Y^-_iT+t=Y^-_iT+t, for all 0 < t≤ T and (X^±_t)_iT≤ t≤ (i+1)T evolve as in (<ref>) and (<ref>) with (η^±,U) instead of (η,U). With these choices it is clear that the inequalities in (-2) hold on B_i^c, since for instance Y^+_(i+1)T≤Y^+_iT-T ≤ X^+_iT-T≤ X^+_(i+1)T -a.s., using the induction hypothesis and the fact that increments of X^+ are  bounded from below by -1. The inequality X^-_(i+1)T≤Y^-_(i+1)T is derived similarly.


We now turn to the case that B_i occurs, which brings into play Lemma <ref>.
Conditionally on ℱ_iT and on the event B_i, we couple (x,t)↦η̂^+_iT+t(x+Y^+_iT) and (x,t)↦η̂^-_iT+t(x+Y^-_iT) for x∈ℤ and t∈[0,iT], as well as ( U_w+(0,iT): w ∈𝕃,  π_2(w)≤ T -1) following the coupling of (η^+,η^-, U) provided by Lemma <ref>, with the choice M=M_j. The requirement of (M,L)-balancedness of the initial condition needed for Lemma <ref> to apply is precisely provided by B_i, cf. (<ref>).

Combining (<ref>), the Markov property (<ref>) applied at time iT, and in view of the choices made on B_i^c, it readily follows that the processes
 (η̂^+_t, η̂^-_t)_0≤ t≤ (i+1)T, (U_w)_w∈𝕃, π_2(w)≤ (i+1)T-1 thereby defined have the marginal laws prescribed in (-1). Moreover, by   above application of Lemma <ref>, the processes X^± and Y^± satisfying all of (<ref>)-(<ref>) are declared. Thus, setting 
 
    X^±_iT+t=X^±_iT+X^±_t,  Y^±_iT+t=Y^±_iT+Y^±_t,   for all 0 ≤ t ≤ T,

 it readily follows, combining (<ref>) and the induction assumption on the law of 
 (η̂^±_t)_0≤ t≤ iT, (X^±_t)_0≤ t≤ iT, combined with the Markov property (<ref>) and that of the quenched law, that (X^±_t)_0≤ t≤ (i+1)T declared by (<ref>)
 has the desired marginal law, thus completing the verification of 
 (-1) with (i+1) in place of i. Next, we show (-3) and (-4), before returning to (-2). Since Y^±_(i+1)T-Y^±_iT = Y^±_T by (<ref>), the inequality (<ref>) with (i+1) in place of i is an immediate consequence of (<ref>). Hence  
(-3) holds. Finally, by construction of the coupling extension on the event B_i, which uses Lemma <ref>, and in view of (<ref>) and
 (<ref>), the failure of B_i+1 on the event B_i amounts to the failure of E_restart in (<ref>), from which (-4) 
 follows with (i+1) in place of i. 

 
 It remains to show that (-2) holds with (i+1) in place of i. To this effect, we introduce two auxiliary processes (Z^±_t)_0 ≤ t ≤ (i+1)T, defined as
 
    Z^±_t = Y^±_t,     if  0 ≤ t ≤ iT,
    Y^±_iT + X_t^± ,     if  0 < t ≤ T.

 Combining the induction assumption (-2), the definition of Y^±_t and Z^±_t in (<ref>) and (<ref>) (the latter implying in particular that Z^±_iT= Y^±_iT), one readily deduces from property (<ref>) the ℚ-almost sure inequalities 
 
    Z^-_(i+1)T≤Y^-_(i+1)T and Y^+_(i+1)T≤Z^+_(i+1)T.
 To deduce from this the analogous inequalities with X in place of Z, we apply Lemma <ref>, with (X, X)= (Z^+, X^+), η= η̃= η^+ (whence (<ref>) plainly holds), π_1(w')= Z^+_iT= Y^+_iT, π_1(w)= X^+_iT, π_2(w)=π_2(w') and K= ℤ×[iT, (i+1)T] to deduce that Z^+_(i+1)T≤X^+_(i+1)T holds ℚ-a.s. Note that the condition
  π_1(w')≤π_1(w) necessary for Lemma <ref> to apply is in force by induction hypothesis in (-2).  Together with (<ref>), this yields one of the desired inequalities in (-2) with i+1 in place of i. The other one is obtained in a similar way using Lemma <ref>. This completes the proof of the induction step.
  

We now use the coupling ℚ, which satisfies 
 (-1)-(-4) for all 0 ≤ i ≤ k (and L ≥ L_2), to complete the proof of (<ref>).
To this end, we first extend the laws of X_t^± to all t >kT using the Markov property, by sampling X^±_kT+ · independently conditionally on ℱ_kT. In particular, recalling that k=⌊ L/T⌋, this implies that X_L^± is declared under ℚ. We thus proceed to derive a suitable lower bound on 𝔼^[X_L^+-X_L^-], which is well-defined, and from which 
(<ref>) will follow. 

Using that |X_n+1^± - X_n^±| ≤ 1 for any n ≥ 0, we obtain (with k=⌊ L/T⌋) that

    𝔼^[X_L^+-X_L^-]  + 2T ≥𝔼^[X_L^+-X_L^-] + 2(L-kT) ≥𝔼^[   X^+_kT-X^-_kT] 
    (-2)≥𝔼^[  Y^+_kT-Y^-_kT]
     ≥∑_1≤ i ≤ k𝔼^[ (Y^+_iT- Y^+_(i-1)T)-(Y^-_iT- Y^-_(i-1)T)   ]
    (-3)≥ ke^-(log L)^1/20 - 2T ∑_1 ≤ i ≤ k(B_i-1^c) ≥L/2Te^-(log L)^1/20 - 2L(B_k-1^c),

 for large enough L, where, in the second inequality of the second line, we have used that Y^±_0=0, see (-3), and in the last line, we have first used that the difference of increments is deterministically bounded from below
 by -2T (see (<ref>) and Lemma <ref>), and for the last inequality that the events B_i^c are increasing in i, cf. (<ref>). We also used in various places that L-T≤ kT≤ L.
 
It remains to suitably estimate the probability (B_k-1^c) appearing in the last line of (<ref>), for which we use (-4) and a straightforward induction argument to bound

    (B_k-1^c)≤(B_k-1^c | B_k-2) + 
    (B_k-2^c) (-4)≤ L^-100 + (B_k-2^c) ≤…≤   (k-1)L^-100≤ L^-99,

using also in the penultimate step that (B_0^c)=0. Feeding this into (<ref>) yields that

In order to do this, let us define the event

    B=⋂_(y,j)   {η̂^+_j([y,  y+⌊(log L)^2⌋-1]  ) ≥ (ρ+99ϵ100) ⌊(log L)^2⌋}
       ∩{η̂^-_j([y  ,  y+⌊(log L)^2⌋-1]  ) ≤ (ρ+ϵ100) ⌊(log L)^2⌋},

where the intersection is taken over (y,j) ∈ [-20(ν+1)L,20(ν+1)L]× [0,L].
Note that (B_0^c∩ B)=0 by our initial coupling of η̂^+_0 and η̂^-_0. Thus we have 

    (B_k-1^c)≤(B^c )+∑_i=1^k-1(B_i^c | B_i-1∩ B).

On one hand, (<ref>) yields (for L large enough):

    max_i=1^k-1(B_i^c | B_i-1∩ B)≤ L^-100.

On the other hand, by <ref> applied with (η_0,ρ,ε,ℓ)=(η^+_j(· +y),ρ+ϵ,ϵ, ⌊ (log L)^2⌋) and with (η_0,ρ,ε,ℓ)=(η^-_j(· +y),ρ,ϵ, ⌊ (log L)^2⌋) for (y,j)∈ [-20(ν+1)L, 20(ν+1)L]× [0,L], and by a union bound over all such (y,j), we have

    (B^c)≤ 4(40(ν+1)L+1)(L+1)exp(-densitydev⌊ (log L)^2⌋/10000) ≤  L^-100,

for L large enough.  Injecting (<ref>) and (<ref>) into (<ref>), we obtain

    (B_k-1^c)≤ L^-100+ (k-1)L^-100≤ L^-99

for L large enough. Using the above, together with (<ref>) and (<ref>), we have that


    𝔼^[X_L^+-X_L^-]   ≥L/2Te^-(log L)^1/20  - 2L^-98 -2T ≥ 3C:approx (log L)^100,

as soon as L is large enough (recall T from (<ref>)). Dividing by L and applying (<ref>) whilst observing that X_L^+ has the same law under  as X_L under ^ρ+ϵ, L and  X_L^- has the same law under  as X_L under ^ρ, L, (<ref>) implies that

    v_L(ρ+δ)-v_L(ρ)≥3C:approxL^-1 (log L)^100,

which concludes the proof of Proposition <ref>. 


As mentioned at (<ref>), we prove in fact a much stronger statement than Proposition <ref>, owing to (<ref>), namely that 

    v_L(ρ+δ)-v_L(ρ)≥ L^o(1)

where the o(1) denotes a negative quantity that goes to 0 as L→∞. This is however insufficient to imply directly Theorem <ref>, and the renormalisation in Section <ref> is still essential to improve (<ref>) to a right-hand side bounded away from 0 as L→∞. 





[Necessity for couplings with quenched initial condition]
We explain here the main reason why we need quenched conditions for our couplings. In short, this is due to the lack of an invariant measure (or reasonable proxy thereof) from the point of view of the walk. 

More precisely, abbreviating t=s_2-s_1, the only a-priori lower bound we have for the probability that X^ρ and X^ρ+ε drift away linearly from each other during [s_1,s_2] (corresponding to ℚ(E_6) at (<ref>)) is exp(-Ct ) for some large constant C by uniform ellipticity – we are in fact precisely trying to derive a better bound in this section. 

But this gap is necessary to create a difference between X^ρ+ϵ-X^ρ on a time interval of length T. Hence, to accrue a significant gain in expectation between X^ρ+ϵ-X^ρ, we need to repeat this at least exp(Ct) times. Thus, during that time, X^ρ and X^ρ+ϵ could straddle an interval of width at least exp(C t). The main issue is that we have no a priori information on their local environment (which would not be the case if we had access to an invariant measure and could estimate the speed of convergence to it). 
Hence if the coupling <ref>, that we use between s_1 and s_2 on a interval much narrower than exp(C t), was only valid under the annealed product Bernoulli initial condition (which is a priori not what the walk sees), we could resort to the annealed-to-quenched trick (via Markov's inequality) and a union bound over exp(Ct) intervals to control the probability that the coupling fails. However, the failure probability at <ref> is exp(-C't^1/4) ≫exp(-Ct), hence we cannot obtain any non-trivial bound this way. Note that this does not depend on the choice of t. Furthermore due to the diffusivity of the environment particles and large deviation considerations, it seems unlikely that one could improve the bound of <ref> beyond exp(-Ct^1/2).

This is why we resort to some quenched control, cf. items (i)-(iii) above Lemma <ref>, and also (<ref>). The empirical density was the most accessible and relevant statistic (in particular if the environment is conservative, as is the case of SEP). For similar reasons, we had to establish <ref> in a quenched setting, to ensure that whatever the distribution of the environment around the walker at time iT for some i≥ 1 (as long as it is balanced), there is still a uniformly low probability not to have the required empirical density at time s_1 (see (<ref>)) to perform the coupling of <ref>. Of course the necessity for quenched couplings encapsulated in <ref> and in particular <ref>, means that we have (more) work to do in order to verify this in specific instances, as we do for SEP in the next section.









§ EXCLUSION PROCESS AND COUPLINGS


We start by giving in <ref> a formal definition of the main environment η of interest in this article, the symmetric simple exclusion process (SEP), and first check that it fits the setup of <ref>, in particular, that the basic properties (<ref>)–(<ref>) listed in <ref> hold. The main result of this section, proved in <ref>, is to show that the SEP satisfies the conditions <ref>-<ref> stated in <ref>; see Proposition <ref> below. This implies that our main result, Theorem <ref>, applies in this case; cf. also Theorem <ref> and its proof in <ref>. We refer to Appendix <ref> for another environment η of interest which fits this framework.



 §.§ Definition of SEP and basic properties
 

We fix a parameter ν>0, which will be constant throughout this section and often implicit in our notation. The (rate ν) symmetric simple exclusion process (SEP) is the Markov
process on the state space {0,1}^ℤ (tacitly viewed as a subset of Σ, cf. <ref>) with (pre-)generator

    L f(η)=∑_x,y∈ℤ: |x-y|=1_{η(x)=1,η(y)=0}ν/2(f(η_xy)-f(η)),

for η∈{0,1}^ℤ and f in the domain of L, where η_xy is the configuration obtained from η by exchanging the states of x and y, i.e. such that η_xy(x)=η(y), η_xy(y)=η(x) and η_xy(z)=η(z) for all z∈ℤ∖{x,y}; see <cit.>. We denote 𝐏_SEP^η_0 its canonical law with initial configuration η_0 and drop the subscript SEP whenever there is no risk of confusion. In words, (<ref>) entails that the vertices x such that η(x)=1, which can be seen as the locations of particles evolve like continuous-time symmetric simple random walks on ℤ with rate ν that obey the exclusion rule; that is, particles are only allowed to jump onto empty locations.

It will often be useful to consider the interchange process on ℤ, with generator L defined as in (<ref>) but omitting the exclusion constraint {η(x)=1,η(y)=0}, which interchanges the state of neighbors x and y independently at rate ν/2. We will use the following specific construction of this process. 
Let E={{x,x+1}: x ∈ℤ} denote the set of edges on ℤ and 𝐏 be a probability governing independent Poisson counting processes 𝒫_e of intensity ν/2 on ℝ_+ attached to every edge e ∈ E. For any given η_0∈{0,1}^ℤ, one defines (η_t)_t ≥ 0 under 𝐏 by exchanging the states of η at x and y every time the `clock rings' for 𝒫_e, where e={x,y}. This is well-defined up to a set of measure zero. Then for every η_0 ∈{0,1}^ℤ,

    (η_t)_t ≥ 0 has the same law under 𝐏 and 𝐏_SEP^η_0.

 This follows upon observing that the states of neighboring sites suffering the exclusion constraint can also be exchanged. For our purpose, these two processes are equivalent, but note that they differ when one distinguishes the particles of the system (for instance studying the motion of a tagged particle).

A useful feature of this alternative description is the following. A particle trajectory of the interchange process is obtained by following the trajectory of a state x ∈ℤ such that η_0(x)=1 (a particle) under
𝐏. We won't define this formally but roughly speaking, if e and e' are the two edges incident on x, one waits until the minimum of the first arrival times of these two processes (which is an exponential variable with parameter ν) and jumps across the corresponding edge. Then one repeats this procedure. In particular, it immediately follows that

    12.5cmfor each x such that η_0(x)=1, the particle trajectory of x under 𝐏 follows the law of a continuous time simple random walk with jump rate ν.

Recalling the properties (<ref>)–(<ref>) from <ref>, we first record the following fact.



With

    μ_ρ = ((1- ρ) δ_0 + ρδ_1 )^⊗ℤ,   ρ∈ J def.= (0,1),

the measures (𝐏^η_0: η_0 ∈{0,1}^ℤ) with 𝐏^η_0=𝐏_SEP^η_0 and (μ_ρ: ρ∈ J) satisfy all of  (<ref>)–(<ref>).

 Property (<ref>) is classical, see <cit.> along with Example 3.1(d), p.21 of the same reference. So is (<ref>), i.e. the stationarity of the measure μ_ρ in (<ref>), see <cit.>. The required coupling (for two given initial configurations η_0'  ≼η_0) needed to verify the quenched monotonicity asserted in (<ref>),i) is simply obtained by realizing the process η= (η_t)_t ≥ 0 under the auxiliary measure 𝐏^η_0' and 𝐏^η_0 using the same Poisson processes (𝒫_e). In particular this measure yields a coupling over all possible initial distributions, including η_0 and η_0', and this coupling is seen to preserve the partial order η_0'  ≼η_0 for all t>0. The monotonicity in (<ref>),ii) is classical. Lastly,  upon observing that η_0[0,ℓ-1] is a binomial random variable with parameters ℓ and ρ under 𝐏_ρ, property (<ref>) is obtained by combining (<ref>) and (<ref>), which are well-known large deviation estimates.


In anticipation of <ref>, we now collect a simple lemma to bound the linear deviations of an SEP particle, which we will routinely use in our couplings below.


Let Z=(Z_t)_t≥ 0 denote a simple random walk on ℤ with jump rate ν, starting from 0 at time 0, with law denoted by P. For all t>0 and k,a∈:

    P(max_0≤ s≤ t| Z_s|≥ 2kν t+a) 
    ≤ P(Z makes more than 2kν t+a jumps during [0,t])≤ e^-(2kν t+a)/8.



The first inequality is immediate since Z only performs nearest-neighbor jumps. As for the second one, remark that the number N of jumps performed by Z during [0,t] is a Poisson random variable with parameter ν t.  Hence by (<ref>) applied with λ =ν t and x=(2k-1)ν t +a≥ (2kν t+a)/2> 0, we obtain that  

    P(N≥ 2kν t+a)≤exp( -((2k-1)ν t+a)^2/2(2kν t+a))≤exp (-(2kν t+a)/8),

and the conclusion follows. 








 §.§ Conditions <ref>–<ref> for SEP
 

We now proceed to verify that the conditions introduced in <ref> all hold for the exclusion process introduced in <ref>, as summarized in the next proposition. Its proof occupies the bulk of this section. These properties (above all, <ref> and <ref>) are of independent interest.


 
For (𝐏^η_0: η_0 ∈{0,1}^ℤ_+) with 𝐏^η_0 =𝐏^η_0_SEP, J = (0,1) (cf. (<ref>)), and with ν as appearing in (<ref>), all of <ref>, <ref>, <ref>, <ref> and <ref> hold.

 
 

This follows directly by combining Lemmas <ref>, <ref>, <ref>, <ref> and <ref> below.
 

We now proceed to investigate each of the relevant conditions separately. Throughout the remainder of this section, we work implicitly under the assumptions of Proposition <ref>. In particular, in stating that some property P `holds for SEP,' we mean precisely that P is verified for the choice (𝐏^η_0: η_0 ∈{0,1}^ℤ_+) with 𝐏^η_0 =𝐏^η_0_SEP for all ρ∈ J = (0,1), and with ν the rate parameter underlying the construction of SEP.



The condition <ref> holds for SEP, with no restriction on the choice of ℓ'≥ 1. 



We give a brief overview of the proof. A key idea is to exploit the fact that SEP particles, although not independent, are in fact `more regularly' spread out than a bunch of independent random walks (starting from the same initial positions), which is due to the inherent negative association of the SEP. This fact is implicit in the bound (<ref>) below, which is borrowed from <cit.> (itself inspired from <cit.>), the proof of which uses in a crucial way an inequality due to Liggett, see <cit.>, encapsulating this property. With this observation, it is enough to argue that after time t ≫ℓ^2 (where ℓ is the precision mesh of the empirical density of the initial configuration, as in <ref>), random walks have diffused enough to forget their initial positions and average their density, which follows from classical heat kernel estimates.



We focus on proving the upper inequality (i.e. when each η_0(I)≤ (ρ+ε)ℓ), and comment where necessary on the minor adjustments needed to derive the other inequality in the course of the proof. 
Let ρ,ε∈ (0,1), H,ℓ,t≥ 1 and η_0 be such that the conditions of <ref> hold. We will in fact show <ref> for an arbitrary value of ℓ'≥ 1 although the restriction to ℓ' ≤ℓ is sufficient for later purposes (note that the statement is empty if ℓ'>2(H-2ν t)). Thus, let ℓ'≥ 1 and ℐ denote the set of intervals of length ℓ' included in [-H+2ν t, H-2ν t], and define

    η̅_t(I)= ∑_x∈ I𝐏^η_0(η_t(x)=1),    I  ∈ℐ,

the average number of occupied sites of I after time t ≥ 0. Note that η̅_0(I)=η_0(I). 
By Lemma 2.3 of <cit.> (see also Lemma 5.4 of <cit.>) one knows that for all t ≥ 0 and suitable densitystableexpo∈ (0,∞),

    𝐏^η_0(η_t(I)≥η̅_t(I)+εℓ')≤exp(-densitystableexpoε^2ℓ')

(in fact the bound (<ref>) holds for any initial configuration η_0). Thus, if 

    max_I∈ℐη̅_t(I) ≤ (ρ+2 ε)ℓ',

under our assumptions on η_0 and t,
then (<ref>), a union bound over ℐ, and the upper bound on the maximum in (<ref>) yield that

    𝐏^η_0(max_I⊆ℐη_t(I)>(ρ+3ε)ℓ')≤ 2H  exp(-densitystableexpoε^2ℓ').

A companion inequality to (<ref>) can be deduced in a similar way using the lower bound on the minimum in (<ref>) and exploiting symmetry, i.e. rewriting {η_t(I)< (ρ-3ε) ℓ'} = {ξ_t(I)> ((1-ρ)+3ε) ℓ'} where ξ_t=1-η_t, while observing that (ξ_t)_t ≥0 has law 𝐏^ξ_0, cf. (<ref>). The conclusion <ref> then follows. 

Therefore, we are left with showing (<ref>). In view of (<ref>), it is enough to prove that for every x∈ [-H+2ν t, H- 2ν t], and under our assumptions on η_0 and t,

    𝐏^η_0(η_t(x)=1) ≤ρ +2ε.

Let (Z_s)_s≥ 0 denote a continuous-time symmetric simple random walk on ℤ with jump rate ν, defined under an auxiliary probability P, and let 
p_s(x,y)=P(Z_s=y | Z_0=x ), for x,y∈ℤ and s≥ 0 denote its transition probabilities, which are symmetric in x and y. Writing {η_t(x)=1} as the disjoint (due to the exclusion constraint) union over y ∈ℤ of the event that η_0(y)=1 and the particle starting at y is located at x at time t, it follows using (<ref>) that for all x∈ℤ,

    𝐏^η_0(η_t(x)=1)= ∑_y∈ℤp_t(y,x) η_0(y)= ∑_y∈ Sp_t(x,y),

where S:={y∈ℤ: η_0(y)=1} and we used reversibility in the last step. Using the rewrite (<ref>), we first show the upper bound in (<ref>). Let us define c_t=C:c-t√(ν tlog(ν t)), where the constant C:c-t>0 will be chosen below. Recalling that x∈  [-H+2ν t, H-2ν t], we cover the sites of [x-c_t ,x+c_t] ⊆ [-H,H] using intervals I_1, … , I_q all contained in this interval and each containing ℓ sites, with q=⌈ (2c_t +1)/ℓ⌉. We may assume that all but the last interval I_q are disjoint. For later reference, we note that | I_r∩ S|≤ (ϱ +ε)ℓ for all 1≤ r≤ q by assumption on η_0. By (<ref>), we have that

    𝐏^η_0(η_t(x)=1)≤∑_y∈ℤ∖ [x-c_t,x+c_t]   p_t(x,y)+∑_r=1^q∑_y∈ S∩ I_rp_t(x,y)

We will look at the two terms on the right-hand side separately. Using (<ref>)), one knows that with N denoting the number of jumps of a continuous time random walk with jump rate ν until time t>0, one has ℙ(A)≥ 1-Ce^-ν t/C with A { 2ν t/3≤ N≤ 4ν t/3}. Combining this with  the deviation estimate (<ref>) yields that

    ∑_y∈ℤ∖ [x-c_t,x+c_t]   p_t(x,y)=ℙ(A^c)+2∑_k=⌈ 2ν t/3⌉^⌊4ν t/3⌋ℙ(N=k) ∑_y'≥ c_t ℙ(  Bin(k,12)=y'+k2)
    ≤ Ce^-ν t/C+2∑_k=⌈ 2ν t/3⌉^⌊ 4ν t/3⌋ℙ(N=k) exp( -c_t^2/ 16 ν t)
    ≤ Ce^-ν t/C+2 exp( -C:c-t^2log(ν t)/16)
    ≤1/ν t≤ε/3,

where we choose C:c-t≥√(11), use  that ν t≥densitystable, thus choosing  densitystable large enough, and use the conditions from <ref> for the last inequality.

Next, we want to deal with the points in the interval [x-c_t,x+c_t]. Recall that  a continuous-time simple random walk with rate ν at time t has the same law as a rate 1 continuous-time simple random walk at time ν t. Hence, by  <cit.>,  for all x,y,z such that y,z∈ [x-c_t,x+c_t] and |z-y|≤ℓ,  using that c_t<ν t/2 for densitystable large enough, with C changing from line to line,

    p_t(x,y)/p_t(x,z)≤exp(        |x-z|^2-|x-y|^2/2ν t+C(1/√(ν t)+|x-y|^3+|x-z|^3/(ν t)^2)        )  
    ≤exp(      c  ℓ√(log(ν t))/√(ν t)+C1+log^3/2(ν t)/√(ν t)) ≤exp(  Cε/√(densitystable))≤ 1+ε/3,

where we used that 4ν t>densitystableℓ^2ε^-2log^3(ν t) and ℓ≥1, from  <ref>, and chose densitystable large enough. Using <cit.> again, we also have that, as soon as densitystable is large enough, using the conditions from <ref>,

    p_t(x,z)≤1/√(ν t)≤ε/3ℓ.

Now, recalling that the intervals I_r are disjoint for 1≤ r≤ q-1 and that they all have cardinality ℓ, using (<ref>) and (<ref>), we have that

    ∑_r=1^q∑_y∈ S∩ I_rp_t(x,y)
    ≤∑_r=1^q-1∑_y∈ S∩ I_rp_t(x,y) + ∑_y∈ S∩ I_qp_t(x,y)
    
    ≤(1+ε/3)∑_r=1^q-1∑_y∈ S∩ I_rmin_z∈ I_rp_t(x,z) + ∑_y∈ S∩ I_qε/3ℓ≤(1+ε/3)(ρ+ε)∑_r=1^q-1|I_r|min_z∈ I_rp_t(x,z) + ε |I_q|/3ℓ
    ≤(1+ε/3)(ρ+ε)∑_r=1^q-1∑_y∈ S∩ I_rp_t(x,y) + ε/3≤(1+ε/3)(ρ+ε) + ε/3.

Putting together (<ref>), (<ref>) and (<ref>), and using that ρ+ε≤ 1, we obtain

    𝐏^η_0(η_t(x)=1)≤ε/3+(1+ε/3)(ρ+ε) + ε/3≤ρ +2ε.

This yields the upper bound in (<ref>), and the upper inequality in <ref> follows.  


For the lower bound, which requires to change (<ref>) to ρ-2ε≤𝐏^η_0(η_t(x)=1), one uses the estimate 𝐏^η_0(η_t(x)=1)≥∑_r=1^q-1∑_y∈ S∩ I_rp_t(x,y) instead of (<ref>) and proceeds similarly as in (<ref>). 



The condition <ref> holds for SEP.




 
Recall the construction in (<ref>) of the SEP using 𝐏. Setting ℚ=𝐏, this yields a natural coupling of η and η' with marginal laws 𝐏^η_0 and 𝐏^η'_0, respectively, for any choice of initial distribution η_0 and η'_0. In words, the coupling ℚ identifies η and η' as interchange processes and uses the same Poisson processes (𝒫_e) on the edges of ℤ. Now if η_0 |_[-H, H]≽η_0' |_[-H, H], then under ℚ, we claim that

    {∃ x∈ [-H+2kν t ,H-2kν t ], s∈ [0,t]  ,  η_s(x)<η'_s(x) }⊆⋃_y: η'_0(y)=1, | y| >HE(y),

where E(y) is the event that the particle at y enters the interval [-H+2kν t ,H-2kν t ] before time (s≤)t. 
By (<ref>) with a=| y| -H, we have

    ℚ(E(y))≤exp (-(2kν t+| y| -H)/8).

Applying a union bound to (<ref>) and feeding (<ref>) thus yields that the probability of the complement of the event appearing on the left-hand side of (<ref>) is bounded from above by

    2 ∑_y=H^+∞ℚ(E(y)) ≤ 2 ∑_y'=0^+∞exp (-y'/8-kν t/4) ≤ 20exp(-kν t/4).



[Locality in <ref>]
 For later reference, we record the following locality property of the coupling ℚ constructed in the course of proving Lemma <ref>. Let E_H ⊂ E denote the edges having both endpoints in [-H,H]. Then the above argument continues to work for any specification of clock processes 𝒫_e, 𝒫_e' for e ∉ E_H for η and η', respectively, so long as (𝒫_e)_e ∈ E and (𝒫_e')_e ∈ E end up having the correct law. This observation will be important when several couplings are `concatenated,' as in the proof of Lemma <ref> below (see also Figure <ref>).














The condition <ref> holds for SEP. 


We first give a brief overview of the argument. Lemma <ref> corresponds to a quenched version of <cit.> by Baldasso and Teixeira, in which η_0 and η'_0 are sampled under 𝐏^ρ+ε and 𝐏^ρ respectively. We mostly follow their argument. Since fixing the initial environments induces some changes, and because we will use a variation of this proof to show <ref> for the SEP (Lemma <ref>), we detail below the coupling of η and η', seen as interchange processes. In doing so we also clarify an essential aspect of this coupling; see in particular (<ref>)-(<ref>) below.


 In a nutshell, the idea is to pair injectively each particle of η' with one of η at a relatively small distance (of order t^1/4), during a relatively long time (of order t^3/4), so that they perform independent random walks until they meet (which has a large probability to happen since t^3/4≫(t^1/4)^2), after which they coalesce, i.e. follow the same evolution. To make such a matching possible, we ensure that with large probability, η has more particles than η' on each interval of length roughly t^1/4. Within the present quenched framework, this property is now obtained by means of <ref>, which has already been proved; see Lemma <ref>. Since the probability that at least one particle of η' does not get paired, i.e. does not meet its match, is relatively high (polynomially small in t), we repeat this coupling; see also Figure <ref>.





 
Let ρ∈ J, ε∈ (0,1), and  H,t≥ 1 and η_0,η'_0 satisfy the conditions appearing in <ref>. Recall that 
    ℓ=⌊ t^1/4⌋ and let τ=ℓ^3.
 
We abbreviate I_s= [-H+2ν s, H-2ν s] for s ≥ 0 in the sequel.

Let ℚ= 𝐏⊗𝐏', where 𝐏' is a copy of 𝐏, with 𝐏, 𝐏' governing the independent processes (𝒫_e), (𝒫_e'), respectively, cf. above (<ref>). We will define a coupling of (η,η') under ℚ (to be precise, a suitable extension of ℚ carrying additional independent randomness), inductively in i over the time interval (iτ, (i+1)τ], for 0 ≤ i < ℓ. 
Suppose (η_[0, iτ], η_[0, iτ]' ) have been declared under ℚ for some 0 ≤ i < ℓ, with the correct marginal laws for η_[0, iτ] and η_[0, iτ]' (the case i=0 of this induction assumption holds trivially). We start by controlling the empirical densities of η and η' at time iτ, which are already defined under ℚ. The original proof of <cit.> uses the stationarity of 𝐏^ρ and 𝐏^ρ+ε and (<ref>), while we resort to <ref> (cf. (<ref>) below). Let 

    G_1,idef.={   for all I with I ⊂ I_iτ of length ⌊ℓ/2 ⌋≤ |I| ≤ℓ,
       one has that η_iτ(I)≥ (ρ+ε/2)|I| ≥η'_iτ(I)}.

Observe that G_1,0 is automatically satisfied by assumption on η_0 and η_0'.

We proceed to define ( η_i τ+t)_0 < t ≤τ and ( η'_i τ+t)_0 < t ≤τ under ℚ.
If G_1,i does not occur, we sample (η'_t+ i τ)_0 < t  ≤τ (and in fact for all t>0) in a manner as in (<ref>) using the processes (𝒫_e') after time τ_i, and similarly for (η_t+ i τ)_0 < t  ≤τ using (𝒫_e) instead. Thus in this case η' evolves independently from η from time τ_i on.

If on the other hand G_1,i occurs, we proceed as follows. 
Let Pai_s ⊂ [-H,H] denote the set 

    Pai_s= { x ∈ I_s:  η_s(x)= η_s'(x)=1  },

so that Pai_i τ is measurable relative to (η_i τ, η_i τ'). We refer to Pai_s as the set of paired particles (at time s). Let Π_s = { x ∈ I_s: η_s (x)=1} and Π_s' = { x ∈ I_s: η_s '(x)=1}. Observe that Pai_s⊂Π_s'. Our goal is to reduce the size of their difference as s= i τ for i=1,2,… and eventually achieve equality when i=ℓ.


To this effect, we first define a matching, i.e. an injective map ψ_i: Π_iτ' →Π_iτ, still measurable relative to (η_i τ, η_i τ'), as follows. The map ψ_i acts as identity map on Pai_i τ, a subset of both Π_iτ' and Π_iτ, cf. (<ref>). For each x∈Π_iτ' ∖Pai_i τ, ψ_i(x) is a point in Π_iτ∖Pai_i τ at distance at most ℓ from x. As we now briefly explain, owing to the occurrence of  G_1,i, this can be achieved in such a way that ψ_i is injective. To see this, first note that one can write I_iτ as disjoint union of intervals of length |I| ranging  in ⌊ℓ/2 ⌋≤ |I| ≤ℓ, as follows. One covers I_iτ with contiguous intervals of length ℓ starting at one boundary, leaving a remaining interval I_r at the other boundary of length less than ℓ. If I_r has length at least ⌊ℓ/2 ⌋, one simply adds it, else unless I_r is empty one cuts the penultimate interval into two halves of length at least ⌊ℓ/2 ⌋ each and merges I_r with the last of them. By construction any of the disjoint intervals I thereby obtained has length ⌊ℓ/2 ⌋≤ |I| ≤ℓ as required, and thus on the event G_1,i, see (<ref>), one knows that η_iτ(I) ≥η'_iτ(I). Since the I's are disjoint and their union is I_iτ, it follows that we can pair injectively each particle of Π_iτ' ∖Pai_i τ with a particle of Π_iτ∖Pai_i τ within the same interval. We now fix any such matching ψ_i and call any two particles (x,ψ_i(x)) ∈Π_iτ' ×Π_iτ matched. We note that |x-ψ_i(x)| ≤ℓ by construction.
 
 The evolution for ( η_i τ+s)_0 < s ≤τ and ( η'_i τ+s)_0 < s ≤τ under ℚ (and on G_1,i) is now prescribed as follows. Both ( η_i τ+s)_0 < s ≤τ and ( η'_i τ+s)_0 < s ≤τ will be realized as interchange processes as in (<ref>), thus it is sufficient to specify the relevant (Poisson) clock processes attached to each edge of ℤ.
Let E_H denote the set of edges of ℤ having both endpoints in [-H,H]. For e ∉ E_H, ( η_i τ+s)_0 < s ≤τ and ( η'_i τ+s)_0 < s ≤τ simply use the clocks of 𝒫_e∘θ_iτ and 𝒫_e'∘θ_iτ, respectively, where θ_s denotes the canonical time-shift of the process by s. It remains to specify the clock processes for e ∈ E_H.
Let 𝒫_e= 𝒫_e+ 𝒫_e'. All clock processes attached to edges e ∈ E_H will be defined via suitable thinning of 𝒫_e.

First, one orders chronologically all arrivals for the processes 𝒫_e∘θ_iτ = ( 𝒫_e(s+ i τ))_s ≥ 0 as e ∈ E_H varies  (there are countably many such times and they are a.s. different so this is well-defined on a set of full measure). Let σ_0=0 and σ_1,σ_2 etc. denote the chronologically ordered times thereby obtained. By suitable extension, ℚ is assumed to carry a family { X_n:   n ≥ 0 } of i.i.d. Bernoulli variables with  (X_n=1)= 1- (X_n=0)= 1/2. We regard X_n as the label attached to σ_n. Let ℛ_e be the thinned process obtained from 𝒫_e by only retaining arrivals with label X_n=1. Then,
 
    η_· + i τ uses the clock process ℛ_e for each e ∈ E_H (and 𝒫_e for each e ∉ E_H).

By elementary properties of Poisson processes and applying (<ref>), it follows that (η_s+ i τ)_0< s ≤τ has the correct conditional law given η_i τ; indeed by construction to each edge e of  one has associated independent Poisson processes having the correct intensity. 

The definition of ( η'_i τ+s)_0 < s ≤τ is analogous to (<ref>), and the clock process ℛ_e' for e ∈ E_H underlying the definition of ( η'_i τ+s)_0 < s ≤τ is specified as follows. For a particle x ∈Π_iτ' (resp. Π_iτ), let γ_i; ·'(x) (resp. γ_i;·(x)) denote its evolution
under η'_i τ+· (resp. η_i τ+·). Proceeding chronologically starting at n=1, one chooses whether the clock σ_n is retained or not according to the following rule. With e={x,y}∈ E_H denoting the edge of σ_n,

    if for some z ∈Π_iτ', γ'_i;σ_n-1(z)= γ_i;σ_n-1(ψ_i(z))  ∈{x,y},
       then σ_n is retained iff X_n=1, otherwise iff X_n=0;

 here we think of right-continuous trajectories so γ'_i;σ_n-1(z) is the position of the particle z after the (n-1)-th jump; in fact one could replace each occurrence of σ_n-1 in (<ref>) by an arbitrary time s with σ_n-1≤  s< σ_n, since there is no jump between those times. In words, at time σ_n-1, one inspects if at least one endpoint of e contains (the evolution to time s of) two matched particles, in which case the clock σ_n is retained if it has label 1 only. If no endpoint of e contains matched  particles the clock is retained if it has label 0. The process ( η'_i τ+s)_0 < s ≤τ then simply uses the clocks ℛ_e' on edges e ∈ E_H that are retained according to (<ref>) and such that σ_n < τ. We will now argue that

    given η'_i τ, the process ( η'_i τ+s)_0<s≤τ has law 𝐏^η'_i τ under ℚ.

To see this, one simply notes using a straightforward induction argument that the conditional law of ξ_n = 1{the n-th arrival in (𝒫)_e ∈ E_H is retained}  given ξ_1,…ξ_n-1, σ_1,…,σ_n, X_1,…, X_n-1 and ( η_i τ+t,η'_i τ+s )_0 < s ≤σ_n-1 is that of a Bernoulli-1/2 random variable. From this and the thinning property for Poisson processes it readily follows that ℛ' has the right law.


Overall we have now defined a coupling of (η,η') until time ℓτ≤ t. In case ℓτ < t we simply use the same process (𝒫_e) to define the evolution of both η and η' in the remaining time interval (ℓτ, t]. The Markov property (<ref>), (<ref>) and (<ref>) ensure that η,η' indeed have the desired marginals during [0,t].
In view of (<ref>), this immediately yields that

    {η_t | _[-H+4ν t, H-4ν t]≽η_t' | _[-H+4ν t, H- 4ν t]}^c ⊂{ (Π_t'∖Pai_t) ∩ [-H+4ν t, H- 4ν t] ≠∅}.

The key of the above construction is that the latter event forces one of three possible unlikely scenarios. Namely, as we explain below, one has that

    { (Π_t'∖Pai_t) ∩ [-H+4ν t, H- 4ν t] ≠∅}⊆  B_1 ∪ B_2 ∪ B_3,

where B_1=⋃_i=1^ℓ-1 G_1,i^c,

    B_2   =⋃_s=0^ t-1 {[ one particle of η'_s(ℤ∖ I_s) ends up;     in [-H+4 ν t,  H-4ν t] at time t ]},
    
    B_3   = B_1^c ∩{[           ∃ x ∈Π_0' s.t. γ_iτ'(x) ∈ I_iτ and; inf_ s ∈ [0, τ] Z_s^i(x)>0 for all 0 ≤ i < ℓ ]};
 
here γ_·'(x) refers to the evolution of particle x under η' and with x_i= γ_iτ'(x), one sets Z_s^i(x)= |γ_i;s'(x_i)- γ_i;s(ψ_i(x_i))|. In words Z_s^i follows the evolution of the difference between x_i, which is not paired at time iτ since Z_0^i(x) ≠ 0, and its match ψ_i(x_i), which is well-defined on the event B_1^c. Thus B_3 refers to the event that some particle x ∈Π_0' is found in I_iτ at time iτ for all i and never meets its match during the time interval (iτ, (i+1)τ].

We now explain (<ref>). To this effect we first observe that (<ref>) and (<ref>) ensure that two matched particles at some stage i follow the same evolution once they meet (and thus belong to Pai_s for all later times s) as long as they stay in I_s. Therefore, on the event B_1^c ∩ B_2^c, on which (due to occurrence of B_2^c) no unpaired η'-particle at time t can arise by drifting in from the side, meaning that such a particle cannot be seen in η'_s(ℤ∖ I_s) at any time 0 ≤ s <t,
the set (Π_t'∖Pai_t) ∩ [-H+4ν t, H- 4ν t] being non-empty requires at least one particle from Π_0' to never meet its match at any of the stages 1 ≤ i ≤ℓ (matching happens at all stages due to occurrence of B_1^c). That is, B_3 occurs, and  (<ref>) follows.

 
To finish the proof, we now bound the (bad) events appearing in (<ref>) separately. In view of (<ref>), we apply <ref> (which now holds on account of Lemma <ref>) to η' (resp. η) at time iτ, with (ρ+ε/8, ε/8) (resp. (ρ+7ε/8, ε/8)) instead of (ρ,ε),  with (H,ℓ, iτ ) instead of (H,ℓ,t) and with ℓ' ranging from ⌊ℓ/2⌋ to ℓ, which fulfils the conditions of <ref> if SEPcoupling is large enough so that H> 4ν t and

    min_1≤ i ≤ℓ^4-1 4ν iτ≥ 4ντ >  densitystableℓ^2ε^-2(1+|log^3(ν t)|)≥max_1≤ i ≤ℓ^4-1densitystableℓ^2ε^-2(1+|log^3(ν iτ)|) .

Recalling that ℓ=⌊ t^1/4⌋ and summing over the possible values of ℓ', this gives that

    ℚ(B_1)≤∑_i=1^ℓ-1ℚ(G_1,i^c)≤ 4t^1/2Hexp( -densitystableexpoε^2 2^-7 (ℓ-1)).

We deal with ℚ(B_2) by applying <ref>, which is in force on account of Lemma <ref>.
Noticing that the event indexed by s entering the definition of B_2 in (<ref>) implies that at least one particle of η'_s(ℤ∖ I_s) ends up in [-H+2ν s+2ν t, H- 2ν s-2ν t ] before time s+ t, we get using (<ref>) with k=1, η_0=η_s ≡ 0, and I_s playing the role of [-H,H] that

    ℚ(B_2)
    ≤∑_0 ≤ s < tℚ(
    [ a particle of η'_s(ℤ∖ I_s) ends up in;            [-H+2ν(s+ t), H- 2ν(s+t) ];                      before time s +t ])
    ≤ 20texp(-ν t/4).

Finally, owing to our coupling in (<ref>), (<ref>), conditionally on (η_u, η'_u), u ≤ iτ, the process Z_s^i(x) is a one-dimensional  continuous-time random walk with rate 2ν started at a point in [0,ℓ] (owing to the separation of x_i and its match ψ_i(x_i)) with absorption at 0. If (Z_s)_s≥ 0 is such a random walk and ℙ_k denotes the probability for this walk starting at k∈ [0,ℓ], we have by invariance by translation and the reflection principle:

    max_0≤ k≤ℓℙ_k(min_0≤ s≤τZ_s>0)   = ℙ_ℓ(min_0≤ s≤τZ_s>0)= ℙ_0(min_0≤ s≤τZ_s>-ℓ)
    
       ≤ 2ℙ_0(max_0≤ s≤τ| Z_s|<ℓ)≤ 2ℙ(Z_τ∈ [-ℓ,ℓ]).

Using again <cit.> and taking  SEPcoupling large enough (so that in particular 2ντ=t ≥ 2| x | for any x∈ [-ℓ,ℓ]),  we have thus for some universal constant C>0 (changing from one expression to the next): 

    max_0≤ k≤ℓℙ_k(min_0≤ s≤τZ_s>0)≤2ℓ +1/√(4πντ)exp(C(ν^-1τ^-1+ℓ^3ν^-2τ^-2))≤Cℓ/√(ντ)≤ Cν^-1/2t^-1/8.

Recalling that t>ν^-8 and taking a union bound over x ∈Π_0', the previous estimate applied with the Markov property for (η,η') yields that, as long as SEPcoupling is large enough:

    ℚ(B_3)≤ 2H(Ct^-1/16)^ℓ.

Putting together (<ref>), (<ref>), (<ref>), (<ref>) and (<ref>), we obtain that 

    ℚ( η'_t | _[-H+4ν t, H-4ν t]≼η_t | _[-H+4ν t, H- 4ν t])
    
    ≥ 1 -8t^1/2Hexp( -densitystableexpoε^22^-7(ℓ-1) )  -20texp(- ν t/4)-2H(Ct^-1/16)^ℓ,

which is larger than 1- SEPcoupling2 tHexp(-SEPcoupling2^-1ν/ν +1ε^2t^1/4 ) as required by (<ref>)
provided SEPcoupling and SEPcoupling2 are chosen large enough. 

[Locality in <ref>]
 Similarly as in Remark <ref>, which exhibits an analogous property for the coupling inherent to <ref>, the coupling ℚ yielding property <ref> constructed in the proof of Lemma <ref> can be performed for any specification of clock processes (𝒫_e, 𝒫_e')_e ∉ E_H used to define η,η', so long as the marginal laws of (𝒫_e)_e ∈ E and (𝒫_e')_e ∈ E, are that of independent Poisson processes of intensity ν/2. This can be seen by inspection of the proof: the only `non-trivial' joint distribution concerns (𝒫_e, 𝒫_e')_e ∈ E_H, which are obtained by suitable thinning from (𝒫_e)_e∈ E_H, see in particular the discussion around (<ref>) and (<ref>). 



Combining the couplings supplied by Lemmas <ref> and <ref> multiple times, which will be permitted owing to Remarks <ref> and <ref>, yields the following result.




The condition <ref> holds for SEP. 









Let ρ,ε∈ (0,1), H_1,H_2,t,ℓ≥ 1 and η_0,η'_0 ∈{0,1}^ℤ be such that the assumptions of <ref> hold. In particular, note that these entail that H_2 > H_1. Define 

    t_1= ℓ^4,    t_2= t_1+ℓ^19.

We proceed in two steps and refer to Figure <ref> for visual aid. In the first step, we apply simultaneously the couplings of Lemma <ref> on [-H_1,H_1] and of Lemma <ref> on [-H_2,H_2]∖ [-H_1,H_1], in the time-interval [0,t_1] (in doing so we shall explain how this preserves the marginals of η and η'). As a result, we get that η_t_1(x)≥η'_t_1(x) for all x∈ [-H_2+2 ν t_1 , H_2-2 ν t_1], except possibly around two intervals around -H_1 and H_1, of width O( ν t_1). 


In the second step, we couple the particles of η' on these intervals with "additional" particles of η_t_1∖η'_t_1 on [-H_2,H_2] (using that the empirical density of η' is slightly larger than that of η on [-H_2,H_2] by <ref>), in a manner similar to that used in the proof of Lemma <ref>. This ensures that with large enough probability, all these particles of η' get covered by particles of η within time t_2-t_1, without affecting the coupling of the previous step on account of the Markov property. Finally, during the time interval [t_2,t] we use again the natural coupling of Lemma <ref>, and conclude by showing (<ref>) and (<ref>). We now proceed to make this precise.




Step 1: we construct a coupling ℚ_1 of the evolutions of η and η' during the time-interval [0,t_1] such that if we define the (good) events

    G_1={∀ x∈ [-H_1+2  ν t_1, H_1-2  ν t_1], ∀ s∈ [0,t_1]:  η_s(x)≥η'_s(x) }, 
       G_2={∀ x ∈ [-H_2+2 ν t_1, -H_1-2 ν t_1-1]∪ [H_1+2 ν t_1+1,  H_2-2 ν t_1] :  η_t_1(x)≥η'_t_1(x) },

 then 

    ℚ_1(G_1∩ G_2)≥ 1 - 3SEPcoupling2 t_1H_2exp(- SEPcoupling2^-1ν/ν+1ε^2ℓ).


The coupling ℚ_1 is defined as follows. Let (𝒫_e)_e ∈ E be a family of i.i.d. Poisson processes on ℝ_+ of intensity ν/2. These processes are used to describe the exchange times for η (seen as an interchange process as in (<ref>)), during the time-interval [0,t_1]. We now define the exchange times  (𝒫_e')_e ∈ E to be used for η' during [0,t_1] as follows. For an edge e having at least one endpoint outside [-H_2,H_2] or at least one endpoint inside [-H_1, H_1], set 𝒫_e'= 𝒫_e. It remains to specify 𝒫_e' for e with both endpoints in [-H_2,H_2] but outside [-H_1,H_1]. This set splits into two disjoint intervals E_±, which are both dealt with separately and in exactly the same manner. Thus restricting our attention to E_+, one couples (𝒫_e')_e ∈ E_+ and (𝒫_e)_e ∈ E_+ in exactly the same manner as in the proof of Lemma <ref>, with the interval I_+, defined as the set of all endpoints of edges in E_+, playing the role of [-H,H]. The fact that Lemma <ref> applies even though the processes  𝒫_e and 𝒫_e' have been specified for certain edges e ∉ E_+ is owed to Remark <ref>. Define I_- similarly and perform the same coupling of (𝒫_e')_e ∈ E_- and (𝒫_e)_e ∈ E_-.


Since the sets of edges E_-, E_+ and E ∖ (E_- ∪ E_+)  are disjoint, it readily follows that (𝒫_e)_e ∈ E is an i.i.d. family of Poisson processes on ℝ_+ of intensity ν/2. This ensures that under ℚ_1, η∼𝐏^η_0 and  η'∼𝐏^η'_0. 

Now, by our assumptions on ρ, ε, H,ℓ,t_1,η_0 and η'_0, the above construction of ℚ_1 together with Remark <ref> ensure that Lemma <ref> applies on the interval [-H_1, H_1] with t=t_1 and k=1 (recall to this effect that the relevant coupling for which <ref> is shown to hold is simply ℚ=𝐏, see above (<ref>), and that this coupling is also local in the sense of Remark <ref>). This yields that 

    ℚ_1(G_1) ≥ 1 -20 exp (-  νt_1/4).

Second, our assumptions (taking compatible>SEPcoupling) and the above construction of ℚ also allow us to apply Lemma <ref> on E_- and on E_+ instead of [-H,H], with the same values of ρ, ε and ℓ, and with t=t_1 (in particular, ν^8t_1=(ν^2ℓ)^4>1). We obtain that

    ℚ_1(G_2) ≥ 1 - 2SEPcoupling2 t_1H_2exp(- SEPcoupling2^-1ν/ν+1ε^2ℓ).

Combining (<ref>) and (<ref>) yields (<ref>), since 20exp (-  νt_1/4)≤SEPcoupling2 t_1H_2exp(- SEPcoupling2^-1ν/ν+1ε^2ℓ) if compatible is chosen large enough. This concludes Step 1.









Step 2:  We now extend ℚ_1 to a coupling ℚ_2 up to time t, using a slight variation of the coupling in the proof of Lemma <ref> in the time-interval [t_1, t_2]. 
For definiteness of ℚ_2, on the complement of  G_1∩ G_2, use (𝒫_e)_e ∈ E for the exchange times of both η and η' during the time [t_1,t]. Focusing now on the case where G_1 ∩ G_2 occurs, the aim of the step is to show that we can have

    ℚ_2(η'_t_2|_[-H+4ν t_2, H-4ν t_2]≼η_t_2|_[-H+4ν t_2, H-4ν t_2] |  G_1∩ G_2)≥ 1 -  H_2exp( - ν/ν+1ε^2ℓ^4).

Fix any realization of η_t_1, η'_t_1 such that G_1∩ G_2 holds.
Define Pai_0 (cf. (<ref>)) as the set of vertices in I_0 def.=[-H_2+2 ν t_1, H_2-2 ν t_1] containing both a particle of η_t_1 and of η'_t_1, and think of these particles as being paired. Let U_0 (resp. U'_0) be the set of unpaired particles of η_t_1 (resp. η'_t_1) in I_0. By definition of G_1 and G_2, the particles of U'_0 must be in [-H_1-2 ν t_1, -H_1+2 ν t_1]∪ [H_1-2 ν t_1, H_1+2 ν t_1] when the event G_1∩ G_2 occurs; cf. Figure <ref>. Hence, on G_1∩ G_2 we have that 

    | U'_0|≤ 8 ν t_1.

Denote B_1,0^c the event that on every interval of length between ℓ^5/2 and ℓ^5 included in I_0, η_t_1 has at least εℓ^5/10≥ 8 ν t_1 unmatched particles (recall that ℓ>80ν/ε by assumption). On B_1,0, use (𝒫_e)_e ∈ E as exchange time process to define both η and η' during [t_1,t] (cf. the discussion leading to (<ref>)). 

Henceforth, assume that B_1,0^c ∩ G_1 ∩ G_2 occurs. Following the line of argument in the paragraph after (<ref>), one matches injectively each particle of U_0' with a particle of U_0 at distance at most ℓ^5. In the present context this is possible owing to (<ref>) and occurrence of B_1,0^c. Then one couples the evolutions of η and η', first during [t_1, t_1+ℓ^15] as done in the proof of Lemma <ref> during the time interval [0, τ]. Then iteratively at times t_1+iℓ^15 for 1≤ i ≤ℓ^4-1, one performs on I_i= [-H_2+2 ν(t_1+iℓ^15), H_2-2 ν(t_1+iℓ^15)] the same coupling at times i ⌊ t^3/4⌋ on the event B_1,i^c that for any interval I⊆ I_i of length ranging between ℓ^5/2 and ℓ^5, one has η_t_1+iℓ^15(I)≥η'_t_1+iℓ^15(I).  On B_1,i, use (𝒫_e)_e ∈ E for the exchange times of both η and η' during the time interval [t_1+iℓ^15,t].


Overall, this yields a coupling of (η_·∧ t_2, η_·∧ t_2') with the correct marginal law (as in the proof of Lemma <ref>). Finally
one extends this coupling during [t_2, t] on the event G_1 ∩ G_2 ∩⋂_i=0^ℓ^4-1B_1,i^c by using the same exchange times for η and η'. It follows that η∼𝐏^η_0 and η'∼𝐏^η'_0 under ℚ_2.

In much the same way as in (<ref>), it follows from the above construction that the complement of the event on the left-hand side of (<ref>) implies  that at least one particle of η' in the interval [-H_2+2 ν t_2,  H_2-2 ν t_2] is unpaired at time t_2, which in turn (cf. (<ref>)-(<ref>)) implies the occurrence of 

    ( ⋃_i=0^ℓ^4-1B_1,i) ∪ B_2 ∪ B_3

where

    B_2= ⋃_s=0^ℓ^19-1{[ a particle of η'_t_1+ s(ℤ∖ [-H_2+2 ν(t_1+s),  H_2-2 ν(t_1+s)]);                ends up in η'_t_2([-H_2+4 ν t_2,  H_2-4 ν t_2]) ]}
       B_3={   at time t_2, one particle from η'_t_1([-H_2+2 ν t_1,  H_2-2 ν t_1])
        has been in I_i for all 0≤ i < ℓ^4 and remains unpaired}.

We now mimic (<ref>), (<ref>) and (<ref>) to handle ∑_i=0^ℓ^4-1ℚ_2(B_1,i), ℚ_2(B_2) and ℚ_2(B_3)  respectively. In detail, for the first term, we apply <ref> with (H,t)=(H_2,iℓ^15) for 1≤ i ≤ℓ^4-1, and ℓ' ranging from ℓ^5/2 to ℓ^5, noting that 

    H_2>4ν iℓ^15≥ 4νℓ^15≥densitystableℓ^19/2ε^-2(1+|log^3(νℓ^19)|)≥densitystable(iℓ^15)^1/2ε^-2(1+|log^3(ν iℓ^15)|).

For the third inequality, remark that νℓ> densitystableε^-2(1+|log^3(νℓ^4) |) (taking compatible>densitystable), hence it is enough to show that ℓ^9/2(1+|log^3(νℓ^4)|)≥ 1+|log^3(νℓ^19)|. But 1+|log^3(νℓ^19)|≤ 1+4|log^3(νℓ^4)|+60logℓ (since (a+b)^3≤ 4a^3+4b^3 for a,b≥ 0). Taking compatible large enough so that νℓ^100 and thus ℓ is large enough (recall that ℓ>80ν/ε>ν), we have 1+4|log^3(νℓ^4)|+60logℓ≤ 1+4|log^3(νℓ^4)|+ ℓ≤ℓ^9/2(1+|log^3(νℓ^4)|) as desired. 


For the second term ℚ(B_2), we use <ref>, and for the third term ℚ(B_3), we note that a continuous-time random walk with rate 2ν started in [0,ℓ^5] will hit 0 before time ℓ^15 with probability at least 1-Cℓ^5/(νℓ^15)^1/2≥ 1-Cℓ^-2 (note that νℓ≥compatible>1 if we take  compatible>1). 
We obtain that

    ℚ_2(∀ x∈ [-H_2+4 ν t_2,  H_2-4 ν t_2], η_ t_2(x) ≥η'_ t_2(x)  )
               ≥  1-∑_i=0^ℓ^4-1ℚ_2(B_1,i) - ℚ_2(B_2)-ℚ_2(B_3)    
               ≥ 1- 4ℓ^9 H_2 exp(- densitystableexpoε^22^-7(ℓ^5-1) ) - 20 ℓ^19exp (- νℓ^19 /4) - 2H_2 (Cℓ^-2 )^ℓ^4
               ≥ 1 - H_2exp( -ν/ν+1ε^2ℓ^4),

if compatible in <ref> is chosen large enough. This yields (<ref>).



Let ℚdef.=ℚ_2. It remains to establish (<ref>) and (<ref>).
Owing to the way the coupling ℚ is defined during the intervals [0,t_1],[t_1,t_2] and [t_2,t], ℚ has the following property: in [-H_1,H_1], any particle of η' that is covered at some time s<t by a particle of η will be covered by this particle until time t, or until it leaves [-H_1,H_1]. Moreover, by assumption every particle of η'_0([-H_1,H_1]) is covered by a particle of η_0.  Therefore,

    {∀ s∈ [0,t],  η_s|_[-H_1+4νt, H_1-4νt]≽η'_s|_[-H_1+4νt, H_1-4νt]}^ c
    ⊆⋃_s=1^t {a particle of η'_s(∖ [-H_1,H_1])
    enters [-H_1+4νt,H_1-4νt ] before or at time t}.

By Lemma <ref> applied with (t,k,a)=(t-s,2,4ν t+x) for every s≤ t and x≥ 0 if η'_s(± (H_1+x))=1, a union bound over all particles appearing in the event on the right-hand side of (<ref>) leads to the bound on the -probability of the left-hand side by 2t∑_x≥ 0exp(-(4ν t+x) /8)≤ 20texp (-ν t/4), and (<ref>) follows.

As for (<ref>), first note that by (<ref>) and (<ref>), and for compatible large enough, we have that 

    ℚ(η'_ t_2|_[-H_2+4ν t_2, H_2-4ν t_2]≼η_ t_2|_[-H_2+4ν t_2, H_2-4ν t_2])≥ 1 - 4SEPcoupling2 t_1 H_2exp(-SEPcoupling2^-1ν/ν+1ε^2ℓ).

Since we use, during [t_2,t], the same natural coupling as in the proof of Lemma <ref>, letting B_4 denote the event that a particle of η'_t_2(ℤ∖ [-H_2+4ν t_2, H_2-4ν t_2]) ends up in [-H_2+6ν t, H_2-6ν t]⊆ [ -H_2+4ν t_2+2ν t, H_2-4ν t_2-2ν t] in time at most t, we obtain, provided compatible is large enough and abbreviating ξ= SEPcoupling2^-1ν/ν+1ε^2ℓ, that 

    ℚ(η'_ t|_[-H_2+6ν t, H_2-6ν t]≼η_ t|_[-H_2+6ν t, H_2-6ν t])
    ≥ 1 - 4SEPcoupling2 t_1 H_2e^-ξ-ℚ(B_4)
    ≥  1 - 4SEPcoupling2 t_1 H_2e^-ξ-20e^-ν t/4≥  1 - 5SEPcoupling2 t_1 H_2e^-ξ.

This shows (<ref>) (recalling that t_1=ℓ^4 by (<ref>)), and concludes the proof.



The final result which feeds into the proof of Proposition <ref> is the following.


The condition <ref> holds for SEP. 



Let ℓ≥ 1, ρ∈ (0,1) and η_0, η'_0 be such that the conditions of <ref> hold. In particular, these imply the existence of x_0∈ [0, ℓ] such that η_0(x_0)=1 and η'_0(x_0)=0. Let ℚ = 𝐏 as above (<ref>), by which (η,η') are coupled as interchange processes using the same exchange times (𝒫_e)_e∈ E.  As observed in (<ref>), under ℚ the particle of η_0 starting at x_0 moves like a simple random walk Z=(Z_t)_t≥ 0 with jump rate ν, and we have η'_t(Z_t)=0 for all t≥ 0 by construction of 𝐏.  Hence, ℚ(η_ℓ( x )>0  ,  η'_ℓ( x )=0) ≥ℚ(Z_ℓ= x) and therefore, in order to deduce (<ref>) it is enough to argue that

    ℚ(Z_ℓ= x)≥(ν2e^ν)^6(ρ+1)ℓ,    x=0,1.

Indeed, let Z^L_ℓ (resp. Z^R_ℓ) denote the number of jumps of Z to the left (resp. right) during the time interval [0,ℓ]. These two variables are independent and distributed as Poi(νℓ/2), which entails that, for x=0,1, and x_0 ≥ x,

    ℚ(Z_ℓ= x)≥ℚ(Z^L_ℓ=x_0-x)ℚ(Z^R_ℓ=0)≥(ℓν/2)^x_0-xe^-ℓν/(x_0 -x)!≥(ν/2)^x_0-x e^-ℓν
    ≥(ν/2e^ν)^x_0-xe^-(ℓ-(x_0-x))ν,

using that (x_0-x)! ≤ x_0^x_0-x≤ℓ^x_0-x  in the third step.
Since 0≤ x_0-x≤ℓ and ν≤ 2e^ν, (<ref>) follows for all x_0 ≥ x (and x=0,1), and it is easy to see that the bound remains true in the remaining case, i.e. when x_0=0 = 1-x (now forcing Z^L_ℓ=0 and Z^R_ℓ=1 instead, which by symmetry of Z^L_ℓ and Z^R_ℓ yields the same bound as when x_0=x+1). Overall this yields (<ref>). 
Finally, since the marginal of the coupling ℚ for (η,η') is that of Lemma <ref>, we get the first inequality of (<ref>) from <ref> with t=ℓ. The second inequality follows from our condition on k (using that ρ≤ 1).
















§ CONCENTRATION ESTIMATES


We collect here a few classical facts on concentration of Poisson and binomial distributions, that are repeatedly use to control the probability that the environment could have an abnormal empirical density. The PCRW case corresponds to Poisson distributions, and the SSEP to binomial distributions).

Let λ,x >0, and X∼Poisson(λ). Then 

    ℙ(X≥λ+x)≤exp(-x^2/2(λ+x)).

If x∈ [0,λ], then 

    ℙ(X≤λ-x)≤exp(-x^2/2(λ+x)).

Let m∈ℕ, p∈(0,1) and X∼Bin(m,p). Then for all q ∈ (0,1-p), we have

    ℙ(X≥ (p+q)m)≤exp (-mq^2/3)

and for all q∈ (0,p):

    ℙ(X≤ (p-q)m)≤exp (-mq^2/2).




We get (<ref>) (resp. (<ref>)) from Theorem 4.4 (resp. Theorem 4.5) of <cit.> with μ=mp and δ=q/p≥ q in both cases.  We now turn to (<ref>).
By a classical application (and optimization) of Chernoff's bound (see Theorem 5.4 of <cit.>), one shows that 

    ℙ(X≥λ+x)≤e^-λ(eλ)^λ+x/(λ+x)^λ+x=exp(-λ - (λ+x)(log(λ +x)-logλ -1)).

Hence for (<ref>), it remains to show that 

    λ + (λ+x)(log(λ +x)-logλ -1)≥x^2/2(λ+x).

Setting u=1+x/λ and multiplying both sides by u/λ this amounts to show that the map f:[1,∞) →ℝ defined by 

    f(u)= u+u^2(log u  -1) - (u-1)^2/2

remains non-negative. Indeed, f(1)=0 and f'(u)=1+2u(log u  -1) +u-(u-1)=2(1+u(log u  -1)). One checks that log u  -1≥ -1/u for all u≥ 1 (with equality iff u=1) so that f' is nonnegative on [1,∞), and this concludes the proof of (<ref>). One proves (<ref>) via the same method.




§ THE PCRW ENVIRONMENT
 
In this Appendix, we consider another environment, the Poisson Cloud of Random Walks (PCRW) previously considered in <cit.> among others; we refer to the introduction for a more complete list of references. For this environment, the parameter ρ∈ (0,∞) governs the intensity of walks entering the picture. We show below, see Lemma <ref> and Proposition <ref>, that the PCRW also fits the setup of <ref> and  
 satisfies <ref>-<ref>. Hence, this environment yields another example to which the conclusions of our main result, Theorem <ref>, apply. The proof is virtually the same as that of Theorem <ref> given in <ref>, upon noting that the relevant law of large numbers (<ref>) in this context was also shown in <cit.>, yielding the existence of the speed v(ρ) at all but at most two values ρ=ρ_± (as for SEP). 
The PCRW is defined below using random walks evolving in discrete time, following the practice of <cit.> and other previous works, but the following results could easily be adapted to random walks in continuous time (with exponential holding times of mean one).

 
 


 §.§ Definition of the PCRW


The PCRW is a stochastic process η= (η_t(x);  x ∈ℤ, t ∈ℝ_+) with state space Σ=ℤ^ℤ_+ defined as follows: for any given initial configuration η_0∈Σ and every x∈ℤ, place η_0(x) particles at x. Then, let all the particles follow independent discrete-time lazy simple random walks, i.e. at each integer time, any given particle stays put with probability 1/2, or jumps to its left or right neighbour with the same probability 1/4. 
For t≥ 0 and x∈ℤ, let η_t(x) be the number of particles located at x. We denote by ^η_0_PCRW the canonical law of this environment with initial state η_0, and frequently abbreviate ^η_0_=^η_0_PCRW below. 















 §.§ Properties of the PCRW

We proceed to show that the PCRW environment has the desired features, i.e. that the properties (<ref>)-(<ref>) listed in <ref> as well as the conditions <ref>-<ref> appearing in <ref> all hold. The parameter ρ indexing the stationary measures will naturally vary in (0,∞). 
We will in practice always consider a bounded open interval J= (K^-1,K) for arbitrary K > 1 below. The constants densitydev, …, SEPcoupling appearing as part of the conditions we aim to verify will henceforth be allowed to tacitly depend on K. Note that this is inconsequential for the purposes of deriving monotonicity of v(·) on (0,∞) (cf. (<ref>)) since this is a local property: to check monotonicity at ρ one simply picks K large enough such that ρ∈(K^-1,K) =J.

For the remainder of this appendix, let K>1 be arbitrary and Jdef.= (K^-1,K). We start by verifying properties (<ref>)-(<ref>). 


With

    μ_ρ = Poi(ρ)^⊗ℤ,   ρ∈ (0,+∞),

the measures (𝐏^η_0: η_0 ∈{0,1}^ℤ) with 𝐏^η_0=𝐏_PCRW^η_0 and (μ_ρ: ρ∈ J) satisfy all of  (<ref>)-(<ref>).



Fix ρ >0. 
Property (<ref>) is classical, and follows readily from the time-homogeneity, translation invariance and axial symmetry of the lazy simple random walk. 
Property (<ref>) is also standard: if η_0∼μ_ρ, by suitably thinning the Poisson process one can realize η_0 by decomposing η_0(x)=l(x)+c(x)+r(x) for all x∈ℤ, where l(x) (resp. c(x), r(x)) is the number of particles starting from x that make their first move to the left (resp. stay put, and make their first move to the right), with l(x),r(x)∼Poi(ρ/4), c(x)∼Poi(ρ/2) and the family of variables (l(x),c(x),r(x))_x∈ℤ is independent. From this one infers that η_1∼μ_ρ, as η_1(x)=l(x+1)+c(x)+r(x-1) ∼Poi(ρ) for all x∈ℤ, and the variables η_1(x) are independent as x varies. 

As for property (<ref>), it holds with the following natural coupling (which straightforwardly yields the correct marginal laws for η and η'): if η'_0(x)≤η_0(x) for all x∈ℤ, then one matches injectively each particle of η'_0 to a particle of η_0 located at the same position. The coupling imposes that matched particles follow the same trajectory, and  the remaining particles of η_0 (if any) follow independent lazy simple random walks, independently of the matched particles. 
Finally, Property (<ref>) is a consequence of the fact that under 𝐏^ρ, for every finite interval I and every time t ≥0, η_t(I)∼Poi(ρ| I|), and combining with the tail estimates (<ref>)-(<ref>).


We now establish the conditions <ref>-<ref>.

 
For (𝐏^η_0: η_0 ∈{0,1}^ℤ_+) with 𝐏^η_0 =𝐏^η_0_PCRW, ρ∈ J and with ν=1, all of <ref>, <ref>, <ref>, <ref> and <ref> hold.




The proof of Proposition <ref> is given in <ref> below. We start with a coupling result (which for instance readily implies <ref> as shall be seen), similar in spirit to Lemma B.3 of <cit.>, stating that the evolution of the PCRW with a sufficiently regular deterministic initial condition can be approximated by a product of independent Poisson  variables. This is of independent interest (and lurks in the background of various more elaborate coupling constructions employed in <ref>).


There exist positive and finite constants c:diffusive, [c]EGrestesmallerthanepsilon and [c]coupling-1 such that the following holds. Let  ρ∈ (0,K), ε∈ (0,(K-ρ)  ∧ρ∧ 1 ) and H,ℓ,t∈ℕ be such that c:diffusiveℓ^2< t < H/2 and (ρ +ε) (t^-1log t)^1/2ℓ< EGrestesmallerthanepsilonε. There exists a coupling  of (η^ρ-ε , η_t, η^ρ+ε) with η^ρ±ε∼μ_ρ±ε (and η_t sampled under 𝐏^η_0) such that, if  η_0∈Σ is such that for any interval I⊆ [0,H] with | I|=ℓ, 

    (ρ - ε/2) ℓ≤η_0(I)    (resp. η_0(I) ≤ (ρ + ε/2) ℓ),

then with G={η^ρ-ε|_[t, H-t]≼η_t|_[t, H-t]} (resp. G={η_t|_[t, H-t]≼η^ρ+ε|_[t, H-t]}),
 
    (G) ≥ 1 - H exp(-coupling-1 (ρ+ε)^-1ε^2√(t)).

  Moreover, the coupling ℚ is local in the sense that (η^ρ-ε , η_t, η^ρ+ε) |_[t,H-t] depends on the initial condition η_0 through η_0(x), x ∈ [0,H], alone. 


We now prepare the ground for the proof of Proposition <ref>. Let us abbreviate I_t=[t,H-t]. We use the framework of soft local times from Appendix A of <cit.> (the latter following Section 4 of <cit.>), which we extend to fit our needs. We define a coupling ℚ as follows.
Let Λ (defined under ℚ) be a Poisson point process on ⊗ℝ_+ with intensity 1⊗λ where 1 stands for the counting measure and λ is the Lebesgue measure on ℝ. For each z∈ I_t, set 

    η^ρ±εdef.=Λ({z}× (0,ρ±ε]).

 For z∈∖ I_t, let independently η^ρ±ε(z)∼Poi(ρ±ε). This indeed yields the correct marginal distributions μ_ρ±ε in view of (<ref>). 


As for η_t, given any initial configuration η_0 ∈Σ let (x_i)_i≥ 1 denote an arbitrary ordering of the positions of the (finitely many) particles of η_0([0,H]) (counted with multiplicity, hence the sequence (x_i)_i≥ 1 is not necessarily injective). Define for i≥ 1 and z∈ [-t,H+t] g_i(z):=q_t(x_i,z) with (q_n)_n ∈ℕ denoting the discrete-time heat kernel for the lazy simple random walk. Let ξ_1:=sup{t≥ 0 :  ⋃_z∈Λ({z}× (0,tg_1(z)])=0} and for i≥ 2, define recursively 

    ξ_idef.=sup{t≥ 0: ⋃_z∈Λ({z}× (0,ξ_1g_1(z)+… + ξ_i-1g_i-1(z)+tg_i(z)])=i-1},

see Figure 5 of <cit.>. 
Note that since each g_i has a finite support (included in [y_i-t,y_i+t]), the ξ_i's are well-defined. In fact by Propositions A.1-A.2 of <cit.>, the variables are i.i.d. Exp(1). For all z ∈ [-t,H+t], we define the soft local time

    G_η_0 (z)def.=∑_i≥ 1ξ_i q_t(x_i,z),

with ξ_i as in (<ref>). With these definitions, it follows, denoting 

    h(z)def.=Λ({z}× (0,G_η_0(z))),

 that the family (h(z))_z∈ is distributed as η̃_t, defined as the restriction of η_t under 𝐏^η_0 restricted to the particles of η_0([0,H]). To see this, note that ℚ is such that, if u is the -coordinate of the particle of Λ seen when determining ξ_i at (<ref>), then the particle x_i of η_0 moves to u by time t. Remark indeed that by (<ref>) and the spatial Markov property for Poisson point processes, the choice of u is proportional to g_i(·)=q_t(x_i,·) and independent of what happened in the first i-1 steps. In particular, (h(z))_z∈ I_t is distributed as η_t|_I_t, since all the particles of η_t|_I_t perform at most one step per unit of time, and must have been in [0,H] at time 0. Finally, independently of all this, let all particles of η_0(∖ [0,H]) follow independent lazy random walks. 
 
 Overall ℚ indeed defines a coupling of 
(η^ρ-ε , η_t, η^ρ+ε) with the required marginal law, and the desired locality (see below (<ref>)) follows immediately from the previous construction. Moreover, (<ref>) and (<ref>) imply that under ℚ, for all t ∈ℕ  and η_0∈Σ, 

    {η^ρ-ε|_I_t≼η_t|_I_t}⊆{∀ z∈ I_t: ρ-ε≤ G_η_0 (z) },
       {η_t|_I_t≼η^ρ+ε|_I_t}⊆{∀ z∈ I_t:  G_η_0 (z)≤ρ+ε}.

It is now clear from (<ref>) that the desired high-probability domination in (<ref>) hinges on a suitable control of the soft local time G_η_0 defined by (<ref>). To this effect we first isolate the following first moment estimate.






Under the assumptions of Proposition <ref>, there exists EGheatkernel such that for all z ∈ I_t, 

    (ρ - ε/2) (1- EGheatkernelℓ√(log t/t)) ≤𝔼^[G_η_0 (z)],    (resp. 𝔼^[G_η_0 (z)] ≤   (ρ + ε/2) (1+ EGheatkernelℓ√(log t/t))).




Let c_t=√(t log t) and fix z∈ [-H+t,H-t].
Cover [z-⌊ c_t⌋,z+⌊ c_t⌋] by a family (I_i)_1≤ i≤⌈ (2⌊ c_t⌋+1)/ℓ⌉ of intervals of length ℓ, all disjoint except possibly I_1 and I_2. We focus on the upper bound on 𝔼^[G_η_0 (z)] in (<ref>) (the lower bound is derived in a similar fashion). 
By assumption in (<ref>), we have that η_0(I_i) ≤ (ρ + ε/2) ℓ for all i, hence, recalling that ξ_i in (<ref>) has unit mean, 

    E^[G_η_0 (z)] (<ref>)=∑_i≥ 1 q_t(x_i,z) ≤∑_i=1^⌈ (2⌊ c_t⌋+1)/ℓ⌉ (ρ + ε/2) |I_i| max_x ∈ I_i q_t(z,x) +2∑_x≥ z+c_t-1 q_t(z,x).

We start by dealing with the last term above. By Azuma's inequality, we have that

    ∑_x≥ z+c_t-1 q_t(z,x)≤exp( -(c_t-1)^2/2t)≤exp( -log t/2+√(log t/t))≤C(ρ+ε2)/√(t),

for some  constant C>0, depending on K. 
Let us now handle the first term in the right-hand side of (<ref>). We start by noting that

    ∑_i=1^⌈ (2⌊ c_t⌋+1)/ℓ⌉ (ρ + ε2) |I_i| max_x ∈ I_i q_t(z,x) 
    ≤ (ρ + ε2) ∑_i=1^⌈ (2⌊ c_t⌋+1)/ℓ⌉∑_y ∈ I_i q_t(z,y) +(ρ + ε2)∑_i=1^⌈ (2⌊ c_t⌋+1)/ℓ⌉∑_y ∈ I_imax_x ∈ I_i (q_t(z,x)-q_t(z,y))

By <cit.>, we have that

    max_y∈q_t(z,y) ≤Ct^-1/2.

Recalling that at most I_1 and I_2 may overlap, the above implies that

    ∑_i=1^⌈ (2⌊ c_t⌋+1)/ℓ⌉∑_y ∈ I_i q_t(z,y) ≤ 1+∑_y∈ I_1q_t(z,y)≤ 1+Cℓ/√(t).

It remains to deal with the last term in (<ref>). By standard heat kernel estimates (see for instance <cit.> and  <cit.>) and a computation similar to (<ref>), combined with a large deviation estimate on the number N_t of non-zero steps performed by the lazy random walk up to time t (using Azuma's inequality for instance),  for all x,y∈ [z-c_t,z+c_t]  with |x-y|≤ℓ and  first assuming that both |x-z| and |y-z| are even, leaving C be a universal constant changing from line to line, we have that

    q_t(z,x)    ≤∑_n=⌊ t/4-c_t⌋^⌈ t/4+c_t ⌉ℙ(N_t=2n) q_2n(z,y)×exp(  Cℓ c_t/t) + ℙ(|N_t-t2|>2c_t)
       ≤ q_t(z,y)×(1+Cℓ√(log t/t)) + 2exp(-2log t),

where we have to choose  c:diffusive (and hence t) large enough in the assumptions of Proposition <ref>
The case where both |x-z| and |y-z| are odd is treated similarly, considering 2n+1 instead of 2n. If |x-z| is even and |y-z| is odd, note that for all n such that ⌊ t/4-c_t⌋≤ n≤⌈ t/4+c_t ⌉,
    ℙ(N_t=2n)=2n+1/t-2n·ℙ(N_t=2n+1)≤(1+C√(log t/t))·ℙ(N_t=2n+1),

where a corresponding lower bound holds in order to treat the case where |x-z| is odd and |y-z| is even.
Hence the result in (<ref>) holds regardless of the parity of |x-z| and |y-z|. 
Using (<ref>), we obtain that

    ∑_i=1^⌈ (2⌊ c_t⌋+1)/ℓ⌉∑_y ∈ I_imax_x ∈ I_i (q_t(z,x)-q_t(z,y))
    ≤∑_i=1^⌈ (2⌊ c_t⌋+1)/ℓ⌉∑_y ∈ I_i Cℓ√(log t/t) q_t(z,y) + 1/t
    ≤ Cℓ√(log t/t)+∑_y∈ I_1q_t(z,y) ≤ Cℓ√(log t/t),

where we used (<ref>) and the fact that 1≤ℓ^2<t/c:diffusive, chose  c:diffusive (and hence t) large enough, and let the value of C change from one line to the next.
Substituting (<ref>) and (<ref>) into (<ref>) and feeding the resulting estimate together with (<ref>), into (<ref>) yields that

    E^[G_η_0 (z)]  ≤(ρ + ε/2) ( 1+ Cℓ/√(t)  +Cℓ√(log t/t) +C/√(t))≤(ρ + ε/2) ( 1  +Cℓ√(log t/t)),

and the conclusion follows.


We are now ready to give the short proof of Proposition <ref>, which  combines the above ingredients.


We use the coupling ℚ defined atop Lemma <ref> and show that G_η_0 concentrates in order to exploit (<ref>). To this end, first note that for all θ < 1/2min_x q_t(x,z)^-1,

    𝔼^[ e^θ G_η_0 (z)]= ∏_i ≥ 11/1-θ q_t(x_i,z).

Observe that only a finite number of factors may differ from 1 (which requires q_t(x_i,z)>0, hence | x_i-z|≤ t). 
 By (<ref>), the probability (G^c) with G={η_t|_[t, H-t]≼η^ρ+ε|_[t, H-t]} is thus bounded from above by 

    [∃ z∈ I_t :   G_η_0 (z) > ρ + ε ] ≤ H sup_z ∈ I_t [ G_η_0 (z) > ρ + ε ] 
    ≤  H  sup_z exp{- θ(ρ + ε - ∑_i≥ 1  q_t(x_i,z) ) + ∑_i≥ 1 θ^2q_t(x_i,z)^2}≤ H exp{ -(ρ+ ε - ∑ q)^2/4∑ q^2},

using (<ref>), the exponential Markov inequality and the inequality log(1-x)≥-x - x^2 for |x|< 1/2 in the second step and optimizing over θ in the third, and abbreviating ∑ q^α= ∑_i≥ 1q_t(x_i,z)^α. Using (<ref>) and then (<ref>), we have

    ∑_i≥ 1q_t(x_i,z)^2≤C/√(t)∑_i≥ 1q_t(x_i,z) =  C/√(t) E^[G_η_0 (z)] 
    ≤C/√(t)(K+1+ EGheatkernel (ρ+ε)ℓ√(log t/t))≤C/√(t)((K+1) +    EGheatkernelEGrestesmallerthanepsilonε)≤C/K√(t),

 where we used the  assumptions of Proposition <ref>, chose EGrestesmallerthanepsilon  small enough (depending on EGheatkernel), and let the value of C change in the last inequality (depending on K≥ 1).
 Moreover, 
 
    K+1≥ρ+ ε - ∑_i≥ 1q_t(x_i,z)≥ε/2-EGheatkernel(ρ+ε)ℓ√(log t/t)≥ε/2-EGheatkernelEGrestesmallerthanepsilonε≥ε/4,

 provided that EGrestesmallerthanepsilon is small enough (depending on EGheatkernel).
Substituting the two displays above into (<ref>) provides the asserted upper bound on ℚ(G^c) in (<ref>). For the other choice of G in (<ref>), we bound, using that log (1+x)≥ x-x^2/2 for all x≥ 0,

    [∃ z∈ I_t :   G_η_0 (z) < ρ - ε ] ≤ Hsup_z ∈ I_t [ G_η_0 (z) < ρ - ε ] 
    ≤  H  sup_z exp{- θ(ε -ρ + ∑_i≥ 1q_t(x_i,z) ) + 1/2∑_i≥ 1θ^2q_t(x_i,z)}≤ H exp{ -(ε -ρ+ ∑ q)^2/2∑ q^2},

optimizing again over θ in the last step. We conclude in the same way as for the upper bound.











 §.§ Proof of Proposition <ref>
  The proof of Proposition <ref> follows immediately by combining Lemmas <ref>-<ref> below, each of which focuses on one specific property among <ref>, <ref>, <ref>, <ref> and <ref>, which are proved in this order. Recall that J=(K^-1,K) for some K >1 and that constants may implicitly depend on K.

Condition <ref> (with ν=1) holds for PCRW.



 Let ρ,ε, H,ℓ,t and η_0 be such that the conditions of <ref> hold.  It is straightforward to check that these imply the conditions for applying Proposition <ref> with (2H,2ε) instead of (H,ε), provided that densitystable is large enough w.r.t. c:diffusive, EGrestesmallerthanepsilon  and K. Hence, we can now use Proposition <ref> with (2H,2ε) to show <ref>.


Let 1 ≤ℓ' ≤ℓ. By (<ref>) (with an appropriate coupling ℚ under which η∼𝐏^η_0 and η^ρ±ε∼μ_ρ±ε, and translating [0,2H] to [-H,H] by means of (<ref>)), we have that

    𝐏^η_0([            for all I' ⊂ [-H+2 t,H-2 t]; of length ℓ': ±( η_t(I') -ρℓ' ) ≤ 3εℓ' ])≥ 1 -  2 exp(-coupling-1 (ρ+ε)^-1ε^2√(t))-p_±

where

    p_±def.=μ_ρ±ε([   there exists an interval I' of length ℓ' included in; [-H+2 t,H-2 t] so that: | η^ρ±ε(I') -(ρ±ε) ℓ' | ≥ 2εℓ' ]).

By (<ref>) (which holds on account of Lemma <ref>) and a union bound over all intervals I'⊆ [-H+2 t,H-2 t] of length ℓ', we have that
p_±≤ 2H exp(-densitydevε^2ℓ').  Combining this and (<ref>), noting that coupling-1(ρ+ε)^-1√(t)≥densitystableexpoℓ≥densitystableexpoℓ' if we choose densitystableexpo small enough w.r.t. K and coupling-1, yields <ref>. 



For every H,t≥ 0, and all η_0,η'_0 ∈Σ such that η_0 |_[0, H]≽η_0' |_[0, H], there exists a coupling  of η,η' with respective marginals ^η_0 and ^η'_0 such that

    (∀ s∈ [0,t],  η_s|_[t, H-t]≽η'_s|_[t, H-t])=1.

Therefore, condition <ref> holds for PCRW with ν=1. 



Clearly, (<ref>) implies <ref>, up to changing H to 2H and translating [0,2H] to [-H,H] (using (<ref>), as established in Lemma <ref>). We now show (<ref>).

Let H,t≥ 0 and η_0,η'_0∈Σ be as above. 
Couple η and η' by matching injectively each particle of η'_0(x) to a particle of η_0(x), for all x∈ [0,H], and by imposing that matched particles follow the same trajectory (and by letting all other particles follow independent lazy random walks). 


Since particles can make at most one move (to a neighbouring position) per unit of time due to the discrete-time nature of the walks, no particle of η'_0 outside of [0,H] can land in [t,H-t] before or at time t. Thus the event in (<ref>) holds with probability 1.









Let ρ∈ (K^-1,K), ε∈ (0,(K-ρ) ∧ρ∧ 1), and H,ℓ,t∈ℕ be such that c:diffusiveℓ^2<t<H/2 and (ρ +3/2ε) (t^-1log t)^1/2ℓ< EGrestesmallerthanepsilonε/4. Let η_0,η'_0∈Σ be such that for every interval I⊆ [0,H ] of length ℓ, we have η_0(I)≥ (ρ+3ε/4)ℓ and η'_0(I)≤ (ρ+ε/4)ℓ. Then there exists a coupling ℚ of η and η' such that 

    ℚ( η'_t | _[t, H-t]≼η_t | _[t, H-t])≥ 1- 4H exp(-coupling-1(ρ+ε)^-1ε^2√(t)/4).

Consequently, <ref> with ν=1 holds for PCRW. Moreover, ℚ is local in that (η'_t, η_t) |_[t,H-t] depends on the initial conditions (η_0,η_0') through η_0(x), η_0'(x), x ∈ [0,H], alone.






We first show how (<ref>) implies <ref>. Let ρ,ε,H,ℓ,t,η_0 and η'_0 satisfy the assumptions of <ref> (in particular, ℓ=⌊ t^1/4⌋). Then they also satisfy the assumptions of Lemma <ref> (with 2H instead of H), upon taking SEPcoupling large enough in <ref>. By (<ref>) applied to [-H,H] instead of [0,2H] (again using translation invariance, see (<ref>), established in Lemma <ref>), (<ref>) holds with SEPcoupling2=max(4,coupling-1^-1K/2) since ρ+ε≤ K.

We now proceed to the proof of (<ref>). Let ρ,ε,H,ℓ,t,η_0 and η'_0 satisfy the assumptions of Lemma <ref>. Then we can apply Proposition <ref> to η_0 with (ρ+ε,ε/2) instead of (ρ,ε), and the same values of H,ℓ,t. Similarly, we can apply it to η'_0 with (ρ-ε,ε/2) instead of (ρ,ε). This entails the existence of two couplings ℚ^1 of (η_t,η^ρ+ε/2) and ℚ^2 of (η^ρ+ε/2,η'_t), where η^ρ+ε/2∼μ_ρ+ε/2, such that, abbreviating I_t=[t,H-t],
 
    ^1(η'_t|_I_t≼η^ρ+ε/2|_I_t) ∧^2(  η^ρ+ε/2|_I_t≼η_t|_I_t)  ≥ 1 - H exp(-coupling-1/4 (ρ+ε/2)^-1ε^2√(t)).

Applying <cit.> with (X,Y)=(η_t,η^ρ+ε/2) and (Y',Z)= (η^ρ+ε/2,η'_t), one can `chain' ℚ^1 and ℚ^2, i.e. one obtains a coupling ℚ of (η_t|_I_t,η^ρ+ε/2|_I_t, η'_t|_I_t) such that the pair (η_t|_I_t,η^ρ+ε/2|_I_t) has the same (marginal) law as under ℚ^1 and (η^ρ+ε/2|_I_t, η'_t|_I_t) has the same law as under ℚ^2; explicitly, a possible choice is
  
    (η_t|_I_t=μ_A, η'_t|_I_t=μ_B, η^ρ+ε/2|_I_t=μ_C)   
    
      =^1(η_t|_I_t=μ_A | η^ρ+ε/2|_I_t=μ_C) ·^2(η'_t|_I_t=μ_B | η^ρ+ε/2|_I_t=μ_C) ·^1(η^ρ+ε/2|_I_t=μ_C),

with μ_A, μ_B, μ_C  ranging over point measures on I_t. On account of <cit.> applied with the choices ε_1=1- ^1(η'_t|_I_t≼η^ρ+ε/2|_I_t ) and ε_2=1-  ^2(  η^ρ+ε/2|_I_t≼η_t|_I_t), ℚ has the property that 
ℚ(η'_t|_I_t≼η_t|_I_t) ≥ 1 -ε_1-ε_2. In view of (<ref>), (<ref>) follows. The asserted locality of ℚ is inherited from ℚ^i, i=1,2, due to Proposition <ref> (used to define ℚ^i). 































Condition <ref> with ν=1 holds for PCRW. 



Let ρ∈ (K^-1,K), ε∈ (0,1), H_1,H_2,t,ℓ∈, and η_0,η'_0∈Σ be such that the conditions of <ref> hold. We proceed by a two-step coupling similar to the one in Lemma <ref> and first give a short overview of both steps; cf. also Fig. <ref>. In the first step, we couple η and η' during the time interval [0, t_1], with t_1:=ℓ^4, using the coupling of Lemma <ref> on [-H_2,H_2]∖ [-H_1,H_1] and the coupling given in Lemma <ref>, making sure that these couplings can be simultaneously performed on disjoint intervals. As a result, we get that η_t_1(x)≥η'_t_1(x) for all x∈ [-H_2+t_1 , H_2- t_1], except possibly within two intervals around -H_1 and H_1, of width O(t_1). 

In the second step, during the time interval [t_1,t], we couple the particles of η' on these intervals with "additional" particles of η_t_1∖η'_t_1 on [-H_2,H_2] (using that the empirical density of η' is slightly larger than that of η on [-H_2,H_2] by <ref>), using Lemma <ref>. This ensures that with large enough probability, all these particles of η' get covered by particles of η within time t-t_1, without affecting the coupling of the previous step by the Markov property.




Step 1: choosing compatible large enough (in a manner depending on K, c:diffusive and EGrestesmallerthanepsilon), as we now briefly explain, the conditions of Lemma <ref> hold for η_0,η'_0, with (H,ℓ,t)=(H_2-H_1-1,ℓ,t_1) up to translating [0,H] in either of the intervals [-H_2,-H_1-1] or [H_1+1,H_2]. Indeed, the choice t_1=ℓ^4 and the assumptions in <ref> yield that 

    (ρ+3ε/2)(t_1^-1log t_1)^1/2ℓ≤(K+2)ℓ^-1/2≤ (K+2)ε/√(compatible)≤EGrestesmallerthanepsilonε/4,

where we choose compatible large enough depending on EGrestesmallerthanepsilon and K. 


During the time interval [0,t_1], we apply  Lemma <ref>, which we now know is in force, simultaneously on [-H_2,-H_1-1] and [H_1+1,H_2]. This is possible owing to the locality property stated as part of Lemma <ref> (see below (<ref>)), since the couplings involved rely independently on the particles of η_0([-H_2,-H_1-1]) and η'_0([-H_2,-H_1-1]), and those of η_0([H_1+1,H_2]) and η'_0([H_1+1,H_2]) respectively. Moreover, by suitable extension of this coupling we can also couple, during the interval [0,t_1], the particles of η_0([-H_1,H_1]) and η'_0([-H_1,H_1]) in the following way: match injectively each particle of η'_0(x) to a particle of η_0(x), for all x∈ [-H_1,H_1], and impose that matched particles follow the same trajectory (note that this is precisely the coupling underlying the statement of Lemma <ref>). 

From the construction in the previous paragraph, the four groups of particles η_0(∖ [-H_2,H_2]), η_0([-H_2,-H_1-1]), η_0([-H_1,H_1]) and η_0([H_1+1,H_2]) evolve independently under , and within each group the particles themselves follow independent lazy simple random walks. Hence under , during [0,t_1], we have indeed η∼^η_0, and by a similar argument that η'∼^η'_0. 

Now consider the events _1={∀ x∈ [-H_1+t_1,H_1-t_1], ∀ s∈ [0,t_1], η_s(x)≥η'_s(x) } and _2= {∀ x∈ [-H_2+t_1,-H_1-1-t_1]∪ [H_1+1+t_1,H_2-t_1], η_t_1(x)≥η'_t_1(x)  } declared under . By Lemmas <ref> and <ref>, respectively, we have that

    (_1)=1 and (_2)≥ 1 - 8 (H_2-H_1)exp(-coupling-1(ρ+ε)^-1ε^2ℓ^2/4).

Then, define (still under ) two further events

    _3= {for all intervals I⊆  [-H_2+2t_1,H_2-2t_1]  of length ℓ^2:  η'_t_1(I)≤  (ρ+2ε/5) ℓ^2}
       _4={for all intervals I⊆ [-H_2+2t_1,H_2-2t_1] of length ℓ^2:  η_t_1(I)≥ (ρ+3ε/5)ℓ^2 }.

We apply condition <ref>,  which holds by Lemma <ref> to η' with (ρ,ε,ℓ,ℓ',H,t)=(ρ+ε/5,ε/20,ℓ,ℓ^2,2H_2,t_1), and to η with (ρ,ε,ℓ,ℓ',H,t)=(ρ+3ε/4,ε/20,ℓ,ℓ^2,2H_2,t_1). A straightforward computation proves that the necessary conditions are implied by the assumptions in <ref>. This yields

    (_3 ∩_4) ≥ 1-16H_2exp(-densitystableexpoε^2ℓ^2/400).



Step 2: since _1 holds with full -measure, we can, as in Lemma <ref>, pair injectively each particle of η'_t_1([-H_1+t_1,H_1-t_1]) to one of η_t_1 on the same site, and impose by suitable extension of  that paired particles follow the same trajectory during [t_1,t], all pairs being together independent. We obtain in this way that

    (∀ s∈ [0,t],  η_s|_[-H_1+t, H_1-t]≽η'_s|_[-H_1+t, H_1-t])=1.

To complete the construction of  it remains to describe the trajectory of the particles of η'_t_1(∖ [-H_1+t_1,H_1-t_1]) and η_t_1(∖ [-H_1+t_1,H_1-t_1]), and those of η_t_1([-H_1+t_1,H_1-t_1]) that were not paired. On  (_1 ∩_2∩_3 ∩_4 )^c, let all these particles follow independent lazy simple random walks during [t_1,t], independently from the particles paired at (<ref>). On  (_1 ∩_2∩_3 ∩_4 )⊆ (_1∩_2), note that η_t(x)≥η'_t(x) for all x∈ [-H_2+t_1, H_2-t_1]∖ I_1, where

    I_1=[-H_1-t_1,-H_1+t_1-1] ∪ [H_1-t_1+1,H_1+t_1].

We pair injectively each particle of η'_t_1( [-H_2+t_1, H_2-t_1]∖ I_1) to one of η_t_1 on the same site, and impose by suitable extension of  that paired particles follow the same trajectory during [t_1,t], all pairs being together independent. 


For convenience, we introduce

    η_t_1(x)=
            η_t_1(x)-η'_t_1(x)_{x ∈ [-H_2+t_1, H_2-t_1]∖ I_1 }
       η_t_1'(x)=η'_t_1(x)_{x ∈ I_1 },

which denote the number of particles of η_t_1 and η'_t_1 at position x∈ℤ whose trajectory has not yet been described. It thus remains to cover the particles of η' by those of η by time t. Let us first explain the reasoning to establish this covering. Note that the two intervals making up I_1 escape to our couplings during [0,t_1], so that we can only guarantee that the empirical density of η_t_1' is lower than ρ+2ε/5, see _3. Fortunately, _3 and _4 ensure that the empirical density of η_t_1 is at least ε/5 on [-H_2+t_1, H_2-t_1]∖ I_1, which is much wider than I_1. We thus apply Lemma <ref> with a mesh much larger than | I_1| =4t_1 in order to 'dilute' the particles of η'_t_1. By making this coupling independent of the other particles of η,η' previously paired, we will ensure that both η and η' have the correct PCRW marginals. 


We now formalise this coupling. By choosing compatible large enough, one can check, via a straightforward computation, that the assumptions in <ref> imply the necessary conditions to apply Lemma <ref> for η and η' of  on [-H_2+2t_1,H_2-2t_1] with (H,ℓ,t,ρ,ε )= (2H_2-4t_1,ℓ^5,t-t_1,ε/40,ε/50). Hence by Lemma <ref>, we can extend  such that 

    the trajectories of the particles of η_t_1+· and
       η'_t_1+· are independent of those paired at (<ref>),

 and such that (using that ε < 1), on the event _1 ∩_2∩_3 ∩_4,

    (η_t|_[-H_2+2t,H_2-2t]≽η'_t|_[-H_2+2t,H_2-2t]  |   (η_s, η_s' )_ s ∈ [0, t_1]) 
    ≥ 1- 8H_2 exp(-coupling-1ε^2√(t-t_1)/10^4).

Let us check that Step 2 yields the marginals η∼^η_1 and η∼^η'_1 during [t_1,t] (we have already seen in Step 1 that  η∼^η_0 and η∼^η'_0 during [0,t_1] so that the Markov property (<ref>) will ensure that  η∼^η_0 and η∼^η'_0 during [0,t]). Remark that the events _i, 1≤ i≤ 4 are measurable w.r.t. the evolution of η and η' until time t_1. On (_1 ∩_2∩_3 ∩_4 )^c, by (<ref>) and the paragraph below (<ref>), it is clear that all particles of η_t_1 follow independent lazy simple random walks, and that the same is true for η'_t_1. On _1 ∩_2∩_3 ∩_4, (<ref>) and Lemma <ref> ensure that this is also the case. Therefore, we have indeed that η∼^η_1 and η∼^η'_1.


Finally, we explain how to derive <ref> from our construction. Note that (<ref>) immediately follows from (<ref>) (with full -probability). As for (<ref>), we have

    Q def.=(η_t|_[-H_2+6t,H_2-6t]≽η'_t|_[-H_2+6t,H_2-6t]) 
    ≥(η_t|_[-H_2+2t,H_2-2t]≽η'_t|_[-H_2+2t,H_2-2t])

by (<ref>) and (<ref>). Thus, by combining (<ref>), (<ref>), (<ref>) and (<ref>), we get

    Q ≥ 1- (_2^c∪_3^c∪_4^c)-8H_2 exp(-coupling-1ε^2√(t-t_1)/10000)
    
    ≥ 1-32H_2exp( -densitystableexpoε^2ℓ/64 )
    ≥ 1-5SEPcoupling2ℓ^4H_2exp( -ε^2ℓ/(2SEPcoupling2)),
 
choosing compatible and SEPcoupling2 large enough (w.r.t. K, densitystableexpo and coupling-1). 
This yields (<ref>) and concludes the proof,  since (<ref>) is implied by Lemma <ref>.











































Condition <ref> (with ν=1) holds for PCRW, the constraint on k with the pre-factor 48 now replaced by 24(K+1).

 



The modification of the pre-factor appearing in the constraint on k is inconsequential for our arguments (and consistent with SEP where one can afford to choose K=1 since J=(0,1)). Indeed <ref> is only used at (<ref>), where this modified condition on k clearly holds for L large enough (K being fixed). 


 We adapt the proof of Lemma <ref>. 
Let H,ℓ,k≥ 1, ρ∈ (0,K), ε∈ (0,K-ρ) and η_0, η'_0 be such that the conditions of <ref> hold. We can thus pair injectively each particle of η'_0([-H,H]) to one particle of η_0([-H,H]) located at the same position. Moreover, y assumption there is at least one particle of η_0([0,ℓ]) that is not paired. For s≥ 0, denote Z_s the position of this particle at time s. 

Let  be a coupling of η and η' during [0,ℓ] such that paired particles perform the same lazy simple random walk (independently from all other pairs), and all other particles of η_0 and η'_0 follow independent lazy simple random walks (which yields the marginals  η∼^η_0 and η'∼^η'_0). As in Lemma <ref>, we get that 

    (∀ s∈ [0,ℓ],  η_s|_[-H+ℓ, H-ℓ]≽η'_s|_[-H+ℓ, H-ℓ])=1

and (<ref>) follows. 

It remains to show (<ref>). Assume for convenience that ℓ is even (the case ℓ odd being treated in essentially the same way). Similarly as in the proof of Lemma <ref>, we get that

    ℚ(η_ℓ( x )>0  ,  η'_ℓ( x )=0)≥ℚ( Z_ℓ=x ,  η'_ℓ(x)= 0),

for x=0,1. Note that by our construction, the two events {Z_ℓ=x } and {η'_ℓ(x)= 0} are independent. Clearly, we have that for both x=0,1,

    (Z_ℓ=x)≥ 4^-ℓ.

Note that there is no parity issue in (<ref>) because Z performs a lazy random walk. 
Moreover, since η'_0([-3ℓ+1, 3ℓ])≤ 6(ρ+1)ℓ by assumption and since no particle outside [-3ℓ+1, 3ℓ] can reach 0 by time ℓ, it follows that at time ℓ-1, there are at most 6(ρ+1)ℓ particles of η'_0 in [-1,1], and each of them has probability at least 1/2 not to be at x ∈{0,1} at time ℓ. Hence

    ( η'_ℓ(x)= 0)≥ 2^-6(ρ +1)ℓ.

Putting together (<ref>), (<ref>) and (<ref>), we get that the probability on the left of (<ref>) is bonded from below by (2e)^-6(ρ+1)ℓ, whence (<ref>).










abbrv



