Scaling limits of recurrent excited random walks on integers

ISSN:1083-589X in PROBABILITY

Scaling limits of recurrent excited random walks on integers

Dmitry Dolgopyat

Elena Kosygina

Abstract

We describe scaling limits of recurrent excited random walks (ERWs) onZ^{in i.i.d.}

cookie environments with a bounded number of cookies per site. We allow both pos- itive and negative excitations. It is known that ERW is recurrent if and only if the expected total drift per site,δ, belongs to the interval[−1,1]. We show that if|δ|<1 then the diffusively scaled ERW under the averaged measure converges to a(δ,−δ)- perturbed Brownian motion. In the boundary case, |δ| = 1, the space scaling has to be adjusted by an extra logarithmic term, and the weak limit of ERW happens to be a constant multiple of the running maximum of the standard Brownian motion, a transient process.

Keywords: Excited random walk; cookie walk; branching process; random environment; per- turbed Brownian motion.

AMS MSC 2010:60K37; 60F17; 60G50.

Submitted to ECP on December 27, 2011, final version accepted on August 1, 2012.

SupersedesarXiv:1201.0379.

1 Introduction and main results

Given an arbitrary positive integerM let ΩM :=

((ωz(i))_i∈N)_z∈Z| ωz(i)∈[0,1],fori∈ {1,2, . . . , M}

andω_z(i) = 1/2,fori > M, z∈Z .

An element of Ω_M is called a cookie environment. For each z ∈ Z, the sequence {ωz(i)}_i∈N can be thought of as a stack of cookies at site z. The number ωz(i) rep- resents the transition probability fromz toz+ 1 of a nearest-neighbor random walk upon thei-th visit to z. Ifωz(i) ≥1/2 (resp. ωz(i)<1/2) the corresponding cookie is called non-negative (resp. negative).

LetPbe a probability measure onΩ_M, which satisfies the following two conditions:

(A1) Independence: the sequence(ωz(·))z∈Zis i.i.d. underP^; (A2) Non-degeneracy:Eh

QM

i=1ω0(i)i

>0 and Eh QM

i=1(1−ω0(i))i

>0.

Forx∈Z^andω∈ΩM consider an integer valued processX:= (Xj), j≥0, on some probability space(X,F, Px,ω), whichPx,ω-a.s. satisfiesPx,ω(X0=x) = 1and

Px,ω(Xn+1=Xn+ 1| Fn) = 1−Px,ω(Xn+1=Xn−1| Fn) =ωX_n(LX_n(n)),

∗University of Maryland, USA. E-mail:[email protected]

†Baruch College and the CUNY Graduate Center, USA. E-mail:[email protected]

whereFn ⊂ F, n≥0, is the natural filtration ofX and L_m(n) :=Pn

j=01{Xj=m} is the number of visits to sitembyX up to timen. Informally speaking, upon each visit to a site the walker eats the topmost cookie from the stack at that site and makes one step to the right or to the left with probabilities prescribed by this cookie. The consumption of a cookieωz(i)induces a drift of size2ωz(i)−1. Sinceωz(i) = 1/2 for alli > M, the walker will make unbiased steps fromzstarting from the(M+ 1)-th visit toz. Letδbe the expected total drift per site, i.e.

δ := E

"

X

i≥1

(2ω0(i)−1)

#

= E

"_M X

i=1

(2ω0(i)−1)

#

. (1.1)

The parameterδplays a key role in the classification of the asymptotic behavior of the walk. For a fixedω ∈Ωthe measureP_ω,x is calledquenched. Theaveraged measure P_xis obtained by averaging over environments, i.e.P_x(·) :=E(P_x,ω(·)).

There is an obvious symmetry between positive and negative cookies: if the envi- ronment(ωz)_z∈Z is replaced by (ω_z⁰)_z∈Z whereω⁰_z(i) = 1−ωz(i), for alli ∈ N, z ∈ Z^, thenX⁰, the ERW corresponding to the new environment, satisfiesX⁰ =^d −X, where=^d denotes the equality in distribution. Thus, it is sufficient to consider only non-negativeδ (this, of course, allows both negative and positive cookies), and we shall always assume this to be the case.

ERW on Z in a non-negative cookie environment and its natural extension to Z^d (when there is a direction inR^d such that the projection of a drift induced by every cookie on that direction is non-negative) were considered previously by many authors (see, for example, [4], [22], [23], [2], [3], [17] [5], [9], [16], and references therein).

Our model allows both positive and negative cookies but restricts their number per site toM. This model was studied in [14], [15], [20], [19]. It is known that the process is recurrent (i.e. forP^-a.e.ωit returns to the starting point infinitely often) if and only ifδ≤1([14]). For transient (i.e. not recurrent) ERW, there is a rich variety of limit laws underP₀([15]).

In this paper we study scaling limits of recurrent ERW underP0. The functional limit theorem for recurrent ERW in stationary ergodic non-negative cookie environments on stripsZ×(Z/LZ),L∈N, under the quenched measure was proven in [9]. Our results deal only with i.i.d. environments on Z with bounded number of cookies per site but remove the non-negativity assumption on the cookies. We are also able to treat the boundary caseδ= 1. Extensions of these results and results of [15] to strips, orZ^{d for} d >1, or the “boundary” case for the model treated in [9] are still open problems.

To state our results we need to define the candidates for limiting processes. Let D([0,∞))be the Skorokhod space of càdlàg functions on [0,∞) and denote by ⇒^J1 the weak convergence in the standard (J1) Skorokhod topology onD([0,∞)). Unless stated otherwise, all processes start at the origin at time0. LetB = (B(t)), t ≥0, denote a standard Brownian motion andX_α,β= (X_α,β(t)), t≥0, be an(α, β)-perturbed Brownian motion, i.e. the solution of the equation

Xα,β(t) =B(t) +αsup

s≤t

Xα,β(s) +βinf

s≤tXα,β(s), (1.2)

For(α, β)∈(−∞,1)×(−∞,1)the equation (1.2) has a pathwise unique solution that is adapted to the filtration ofB and is a.s. continuous ([18], [7]). Now we can state the results of our paper.

Theorem 1.1(Non-boundary case). Ifδ∈[0,1)then X_[n·]

√n

J₁

⇒X_δ,−δ(·)asn→ ∞.

We note that there are other known random walk models which after rescaling con- verge to a perturbed Brownian motion (see, e.g., [8, 21]).

Theorem 1.2(Boundary case). Letδ= 1andB^∗(t) := max_s≤tB(s),t ≥0. Then there exists a constantD >0such that

X_[n·]

D√ nlogn

J1

⇒B^∗(·)asn→ ∞.

Observe that forδ= 1the limiting process is transient while the original process is recurrent. To prove Theorem 1.2 we consider the processSj:= max_0≤i≤jXi,j≥0, and show that after rescaling it converges to the running maximum of Brownian motion.

The stated result then comes from the fact that with an overwhelming probability the maximum amount of “backtracking” ofX_j fromS_jforj ≤[T n]is of order√

n, which is negligible on the scale√

nlogn(see Lemma 5.2).

2 Notation and preliminaries

Assume thatδ≥0andX₀= 0. LetT_x= inf{j≥0 : X_j =x}be the first hitting time ofx∈Z^{. Set}

Sn= max

k≤nXk, In= min

k≤nXk, Rn =Sn−In+ 1, n≥0.

At first, we recall the connection with branching processes exploited in [2], [3], [14], and [15].

Forn∈N^and0≤k≤ndefine D_n,k =

T_n−1

X

j=0

1{X_j=k, X_j+1=k−1},

the number of jumps fromktok−1before timeT_n. Then Tn=n+ 2X

k≤n

Dn,k =n+ 2 X

0≤k≤n

Dn,k+ 2X

k<0

Dn,k. (2.1)

Consider the “backward” process(Dn,n, D_n,n−1. . . , Dn,0). Obviously,Dn,n = 0for every n∈N. Moreover, givenDn,n, D_n,n−1, . . . , Dn,k+1, we can write

Dn,k=

D_n,k+1+1

X

j=1

(#of jumps fromktok−1between the(j−1)-th andj-th jump fromktok+ 1before timeTn), k= 0,1, . . . , n−1.

Here we used the observation that the number of jumps from k tok+ 1 before time T_n is equal to D_n,k+1+ 1 for all 0 ≤ k ≤ n−1. It follows from the definition that (D_n,n, D_n,n−1. . . , D_n,0)is a Markov process. Moreover, it can be recast as a branch- ing process with migration (see [14], Section 3, as well as [15], Section 2). LetV :=

(Vk), k≥0, be the process such thatV0= 0and

(V₀, V₁, . . . , V_n)= (D^d _n,n, D_n,n−1. . . , D_n,0) for alln∈N.

Denote byσ∈[1,∞]andΣ∈[0,∞]respectively the lifetime and the total progeny over the lifetime ofV, i.e.σ= inf{k >0 : Vk = 0}, Σ =Pσ−1

k=0Vk. The probability measure that corresponds toV will be denoted byP₀^V. The following result will be used several times throughout the paper.

Theorem 2.1([15], Theorems 2.1 and 2.2). Letδ >0. Then

n→∞lim n^δP₀^V(σ > n) =C1∈(0,∞); (2.2)

n→∞lim n^δP₀^V Σ> n²

=C2∈(0,∞). (2.3)

We shall need to considerV over many lifetimes. Letσ0= 0,Σ0= 0, σ_i = inf{k > σi−1: V_k= 0}, Σ_i=

σi−1

X

k=σ_i−1

V_k, i∈N. (2.4)

Then(σi−σ_i−1,Σi)_i∈N are i.i.d. underP₀^V,(σi−σ_i−1,Σi)= (σ,^d Σ),i∈N^.

3 Non-boundary case: two useful lemmas

Letδ∈[0,1). First of all, we show that by timenthe walker consumes almost all the drift betweenInandSn.

Lemma 3.1. Assume thatδ∈[0,1). Givenγ1> δ, there existγ2>0andθ∈(0,1)such that for all1≤`≤n

P0 n−1

X

m=n−`

1{L_m(T_n)<M}> `^γ1

!

≤θ^`γ2 and (3.1)

P₀





−(n−`)

X

m=−(n−1)

1{Lm(T−n)<M}> `^γ1



≤θ^`γ2. (3.2)

Proof. We shall start with (3.1) and use the connection with branching processes. Since the event we are interested in depends only on the environment and the behavior of the walk on{n−`, n−`+ 1, . . .}, we may assume without loss of generality that the process starts atn−`and, thus, by translation invariance consider only the case`=n.

LetL^V_k(n) =Pn

j=01{Vj=k}. We have P0

n−1

X

m=0

1{Lm(Tn)<M}> n^γ1

!

≤P0 n

X

m=0

1{Dn,m<M}> n^γ1

!

=P₀^V

n

X

m=0

1{Vm<M}> n^γ1

!

≤M max

0≤k<MP₀^V

n

X

m=0

1{Vm=k}> n^γ1 M

!

(3.3)

=M max

0≤k<MP₀^V

L^V_k(n)> n^γ1 M

.

At first, consider the case δ ∈ (0,1). Let k = 0. Then (see (2.2) and (2.4)) for all sufficiently largenwe get

P₀^V

L^V₀(n)>n^γ1 M

≤

[n^γ1/M]

Y

i=1

P₀^V (σi−σ_i−1≤n)≤

1− C1

2n^δ

^[nγ1/M]

. Sinceγ1> δ, this implies the desired estimate fork= 0.

Letk∈ {1,2, . . . , M−1}. Then for anyε >0 P₀^V

L^V_k(n)>n^γ1 M

= P₀^V

L^V_k(n)> n^γ1

M , L^V₀(n)> εn^γ1 2M

+P₀^V

L^V_k(n)> n^γ1

M , L^V₀(n)≤εn^γ1 2M

≤P₀^V

L^V₀(n)>εn^γ1 2M

+P₀^V

L^V₀(n)≤εn^γ1 2M

L^V_k(n)> n^γ1 M

.

We only need to estimate the last term. Notice that by (A2) there is ε > 0 such that P₀^V(V_j+1 = 0|V_j =k) ≥ εfor all k ∈ {1,2, . . . , M−1} and j ∈ N. Therefore, the last term is bounded above by the probability that in at least[n^γ1/M]independent Bernoulli trials with probability of success in each trial of at leastεthere are at most[εn^γ1/(2M)]

successes. This probability is bounded above byexp(−cn^γ1/M)for some positive c = c(ε). This completes the proof of (3.1) forδ >0.

If δ = 0 we modify the environment by increasing slightly the drift (to the right) in the first cookie at each site. LetVe be the branching process corresponding to the modified environment. There is a natural coupling betweenV andVe such thatVe_j≤V_j, j∈ {0,1, . . . , n}. Accordingly,

n

X

j=0

1{Vj<M}≤

n

X

j=0

1_{eVj<M},

and (3.1) forδ= 0follows from the result forδ >0and the second line of (3.3).

Next after replacingX by−X proving (3.2) reduces to proving (3.1) forδ≤0 and γ1>0. As above, the result forδ≤0can be deduced from the result forδ∈(0, γ1)by coupling of the corresponding branching processes.

Next we show that√

nis a correct scaling in Theorem 1.1.

Lemma 3.2. Assume that δ ∈ [0,1). There existsθ ∈ (0,1) such that for all L > 0,

`∈N∪ {0}, andn∈N

P0

T`+n−T`≤n² L

≤θ

√

L and P0

T_{−`−n</sub>−T<sub>−`}≤n² L

≤θ

√ L.

Proof. We shall prove the first inequality forδ∈(0,1). The caseδ= 0and the second inequality are handled in exactly the same way as in the proof of Lemma 3.1.

SinceT_{n+`</sub>−T<sub>`}≥Pn+`

k=`D<sub>n+`,k</sub>=^d Pn

j=0V_j, it is enough to show that

P₀^V





n

X

j=0

V_j ≤n² L



≤θ

√L.

Notice that by the Markov property and the stochastic monotonicity ofV in the initial number of particles

P₀^V





m+k

X

j=0

V_j≤n



≤P₀^V





m+k

X

j=m+1

V_j ≤n

m

X

j=0

V_j≤n



P₀^V





m

X

j=0

V_j≤n





≤P₀^V





k

X

j=0

Vj ≤n



P₀^V





m

X

j=0

Vj ≤n



. (3.4)

Suppose that we can show that there existK, n₀∈Nsuch that for alln≥n₀

P₀^V





Kn

X

j=0

Vj≤n²



≤1

2. (3.5)

Then using (3.4) and (3.5) we get that for allL >4K²andn≥√ Ln₀

P₀^V





n

X

j=0

Vj ≤n² L



≤



P₀^V





[2Kn/√ L]

X

j=0

Vj≤ n² L









[√ L/(2K)]

≤



P₀^V





2K[n/√ L]

X

j=0

Vj ≤4 n

√ L

2







[√ L/(2K)]

≤ 1

2

1/(4K)!

√L

,

and we are done.

To prove (3.5), we observe that due to (2.2) the sequence σm/m^1/δ, m ∈ N^{, has a} limiting distribution ([10], Theorem 3.7.2) and, thus, ifK is large thenP0(σ_[(^√_Kn)δ] >

Kn)≤1/4for all large enoughn. We conclude that there is ann0∈Nsuch that for all n≥n₀

P₀^V





Kn

X

j=0

V_j ≤n²



≤ 1 4+P₀^V





σ_[(^√_Kn)δ]

X

j=0

V_j≤n², σ_[(^√_Kn)δ] ≤Kn





≤ 1 4+P₀^V





[(√ Kn)^δ]

X

i=1

Σi≤n²



≤1 4+

[(√ Kn)^δ]

Y

i=1

P₀^V Σi≤n^2(2.3)

≤ 1 4+

1− C2

2n^δ [(√

Kn)^δ]

.

This immediately gives (3.5) ifKis chosen sufficiently large.

4 Non-boundary case: Proof of Theorem 1.1

Let∆n =Xn+1−Xnand B_n =

n−1

X

k=0

(∆_k−E_0,ω(∆_k|Fk)), C_n=

n−1

X

k=0

E_0,ω(∆_k|Fk). (4.1)

ThenX_n=B_n+C_n, where(B_n), n≥0is a martingale. Define X⁽ⁿ⁾(t) :=X_[nt]

√n , B⁽ⁿ⁾(t) :=B_[nt]

√n , C⁽ⁿ⁾(t) := C_[nt]

√n , t≥0, n∈N.

Theorem 1.1 is an easy consequence of the following three lemmas, the first of which holds for the quenched and the last two for the averaged measures.

Lemma 4.1. Let B be a standard Brownian motion. Then B⁽ⁿ⁾ ⇒^J1 B as n → ∞ for P^-a.e.ω.

Lemma 4.2. For eacht≥0andε >0 P0

sup

k≤nt

|Ck−δRk|

√n > ε

→0.

Lemma 4.3. The sequence X⁽ⁿ⁾, n ≥ 1, is tight in D([0,∞)). Moreover, if X is a limit point of this sequence and P is the corresponding measure on D([0,∞)) then P(X ∈C([0,∞))) = 1.

Proof of Theorem 1.1 assuming Lemmas 4.1–4.3. SinceX⁽ⁿ⁾,n≥1, is tight andB⁽ⁿ⁾⇒^J1 Basn→ ∞, the sequenceC⁽ⁿ⁾,n≥1, as the difference of two tight sequences is also tight. We can assume by choosing a subsequence thatX⁽ⁿ⁾⇒^J1 X, whereXis continuous

by Lemma 4.3. The mappingx(·) 7→ r^x(·) := sup_s≤·x(s)−inf_s≤·x(s)is continuous on C([0, t]). Therefore, by the continuous mapping theorem

r^X(n)(·) = R_[n·]

√n

J₁

⇒r^X(·). (4.2)

The tightness ofC⁽ⁿ⁾,n ≥1, (4.2), Lemma 4.2, and the “convergence together” result ([6], Theorem 3.1) imply thatC⁽ⁿ⁾⇒^J1 δr^X asn→ ∞.

Now we have a vector-valued sequence of processes(X⁽ⁿ⁾, B⁽ⁿ⁾, C⁽ⁿ⁾), n ≥1, that is tight. Therefore, along a subsequence, this 3-dimensional process converges to (X, B, δr^X). SinceX⁽ⁿ⁾=B⁽ⁿ⁾+C⁽ⁿ⁾, we get thatX =B+δr^X.

We shall conclude this section with proofs of Lemmas 4.1–4.3.

Proof of Lemma 4.1. We shall use the functional limit theorem for martingale differ- ences ([6], Theorem 18.2). Letξ_nk=n^−1/2(∆_k−1−E_0,ω(∆_k−1|Fk−1)),k, n∈N^{. Due to} rescaling and the fact that ERW moves in unit steps, it is obvious that the Lindeberg condition,

X

k≤nt

E0,ω[ξ_nk² 1{|ξnk|≥ε}]→0 asn→ ∞for everyt≥0andε >0,

is satisfied. Thus, we just have to show the convergence of the quadratic variation process, i.e. forP^-a.e.ωfor eacht≥0

X

k≤nt

E_0,ω(ξ_nk² |Fk−1) =[nt]

n − 1 n

X

k≤nt

(E_0,ω(∆_k−1|Fk−1))²⇒t (4.3) asn→ ∞. Since

0≤ 1 n

X

k≤nt

(E_0,ω(∆_k−1|Fk−1))²≤ M n R_[nt],

it is enough to prove thatP0,ω(R[nt]> εn)→0a.s. for eachε >0. We have P0,ω(R[nt]> εn)≤P0,ω(T[εn/3]≤nt) +P0,ω(T_−[εn/3]≤nt) =:fn,ε(ω, t).

By Fubini’s theorem and Lemma 3.2, E

∞

X

n=1

f_n,ε(ω, t)

!

=

∞

X

n=1

Ef_n,ε(ω, t) =

∞

X

n=1

P₀ T_[εn/3]≤nt

+P₀ T_−[εn/3] ≤nt

<∞.

This implies thatfn,ε(ω, t)→0a.s. asn→ ∞and completes the proof.

Proof of Lemma 4.2. Let d_m = PM

i=1(2ω_m(i)−1) be the total drift stored at site m, m∈Z^{. Then}

Ck−δRk=

S_k

X

m=I_k

(dm−δ)−

S_k

X

m=I_k

1{Lm(k)<M}

M

X

j=Lm(k)+1

(2ωm(j)−1).

By Lemma 3.2, given ν > 0, we can choose K sufficiently large so that P₀(R_[nt] >

K√

n)< ν/2for alln∈N^{. We have}

P0

sup

k≤nt

|Ck−δRk|

√n > ε

≤P0



maxk≤nt

PSk

m=Ik(dm−δ) Rk

Rk

√n > ε 2,R[nt]

√n ≤K





+P₀





√M n

S_[nt]

X

m=I_[nt]

1{Lm([nt])<M}> ε 2,R_[nt]

√n ≤K



+ν

2. (4.4)

By the strong law of large numbers lim

(a+b)→∞(a+b)⁻¹Pb

m=−a(d_m−δ) = 0(P-a.s.). There- fore, forP^-a.e.ωthere is anr(ω)∈N^{such that}R⁻¹_k

PS_k

m=I_k(dm−δ)

≤ε/(2K)whenever Rk ≥r(ω), and the first term in the right-hand side of (4.4) does not exceed

P₀

2(M + 1)r(ω)

√n > ε 2,R_[nt]

√n ≤K

≤E

P_0,ω

r(ω)> ε√ n 4(M + 1)

→0 asn→ ∞.

Thus, we only need to estimate the second term in the right-hand side of (4.4).

Divide the interval[I_[nt], S_[nt]]into subintervals of lengthn^1/4.By Lemma 3.1, given γ₁ ∈ (δ,1), with probability at least 1−θ^nγ2/4Kn^1/4 all subintervals except the two extreme ones have at mostn^γ1/4points which are visited less thanM times. Hence, for nsufficiently large

P0





√M n

S_[nt]

X

m=I_[nt]

1{Lm([nt])<M} >ε 2,R[nt]

√n ≤K



≤

P0





S_[nt]

X

m=I_[nt]

1{Lm([nt])<M}> n^(1+γ1)/4+ 2n^1/4,R_[nt]

√n ≤K



≤θ^nγ2/4Kn^1/4, and the proof is complete.

Proof of Lemma 4.3. The idea of the proof is the following. IfX⁽ⁿ⁾has large fluctuations then eitherB⁽ⁿ⁾has large fluctuations orC⁽ⁿ⁾has large fluctuations.B⁽ⁿ⁾is unlikely to have large fluctuations, since it converges to the Brownian motion. By Lemma 3.1,C_n can have large fluctuations only ifS_n increases orI_n decreases. However by Lemma 3.2 neitherInnorSncan change too quickly. Let us give the details.

To prove both statements of Lemma 4.3 it is enough to show that there existsC3, α >

0such that for all`∈Nand sufficiently largen, n >2<sup>`</sup>,

P0(∪_k<2`Ωn,k,`)≤C32^−α`, (4.5) where

Ω_n,k,`=

X⁽ⁿ⁾ k+ 1

2^`

−X⁽ⁿ⁾ k

2^`

>2^−`/8

(see e.g. the last paragraph in the proof of Lemma 1 in [11], Chapter III, Section 5).

Let

m1:=

kn 2^`

, m2:=

(k+ 1)n 2^`

, J := 1

4n^1/22^−`/8. (4.6) Then

Ωn,k,`={|Xm<sub>2</sub>−Xm<sub>1</sub>|>4J} ⊂Ω<sup>B</sup><sub>n,k,`</sub>∪Ω^C_n,k,`, where

Ω^B_{n,k,`</sub>={|Bτ−Bm1|> J, τ ≤m2}, Ω<sup>C</sup><sub>n,k,`}={|Cτ−Cm1|>3J, τ ≤m2}, τ:= inf{m > m1 : |Xm−X_m1|>4J}andB_nandC_n are defined in (4.1).

Since(B_j+m1−Bm1),j ≥0, is a martingale, whose quadratic variation grows at most linearly, the maximal inequality and Burkholder-Davis-Gundy inequality ([13], Theorem 2.11 withp= 4) imply that

P0,ω(Ω^B_n,k,`)≤P0,ω

max

m1≤j≤m2

|Bj−Bm₁|> J

≤ C(m2−m1)²

J⁴ ≤C⁰2^−3`/2.

Hence,P0

∪_k<2`Ω<sup>B</sup><sub>n,k,`</sub>

≤C⁰2^−`/2.

To controlP₀(Ω^C_n,k,`)consider the following intervals:

A1= (−∞, Im₁)∩Γ, A2= [Im₁, Sm₁]∩Γ, A3= (Sm₁,∞)∩Γ, whereΓ = [Xm₁−4J, Xm₁+ 4J]. Then

Ω^C_n,k,`⊂

3

[

s=1







τ−1

X

j=m1

|E0,ω(∆j| Fj)|1{Xj∈As}> J, τ ≤m2







⊂

3

[

s=1







m2−1

X

j=m₁

|E0,ω(∆j| Fj)|1{Xj∈As}> J







=:

3

[

s=1

Ω^C_{n,k,`,s</sub>. To estimateP<sub>0</sub>(Ω<sup>C</sup><sub>n,k,`,3})note that to accumulate a drift larger than J the walk should visit at least[J/M]distinct sites, i.e.

Ω^C_n,k,`,3⊂ {TS_m1+[J/M]−TSm1+1≤m2−m1}.

LetJ¯= [J/(2M)]and`¯=`/8. There exists anm∈N^{such that} Sm₁+ 1≤mJ¯≤(m+ 1) ¯J ≤Sm₁+ [J/M].

Using Lemma 3.2, we can findK >1such thatP0(Sn> K√

n)<2^−¯`for all sufficiently largen. Therefore,

P0(Ω^C<sub>n,k,`,3</sub>)≤2<sup>−`¯</sup>+P0

∪_m<2`+3<sup>¯</sup> M KΩ<sup>†</sup><sub>n,m,`</sub>, Sn ≤K√ n

, whereΩ^†_n,m,` =

T_{(m+1) ¯J}−T_mJ¯≤m₂−m₁ . Sincem₂−m₁ ≤CJ¯²/2^6¯` for some con- stantC >0, Lemma 3.2 implies that there isθ <ˆ 1such that and all sufficiently large n

P₀

∪_m<2¯`+3KMΩ<sup>†</sup><sub>n,m,`</sub>

≤ X

m<2^`+3¯ KM

P₀ Ω^†_n,m,`

≤2^{¯`+3</sup>KMθˆ<sup>23`} < C⁰⁰2<sup>−`</sup>. P<sub>0</sub>(∪<sub>k<2</sub>`Ω^C_n,k,`,1)is estimated in the same way.

We consider now A2, which is a random subinterval of [−m1, m1] and, on Ω^C_{n,k,`,2</sub>, has length betweenJ/M and8J. To estimateP0(Ω<sup>C</sup><sub>n,k,`,2})we notice that by Lemma 3.1, outside of an event of exponentially small (inJ^γ2) probability, the number of cookies that are left inA2 at timem1does not exceedCJ^γ1, whereγ1 <1. Even if the walker consumes all cookies in that interval, it can not build up a drift of sizeJ CJ^γ1 (forJ large). With this idea in mind, we turn now to a formal proof.

As we noted above, on Ω^C_n,k,`,2, we have A2 ∈ I, where I denotes the set of all intervals of the form

[a, b], a, b∈Z, −m₁≤a < b≤m₁, J/M≤b−a≤8J.

The cardinality ofI does not exceed16m1J ≤Cn^3/2. Therefore, P₀(Ω^C_n,k,`,2)≤Cn^3/2max

A∈IP₀





m2−1

X

j=m₁

|E_0,ω(∆_j| F_j)|1{X_j∈I} > J, A₂=A



. (4.7) By the definition ofA2, the walk necessarily crosses the intervalA2by the timem1. The leftover drift inA₂is at mostM times the number of sites inA₂, which still have at least one cookie. WritingAas[a, b],a, b∈Z^,a < b, we can estimate the last probability by

P₀ M

b

X

m=a

1{Lm(T_a∨Tb)<M}> J

!

=P₀

b

X

m=a

1{Lm(T_a∨Tb)<M}> J/M

! .

If a ≥ 0 we can apply Lemma 3.1 and get that for all sufficiently large n (such that (8J)^γ1 ≤J/M)

P₀

b

X

m=a

1{L_m(T_a∨T_b)<M}> J/M

!

≤P₀

b

X

m=a

1{L_m(T_b)<M}>(b−a)^γ1

!

≤θ^(b−a)γ2 ≤θ^(J/M)γ2. (4.8) The caseb≤0is similar. Finally, consider the casea <0< b. Then

P0 b

X

m=a

1{Lm(Ta∨Tb)<M}> J/M

!

≤P0 0

X

m=a

1{Lm(Ta)<M}> J/(2M)

!

+P0 b

X

m=0

1{Lm(Tb)<M}> J/(2M)

!

. (4.9)

Ifb ≤J/(2M)then the last term in (4.9) is0. But for J/(2M) < b ≤8J we have that b^γ1≤J/(2M)for all sufficiently largeJ. Lemma 3.1 implies that

P0 b

X

m=0

1{Lm(Tb)<M}> J/(2M)

!

≤P0 b

X

m=0

1{Lm(Tb)<M}> b^γ1

!

≤θ^bγ2 ≤θ^(J/(2M))γ2.

The first term in the right-hand side of (4.9) is estimated in the same way. We conclude that for some constantCand all sufficiently largen

P0(∪_k<2`Ω<sup>C</sup><sub>n,k,`,2</sub>)≤Cn^3/22^{`</sup>θ<sup>(J/(2M))γ2</sup> <2<sup>−`}. This completes the proof of (4.5) establishing Lemma 4.3.

5 Boundary case: Proof of Theorem 1.2.

Letδ= 1. Fort≥0andn≥2set T⁽ⁿ⁾(x) := T_[nx]

n²/log²n, X⁽ⁿ⁾(t) := X_[nt]

√nlogn, S⁽ⁿ⁾(t) := S_[nt]

√nlogn.

LetΣ_j, j ≥0 be i.i.d. positive integer-valued random variables defined in (2.4). They satisfy (2.3) withδ= 1and by [12, Chapter 9, Section 6] for some constanta >0

P[n·]

j=0Σj

n²

J1

⇒aH(·) asn→ ∞, (5.1)

whereH:= (H(x)), x≥0, is a stable subordinator with index1/2. More precisely, H(x) = inf{t≥0 : B(t) =x}. (5.2) We shall need the following two lemmas.

Lemma 5.1. The finite dimensional distributions ofT⁽ⁿ⁾converge to those ofcH, where c >0is a constant andH is given by (5.2).

Lemma 5.2. For everyε >0,T >0

n→∞lim P0

sup

0≤t≤T

(S⁽ⁿ⁾(t)−X⁽ⁿ⁾(t))> ε

= 0.

Theorem 1.2 is an easy consequence of these lemmas.

Proof of Theorem 1.2. Lemma 5.1 implies that the finite dimensional distributions of the processS⁽ⁿ⁾converge to those ofDB^∗, whereD >0is a constant. Since the trajec- tories ofS⁽ⁿ⁾are monotone and the limiting processB^∗is continuous, we conclude that S⁽ⁿ⁾converges weakly to DB^∗ in the (locally) uniform topology (see [1], Corollary 1.3 and Remark (e) on p. 588). Finally, by Lemma 5.2 for eachT >0

sup

0≤t≤T

(S⁽ⁿ⁾(t)−X⁽ⁿ⁾(t))→0

inP₀probability. By the “converging together” theorem ([6, Theorem 3.1]) we conclude thatX⁽ⁿ⁾converges weakly toDB^∗in the (locally) uniform topology, and, thus, inJ1. Proof of Lemma 5.1. Letk ∈N^and 0 =x0 < x1 <· · · < xk. We have to show that for any0 =t0< t1< t2<· · ·< tk

P₀(T⁽ⁿ⁾(x_k)−T⁽ⁿ⁾(x_i)≤t_k−i, ∀i= 0,1,2, . . . , k−1)

→P(T(x_k)−T(x_i)≤t_k−i, ∀i= 0,1, . . . , k−1), asn→ ∞, whereT(·) =cH(·)for somec >0.

At timeT_[nxk] consider the structure of the corresponding branching process as we look back from [nxk]. Notice thatD_[nxi],j ≤ D_[nxk],j fori ≤ k and allj. This simple observation will allow us to get bounds on T_[nxi], i = 1,2, . . . , k−1, in terms of the structure of downcrossings at timeT[nx_k]. This means that we can use the same copy of the branching processV to draw conclusions about all hitting timesT_[nxi],i= 1,2, . . . , k.

We shall use notation (2.4) and letN⁽⁰⁾= 0,

N^(k−i)= min{m∈N: σm≥[nxk]−[nxi]}, i= 0,1,2, . . . , k−1.

Since

2

N^(k−i)−1

X

j=1

Σj≤T_[nxk]−T_[nxi]≤nxk−nxi+ 2

N^(k−i)

X

j=1

Σj, we have

P0(T⁽ⁿ⁾(xk)−T⁽ⁿ⁾(xi)≤t_k−i, ∀i= 0,1,2, . . . , k−1)

≤P



2

N^(k−i)−1

X

j=1

Σ_j ≤n²t_k−i/log²n, ∀i= 0,1,2, . . . , k−1



 (5.3)

and

P₀(T⁽ⁿ⁾(x_k)−T⁽ⁿ⁾(x_i)≤t_k−i, ∀i= 0,1,2, . . . , k−1)

≥P



[nxk]−[nxi] + 2

N^(k−i)

X

j=1

Σj≤n²tk−i/log²n, ∀i= 0,1,2, . . . , k−1



. (5.4)

Next we provide some control onN^(k−i),i= 0,1, . . . , k−1, and on the maximal lifetime over[nx_k]generations. Theorem 2.1 and [10, Theorem 3.7.2] imply thatσ_n/(nlogn)⇒ b⁻¹for some positive constantb. From this it is easily seen that

min{m∈N: σm> n}

nb/logn ⇒1 asn→ ∞. (5.5)

Recalling our definition ofN^(k−i)we get that for everyε, ν >0there isn₀such that for alln≥n₀

P

1−ν ≤N^(k−i)

N¯^(k−i) ≤1 +ν, i= 0, . . . , k−1

>1−ε,

whereN¯^(k−i)=b(x_k−x_i)n/logn. In particular, forC= (1 +ν)bx_kwe have that P

N^(k)≤ Cn logn

>1−ε.

Defineλn = (logn)^−1/2 (any sequenceλn, n∈ N, such that λn → 0and λnlogn → ∞ will work) and notice that by Theorem 2.1 there isn1such that for alln≥n1

P

1≤i≤Cn/maxlogn(σi−σi−1)≤nλn

≥

1− 2C₁ nλn

Cn/logn

>1−ε.

Thus, on a setΩεof measure at least1−2εfor alln≥n0∨n1the number of lifetimes of the branching process V covering [nxk]−[nxi] generations, i = 0,1,2, . . . , k−1, is well controlled and the maximal lifetime over[nxk]generations does not exceednλn. In particular, onΩε, the number of lifetimes in any interval([nxi],[nxi+1]), i= 0,1, . . . , k−1, goes to infinity asn→ ∞.

Finally, onΩ_εwe get from (5.3) and (5.1) that P0(T⁽ⁿ⁾(xk)−T⁽ⁿ⁾(xi)≤t_k−i, ∀i= 0,1,2, . . . , k−1)

≤P



2

(1−ν) ¯N^(k−i)−1

X

j=1

Σ_j≤n²t_k−i/log²n, ∀i= 0,1,2, . . . , k−1





=P





P(1−ν) ¯N^(k−i)−1

j=1 Σj

((1−ν)n/logn)² ≤ t_k−i

2(1−ν)², ∀i= 0,1,2, . . . , k−1





→P(aH(b(x_k−x_i))≤(1−ν)⁻²t_k−i/2∀i= 0,1,2, . . . , k−1)

=P(2ab²(H(xk)−H(xi))≤tk−i(1−ν)⁻²)∀i= 0,1,2, . . . , k−1).

The lower bound is shown starting from (5.4) in exactly the same way. Lettingν → 0 and thenε→0we obtain the statement of the lemma withT(·) = 2ab²H(·) =:cH(·). Proof of Lemma 5.2. Without loss of generality we can consider t ∈ [0,1]. Fix some ν >0. We have

P₀

sup

0≤t≤1

(S⁽ⁿ⁾(t)−X⁽ⁿ⁾(t))> ε

≤P₀(S_n≥K√

nlnn)+

P0

0≤m≤nmax (Sm−Xm)> ε√

nlnn, Sn< K√ nlnn)

. (5.6)

By Lemma 5.1 we can findK >0such that for all largen P₀(S_n ≥K√

nlnn)≤P₀(T_[K^√_nlnn] ≤n)< ν.

To estimate the last term in (5.6) we shall use properties of the branching processV.

LetN = min{m∈N: σ_m> K√

nlnn}. Then the last term in (5.6) is bounded by P₀^V

maxi≤N(σi−σi−1)≥ε√ nlnn

≤ P₀^V(N > C√

n) +P₀^V

max

i≤C√ n

(σi−σ_i−1)≥ε√

nlnn, N ≤C√ n

_(5.5)

≤ ν+P₀^V

max

i≤C√ n

(σi−σi−1)≥ε√ nlnn

, for some largeCand all sufficiently largen. Finally, from (2.2) we conclude that for all large enoughnthe last probability does not exceed

1−

1− 2C1

ε√ nlnn

[C√ n]

< ν.

This completes the proof.

References

[1] Aldous, D.: Stopping times and tightness, II.Ann. Probab.17, (1989), no. 2. 586–595. MR- 0985380

[2] Basdevant, A.-L. and Singh, A.: On the speed of a cookie random walk. Probab. Theory Related Fields141, (2008), no. 3-4, 625–645. MR-2391167

[3] Basdevant, A.-L. and Singh, A.: Rate of growth of a transient cookie random walk.Electron.

J. Probab.13, (2008), no. 26, 811–851. MR-2399297

[4] Benjamini, I. and Wilson, D. B.: Excited random walk.Electron. Comm. Probab.8, (2003), 86–92. MR-1987097

[5] Bérard, J. and Ramírez, A.: Central limit theorem for the excited random walk in dimension d≥2.Elect. Comm. in Probab. 12, (2007), no. 30, 303–314. MR-2342709

[6] Billingsley, P.: Convergence of probability measures. Second edition. John Wiley & Sons, Inc., New York, 1999. x+277 pp. MR-1700749

[7] Chaumont, L. and Doney, R. A.: Pathwise uniqueness for perturbed versions of Brownian motion and reflected Brownian motion,Probab. Theory Related Fields 113, (1999), no. 4, 519–534. MR-1717529

[8] Davis, B.: Weak limits of perturbed random walks and the equationYt=Bt+αsup{Ys: s≤ t}+βinf{Ys: s≤t},Ann. Probab.24, (1996), 2007–2023. MR-1415238

[9] Dolgopyat, D.: Central limit theorem for excited random walk in the recurrent regime.ALEA, Lat. Am. J. Prob. Mat. Stat.8, (2011), 259–268. MR-2831235

[10] Durrett, R.: Probability: theory and examples. Fourth edition. Cambridge Series in Statis- tical and Probabilistic Mathematics.Cambridge University Press, Cambridge, 2010. x+428 pp. MR-2722836

[11] Gihman, I. I. and Skorohod, A. V.: The theory of stochastic processes. I. Translated from the Russian by S. Kotz. Die Grundlehren der mathematischen Wissenschaften, Band 210.

Springer-Verlag, New York-Heidelberg, 1974. viii+570 pp. MR-0346882

[12] Gikhman, I. I. and Skorokhod, A. V.: Introduction to the theory of random processes. Trans- lated from the Russian by Scripta Technica, Inc.. W. B. Saunders Co., Philadelphia, Pa.- London-Toronto, Ont., 1969. xiii+516 pp. MR-0247660

[13] Hall, P. and Heyde, C. C.: Martingale limit theory and its application.Academic Press, Inc., New York-London, 1980, xii+308 pp. MR-0624435

[14] Kosygina, E. and Zerner, M. P. W.: Positively and negatively excited random walks on inte- gers, with branching processes,Electron. J. Probab.,13, no. 64, 1952–1979. MR-2453552 [15] Kosygina, E. and Mountford, T.: Limit laws of transient excited random walks on integers.

Ann. Inst. H. Poincaré Probab. Statist. 47, (2011), no. 2, 575–600. MR-2814424

[16] Menshikov, M., Popov, S., Ramirez, A., and Vachkovskaya, M.: On a general many- dimensional excited random walk.Ann. Probab., to appear.

[17] Mountford, T., Pimentel, L. P. R., and Valle, G.: On the speed of the one-dimensional excited random walk in the transient regime.Alea2, (2006), 279–296. MR-2285733

[18] Perman, M. and Werner, W.: Perturbed Brownian motions,Prob. Theory Related Fields,108, (1997), no. 3, 357–383. MR-1465164

[19] Peterson, J.: Large deviations and slowdown asymptotics for one-dimensional excited ran- dom walks. arXiv:1201.0318

[20] Rastegar, R. and Roiterstein, A.: Maximum occupation time of a transient excited random walk onZ. arXiv:1111.1254

[21] Toth, B.: Generalized Ray-Knight theory and limit theorems for self-interacting random walks onZ¹.Ann. Probab.24, (1996), 1324–1367. MR-1411497

[22] Zerner, M. P. W.: Multi-excited random walks on integers.Probab. Theory Related Fields 133, (2005), 98–122. MR-2197139

[23] Zerner, M. P. W.: Recurrence and transience of excited random walks onZ^d and strips.

Electron. Comm. Probab.11, (2006), no. 12, 118–128. MR-2231739

Acknowledgments. The authors are grateful to the Fields Institute for Research in Mathematical Sciences for support and hospitality. D. Dolgopyat was partially sup- ported by the NSF grant DMS 0854982. E. Kosygina was partially supported by a Collaboration Grant for Mathematicians (Simons Foundation) and PSC CUNY Award

# 64603-0042. The authors also thank the anonymous referee for careful reading of the paper and remarks which helped to improve the exposition.