MatthiasBirkner ,AndreasGreven ,FrankdenHollander ∗ Collisionlocaltimeoftransientrandomwalksandintermediatephasesininteractingstochasticsystems

El e c t ro nic

Journ a l of

Pr

ob a b il i t y

Vol. 16 (2011), Paper no. 20, pages 552–586.

Journal URL

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

Collision local time of transient random walks and intermediate phases in interacting stochastic systems

Matthias Birkner¹, Andreas Greven², Frank den Hollander^{3 4}

Abstract

In a companion paper[6], a quenched large deviation principle (LDP) has been established for the empirical process of words obtained by cutting an i.i.d. sequence of letters into words ac- cording to a renewal process. We apply this LDP to prove that the radius of convergence of the generating function of the collision local time of two independent copies of a symmetric and strongly transient random walk onZ^d, d≥ 1, both starting from the origin, strictly increases when we condition on one of the random walks, both in discrete time and in continuous time.

We conjecture that the same holds when the random walk is transient but not strongly transient.

The presence of these gaps implies the existence of anintermediate phasefor the long-time be- haviour of a class of coupled branching processes, interacting diffusions, respectively, directed polymers in random environments .

Key words: Random walks, collision local time, annealed vs. quenched, large deviation princi- ple, interacting stochastic systems, intermediate phase.

AMS 2000 Subject Classification:Primary 60G50, 60F10, 60K35, 82D60.

Submitted to EJP on December 24, 2008, resubmitted upon invitation to EJP on March 27, 2010, final version accepted January 11, 2011.

1Institut für Mathematik, Johannes-Gutenberg-Universität Mainz, Staudingerweg 9, 55099 Mainz, Germany.

Email:birkner@mathematik.uni-mainz.de

2Mathematisches Institut, Universität Erlangen-Nürnberg, Bismarckstrasse 1¹

2, 91054 Erlangen, Germany.

Email:greven@mi.uni-erlangen.de

3Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands.

Email:denholla@math.leidenuniv.nl

4EURANDOM, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

∗This work was supported in part by DFG and NWO through the Dutch-German Bilateral Research Group “Mathematics of Random Spatial Models from Physics and Biology”. MB and AG are grateful for hospitality at EURANDOM. We thank an anonymous referee for careful reading and helpful comments.

1 Introduction and main results

In this paper, we derivevariational representations for the radius of convergence of the generating functions of the collision local time of two independent copies of a symmetric and transient random walk, both starting at the origin and running in discrete or in continuous time, when the average is taken w.r.t. one, respectively, two random walks. These variational representations are subsequently used to establish the existence of an intermediate phase for the long-time behaviour of a class of interacting stochastic systems.

1.1 Collision local time of random walks

1.1.1 Discrete time

LetS= (S_k)^∞_k=0 andS^′= (S^′_k)^∞_k=0 be two independent random walks onZ^d_{, d≥}1, both starting at the origin, with anirreducible,symmetricandtransienttransition kernelp(·,·). Writepⁿfor then-th convolution power ofp, and abbreviatepⁿ(x):=pⁿ(0,x), x ∈Z^d. Suppose that

nlim→∞

logp²ⁿ(0)

logn =:−α, α∈[1,∞). (1.1)

WritePto denote the joint law ofS,S^′. Let

V =V(S,S^′):=

X∞ k=1

1_{S

k=S^′_k} (1.2)

be thecollision local timeofS,S^′, which satisfiesP_{(V <∞) =}1 by transience, and define z₁ := sup¦

z≥1: E^”_z^V _|S^—_{<∞ S-a.s.}^©_{, (1.3)} z₂ := sup¦

z≥1: E^”_z^V—_<∞^©_{. (1.4)}

The lower indices indicate the number of random walks being averaged over. Note that, by the tail triviality ofS, the range ofz’s for whichE_[z^V _|S]converges isS-a.s. constant.¹

Let E := Z^d_{, let Ee = ∪n∈NE}ⁿ be the set of finite words drawn from E, and let P^inv(Ee^N) denote the shift-invariant probability measures on Ee^N, the set of infinite sentences drawn from E. Definee

f: Ee→[0,∞)via

f((x₁, . . . ,x_n)) = pⁿ(x₁+· · ·+x_n)

p^2⌊n/2⌋(0) [2 ¯G(0)−1], n∈N_{, x1, . . . ,xn∈E, (1.5)} where ¯G(0) =P_∞

n=0p²ⁿ(0)is the Green function at the origin associated with p²(·,·), which is the transition matrix ofS−S^′, and p^2⌊n/2⌋(0)>0 for alln∈Nby the symmetry ofp(·,·). The following variational representations hold forz₁andz₂.

1Note thatP_{(V=∞) =}1 for a symmetric and recurrent random walk, in which case triviallyz₁=z₂=1.

Theorem 1.1. Assume(1.1). Then z₁=1+exp[−r₁], z₂=1+exp[−r₂]with r₁ ≤ sup

Q∈P^inv(eE^N)

¨Z

e E

(π₁Q)(d y)logf(y)−I^que(Q)

«

, (1.6)

r₂ = sup

Q∈P^inv(eE^N)

¨Z

e E

(π₁Q)(d y)logf(y)−I^ann(Q)

«

, (1.7)

where π₁Q is the projection of Q onto E, while Ie ^que and I^ann are the rate functions in the quenched, respectively, annealed large deviation principle that is given in Theorem2.2, respectively,2.1below with (see(2.4),(2.7)and(2.13–2.14))

E=Z^d_{, ν(x) =p(x), x∈E, ρ(n) =p}^2⌊n/2⌋_{(0)/[2 ¯G(0)−1], n∈}N_{. (1.8)} Let

P^erg,fin(Ee^N) ={Q∈ P^inv(eE^N): Qis shift-ergodic,m_Q<∞}, (1.9) where m_Q is the average word length underQ, i.e., m_Q =R

e

E(π₁Q)(y)τ(y)with τ(y)the length of the word y. Theorem 1.1 can be improved under additional assumptions on the random walk, namely,²

P

x∈Z^d

kxk^δp(x)<∞ for someδ >0, (1.10)

lim inf

n→∞

log[pⁿ(S_n)/p^2⌊n/2⌋(0) ]

logn ≥0 S−a.s., (1.11)

ninf∈N

E_log[pⁿ_(Sn)/p^2⌊n/2⌋_{(0) ]>−∞. (1.12)} Theorem 1.2. Assume(1.1)and(1.10–1.12). Then equality holds in(1.6), and

r₁ = sup

Q∈P^erg,fin(eE^N)

¨Z

e E

(π₁Q)(d y)logf(y)−I^que(Q)

«

∈R_{, (1.13)}

r₂ = sup

Q∈P^erg,fin(eE^N)

¨Z

e E

(π₁Q)(d y)logf(y)−I^ann(Q)

«

∈R_{. (1.14)}

In Section 6 we will exhibit classes of random walks for which (1.10–1.12) hold. We believe that (1.11–1.12) actually hold in great generality.

BecauseI^que≥I^ann, we haver₁≤r₂, and hencez₂≤z₁(as is also obvious from the definitions ofz₁ andz₂). We prove that strict inequality holds under the stronger assumption that p(·,·)isstrongly transient, i.e.,P_∞

n=1npⁿ(0)<∞. This excludesα∈(1, 2)and part ofα=2 in (1.1).

Theorem 1.3. Assume(1.1). If p(·,·)is strongly transient, then1<z₂<z₁≤ ∞.

2By the symmetry of p(·,·), we have sup_x∈Z^dpⁿ(x) ≤ p^2⌊n/2⌋(0) (see (3.15)), which implies that sup_n∈Nsup_x∈Z^d

log[pⁿ(x)/p^2⌊n/2⌋(0)]≤0.

SinceP_{(V = k) = (1−}F)¯ F¯^k, k∈N_{∪ {0}, with ¯F :=}P _∃k∈N_{: Sk = S}^′

k

, an easy computation givesz₂=1/F. But ¯¯ F=1−[1/G¯(0)](see Spitzer[27], Section 1), and hence

z₂=G(0)/[¯ G(0)¯ −1]. (1.15)

Unlike (1.15), no closed form expression is known for z₁. By evaluating the function inside the supremum in (1.13) at a well-chosenQ, we obtain the following upper bound.

Theorem 1.4. Assume(1.1)and(1.10–1.12). Then

z₁≤1+ X

n∈N

e^−h(pn)

!₋1

<∞, (1.16)

where h(pⁿ) =−P

x∈Z^dpⁿ(x)logpⁿ(x)is the entropy of pⁿ(·).

There are symmetric transient random walks for which (1.1) holds withα=1. Examples are any transient random walk onZin the domain of attraction of the symmetric stable law of index 1 on R, or any transient random walk onZ²in the domain of (non-normal) attraction of the normal law onR². If in this situation (1.10–1.12) hold, then the two threshold values in (1.3–1.4) agree.

Theorem 1.5. If p(·,·)satisfies(1.1)withα=1and(1.10–1.12), then z₁=z₂.

1.1.2 Continuous time

Next, we turn the discrete-time random walks S and S^′ into continuous-time random walks eS = (S_t)_t≥0 andSe^′= (eS^′_t)_t≥0 by allowing them to make steps at rate 1, keeping the same p(·,·). Then the collision local time becomes

Ve:=

Z _∞

0

1_{eS

t=eS^′_t}d t. (1.17)

For the analogous quantitiesez₁ andez₂, we have the following.³

Theorem 1.6. Assume(1.1). If p(·,·)is strongly transient, then1<ez₂<ez₁≤ ∞. An easy computation gives

logez₂=2/G(0), (1.18)

whereG(0) =P_∞

n=0pⁿ(0)is the Green function at the origin associated with p(·,·). There is again no simple expression forez₁.

Remark 1.7. An upper bound similar to(1.16)holds forze₁as well. It is straightforward to show that z₁<∞andez₁<∞as soon as p(·)has finite entropy.

3For a symmetric and recurrent random walk again triviallyze₁=ez₂=1.

1.1.3 Discussion

Our proofs of Theorems 1.3–1.6 will be based on the variational representations in Theorem 1.1–1.2.

Additional technical difficulties arise in the situation where the maximiser in (1.7) has infinite mean word length, which happens precisely when p(·,·)is transient but not strongly transient. Random walks with zero mean and finite variance are transient for d ≥ 3 and strongly transient for d ≥5 (Spitzer[27], Section 1).

Conjecture 1.8. The gaps in Theorems1.3 and 1.6are present also when p(·,·) is transient but not strongly transient providedα >1.

In a 2008 preprint by the authors (arXiv:0807.2611v1), the results in[6]and the present paper were announced, including Conjecture 1.8. Since then, partial progresshas been made towards settling this conjecture. In Birkner and Sun[7], the gap in Theorem 1.3 is proved for simple random walk onZ^d_,d≥4, and it is argued that the proof is in principle extendable to a symmetric random walk with finite variance. In Birkner and Sun [8], the gap in Theorem 1.6 is proved for a symmetric random walk onZ³ with finite variance in continuous time, while in Berger and Toninelli [1]the gap in Theorem 1.3 is proved for a symmetric random walk onZ³ in discrete time under a fourth moment condition.

The role of the variational representation for r₂ is not to identify its value, which is achieved in (1.15), but rather to allow for acomparisonwithr₁, for which no explicit expression is available. It is an open problem to prove (1.11–1.12) under mild regularity conditions onS. Note that the gaps in Theorems 1.3–1.6 do not require (1.10–1.12).

1.2 The gaps settle three conjectures

In this section we use Theorems 1.3 and 1.6 to prove the existence of an intermediate phase for three classes of interacting particle systems where the interaction is controlled by a symmetric and transient random walk transition kernel. ⁴

1.2.1 Coupled branching processes

A.Theorem 1.6provesa conjecture put forward in Greven[17],[18]. Consider a spatial population model, defined as the Markov process (η_t)_t≥0, with η(t) = {η_x(t): x ∈ Z^d_{} where ηx(t) is the} number of individuals at site x at time t, evolving as follows:

(1) Each individual migrates at rate 1 according toa(·,·).

(2) Each individual gives birth to a new individual at the same site at rateb.

(3) Each individual dies at rate(1−p)b.

(4) All individuals at the same site die simultaneously at ratep b.

4In each of these systems the case of a symmetric and recurrent random walk is trivial and no intermediate phase is present.

Here,a(·,·)is an irreducible random walk transition kernel onZ^d_×Z^d_{, b∈(0,∞)}is a birth-death rate, p∈[0, 1]is a coupling parameter, while (1)–(4) occur independently at every x ∈Z^d_{. The} case p = 0 corresponds to a critical branching random walk, for which the average number of individuals per site is preserved. The case p>0 is challenging because the individuals descending from different ancestors are no longer independent.

A critical branching random walk satisfies the followingdichotomy(where for simplicity we restrict to the case wherea(·,·)is symmetric): if the initial configurationη₀ is drawn from a shift-invariant and shift-ergodic probability distribution with a positive and finite mean, thenη_t as t → ∞locally dies out (“extinction”) when a(·,·) is recurrent, but converges to a non-trivial equilibrium (“sur- vival”) whena(·,·)istransient, both irrespective of the value ofb. In the latter case, the equilibrium has the same mean as the initial distribution and has all moments finite.

For the coupled branching process with p > 0 there is a dichotomy too, but it is controlled by a subtle interplayofa(·,·), b andp: extinction holds when a(·,·)isrecurrent, but also whena(·,·) is transientandpissufficiently large. Indeed, it is shown in Greven[18]that ifa(·,·)is transient, then there is a uniquep_∗∈(0, 1]such that survival holds forp<p_∗and extinction holds forp>p_∗. Recall the critical valuesez₁,ez₂introduced in Section 1.1.2. Then survival holds ifE_(exp[bpVe]|eS)<

∞S-a.s., i.e., ife p<p₁ with

p₁=1∧(b⁻¹logez₁). (1.19)

This can be shown by a size-biasing of the population in the spirit of Kallenberg[23]. On the other hand, survival with afinite second momentholds if and only ifE_{(exp[bpVe])<∞}, i.e., if and only if p<p₂with

p₂=1∧(b⁻¹logez₂). (1.20)

Clearly, p_∗≥p₁≥p₂. Theorem 1.6 shows that ifa(·,·)satisfies (1.1) and is strongly transient, then p₁>p₂, implying that there is an intermediate phase of survival with aninfinite second moment.

B. Theorem 1.3 corrects an error in Birkner [3], Theorem 6. Here, a system of individuals living on Z^d is considered subject to migration and branching. Each individual independently migrates at rate 1 according to a transient random walk transition kernela(·,·), and branches at a rate that depends on the number of individuals present at the same location. It is argued that this system has an intermediate phase in which the numbers of individuals at different sites tend to an equilibrium with a finite first moment but an infinite second moment. The proof was, however, based on a wrong rate function. The rate function claimed in Birkner[3], Theorem 6, must be replaced by that in[6], Corollary 1.5, after which the intermediate phase persists, at least in the case where a(·,·) satisfies (1.1) and is strongly transient. This also affects[3], Theorem 5, which uses[3], Theorem 6, to computez₁in Section 1.1 and finds an incorrect formula. Theorem 1.4 shows that this formula actually is an upper bound forz₁.

1.2.2 Interacting diffusions

Theorem 1.6 proves a conjecture put forward in Greven and den Hollander [19]. Consider the system X = (X(t))_t≥0, with X(t) = {X_x(t): x ∈ Z^d_}, of interacting diffusions taking values in [0,∞)defined by the following collection of coupled stochastic differential equations:

d X_x(t) = X

y∈Z^d

a(x,y)[X_y(t)−X_x(t)]d t+p

bX_x(t)² dW_x(t), x ∈Z^d_{, t≥0. (1.21)}

Here, a(·,·)is an irreducible random walk transition kernel on Z^d_×Z^d_{, b ∈(0,∞)}is a diffusion constant, and (W(t))_t≥0 withW(t) = {W_x(t): x ∈ Z^d_} is a collection of independent standard Brownian motions onR. The initial condition is chosen such thatX(0)is a shift-invariant and shift- ergodic random field with a positive and finite mean (the evolution preserves the mean). Note that, even thoughX a.s. has non-negative paths when starting from a non-negative initial conditionX(0), we prefer to writeX_x(t)asp

X_x(t)² in order to highlight the fact that the system in (1.21) belongs to a more general family of interacting diffusions with Hölder-¹

2 diffusion coefficients, see e.g.[19], Section 1, for a discussion and references.

It was shown in[19], Theorems 1.4–1.6, that ifa(·,·)issymmetricandtransient, then there exist 0<

b₂≤b_∗such that the system in (1.21) locally dies out when b>b_∗, but converges to an equilibrium when 0< b< b_∗, and this equilibrium has afinite second moment when 0< b< b₂ and aninfinite second momentwhen b₂ ≤ b < b_∗. It was shown in[19], Lemma 4.6, that b_∗≥ b_∗∗=logez₁, and it was conjectured in[19], Conjecture 1.8, that b_∗> b₂. Thus, as explained in[19], Section 4.2, if a(·,·)satisfies (1.1) and is strongly transient, then this conjecture is correct with

b_∗≥logez₁ > b₂=logez₂. (1.22) Analogously, by Theorem 1.1 in[8]and by Theorem 1.2 in[7], the conjecture is settled for a class of random walks in dimensionsd=3, 4 including symmetric simple random walk (which ind=3, 4 is transient but not strongly transient).

1.2.3 Directed polymers in random environments

Theorem 1.3disprovesa conjecture put forward in Monthus and Garel[25]. Leta(·,·)be a symmet- ric and irreducible random walk transition kernel onZ^d_×Z^d_{, letS= (Sk)}^∞

k=0 be the corresponding random walk, and let ξ = {ξ(x,n): x ∈ Z^d_{,n ∈} N_{} be i.i.d.} R-valued non-degenerate random variables satisfying

λ(β):=logE _{exp[βξ(x,n)]∈}R _∀β∈R_{. (1.23)} Put

e_n(ξ,S):=exp



Xⁿ

k=1

βξ(S_k,k)−λ(β)



, (1.24)

and set

Z_n(ξ):=E_{[en(ξ,S)] =} ^X

s₁,...,s_n∈Z^d



 Yn k=1

p(s_k−1,s_k)



 e_n(ξ,s), s= (s_k)^∞_k=0,s₀=0, (1.25)

i.e., Z_n(ξ)is the normalising constant in the probability distribution of the random walkS whose paths are reweighted by e_n(ξ,S), which is referred to as the “polymer measure”. The ξ(x,n)’s describe a random space-time medium with whichS is interacting, withβ playing the role of the interaction strength or inverse temperature.

It is well known thatZ= (Z_n)_n∈Nis a non-negative martingale with respect to the family of sigma- algebrasFn:=σ(ξ(x,k),x ∈Z^d_{, 1≤k≤n),n∈}N_{. Hence}

n→∞lim Z_n=Z_∞≥0 ξ−a.s., (1.26)

with the event {Z_∞ = 0} being ξ-trivial. One speaks of weak disorder if Z_∞ > 0 ξ-a.s. and of strong disorder otherwise. As shown in Comets and Yoshida[12], there is a unique critical value β_∗∈[0,∞] such that weak disorder holds for 0≤ β < β_∗ and strong disorder holds for β > β_∗. Moreover, in the weak disorder region the paths have a Gaussian scaling limit under the polymer measure, while this is not the case in the strong disorder region. In the strong disorder region the paths are confined to a narrow space-time tube.

Recall the critical valuesz₁,z₂ defined in Section 1.1. Bolthausen[9]observed that E^”_Z²

n

—=E h

exp

{λ(2β)−2λ(β)}V_ni

, withV_n:=

Xn k=1

1_{Sk=S′

k}, (1.27) whereSandS^′are two independent random walks with transition kernelp(·,·), and concluded that ZisL²-bounded if and only ifβ < β₂ withβ₂∈(0,∞]the unique solution of

λ(2β₂)−2λ(β₂) =logz₂. (1.28)

SinceP_(Z∞>0)≥E_[Z∞]²_/E_[Z²

∞]andE_{[Z∞] =Z0=1 for an L}²-bounded martingale, it follows that β < β₂ implies weak disorder, i.e.,β_∗≥ β₂. By a stochastic representation of the size-biased law ofZ_n, it was shown in Birkner[4], Proposition 1, that in fact weak disorder holds ifβ < β₁ with β₁∈(0,∞]the unique solution of

λ(2β₁)−2λ(β₁) =logz₁, (1.29)

i.e.,β_∗≥β₁. Sinceβ7→λ(2β)−2λ(β)is strictly increasing for any non-trivial law for the disorder satisfying (1.23), it follows from (1.28–1.29) and Theorem 1.3 that β₁ > β₂ when a(·,·) satisfies (1.1) and is strongly transient and when ξ is such that β₂ < ∞. In that case the weak disorder region contains a subregion for whichZ isnot L²-bounded. This disproves a conjecture of Monthus and Garel[25], who argued thatβ₂=β_∗.

Camanes and Carmona[10]consider the same problem for simple random walk and specific choices of disorder. With the help of fractional moment estimates of Evans and Derrida[16], combined with numerical computation, they show thatβ_∗> β₂for Gaussian disorder ind≥5, for Binomial disorder with small mean ind≥4, and for Poisson disorder with small mean ind≥3.

See den Hollander[21], Chapter 12, for an overview.

Outline

Theorems 1.1, 1.3 and 1.6 are proved in Section 3. The proofs need only assumption (1.1). Theo- rem 1.2 is proved in Section 4, Theorems 1.4 and 1.5 in Section 5. The proofs need both assumptions (1.1) and (1.10–1.12)

In Section 2 we recall the LDP’s in [6], which are needed for the proof of Theorems 1.1–1.2 and their counterparts for continuous-time random walk. This section recalls the minimum from [6]

that is needed for the present paper. Only in Section 4 will we need some of the techniques that were used in[6].

2 Word sequences and annealed and quenched LDP

Notation. We recall the problem setting in [6]. Let E be a finite or countable set of letters. Let eE = ∪_n∈^NEⁿ be the set of finite words drawn from E. Both E and Ee are Polish spaces under the discrete topology. Let P(E^N) and P(Ee^N) denote the set of probability measures on sequences drawn fromE, respectively,E, equipped with the topology of weak convergence. Writee θ andθefor the left-shift acting onE^N, respectively,Ee^N. WriteP^inv(E^N),P^erg(E^N)andP^inv(Ee^N),P^erg(Ee^N)for the set of probability measures that are invariant and ergodic underθ, respectively,θe.

Forν ∈ P(E), letX = (X_i)_i∈Nbe i.i.d. with lawν. Forρ∈ P(N_{), letτ= (τi)i∈N}be i.i.d. with law ρhaving infinite support and satisfying thealgebraic tail property

limn→∞

ρ(n)>0

logρ(n)

logn =:−α, α∈[1,∞). (2.1)

(No regularity assumption is imposed on supp(ρ).) Assume thatX andτare independent and write Pto denote their joint law. Cut words out ofX according toτ, i.e., put (see Fig. 1)

T₀:=0 and T_i:=T_i−1+τ_i, i∈N_{, (2.2)} and let

Y⁽ⁱ⁾:= X_Ti

−1+1,X_Ti

−1+2, . . . ,X_Ti

, i∈N_{. (2.3)}

Then, under the lawP_{, Y = (Y}⁽ⁱ⁾_)i∈N is an i.i.d. sequence of words with marginal lawq_ρ,ν on eE given by

q_ρ,ν (x₁, . . . ,x_n)

:=P _Y⁽¹⁾_{= (x1, . . . ,xn)=ρ(n)ν(x1)· · ·ν(xn), n∈}N_{, x1, . . . ,xn∈E.}

(2.4) τ₁

τ₂ τ₃ τ₄

τ₅

T₁ T₂ T₃ T₄ T₅

Y⁽¹⁾ Y⁽²⁾ Y⁽³⁾ Y⁽⁴⁾ Y⁽⁵⁾

X

Figure 1: Cutting words from a letter sequence according to a renewal process.

Annealed LDP.ForN ∈N_{, let(Y}⁽¹⁾_{, . . . ,Y}^(N)₎^per be the periodic extension of (Y⁽¹⁾, . . . ,Y^(N))to an element ofEe^N, and define

R_N := 1 N

NX−1 i=0

δ_θei(Y⁽¹⁾,...,Y^(N))^per ∈ P^inv(Ee^N), (2.5) theempirical process of N -tuples of words. The following large deviation principle (LDP) is standard (see e.g. Dembo and Zeitouni[14], Corollaries 6.5.15 and 6.5.17). Let

H(Q|q^⊗_ρ,ν^N):= lim

N→∞

1 Nh

 Q_|

FN

(q^⊗_ρ,ν^N)_|

FN

‹

∈[0,∞] (2.6)

be thespecific relative entropy of Q w.r.t. q_ρ,ν^⊗N, whereFN = σ(Y⁽¹⁾, . . . ,Y^(N)) is the sigma-algebra generated by the first N words, Q_|

FN is the restriction of Q to FN, and h(· | ·) denotes relative entropy (defined for probability measuresϕ,ψon a measurable spaceF ash(ϕ|ψ) =R

Flog^dϕ

dψdϕ if the density ^dϕ

dψ exists and as∞otherwise).

Theorem 2.1. [Annealed LDP] The family of probability distributionsP_{(RN ∈ ·), N ∈}N, satisfies the LDP onP^inv(eE^N)with rate N and with rate function I^ann: P^inv(Ee^N)→[0,∞]given by

I^ann(Q) =H(Q|q_ρ,ν^⊗N). (2.7)

The rate function I^annis lower semi-continuous, has compact level sets, has a unique zero at Q=q^⊗_ρ,ν^N, and is affine.

Quenched LDP.To formulate the quenched analogue of Theorem 2.1, we need some further nota- tion. Letκ:Ee^N→E^Ndenote theconcatenation mapthat glues a sequence of words into a sequence of letters. ForQ∈ P^inv(Ee^N)such that m_Q:=E_Q[τ1]<∞(recall thatτ₁ is the length of the first word), defineΨ_Q∈ P^inv(E^N)as

Ψ_Q(·):= 1 m_QE_Q





τX1−1 k=0

δ_θ^k_κ(Y)(·)



. (2.8)

Think ofΨ_Q as the shift-invariant version of the concatenation of Y under the law Q obtained after randomising the location of the origin.

For tr∈N_{, let[·]tr: eE→[E]e tr:=∪}^tr_n=1Eⁿ_{denote the}word length truncationmap defined by

y = (x₁, . . . ,x_n)7→[y]_tr:= (x₁, . . . ,x_n∧tr), n∈N_{, x1, . . . ,xn∈E. (2.9)} Extend this to a map fromeE^Nto[E]e ^N_tr via

(y⁽¹⁾,y⁽²⁾, . . .)

tr:= [y⁽¹⁾]_tr,[y⁽²⁾]_tr, . . .

, (2.10)

and to a map fromP^inv(Ee^N)toP^inv([eE]^N_tr)via

[Q]_tr(A):=Q({z∈eE^N: [z]_tr∈A}), A⊂[E]e ^N_tr measurable. (2.11) Note that ifQ∈ P^inv(Ee^N), then[Q]_tris an element of the set

P^inv,fin(Ee^N) ={Q∈ P^inv(eE^N): m_Q<∞}. (2.12) Theorem 2.2. [Quenched LDP, see[6], Theorem 1.2 and Corollary 1.6](a) Assume(2.1). Then, forν^⊗N–a.s. all X , the family of (regular) conditional probability distributionsP_{(RN ∈ · |X), N ∈}N_, satisfies the LDP on P^inv(Ee^N) with rate N and with deterministic rate function I^que: P^inv(Ee^N) → [0,∞]given by

I^que(Q):=







I^fin(Q), if Q∈ P^inv,fin(Ee^N),

trlim→∞I^fin [Q]_tr

, otherwise, (2.13)

where

I^fin(Q):=H(Q|q^⊗_ρ,ν^N) + (α−1)m_QH(Ψ_Q|ν^⊗N). (2.14) The rate function I^que is lower semi-continuous, has compact level sets, has a unique zero at Q=q^⊗_ρ,ν^N, and is affine. Moreover, it is equal to the lower semi-continuous extension of I^fin fromP^inv,fin(Ee^N)to P^inv(Ee^N).

(b) In particular, if(2.1)holds withα=1, then forν^⊗N–a.s. all X , the familyP_{(RN ∈ · |X)satisfies} the LDP with rate function I^anngiven by(2.7).

Note that the quenched rate function (2.14) equals the annealed rate function (2.7) plus an addi- tional term that quantifies the deviation ofΨ_Q from the reference lawν^⊗Non the letter sequence.

This term is explicit whenm_Q<∞, but requires a truncation approximation whenm_Q=∞. We close this section with the following observation. Let

Rν:=

Q∈ P^inv(Ee^N): w−lim

L→∞

1 L

L−1

X

k=0

δ_θ^k_κ(Y)=ν^⊗NQ−a.s.

. (2.15)

be the set ofQ’s for whichthe concatenation of words has the same statistical properties as the letter sequence X. Then, forQ∈ P^inv,fin(eE^N), we have (see[6], Equation (1.22))

Ψ_Q=ν^⊗N ⇐⇒ I^que(Q) =I^ann(Q) ⇐⇒ Q∈ Rν. (2.16)

3 Proof of Theorems 1.1, 1.3 and 1.6

3.1 Proof of Theorem 1.1

The idea is to put the problem into the framework of (2.1–2.5) and then apply Theorem 2.2. To that end, we pick

E:=Z^d_{, eE=}ÝZ^d _:=∪n∈N(Z^d₎ⁿ_{, (3.1)} and choose

ν(u):=p(u), u∈Z^d_{, ρ(n):=} ^p

2⌊n/2⌋(0)

2 ¯G(0)−1, n∈N_{, (3.2)} where

p(u) =p(0,u),u∈Z^d_{, p}ⁿ_{(v−u) =p}ⁿ_(u,v),u,v∈Z^d_, G(0) =¯ X∞ n=0

p²ⁿ(0), (3.3) the latter being the Green function ofS−S^′at the origin.

Recalling (1.2), and writing

z^V= (z−1) +1V

=1+ XV N=1

(z−1)^N V

N

(3.4)

with V

N

= X

0<j₁<···<jN<∞

1_{S

j1=S^′_j

1,...,S_jN=S^′_jN}, (3.5)

we have

E^”_z^V _|S^—₌₁₊ X∞ N=1

(z−1)^NF_N⁽¹⁾(X), E^”_z^V— ₌₁₊ X∞ N=1

(z−1)^NF_N⁽²⁾, (3.6) with

F_N⁽¹⁾(X):= X

0<j1<···<j_N<∞

P _Sj

1=S^′_j

1, . . . ,S_j

N =S^′_j

N |X

, F_N⁽²⁾ :=E_F⁽¹⁾

N (X)

, (3.7)

where X = (X_k)_k∈Ndenotes the sequence of increments ofS. (The upper indices 1 and 2 indicate the number of random walks being averaged over.)

The notation in (3.1–3.2) allows us to rewrite the first formula in (3.7) as F_N⁽¹⁾(X) = X

0<j1<···<jN<∞

YN i=1

p^ji−ji−1





j_i−Xj_i−1 k=1

X_ji

−1+k





= X

0<j₁<···<jN<∞

YN i=1

ρ(j_i−j_i−1) exp



 XN

i=1

log



p^ji−ji−1(Pj_i−j_i−1 k=1 X_ji

−1+k) ρ(j_i−j_i−1)







.

(3.8)

LetY⁽ⁱ⁾= (X_j

i−1+1,· · ·,X_ji). Recall the definition of f : ZÝ^d_{→[0,∞)in (1.5),} f((x₁, . . . ,x_n)) = pⁿ(x₁+· · ·+x_n)

p^2⌊n/2⌋(0) [2 ¯G(0)−1], n∈N_{, x1, . . . ,xn∈}Z^d_{. (3.9)} Note that, sinceÝZ^d carries the discrete topology, f is trivially continuous.

LetR_N ∈ P^inv((ÝZ^d₎^N₎ be the empirical process of words defined in (2.5), andπ₁R_N ∈ P(ÝZ^d_)the projection ofR_N onto the first coordinate. Then we have

F_N⁽¹⁾(X) =E



exp X^N

i=1

logf(Y⁽ⁱ⁾)

! X



=E



exp

‚ N

Z

Ý Z^d

(π₁R_N)(d y)logf(y)

ΠX



, (3.10)

wherePis the joint law ofX andτ(recall (2.2–2.3)). By averaging (3.10) overX we obtain (recall the definition ofF_N⁽²⁾from (3.7))

F_N⁽²⁾=E

– exp

‚ N

Z

Ý Z^d

(π₁R_N)(d y)logf(y)

Ϊ

. (3.11)

Without conditioning onX, the sequence(Y⁽ⁱ⁾)_i∈Nis i.i.d. with law (recall (2.4)) q_ρ,ν^⊗N with q_ρ,ν(x₁, . . . ,x_n) = p^2⌊n/2⌋(0)

2 ¯G(0)−1 Yn k=1

p(x_k), n∈N_{, x1, . . . ,xn∈}Z^d_{. (3.12)}

Next we note that

f in (3.9) isbounded from above. (3.13)

Indeed, the Fourier representation ofpⁿ(x,y)reads pⁿ(x) = 1

(2π)^d Z

[−π,π)^d

d k e^−i(k·x)bp(k)ⁿ (3.14) withbp(k) =P

x∈Z^de^i(k·x)p(0,x). Becausep(·,·)is symmetric, we havebp(k)∈[−1, 1], and it follows that

max

x∈Z^d

p²ⁿ(x) =p²ⁿ(0), max

x∈Z^d

p²ⁿ⁺¹(x)≤p²ⁿ(0), ∀n∈N_{. (3.15)} Consequently, f((x₁, . . . ,x_n)) ≤ [2 ¯G(0)−1] is bounded from above. Therefore, by applying the annealedLDP in Theorem 2.1 to (3.11), in combination with Varadhan’s lemma (see Dembo and Zeitouni[14], Lemma 4.3.6), we getz₂=1+exp[−r₂]with

r₂:= lim

N→∞

1

NlogF_N⁽²⁾≤ sup

Q∈P^inv((ZÝ^d)^N)

¨Z

ÝZ^d

(π₁Q)(d y)logf(y)−I^ann(Q)

«

= sup

q∈P(ZÝ^d)

¨Z

Ý Z^d

q(d y)logf(y)−h(q|q_ρ,ν)

« (3.16)

(recall (1.3–1.4) and (3.6)). The second equality in (3.16) stems from the fact that, on the set of Q’s with a given marginalπ₁Q=q, the functionQ7→I^ann(Q) =H(Q|q_ρ,ν^⊗N)has a unique minimiser Q = q^⊗N (due to convexity of relative entropy). We will see in a moment that the inequality in (3.16) actually is an equality.

In order to carry out the second supremum in (3.16), we use the following.

Lemma 3.1. Let Z:=P

y∈ZÝ^d f(y)q_ρ,ν(y). Then Z

ZÝ^d

q(d y)logf(y)−h(q|q_ρ,ν) =logZ−h(q|q^∗) ∀q∈ P(ÝZ^d_{), (3.17)}

where q^∗(y):= f(y)q_ρ,ν(y)/Z, y∈ÝZ^d_.

Proof. This follows from a straightforward computation.

Inserting (3.17) into (3.16), we see that the suprema are uniquely attained atq=q^∗andQ=Q^∗= (q^∗)^⊗N, and thatr₂≤logZ. From (3.9) and (3.12), we have

Z=X

n∈N

X

x₁,...,x_n∈Z^d

pⁿ(x₁+· · ·+x_n) Yn k=1

p(x_k) =X

n∈N

p²ⁿ(0) =G(0)¯ −1, (3.18)

where we use that P

v∈Z^dp^m(u+v)p(v) = p^m+1(u), u∈Z^d_{, m ∈}N, and recall that ¯G(0) is the Green function at the origin associated withp²(·,·). Henceq^∗is given by

q^∗(x₁, . . . ,x_n) = pⁿ(x₁+· · ·+x_n) G(0)¯ −1

Yn k=1

p(x_k), n∈N_{,x1, . . . ,xn∈}Z^d_{. (3.19)}

Moreover, sincez₂ =G¯(0)/[G¯(0)−1], as noted in (1.15), we see thatz₂ =1+exp[−logZ], i.e., r₂=logZ, and so indeed equality holds in (3.16).

The quenched LDP in Theorem 2.2, together with Varadhan’s lemma applied to (3.8), gives z₁ = 1+exp[−r₁]with

r₁:= lim

N→∞

1

NlogF_N⁽¹⁾(X)≤ sup

Q∈P^inv((ZÝ^d)^N)

¨Z

Ý Z^d

(π₁Q)(d y)logf(y)−I^que(Q)

«

X−a.s., (3.20) where I^que(Q) is given by (2.13–2.14). Without further assumptions, we are not able to reverse the inequality in (3.20). This point will be addressed in Section 4 and will require assumptions (1.10–1.12).

3.2 Proof of Theorem 1.3

To compare (3.20) with (3.16), we need the following lemma, the proof of which is deferred.

Lemma 3.2. Assume (1.1). Let Q^∗ = (q^∗)^⊗N with q^∗ as in (3.19). If m_Q∗ < ∞, then I^que(Q^∗) >

I^ann(Q^∗).

With the help of Lemma 3.2 we complete the proof of the existence of the gap as follows. Since logf is bounded from above, the function

Q7→

Z

Ý Z^d

(π₁Q)(d y)logf(y)−I^que(Q) (3.21) is upper semicontinuous. Therefore, by compactness of the level sets of I^que(Q), the function in (3.21) achieves its maximum at someQ^∗∗that satisfies

r₁= Z

Ý Z^d

(π₁Q^∗∗)(d y)logf(y)−I^que(Q^∗∗)≤ Z

Ý Z^d

(π₁Q^∗∗)(d y)logf(y)−I^ann(Q^∗∗)≤r₂. (3.22) Ifr₁=r₂, thenQ^∗∗=Q^∗, because the function

Q7→

Z

Ý Z^d

(π₁Q)(d y)logf(y)−I^ann(Q) (3.23) hasQ^∗as its unique maximiser (recall the discussion immediately after Lemma 3.1). ButI^que(Q^∗)>

I^ann(Q^∗)by Lemma 3.2, and so we have a contradiction in (3.22), thus arriving atr₁<r₂. In the remainder of this section we prove Lemma 3.2.

Proof. Note that

q^∗((Z^d₎ⁿ_{) =} ^X

x₁,...,x_n∈Z^d

pⁿ(x₁+· · ·+x_n) G¯(0)−1

Yn k=1

p(x_k) = p²ⁿ(0)

G(0)¯ −1, n∈N_{, (3.24)} and hence, by assumption (1.2),

n→∞lim

logq^∗((Z^d₎ⁿ₎

logn =−α (3.25)