N Enriquez

C Lucas

F Simenhaus

THE ARCSINE LAW AS THE LIMIT OF THE INTERNAL DLA CLUSTER GENERATED BY SINAI'S WALK

Keywords: Sinai's walk, internal DLA, random walks in random environments, excursion theory

We identify the limit of the internal DLA cluster generated by Sinai's walk as the law of a functional of a Brownian motion which turns out to be a new interpretation of the Arcsine law.

Introduction

The internal diffusion limited aggregation method was first introduced by Diaconis and Fulton in 1982 (see [START_REF] Diaconis | A growth model, a game, an algebra, Lagrange inversion, and characteristic classes[END_REF]) and gives a protocol for building a sequence of growing random sets A(n), n 0 using random walks. At each iteration, the set A(n + 1) is obtained from A(n) by addition of the first site visited by a walk starting from 0 outside A(n). When the walk is a simple random walk on Z d , the cluster has the ball as asymptotic limit shape ( [START_REF] Lawler | Internal diffusion limited aggregation[END_REF]). In the special and trivial case of dimension one, the cluster A(n) is an interval denoted by [g n , d n ] and d n /n converges almost surely to 1/2. In this paper, we consider the case where the cluster is generated by one dimensional walks evolving in an inhomogeneous random medium. More precisely we are dealing with one dimensional recurrent random walks in random environment often called Sinai's walk. One can rapidly realize that depending on the profile of the potential associated to the environment the cluster may be drastically asymmetric. One can even prove that lim sup d n /n = 1 and lim inf d n /n = 0 almost surely (Theorem 2). But beyond this rough result we are able to prove, under the annealed measure, a convergence in law for d n /n towards the Arcsine law (Theorem 1). The Arcsine law comes out from a new functional of the Brownian motion which in our case is the scaling limit of the potential. This functional stems from the exploration of the potential by the growing cluster. It involves in Sinai's terminology the largest valley of width smaller than one containing the origin. Let us remind that the limit law of the walk in Sinai's theorem after scaling by ln 2 n involves the smallest valley of height one.

Finally, we mention that this result provides a new understanding of the Arcsine law which is different from the two classical ones (last zero of the 2000 Mathematics Subject Classification. 60K37, 60F05. * Modélisation aléatoire de Paris 10 (MODAL'X)-Université Paris Ouest Nanterre La Défense. email 1: nenriquez@u-paris10.fr. email 2: clucas@clipper.ens.fr. email 3: fsimenhaus@u-paris10.fr.

Brownian motion before 1, and the time spent by the Brownian motion above 0 before 1).

Notations and main results

We first introduce Sinai's random walk in random environment. An environment ω is a collection (ω(i)) i∈Z of numbers in [0, 1]. We denote by Ω := [0, 1] Z the set of environments.

For a given environment ω, we define a Markov chain (X n ) n∈N of law P ω , often called quenched law, by

P ω (X 0 = 0) = 1,
and for every x ∈ Z and n ∈ N,

P ω (X n+1 = x + 1|X n = x) = ω(x), P ω (X n+1 = x -1|X n = x) = 1 -ω(x).
We endow Ω with its canonical σ-field and a probability measure P of the form P := µ ⊗Z , where µ is a probability on [0, 1]. We can now define a probability P on the space of trajectories, called the annealed law, by :

P = Ω P ω dP.
Introducing the notation ρ(i) := 1-ω(i) ω(i) , we make the following assumptions on µ :

(i) µ(ω(0) = 0) = µ(ω(0) = 1) = 0 (ii) E µ (log ρ(0)) = 0 (iii) E µ (log ρ(0)) 2 < ∞ A random walk in random environment satisfying the assumptions above is usually called a Sinai walk, referring to the famous article of Sinai [START_REF] Ya | The limit behavior of a one-dimensional random walk in a random environment[END_REF] proving the convergence in law of X n /(log n) 2 under the annealed law.

• Assumption of ellipticity (i) is an irreducibility assumption.

• Assumption (ii) ensures that P ω is recurrent P-almost surely (see [START_REF] Tavaré | Lectures on probability theory and statistics[END_REF] for a survey on one dimensional random walks in random environments). • Assumption (iii) makes it possible to apply Donsker's principle to the potential V ω (see (1) below). Let us now explain the construction of the internal diffusion limited aggregation cluster for a given environment ω ∈ [0, 1] Z .

Let (X j (n)) n∈N be an i.i.d. family of random walks such that ∀j ∈ N, (X j ) has law P ω . We now define our cluster A(n) as a classical internal diffusion limited aggregation cluster using this family of random walks. Define A(n) and the stopping times (θ k ) k∈N recursively in the following way :

θ 0 = 0, A(0) = {0} = {X 0 (θ 0 )},
and for all j > 0,

θ j = inf{n 0 : X j (n) ∈ A(j -1)}, A(j) = A(j -1) ∪ {X j (θ j )}.
Remark 2.1. We stress the fact that under the annealed law, the same environment is used throughout the construction of A(n).

As the construction of the cluster uses an i.i.d sequence of walks, the following notations will be helpful to state our theorems,

P ω = P ⊗N ω and P = Ω P ω dP.
The crucial tool introduced by Sinai in [START_REF] Ya | The limit behavior of a one-dimensional random walk in a random environment[END_REF] is the potential associated to a given environment :

V ω (0) = 0 V ω (i) = i k=1 ln ρ(k) if i 1, (1)
V ω (i) = - 0 k=i+1 ln ρ(k) if i -1.
For all n 0, we define the renormalized potential

V (n) ω (t) = 1 √ n V ω (⌊nt⌋).
It follows from Donsker's principle and Assumption (iii) that, as n goes to infinity, (V

P d n n ∈ (a, b) ---→ n→∞ b a 1 π x(1 -x) dx.
Moreover the following theorem describes the almost sure behavior of the DLA cluster in a typical environment : Theorem 2. P-a.s., with P ω probability one,

lim sup n→∞ d n n = 1, and
lim inf n→∞ d n n = 0.

Proof of Theorem 1

The proof of Theorem 1 can be decomposed in the three following steps.

3.1. Good environments. For each n, we define the set of good environments which will turn out to be of high probability and on which we will be able to control the position of the cluster at step n. For all cadlag functions v : R → R, we define,

T + y (v) = inf {t 0, such that v(t) y} , T - y (v) = -sup {t 0, such that v(t) y} , ȳ = sup{y 0, such that T + y + T - y 1}. ( 2
)
The excursion α below the maximum at T + ȳ is defined by α = inf t 0, such that v(T + ȳ + t) v(T + ȳ ) , and the one to the left of -T - ȳ is defined analogously:

β = inf t 0, such that v(T - ȳ -t) v(T - ȳ )
. In order to make the computation more readable, we will use for all n ∈ N the following notations:

T + ȳn = T + ȳ (V (n) ), T - ȳn = T - ȳ (V (n) ), ȳn = ȳ(V (n) ), α n = α(V (n) ), β n = β(V (n) ).
Let (B t ) t∈R be a real standard Brownian motion defined on an abstract probability space (Ω, F, P). We define with a slight abuse of notation,

T + ȳ = T + ȳ (B), T - ȳ = T - ȳ (B), ȳ = ȳ(B), α = α(B), β = β(B)
These notations (as well as d * and g * introduced in the next section) are illustrated in Figure 1 in the case of the Brownian motion.

B t 1 ȳ α t T + ȳ d * 0 T - ȳ = g * Figure 1
. On this example α > 0 while β = 0. The bold part of the path corresponds to the "theoretical" part of the potential that is explored by the cluster.

Remark 3.1. Throughout the paper we make use of Donsker's principle for the functionals α, β, T + ȳ , T - ȳ , ȳ, as well as d * (introduced in the next section), which are not continuous with respect to the Skorohod topology. However, we observe, for all these functionals, that the set on which they are discontinuous is a subset of trajectories having two local maxima at the same height which has Wiener measure 0.

For all ǫ > 0 and n > 0, we define the following events:

B ǫ,+ n =    sup [-T - ȳn -βn-ǫ,-T - ȳn -βn] V (n) ω ȳn + n 1/3 √ n    ∩ {β n < ǫ} , B ǫ,- n =    sup [T + ȳn +αn,T + ȳn +αn+ǫ] V (n) ω ȳn + n 1/3 √ n    ∩ {α n < ǫ} , C ǫ,+ n =    sup [-T - ȳn +ǫ,0] V (n) ω ȳn - n 1/3 √ n    , C ǫ,- n =    sup [0,T + ȳn -ǫ] V (n) ω ȳn - n 1/3 √ n    .
These events can be described as follows. On B ǫ,+ n , the length of the excursion below the supremum to the left of -T - ȳn is smaller than ǫ. Furthermore, to the left of this excursion the potential increases enough to build an obstacle for the walk. On C ǫ,+ n , there is no significant obstacle between 0 and -T - ȳn + ǫ. On the intersection of these two events, we expect the left border of the cluster to be close to -T - ȳn while the right border should go beyond T + ȳn . The events indexed by "-" refer to the symmetric situation and can be described in the same way. Lemma 3.1. For all ǫ > 0,

lim n→∞ P B ǫ,+ n ∩ C ǫ,+ n ∪ B ǫ,- n ∩ C ǫ,- n = 1
Proof of Lemma 3.1. We define the following filtration :

F 0 = σ (V ω (i), i 0) (3) F k = σ (V ω (i), i -k) for all k > 0. (4)
The process (V ω (-i)) i 0 is Markovian and adapted to F := (F j ) j 0 . The Markov property at the F-stopping time (-nT - ȳn -nβ n ) and classical properties of random walks yield

P   sup [-T - ȳn -βn-ǫ,-T - ȳn -βn] V (n) ω ȳn + n 1/3 / √ n   ---→ n→∞ 1.
The same argument holds for the symmetric case. It follows from Donsker's principle that

P ({β n < ǫ} ∪ {α n < ǫ}) → P ({β < ǫ} ∪ {α < ǫ}) .
As T + ȳ y 0 and T - ȳ y 0 are two strictly increasing subordinators without drift, their sum is also a strictly increasing subordinator without drift, and hits (go through) the level 1 while jumping (see Proposition 1.9 in [START_REF] Bertoin | Subordinators: examples and applications[END_REF]). Furthermore, they are independent so they never jump at the same time (for background on subordinators, we refer to [START_REF] Bertoin | Subordinators: examples and applications[END_REF]). As a consequence, under Wiener measure, either α > 0 and β = 0 or α = 0 and β > 0, hence

P ({β < ǫ} ∪ {α < ǫ}) → 1.
It follows from the same argument that, a.s., one of T + ȳ and T - ȳ is a local maximum (while the other is not). Notice also that -n 1/3 / √ n, +∞ increases to (0, +∞), hence from Donsker's principle,

P C ǫ,- n ∩ C ǫ,+ n ---→ n→∞ P   sup [-T - ȳ +ǫ,T + ȳ -ǫ] B ȳ  .
This happens almost surely because the Brownian motion already has a local maximum with value ȳ at T + ȳ or T - ȳ .

3.2.

The quenched localization of d n . We can now limit our study to the good environments, where with high probability d n is localized near its theoretical position d * n that is a deterministic functional of the potential. More precisely, we define for any cadlag function

d * = T + ȳ + 1 α>β (1 -(T + ȳ + T - ȳ )
), and we will use the following notations :

d * n = d * (V (n) ), d * = d * (B), g * = 1 -d * .
We will also use the notation

g * n = d * n -1. Proposition 3.1.
For all ǫ > 0 and η > 0,

P P ω d n n -d * n > ǫ > η ---→ n→∞ 0.
Proof of Proposition 3.1. If (X n ) n 0 is a Markov chain on Z, we will use, for any q in Z, the notation σ q to denote the hitting time of q by X n , namely σ q = inf{n 0, X n = q}.

We recall (see for example [START_REF] Tavaré | Lectures on probability theory and statistics[END_REF]) that for any ω ∈ Ω,

P ω (σ -b < σ a ) = a-1 i=0 exp(V ω (i)) a-1 i=-b exp(V ω (i)) . ( 5
)
Let n be in N \ {0} and ω be in

B ǫ,+ n ∩ C ǫ,+ n , then P ω (g n < -nT - ȳn -2ǫn) n 2 exp(-n 1/3 ). ( 6
)
Indeed suppose that V ω (T + ȳn ) = ȳn , then

P ω (σ -nT - ȳn -2ǫn < σ n∧(nT + ȳn +nαn-1) ) = n∧(nT + ȳn +nαn-1)-1 i=0 exp(V ω (i)) n∧(nT + ȳn +nαn-1)-1 i=-nT - ȳn -2ǫn exp(V ω (i)) n exp(ȳ n ) exp(ȳ n + n 1/3 ) = n exp(-n 1/3 )
Now as n(T + ȳn +T - ȳn +2ǫ+α n ) > n, the probability in ( 6) can be controlled by the probability that one of n independent random walks in the environment ω exits of the interval [-nT - ȳn -2ǫn, nT + ȳn + nα n -1] by the left side, namely

P ω (g n < -nT - ȳn -2ǫn) < 1 -(1 -n exp(-n 1/3 )) n n 2 exp(-n 1/3 ) (7) Suppose now that V ω (T + ȳn ) > ȳn then P ω (σ -nT - ȳn -2ǫn < σ nT + ȳn -1 ) = nT + ȳn -2 i=0 exp(V ω (i)) nT + ȳn -2 i=-nT - ȳn -2ǫn exp(V ω (i)) n exp(ȳ n ) exp(ȳ n + n 1/3 ) = n exp(-n 1/3 )
It follows from the definition of ȳn that n(T + ȳn + T - ȳn + β n ) n which leads to the same kind of control as in [START_REF] Tavaré | Lectures on probability theory and statistics[END_REF] and concludes the proof of [START_REF] Ya | The limit behavior of a one-dimensional random walk in a random environment[END_REF]. We now complete the study of g n on B ǫ,+ n ∩ C ǫ,+ n by proving the following inequality, P ω (g n nT - ȳn + ǫn) n 2 exp(-n 1/3 ).

Using ( 5) again, we get

P ω (σ nT + ȳn < σ -nT - ȳn +ǫn ) = -nT - ȳn +ǫn-1 i=0 exp(V ω (i)) -nT - ȳn +ǫn-1 i=nT + ȳn exp(V ω (i)) n exp(ȳ n -n 1/3 ) exp(ȳ n ) = n exp(-n 1/3 ).
As nT + ȳn + nT - ȳn + ǫn n, we control the probability of the complementary event in [START_REF] Yor | Local Times and Excursions for Brownian Motion : a concise introduction Lecciones en Mathematicas[END_REF] with the probability that n independent random walks in the environment ω exit [-nT - ȳn + ǫn, nT + ȳn ] through the left side, namely

P ω (g n -nT - ȳn + ǫn) 1 -(1 -n exp(-n 1/3 )) n n 2 exp(-n 1/3 ). Notice now that on B ǫ,+ n ∩ C ǫ,+ n , |T + ȳn -g * n | < ǫ.
With a similar study of the event B ǫ,- n ∩ C ǫ,- n and Lemma 3.1, it is easy to complete the proof of Proposition 3.1. Proof of Lemma 3.2. We note (L t ) t 0 the local time at 0 of B and τ t = sup{u 0, L u < t} the left continuous inverse of L.

Remark 3. The process (T + y ) y 0 is left continuous. Consequently, even if it is unusual, we prefer to work with the left continuous version of the inverse local time of B t . We will also use the name subordinator for a left continuous increasing process with independent increments. For all t 0, denote

A + t = t 0 1 Bs>0 ds,
the time spent by B above 0 up to time t ; and similarly

A - t = t 0 1 Bs<0 ds. Now A + τt + A - τt = τ t
is a subordinator and, as τ t follows the same law as the hitting time of t by the Brownian motion, it is a 1/2-stable subordinator. Moreover it is a consequence of Ito's excursion theorem (see Theorem 2.4 of [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF]) that both processes (A + τt ) and (A - τt ) are independent subordinators with the same law. Each of them deals indeed respectively with one of the disjoint set of positive and negative excursions of B up to time τ t . Hence

(A + τt , A - τt ) (law) = 1 4 (T + t , T - t ) (9)
(we refer to the lecture notes of Marc Yor [START_REF] Yor | Local Times and Excursions for Brownian Motion : a concise introduction Lecciones en Mathematicas[END_REF] for explanations and applications of this identity). Hence

ȳ (law) = sup{t 0, A + τt + A - τt 1} (law) = sup{t 0, τ t 1} (law) = L 1 .
From the choice of the left continuous version of the inverse local time (see Remark 3) we deduce

T + ȳ (law) = A + τ L 1 = A + g 1 (10)
where g 1 = sup{t < 1, B t = 0} is the last zero of (B t ) t 0 before 1. Let us remind that

d * = T + ȳ + 1 α>β (1 -(T + ȳ + T - ȳ )). (11)
Notice now that (T + ȳ , T - ȳ ) is independent of 1 α>β . Indeed, using (9), it is equivalent to check the independence of the sign of B 1 and (A + g 1 , A - g 1 ). Gathering this independence with (11) and (10), we obtain

d * (law) = A + g 1 + ǫ(1 -(A + g 1 + A - g 1 )) = A + g 1 + ǫ(1 -g 1 ), ( 12
)
where ǫ is a Bernoulli variable with parameter 1/2 independent of all other variables. The decomposition of the path of the Brownian motion on [0, 1] into a path on [0, g 1 ] and an incomplete excursion of independent sign on [g 1 , 1] yields

A + g 1 + ǫ(1 -g 1 ) (law)
= A + 1 .

(13) We conclude by recalling Paul Levy's well known result ( [START_REF] Lévy | Sur certains processus stochastiques homogènes[END_REF])which states that A + 1 follows the Arcsine law. Remark 4. Notice that the Proof of Lemma 3.2 has a non-trajectorial nature as shown by the key identity in law (9), which allows to reduce the study of the functional of two independent Brownian motion to that of the functional of a single one.

Remark 5. The random sign ǫ in identity (12) corresponds to the left-right symmetry of the problem, whereas in the classical decomposition (13) it has an up-down meaning.

Proof of Theorem 2

We will only prove the first statement as the second one can be easily deduced using the symmetry of the model.

(V (n) , • • • , V (n k ) ) (law) ⇒ (B 1 , • • • , B k ).
We will also use the fact that for any real Brownian motion B, P(T + ȳ (B) 1 -ǫ) > 0, see for example (10). Now We deduce from Lemma 4.1 and the previous study of C ǫ,- n (see the Proof of Theorem 1) that C ǫ,- n ∩ {T + ȳn > 1 -ǫ} occurs infinitely often. Fix ω in Ω and n in N such that ω ∈ C ǫ,- n ∩ {T + ȳn > 1 -ǫ}. Formula (5) yields

P ω (σ nT - ȳn < σ n(T + ȳn -ǫ) )
n(Tȳ n -ǫ)-1 i=0 exp(V ω (i))

n(Tȳ n -ǫ)-1 i=nT - ȳn exp(V ω (i))

ne ȳn-n 1/3 e ȳn ne -n 1/3

The probability of the event {d n T + ȳn -ǫ} is smaller than the probability that one of n independent random walks in the environment ω exits [-nT + ȳn , n(T + ȳn -ǫ)] through the left side. Hence, P ω (d n T + ȳn -ǫ) 1 -(1 -ne -n 1/3 ) n n 2 e -n 1/3 .

We conclude using Borel Cantelli's Lemma on a subsequence (n j ) j 0 such that C ǫ,+ n j ∩ {T + ȳn > 1 -ǫ} holds for all j 0 (the P-a.s. existence of such a subsequence is a consequence of Lemma 4.1).

ω

  (t)) t∈R converges in law to the Wiener law. Let us notice finally that, by construction, the cluster A(n) is an interval we will denote by [g n , d n ]. We can now state our main result: Theorem 1. Under P , d n /n converges in law to the Arcsine law. Namely, for all 0 a b 1,

3. 3 .Lemma 3 . 2 .

 332 Characterization of the law of d * . Using Donsker's principle and Proposition 3.1, we conclude that d n /n converges in law towards d * . To complete the proof of Theorem 1, we characterize the law of d * . The law of d * is the Arcsine law.

Lemma 4 . 1 .

 41 P-p.s., {T + ȳn > 1 -ǫ} i.o. Proof of Lemma 4.1. Let k be in N * . It is a well known result that there exist k independent Brownian motions (B 1 , • • • , B k ) on (Ω, F, P) such that

lim inf{T + ȳn 1 - 1 ) 1 -

 111 ǫ} ⊂ lim inf {T + ȳn 1 -ǫ} ∩ • • • ∩ {T + ȳk n ǫ • • • P T + ȳ (B k ) 1 -ǫ P T + ȳ (B 1 ) 1 -ǫ kAs k can be chosen arbitrarily big, this concludes the proof of Lemma 4.1.

Acknowledgements

It is a pleasure to thank Professor Marc Yor for pointing out to us the key identity (9).