1Introduction [email protected] THESCALINGLIMITOFSENILEREINFORCEDRANDOMWALK.

ELECTRONIC COMMUNICATIONS in PROBABILITY

THE SCALING LIMIT OF

SENILE REINFORCED RANDOM WALK.

MARK HOLMES¹

Department of Statistics, The University of Auckland, Private Bag 92019, Auckland 1142, New Zealand.

email: [email protected]

SubmittedAugust 20, 2008, accepted in final formFebruary 4, 2009 AMS 2000 Subject classification: 60G50,60K35,60J10,60G52

Keywords: random walk; reinforcement; invariance principle; fractional kinetics; time-change Abstract

We prove that the scaling limit of nearest-neighbour senile reinforced random walk is Brownian Motion when the time T spent on the first edge has finite mean. We show that under suitable conditions, when T has heavy tails the scaling limit is the so-calledfractional kinetics process, a random time-change of Brownian motion. The proof uses the standard tools of time-change and invariance principles for additive functionals of Markov chains.

1 Introduction

The senile reinforced random walk is a toy model for a much more mathematically difficult model known as edge-reinforced random walk (for which many basic questions remain open[e.g. see [15]]). It is characterized by a reinforcement function f :N→ [−1,∞), and has the property that only the most recently traversed edge is reinforced. As soon as a new edge is traversed, rein- forcement begins on that new edge and the reinforcement of the previous edge is forgotten. Such walks may get stuck on a single (random) edge if the reinforcement is strong enough, otherwise (except for one degenerate case) they are recurrent/transient precisely when the corresponding simple random walk is[9].

Formally, a nearest-neighbour senile reinforced random walkis a sequence{S_n}_n≥0of Z^d-valued random variables on a probability space(Ω,F,P

f), with corresponding filtration{F_n=σ(S₀, . . . ,S_n)}_n≥0, defined by:

• S₀=o,P_f-almost surely, andP_f(S₁=x) = (2d)⁻¹I_{|x|=1}.

• Forn∈N,e_n= (S_n−1,S_n)is anF_n-measurableundirectededge and

m_n=max{k≥1 :e_n−l+1=e_nfor all 1≤l≤k} (1.1) is anF_n-measurable,N-valued random variable.

1RESEARCH SUPPORTED BY THE NETHERLANDS ORGANISATION FOR SCIENTIFIC RESEARCH (NWO)

104

• Forn∈Nandx∈Z^dsuch that|x|=1,

P_f(S_n+1=S_n+x|F_n) =1+f(m_n)I_{{(Sn,Sn+x)=en}}

2d+f(m_n) . (1.2)

Note that the triple (S_n,e_n,m_n)(equivalently (S_n,S_n−1,m_n)) is a Markov chain. Hereafter we suppress thef dependence of the probabilityP_f in the notation.

The diffusion constant is defined as lim_n→∞n⁻¹E[|S_n|²](=1 for simple random walk) whenever this limit exists. Let T denote the random number of consecutive traversals of the first edge traversed, andp=P(T is odd). Then whenE[T]<∞, the diffusion constant is given by ([9]and [11])

v= d p

(d−p)E[T], (1.3)

which is not monotone in the reinforcement. Indeed one can prove that (1.3) holds for all f (in the cased=1 and f(1) =−1 this must be interpreted as “ 1/0=∞”). The reinforcement regime of most interest is that of linear reinforcement f(n) =C nfor someC. In this case, by the second order mean-value theorem applied to log(1−x),x<1 we have

P(T ≥n):=

Yn−1

j=1

1+f(j) 2d+f(j)=exp







n−1X

j=1

log

1− 2d−1 2d+C j







=exp







− Xn−1

j=1

2d−1 2d+C j−

Xn−1

j=1

(2d−1)² 2(2d+C j)²(1−u_j)²







=exp







− Xn−1

j=1

2d−1 2d+C j−

X∞

j=1

(2d−1)²

2(2d+C j)²(1−u_j)²+o(1)







=exp

½

−2d−1

C log(2d+C(n−1)) +γ+o(1)

¾

∼ κ n^2d−1C

,

(1.4)

whereu_i ∈(0, ^2d−1

2d+C j), andγis a constant arising from the summable infinite series and the ap- proximation of the finite sum by a log. An immediate consequence of (1.4) is that for f(n) =C n, E[T]is finite if and only ifC<2d−1.

A different but related model, in which the current direction (rather than the current edge) is reinforced according to the functionf was studied in[12, 10]. For such a model,T is the number of consecutive steps in the same direction before turning. In [10], the authors show that in all dimensions the scaling limit is Brownian motion whenσ²=Var(T)<∞andσ²+1−1/d>0. In the language of this paper, the last condition corresponds to the removal of the special cased=1 and f(1) =−1. Moreover when d=1 and T has heavy tails (in the sense of (2.1) below) they show that the scaling limit is anα-stable process when 1< α <2 and a random time change of anα-stable process when 0< α <1. See[10]for more details.

Davis[4]showed that the scaling limit of once-reinforced random walk in one dimension is not Brownian motion (see[15]for further discussion).

In Section 2 we state and discuss the main result of this paper, which describes the scaling limit of S_n when eitherE[T]< ∞ orP(T ≥n)∼ n^−αL(n)for someα > 0 and L slowly varying at infinity. WhenP(T <∞)<1 the walk has finite range since it traverses a random (geometric) number of edges before getting stuck on a random edge. To prove the main result, in Section 3 we observe the walk at the times that it has just traversed a new edge and describe this as an additive functional of a particular Markov chain. In Section 4 we prove the main result assuming the joint convergence of this time-changed walk and the associated time-change process. In Section 5 we prove the convergence of this joint process.

2 Main result

The assumptions that will be necessary to state the main theorem of this paper are as follows:

(A1) P(T<∞) =1, and eitherd>1 orP(T =1)<1.

(A2a) EitherE[T]<∞, or for someα∈(0, 1]andLslowly varying at infinity,

P(T≥n)∼L(n)n^−α. (2.1)

(A2b) If (2.1) holds butE[T] =∞, then we also assume that

whenα=1, ∃ ℓ(n)↑ ∞such that(ℓ(n))⁻¹L(nℓ(n))→0, and(ℓ(n))⁻¹

⌊nℓ(n)⌋

X

j=1

j⁻¹L(j)→1, whenα <1, P(T ≥n,T odd)∼L_o(n)n^−αo, andP(T ≥n,T even)∼L_e(n)n^−αe,

(2.2)

whereℓ, L_o and L_e are slowly varying at∞ and L_o and L_e are such that if α_o =α_e then L_o(n)/L_e(n)→β∈[0,∞]asn→ ∞.

Note that both (2.1) andE[T]<∞may hold whenα=1 (e.g. take L(n) = (logn)⁻²).

By[6, Theorem XIII.6.2], whenα <1 there existsℓ(·)>0 slowly varying such that (ℓ(n))^−αL

n^1αℓ(n)

→(Γ(1−α))⁻¹. (2.3)

Forα >0 let

g_α(n) = (

E[T]n , ifE[T]<∞

n^1αℓ(n) , otherwise (2.4)

By[3, Theorem 1.5.12], there exists an asymptotic inverse function g_α⁻¹(·)(unique up to asymp- totic equivalence) satisfying g_α(g_α⁻¹(n)) ∼ g_α⁻¹(g_α(n))∼ n, and by[3, Theorem 1.5.6]we may assume thatg_αandg_α⁻¹are monotone nondecreasing.

A subordinator is a real-valued process starting at 0, with stationary, independent increments, such that almost every path is nondecreasing and right continuous. Let B_d(t)be a standard d- dimensional Brownian motion. Forα≥1, letV_α(t) =t and forα∈(0, 1), letV_αbe a standard α-stable subordinator (independent ofB_d(t)). This is a strictly increasing pure-jump Levy process whose law is specified by the Laplace transform of its one-dimensional distributions (see e.g.[2, Sections 1.1 and 1.2])

E[e^−λVα(t)]:=e^−tλα. (2.5)

Define the right-continuous inverse ofV_α(t)and (whenα <1 the fractional-kinetics process)Z_α(s) by

V_α⁻¹(s):=inf{t:V_α(t)>s}, Z_α(s) =B_d(V_α⁻¹(s)). (2.6) SinceV_αis strictly increasing, bothV_α⁻¹andZ_αare continuous (almost-surely). The main result of this paper is the following theorem, in whichD(E,R^d)is the set ofcadlagpaths fromEtoR^d. Throughout this paper=⇒denotes weak convergence.

Theorem 2.1. Suppose that f is such that (2.1) holds for someα >0, then as n→ ∞, S_⌊nt⌋

Æ _p

d−pg_α⁻¹(n)

=⇒Z_α(t), (2.7)

where the convergence is in D([0, 1],R^d)equipped with the uniform topology.

2.1 Discussion

The limiting object in Theorem 2.1 is the scaling limit of a simple random walk jumping at random timesτ_i with i.i.d. incrementsT_i=τ_i−τ_i−1(e.g. see[13]) that are independent of the position and history of the walk. In[1]the same scaling limit is obtained for a class of (continuous time) trap models withd≥2, where a random jump rate or waiting time is chosen initially at each site and remains fixed thereafter. In that work, whend=1, the mutual dependence of the time spent at a particular site on successive returns remains in the scaling limit, where the time change/clock process depends on the (local time of the) Brownian motion itself. The independence on returning to an edge is the feature which makes our model considerably easier to handle. For the senile reinforced random walk, the direction of the steps of the walk is dependent on the clock and we need to prove that the dependence is sufficiently weak so that it disappears in the limit.

While the slowly varying functions ing_αandg_α⁻¹are not given explicitly, in many cases of interest one can use[6, Theorem XIII.6.2]and[3, Section 1.5.7]to explicitly construct them. For example, letL(n) =κ(logn)^βfor someβ≥ −1. Forα=1 we can take

ℓ(n) =







κlogn, ifβ=0

κ(log logn), ifβ=−1

|β⁻¹|κ(logn)^β+1, otherwise,

and g_α⁻¹(n) =







n(κlogn)⁻¹, ifβ=0 n(κlog logn)⁻¹, ifβ=−1 n|β|(κlogn)^−(β+1), otherwise.

(2.8) Ifα <1 we can take

ℓ(n) =

‚

κΓ(1−α) logn

α βŒ¹_α

, and g⁻¹_α (n) =n^α€

κ(αlogn)^βŠ−α

. (2.9) Assumption (A1) is simply to avoid the trivial cases where the walk gets stuck on a single edge (i.e. when(1+f(n))⁻¹is summable[9]) or is a self-avoiding walk in one dimension. For linear reinforcement f(n) =C n, (1.4) shows that assumption (A2) holds withα= (2d−1)/C. It may be of interest to consider the scaling limit when f(n)grows likenℓ(n), where lim inf_n→∞ℓ(n) =∞ but such that(1+f(n))⁻¹is not summable. An example is f(n) =nlogn, for whichP(T ≥n)∼ (Clogn)⁻¹satisfies (2.1) withα=0.

The condition (2.2) when α = 1 is so that one can apply a weak law of large numbers. The condition holds for example when L(n) = (logn)^k for any k ≥ −1. For the α < 1 case, the

condition (2.2) holds (with α_o = α_e and L_o = L_e) whenever there exists n₀ such that for all n≥ n₀, f(n) ≥ f(n−1)−(2d−1)(so in particular when f is non-decreasing). To see this, observe that for alln≥n₀

P(T≥n,T even) = X∞

m=⌊ⁿ⁺¹₂ ⌋

P(T=2m) = X∞

m=⌊ⁿ⁺¹₂ ⌋

P(T=2m+1)2d+f(2m+1) 1+f(2m)

≥ X∞

m=⌊ⁿ⁺¹₂ ⌋

P(T=2m+1) =P(T ≥n+1,T odd).

(2.10)

Similarly,P(T≥n,T odd)≥P(T ≥n+1,T even)for alln≥n₀. Ifα_o6=α_e in (2.2), then (2.1) implies thatα=α_o∧α_eandLis the slowly varying function corresponding toα∈ {α_o,α_e}in (2.2).

Ifα_o=α_e then trivially L∼L_o+L_e (∼L_o ifL_o(n)/L_e(n)→ ∞). One can construct examples of reinforcement functions giving rise to different asymptotics for the even and odd cases in (2.2), for example by taking f(2m) =m²and f(2m+1) =C mfor some well chosen constantC >0 depending on the dimension.

3 Invariance principle for the time-changed walk

In this section we prove an invariance principle for any senile reinforced random walk (satisfying (A1)) observed at stopping timesτ_ndefined by

τ₀=0, τ_k=inf{n>(τ_k−1∨1):S_n6=S_n−2}. (3.1) It is easy to see thatτ_n=1+P_n

i=1T_i for eachn≥1, where the T_i,i ≥1 are independent and identically distributed random variables (with the same distribution as T), corresponding to the number of consecutive traversals of successive edges traversed by the walk.

Proposition 3.1. If (A1) is satisfied, then ^p

d−pn−¹₂

S_τ⌊nt⌋ =⇒B_d(t)as n→ ∞, where the conver- gence is in D([0, 1],R^d)with the uniform topology.

The process S_τn is a simpler one than S_n and one may use many different methods to prove Proposition 3.1 (see for example the martingale approach of [11]). We give a proof based on describing S_τn as an additive functional of a Markov chain. This is not necessarily the simplest representation, but it is the most natural to the author.

Let X denote the collection of pairs(u,v) such that v is one of the unit vectors u_i ∈ Z^d, for i∈ {±1,±2,· · · ±d}(labelled so thatu_−i=−u_i) anduis either 0∈Z^d or one of the unit vectors u_i6=−v. The cardinality ofX is then|X |=2d+2d(2d−1) = (2d)².

Given a senile reinforced random walk S_nwith parameter p =P(T odd)∈(0, 1], we define an irreducible, aperiodic Markov chain X_n= (X^[1]_n ,X_n^[2])with natural filtrationG_n=σ(X₁, . . . ,X_n), and finite state-spaceX, as follows.

Forn≥1, letX_n= (S_τn−1−S_τ(n−1),S_τn−S_τn−1), andY_n=X_n^[1]+X_n^[2]. It follows immediately that S_τn=P_n

m=1Y_mand P(X₁= (0,u_i)) = 1−p

2d , and P(X₁= (u_i,u_j)) = p

2d(2d−1), for eachi,j, (j6=−i).

(3.2)

NowT_nis independent ofX₁, . . . ,X_n−1, and conditionally onT_nbeing odd (resp. even),S_τn−S_τ(n−1) (resp. S_τn−S_τn−1) is uniformly distributed over the 2d−1 unit vectors inZ^d other than−X_n−1^[2]

(resp. other than X_n−1^[2]). It is then an easy exercise to verify that{X_n}_n≥1is a finite, irreducible and aperiodic Markov chain with initial distribution (3.2) and transition probabilities given by

P X_n= (u,v)|X_n−1= (u^′,v^′)

= 1

2d−1×







p, ifu=0 andv6=−v^′, 1−p, ifu=−v^′andv6=v^′, 0, otherwise.

(3.3)

By symmetry, the first 2dentries of the unique stationary distribution π~ ∈M₁(X)are all equal (sayπ_a) and the remaining 2d(2d−1)entries are all equal (sayπ_b), and it is easy to check that

π_a= p

2d, π_b= 1−p

2d(2d−1). (3.4)

As an irreducible, aperiodic, finite-state Markov chain,{X_n}_n≥1hasexponentially fast, strong mix- ing, i.e. there exists a constantcandt<1 such that for everyk≥1,

α(k):=sup

n

n

|P(F∩G)−P(F)P(G)|:F∈σ(X_j,j≤n),G∈σ(X_j,j≥n+k) o

≤c t^k. (3.5) Since Y_n is measurable with respect to X_n, the sequence Y_n also has exponentially fast, strong mixing. To verify Proposition 3.1, we use the following multidimensional result that follows easily from[8, Corollary 1]using the Cramér-Wold device.

Corollary 3.2. Suppose that W_n = (W_n⁽¹⁾, . . . ,W_n^(d)), n ≥ 0 is a sequence of R^d-valued random variables such thatE[W_n] =0,E[|W_n|²]<∞andE[n⁻¹P_n

i=1

P_n

i^′=1W_i^(j)W_i^(l)′ ]→σ²I_j=l, as n→

∞. Further suppose that W_nisα-strongly mixing and that there existsβ∈(2,∞]such that X∞

k=1

α(k)^1−2/β<∞, and lim sup

n→∞

kW_nk_β<∞, (3.6)

thenW_n(t):= (σ²n)⁻¹²P_⌊nt⌋

i=1W_i =⇒ B_d(t)as n→ ∞, where the convergence is in D([0, 1],R^d) equipped with the uniform topology.

3.1 Proof of Proposition 3.1

SinceS_τn = P_n

m=1Y_m where|Y_m| ≤ 2, and the sequence {Y_n}_n≥0 has exponentially fast strong mixing, Proposition 3.1 will follow from Corollary 3.2 provided we show that

E



 1 n

Xn

i=1

Xn

i^′=1

Y_i^(j)Y_i^(l)′



→ p

d−pI_j=l, (3.7)

where the superscript(j)denotes the jth component of the vector, e.g.Y_m = (Y_m⁽¹⁾, . . . ,Y_m^(d)). By symmetry,E[Y_i^(j)Y_i^(l)′ ] =0 for alli,i^′and j6=l, and it suffices to prove (3.7) withj=l=1.

Forn≥2,E[X_n^[2],(1)|X_n−1] =^2p−1

2d−1X_n−1^[2],(1), so by induction and the Markov property, E[X_n^[2],(1)|X_m] =

2p−1 2d−1

n−m

X_m^[2],(1), for everyn≥m≥1. (3.8)

Forn≥2,E[Y_n⁽¹⁾|X_n−1] = ^{p−2d(1−p)}_2d−1 X_n−1^[2],(1), and the Markov property forX_nimplies that E[Y_n⁽¹⁾|X_m] =p−2d(1−p)

2d−1

2p−1 2d−1

n−1−m

X^[2],(1)_m , forn>m≥1. (3.9) Forn>m≥1, and lettingr= ^2p−1

2d−1we have

E[Y_n⁽¹⁾Y_m⁽¹⁾] =E[Y_m⁽¹⁾E[Y_n⁽¹⁾|X_m]] = p−2d(1−p)

2d−1 r^n−1−mE[Y_m⁽¹⁾X^[2],(1)_m ]

=p−2d(1−p)

2d−1 r^n−1−m€

E[X^[1],(1)_m X_m^[2],(1)] +E[(X^[2],(1)_m )²]Š

=p−2d(1−p)

2d−1 r^n−1−m×

( _1−p

d(2d−1)+¹

d, m≥2

p d(2d−1)+¹

d, m=1.

(3.10)

LastlyE[|Y₁|²] = (1−p) + ^{4d p}

2d−1 andE[|Y_m|²] =p+^4d(1−p)

2d−1 , form≥2.

Combining these results, we get that E



 Xn

l=1

Xn

m=1

Y_l⁽¹⁾Y_m⁽¹⁾



=2 Xn

l=2

Xl−1

m=2

E[Y_l⁽¹⁾Y_m⁽¹⁾] +2 Xn

l=2

E[Y_l⁽¹⁾Y₁⁽¹⁾] + Xn

l=1

E[|Y_l⁽¹⁾|²]

=2 d

p−2d(1−p) 2d−1





2d−p 2d−1

n

X

l=2

Xl−2

k=0

r^k+ Xn

l=2

2d−1+p 2d−1 r^l−2





+1−p

d + 4p

2d−1+ (n−1) p

d+4(1−p) 2d−1

.

(3.11)

Sincer<1, the second sum overlis bounded by a constant, uniformly inn. Thus, this is equal to 2

d

p−2d(1−p) 2d−1

2d−p 2d−1

n

X

l=2

1−r^l−2 1−r +n

p

d +4(1−p) 2d−1

+O(1)

=n 2

d(1−r)

p−2d(1−p) 2d−1

2d−p 2d−1

+ p

d+4(1−p) 2d−1

+O(1)

=n

(p−2d(1−p))(2d−p) d(d−p)(2d−1) + p

d+4(1−p) 2d−1

+O(1) =n p

d−p+O(1).

(3.12)

Dividing bynand taking the limit asn→ ∞verifies (3.7) and thus completes the proof of Propo- sition 3.1.

4 Proof of Theorem 2.1

Theorem 2.1 is a consequence of convergence of the joint distribution of the rescaled stopping time process and the random walk at those stopping times as in the following proposition.

Proposition 4.1. Suppose that assumptions (A1) and (A2) hold for someα >0, then as n→ ∞,





 S_τ⌊nt⌋

Æ _p

d−pn, τ_⌊nt⌋

g_α(n)





=⇒ B_d(t),V_α(t)

, (4.1)

where the convergence is in€

D([0, 1],R^d),UŠ

× D([0, 1],R),J₁

, and whereU and J₁denote the uniform and Skorokhod J₁topologies respectively.

Proof of Theorem 2.1 assuming Proposition 4.1. Since⌊g_α⁻¹(n)⌋is a sequence of positive integers such that⌊g_α⁻¹(n)⌋ → ∞andn/g_α(⌊g⁻¹_α (n)⌋)→1 asn→ ∞, it follows from (4.1) that asn→ ∞,





 S_τ

⌊⌊g−1 α (n)⌋t⌋

Æ _p

d−p⌊g_α⁻¹(n)⌋, τ_⌊⌊g−1

α(n)⌋t⌋

n





=⇒ B_d(t),V_α(t)

, (4.2)

in€

D([0, 1],R^d),UŠ

× D([0, 1],R),J₁ . Let

Y_n(t) = S_τ

⌊⌊g−1 α (n)⌋t⌋

Æ _p

d−p⌊g⁻¹_α (n)⌋, and T_n(t) = τ_⌊⌊g⁻¹

α (n)⌋t⌋

n , (4.3)

and letT_n⁻¹(t):=inf{s≥0 :T_n(s)> t}=inf{s≥0 :τ_⌊⌊g−1

α (n)⌋s⌋ >nt}. It follows (e.g. see the proof of Theorem 1.3 in[1]) thatY_n(T_n⁻¹(t)) =⇒B_d(V_α⁻¹(t))in€

D([0, 1],R^d),UŠ . Thus, S_τ

⌊⌊g−1 α (n)⌋T −1

n (t)⌋

Æ _p

d−pg_α⁻¹(n)=⇒B_d(V_α⁻¹(t)). (4.4) By definition ofT_n⁻¹, we haveτ_⌊⌊g−1

α (n)⌋T_n⁻¹(t)⌋−1≤nt≤τ_⌊⌊g−1

α(n)⌋T_n⁻¹(t)⌋and hence|S_⌊nt⌋−S_τ

⌊⌊g−1 α (n)⌋T −1

n (t)⌋| ≤ 3. Together with (4.4) and the fact thatg_α⁻¹(n)/⌊g_α⁻¹(n)⌋ →1, this proves Theorem 2.1.

5 Proof of Proposition 4.1

The proof of Proposition 4.1 is broken into two parts. The first part is the observation that the marginal processes converge, i.e. that the time-changed walk and the time-change converge to B_d(t)andV_α(t)respectively, while the second is to show that these two processes are asymptoti- cally independent.

5.1 Convergence of the time-changed walk and the time-change.

Lemma 5.1. Suppose that assumptions (A1) and (A2) hold for someα >0, then as n→ ∞, S_τ⌊nt⌋

Æ _p

d−pn=⇒B_d(t) in(D([0, 1],R^d),U), and τ_⌊nt⌋

g_α(n)=⇒V_α(t) in(D([0, 1],R),J₁). (5.1) Proof. The first claim is the conclusion of Proposition 3.1, so we need only prove the second claim.

Recall that τ_n=1+P_n

i=1T_i where theT_i are i.i.d. with distribution T. Since g_α(n)→ ∞, it is enough to show convergence ofτ^∗_⌊nt⌋= (τ_⌊nt⌋−1)/g_α(n).

For processes with independent and identically distributed increments, a standard result of Sko- rokhod essentially extends the convergence of the one-dimensional distributions to a functional central limit theorem. WhenE[T]exists, convergence of the one-dimensional marginalsτ^∗_⌊nt⌋/nE[T] =⇒ t is immediate from the law of large numbers. The caseα <1 is well known, see for example [6, Section XIII.6]and[16, Section 4.5.3]. The case whereα=1 but (2.1) is not summable is perhaps less well known. Here the result is immediate from the following lemma.

Lemma 5.2. Let T_k≥0be independent and identically distributed random variables satisfying (2.1) and (2.2) withα=1. Then for each t≥0,

τ^∗_⌊nt⌋

nℓ(n)

−→P t. (5.2)

Lemma 5.2 is a corollary of the following weak law of large numbers due to Gut[7].

Theorem 5.3([7], Theorem 1.3). Let X_k be i.i.d. random variables and S_n=P_n

k=1X_k. Let g_n= n^1/αℓ(n)for n≥1, whereα∈(0, 1]andℓ(n)is slowly varying at infinity. Then

S_n−nE”

X I_{|X|≤gn}— g_n

−→P 0, as n→ ∞, (5.3)

if and only if nP(|X|>g_n)→0.

Proof of Lemma 5.2. Note that

E”

T I_{{T≤nℓ(n)}}—

=

⌊nℓ(n)⌋

X

j=1

P(nℓ(n)≥T≥j) =

⌊nℓ(n)⌋

X

j=1

P(T≥ j)− ⌊nℓ(n)⌋P(T ≥nℓ(n)). (5.4) Now by assumption (A2b),

n nℓ(n)E”

T I{|T|≤nℓ(n)}

—= P_{⌊nℓ(n)⌋}

j=1 P(T≥j)

ℓ(n) −⌊nℓ(n)⌋

ℓ(n) P(T≥nℓ(n))

∼ P⌊nℓ(n)⌋

j=1 j⁻¹L(j)

ℓ(n) −⌊nℓ(n)⌋

ℓ(n) (nℓ(n))⁻¹L(nℓ(n))→1.

(5.5)

Theorem 5.3 then implies that(nℓ(n))⁻¹τ_n−→^P 1, from which it follows immediately that (nℓ(n))⁻¹τ_⌊nt⌋= (nℓ(n))⁻¹⌊nt⌋ℓ(⌊nt⌋)(⌊nt⌋ℓ(⌊nt⌋))⁻¹τ_⌊nt⌋−→^P t. (5.6) This completes the proof of Lemma 5.2, and hence Lemma 5.1.

5.2 Asymptotic Independence

Tightness of the joint process in Proposition 4.1 is an easy consequence of the tightness of the marginal processes (Lemma 5.1), so we need only prove convergence of the finite-dimensional distributions (f.d.d.s). Forα≥1 this is simple and is left as an exercise. To complete the proof of Proposition 4.1, it remains to prove convergence of the f.d.d.s whenα <1 (hencep<1).

Let G₁ and G₂ be convergence determining classes of bounded, C-valued functions on R^d and R₊respectively, each closed under conjugation and containing a non-zero constant function, then {g(x₁,x₂) := g₁(x₁)g₂(x₂) : g_i ∈ G_i} is a convergence determining class for R^d×R₊. This follows as in[5, Proposition 3.4.6]where the closure under conjugation allows us to extend the proof to complex-valued functions. Therefore, to prove convergence of the finite-dimensional distributions in (4.1) it is enough to show that for every 0≤t₁<· · ·<t_r≤1,k₁, . . . ,k_r∈R^d and η₁, . . . ,η_r≥0,

E





exp

¨ i

Xr

j=1

k_j·S_τ⌊

nt j⌋

Æ _p

d−pn

−η_jτ_⌊ntj⌋ g_α(n)

«





→E



exp

¨ i

Xr

j=1

k_j·B_d(t_j)

«

E



exp

¨

− Xr

j=1

η_jV_α(t_j)

«

. (5.7)

From (2.6) and the fact thatV_α has independent increments, the rightmost expectation can be written as exp{−P_r

l=1(η^∗_l)^α(t_l−t_l−1)}, whereη^∗_l =P_r

j=lη_j. Let A_n =

i∈ {1, . . . ,n}:T_iis odd , A_⌊n~t⌋ = (A_⌊nt1⌋\ A_⌊nt0⌋, . . . ,A_⌊ntr⌋\ A_{⌊ntr−1⌋})and t₀ = 0.

For fixed nand~t, we writeA= (A⁽¹⁾, . . . ,A^(r))to denote an element of the range of the random variableA_⌊n~t⌋, whereA⁽ⁱ⁾⊆ {⌊nt_i−1⌋+1, . . . ,⌊nt_i⌋}for eachi∈1, . . . ,r. Observe that|A_⌊n~^(l)

t⌋|has a binomial distribution with parameters⌊nt_l⌋ − ⌊nt_l−1⌋andp. Then forε∈(0,¹

2)andB_n(~t):={A:

||A^(l)| −(⌊nt_lp⌋ − ⌊nt_l−1p⌋)| ≤n^1−ε for eachl}, we have thatP(B_n(~t)^c)→0 asn→ ∞. Defining Qⁿ_~

k(~t) =exp n

iP_r

j=1 kj·Sτ⌊nt j⌋

Æ _p

d−pn

o

, and conditioning onA⌊n~t⌋, the left hand side of (5.7) is equal to

e^−gα1(n)

P_r

j=1η_jX

A

E

– Q_~ⁿ

k(~t)exp

¨

− Xr

j=1

η_j τ^∗_⌊nt

j⌋

g_α(n)

«¯

¯

¯

¯

¯

{A_⌊n~t⌋=A}

™

P(A_⌊n~t⌋=A)

= X

A∈B_n(~t)

E

– Q_~ⁿ

k(~t)exp

¨

− Xr

j=1

η_j τ^∗_⌊nt

j⌋

g_α(n)

«¯

¯

¯

¯

¯

{A_⌊n~t⌋=A}

™

P(A_⌊n~t⌋=A) +o(1)

= X

A∈Bn(~t)

E

• Q_~ⁿ

k(~t)

¯

¯

¯{A⌊n~t⌋=A}

˜ E

– exp

¨

− Xr

j=1

η_j P⌊nt_j⌋

i=1 T_i g_α(n)

«¯

¯

¯

¯

¯

{A⌊n~t⌋=A}

™

P(A⌊n~t⌋=A) +o(1), (5.8) where we have used the fact thatS_τn is conditionally independent of the collection{T_i}_i≥1given I_{Tieven},i=1, . . . ,n, to obtain the last equality.

WritingP⌊nt_j⌋

i=1 T_i =P_j

l=1

P_⌊ntl⌋

i=⌊ntl−1⌋+1T_i and using the mutual independence ofT_i,i≥1, the last line of (5.8) is equal to a termo(1)plus

X

A∈B_n(~t)

E

• Q_~ⁿ

k(~t)

¯

¯

¯{A_⌊n~t⌋=A}

˜

P(A_⌊n~t⌋=A) Yr

l=1

E

– exp

¨

−η^∗_l P_⌊ntl⌋

i=⌊ntl−1⌋+1T_i g_α(n)

«¯

¯

¯

¯

¯

{A_⌊n~^(l)_t⌋=A^(l)}

™ . (5.9) Let{T_i^o}_i∈Nbe i.i.d. random variables satisfyingP(T_i^o=k) =P(T=k|Todd), and similarly define T_i^eto be i.i.d. withP(T_i^e=k) =P(T=k|Teven). Thel^thterm in the product in (5.9) is

E

– exp

¨

−η^∗_l P_|A^(l)_|

i=1 T_i^o g_α(n)

«™

E

– exp

¨

−η^∗_l

P_{⌊ntl⌋−⌊ntl−1⌋−|A}^(l)_|

i=1 T_i^e}

g_α(n)

«™

. (5.10)

For T^o we haveP(T^o ≥n) =p⁻¹P(T≥n,T odd)∼p⁻¹n^−αoL_o(n)and there existsℓ_o such that (ℓ_o(n))^−αop⁻¹L_o(n^α1oℓ_o(n))→(Γ(1−α))⁻¹. Define g_α^o

o(n) =n

1

αoℓ_o(n). Similarly define g_α^e

e(n) = n^α1eℓ_e(n).

Observe that P_|A^(l)_|

i=1 T_i^o gα(n) =

P_nl

i=1T_i^o g_α^o

o(n_l) g_α^o

o(n_l) gα(n_l)

g_α(n_l) gα(n) +O





 P_|A^(l)_|

i=1 T_i^o−P_nl

i=1T_i^o g_α^o

o(n^∗_l)

g_α^o

o(n^∗_l) gα(n^∗_l)

g_α(n^∗_l) gα(n)





, (5.11) where n_l := ⌊nt_lp⌋ − ⌊nt_l−1p⌋ and n^∗_l := ||A^(l)| −n_l| ≤n^1−ε since A∈ B_n(~t). By definition of gα and standard results on regular variation we have that gα(n_l)/g_α(n)→ (p(t_l−t_l−1))^α1 and

g_α(n^∗_l)/g_α(n)→ 0. Since α = α_o∧α_e ≤ α_o, the O term on the right of (5.11) converges in probability to 0. Thus, as in the second claim of Lemma 5.1, we get that

P_|A^(l)_|

i=1 T_i^o

g_α(n) =⇒V_α(1)(p(t_l−t_l−1))^α1 lim

n→∞

g_α^o

o(n_l)

g_α(n_l), (5.12)

where forα <1 the limitρ_o :=lim_n→∞ ^g

o αo(nl)

gα(nl) exists in [0,∞] sinceα ≤α_o and in the case of equality, the limit L_o/L_e exists in[0,∞]. Note that we were able to replaceα_o withαin various places in (5.12) due to the presence of the factor ^g

o αo(n_l)

gα(n_l) which is zero whenα_o> α. Therefore E

– exp

¨

−η^∗_l P_|A^(l)_|

i=1 T_i^o g_α(n)

«™

→E h

exp{−η^∗_lV_α(1)(p(t_l−t_l−1))^α1ρ_o} i

, and similarly,

E









 exp







−η^∗_l

P_{⌊ntl⌋−⌊ntl−1⌋−|A}^(l)_|

i=1 T_i^e

g_α(n)

















→E h

exp{−η^∗_lV_α(1)((1−p)(t_l−t_l−1))^α1ρ_e} i

.

(5.13) SinceE[e^−ηVα(1)] =exp{−η^α}, it remains to show that

(p(t_l−t_l−1))^1αρ_o α

+

((1−p)(t_l−t_l−1))^α1ρ_e α

=t_l−t_l−1, i.e. pρ^α_o+ (1−p)ρ^α_e =1.

(5.14) If α_o < α_e (or α_o =α_e and L_o/L_e → ∞), thenα=α_o, and L ∼ L_o. It is then an easy exercise in manipulating slowly varying functions to show that ℓ_o ∼ p^−1/αℓ and therefore ρ_o = p^−1/α and ρ_e = 0, giving the desired result. Similarly if α_o > α_e (or α_o = α_e and L_o/L_e → 0) we get the desired result. Whenα_o=α_e<1 and L_o/L_e →β∈(0,∞)we have that L∼ L_o+L_e ∼ (1+β)L_e∼(1+β⁻¹)L_o. It follows thatℓ_e∼((1−p)(1+β))^−1/αℓ. Similarlyℓ_o∼(p(1+β⁻¹))^−1/αℓ, and therefore ρ_o = (p(1+β⁻¹))^−1/α andρ_e = ((1−p)(1+β))^−1/α. The result follows since (1+β)⁻¹+ (1+β⁻¹)⁻¹=1.

Acknowledgements

The author would like to thank Denis Denisov, Andreas Löpker, Rongfeng Sun, and Edwin Perkins for fruitful discussions, and an anonymous referee for very helpful suggestions.

References

[1] G. Ben Arous and J. ˇCerný. Scaling limit for trap models onZ^d. Ann. Probab., 35(6):2356–

2384, 2007 MR2353391

[2] J. Bertoin. Subordinators: Examples and Applications. InLectures on Probability Theory and Statistics: Ecole D’Ete de Probabilites de Saint-Flour XXVII - 1997. Springer, 1999. MR1746300 [3] N.H. Bingham, C.M. Goldie, and J.L. Teugels.Regular Variation. Cambridge Unviersity Press,

1987. MR0898871

[4] B. Davis. Weak limits of perturbed random walks and the equationY_t =B_t+αsup{Y_s: s≤ t}+βinf{Y_s: s≤t}. Ann. Probab., 24(4):2007–2023, 1996. MR1415238

[5] S Ethier and T. Kurtz.Markov Processes: Characterization and Convergence. Wiley, New York, 1986. MR0838085

[6] W. Feller. An Introduction to Probability Theory and its Applications vol. 2. Wiley, New York, 1966. MR0210154

[7] A. Gut. An extension of the Kolmogorov-Feller weak law of large numbers with an applica- tion to the St. Petersburg game. J. Theor. Prob., 17:769–779, 2004. MR2091561

[8] N. Herrndorf. A functional central limit theorem for weakly dependent sequences of random variables.Ann. Probab., 12:141–153, 1984. MR0723735

[9] M. Holmes and A. Sakai. Senile reinforced random walks. Stoch. Proc. Appl., 117:1519–

1539, 2007. MR2353038

[10] L. Horváth and Q. Shao. Limit distributions of directionally reinforced random walks. Adv.

in Math., 134:367–383, 1998. MR1617789

[11] W. Kager. Diffusion constants and martingales for senile random walks. arXiv:0705.3305v2 2007.

[12] R.D. Mauldin, M. Monticino, and H. Weizsäcker. Directionally reinforced random walks.Adv.

in Math., 117:239–252, 1996. MR1371652

[13] M.M. Meerschaert and H.-P. Scheffler. Limit theorems for continuous-time random walks with infinite mean waiting times. J. Appl. Prob., 41:623–638, 2004. MR2074812

[14] E.W. Montroll and G.H. Weiss. Random walks on lattices ii.J. Math. Phys., 6:167–181, 1965.

MR0172344

[15] R. Pemantle. A survey of random processes with reinforcement.Probability Surveys, 4:1–79, 2007. MR2282181

[16] W. Whitt.Stochastic-process limits. Springer-Verlag, New York, 2002. MR1876437