How long does it take for Internal DLA to forget its initial profile?
Lionel Levine Vittoria Silvestri
math.PR

Galaxy Zoo: Morphological classification of galaxy images from the Illustris simulation
    Gregory F. Snyder
    Received: date / Revised version: date
=======================================================================================



December 30, 2023



Internal DLA is a discrete model of a moving interface. On the cylinder graph _N ×, a particle starts uniformly on _N ×{0} and performs simple random walk on the cylinder until reaching an unoccupied site in _N ×_≥ 0, which it occupies forever. This operation defines a Markov chain on subsets of the cylinder.
We first show that a typical subset is rectangular with at most logarithmic fluctuations. We use this to prove that two Internal DLA chains started from different typical subsets can be coupled with high probability by adding order N^2 log N particles. For a lower bound, we show that at least order N^2 particles are required to forget which of two independent typical subsets the process started from.









§ INTRODUCTION

Internal Diffusion-Limited Aggregation (IDLA) models a random subset of ^d that grows in proportion to the harmonic measure on its boundary seen from an internal point. 
More precisely, let A(0)={ 0} denote the subset (“cluster”) at time t=0. For integer times t≥ 1 inductively define
	
    A(t) = A(t-1) ∪{ Z_t } ,

where Z_t denotes the exit location from A(t-1) of a simple random walk on ^d starting from 0, independent of the past. The process (A(t))_t≥ 0 is a Markov chain on the space of connected subsets of ^d. As t→∞, the asymptotic shape of A(t) is an origin-centered Euclidean ball <cit.> and its fluctuations from the ball are at most logarithmic in dimensions d ≥ 2 <cit.>; see also <cit.> for a lower bound on the fluctuations. 
Space-time averages of the fluctuations converge to a logarithmically correlated Gaussian field <cit.>. 


In the setting of the cylinder graph <cit.> it was asked what happens if the process is initiated with a cluster A(0) other than a singleton: How long does it take for IDLA to forget the shape of A(0)? 
Our main results, Theorems <ref> and <ref> below, give upper and lower bounds that match up to a log factor.

Fix an integer N≥ 3, and let _N × denote the cylinder graph with the cycle on N vertices as base graph. We refer to x ∈_N as the horizontal coordinate, and to y ∈ as the vertical coordinate. For k∈, we call { y=k} := _N ×{k} the k^th level of the cylinder, and R_k := { (x,y) : y≤ k} the infinite rectangle of height k.
 

 
It is sometimes convenient to formulate the growth in terms of aggregation of particles. Let A(0) be the union of the lower half-cylinder R_0 with a finite (possibly empty) set of sites in the upper half-cylinder. At time zero, each site in A(0) is occupied by a particle.
At each discrete time step, a new particle is released from a uniform point on level 0, and performs a simple random walk until reaches an unoccupied site, which it occupies forever.
Motion of particles is instantaneous: we do not take into account how many random walk steps are required for a particle reach an unoccupied site, but rather increment the time by 1 after it does so.

Formally, we define A(t) inductively according to (<ref>), where Z_t is the the exit location from A(t-1) of a simple random walk on the cylinder graph starting from a uniform random site on level 0, independent of the past. Note that this is equivalent to adding a new site to the cluster according to the harmonic measure on its exterior boundary seen from level -∞. 
When A(0) = R_0 we say that the process is “starting from flat”.


In the cylinder setting there are two parameters, the size N of the base graph, and the time t. 
Just as large IDLA clusters on ^d are logarithmically close to Euclidean balls, it is natural to expect large

 IDLA clusters on the cylinder to be logarithmically close to filled rectangles. 
 When t = N^2 this was stated in <cit.> (but not proved there, as the proof method is the same as in <cit.>).
Our first result extends this result to large times t ≤ N^m, which we will later use to control the fluctuations of stationary clusters. 
 
Let (A(t))_t≥ 0 be an IDLA process on _N × starting from the flat configuration A(0)= R_0. 


For any >0, m∈ there exists a constant  b_ ,m, depending only on  ,m, such that 
	
    (  R_t/N - b_ ,mlog N ⊆  A(t) ⊆
    	R_t/N + b_ ,m log N    ∀ t≤ N^m ) ≥ 1-N^-

for N large enough. 











We prove the above result in two steps. To start with, we argue that (<ref>) holds for T ≤ (N log N )^2, which can be shown by adapting the Jerison, Levine and Sheffield arguments <cit.> to the cylinder setting (cf. Theorem <ref>). We then invoke the Abelianproperty of IDLA (cf. Section <ref>) to build large clusters by piling up nearly rectangular blocks of ( N^2 log N) particles each.




Suppose now that the IDLA process on _N × is not initiated from the flat configuration R_0, but rather from an arbitrary connected cluster A(0) ⊃ R_0. How long does it take for the process A(t) to forget that it did not start from flat? 
Clearly, the answer to this question very much depends on A(0). For example, it will take an arbitrarily large time to forget an arbitrarily tall initial profile. On the other hand, most profiles are unlikely for IDLA dynamics. This leads us to the following related question: 



 How long does it take for IDLA to forget a typical initial profile? 



To define “typical” let 
	
    Ω := { A ⊆_N × :  A = R_0 ∪ F  for some finite F}

denote the set of clusters which are completely filled up to level 0. This is 
 the state space of IDLA. On Ω we introduce the following 


 shift procedure: each time the cluster is completely filled up to level k>0, we shift the cluster down by k. 
[Shifted IDLA]
Let  be the map from the space of IDLA configurations to itself defined as follows. For a given cluster A, let
	
    k_A := max{ k≥ 0 : 
    
    	R_k ⊆ A }

be the height of the maximal filled (infinite) rectangle contained in A.
The downshift of A is the cluster 
	
    (A) := { (x,y-k_A) : (x,y) ∈ A },



Note that k_ (A) = 0, so ( (A)) = (A).   
Now from the IDLA chain  (A(t))_t≥ 0 we set
	
    A^*(t) :=  ( A(t))

for all t≥ 0. We will refer to (A^*(t))_t≥ 0 as the shifted process associated to (A(t))_t≥ 0. 


The shifted process defines a new Markov chain on the same configuration space Ω. While the original IDLA chain is transient, we will see that Shifted IDLA is a positive recurrent Markov chain (cf. Remark <ref>) and it thus has a stationary distribution, which we denote by μ_N. 




Recall from <cit.> that a probability distribution 

is called a warm start for a given Markov chain if it is upper bounded by a constant factor times the  

stationary distribution of the chain.  
We relax this definition below. 
[Lukewarm start]
For k∈, a probability measure ν_N on Ω is said to be a k-lukewarm start (for Shifted IDLA) if 
	
    ν_N(A) ≤ N^k μ_N(A)      ∀ A ∈Ω .

We say that ν_N is a lukewarm start if it is a k-lukewarm start for some k∈.

[Typical clusters]
A random cluster A ∈Ω is said to be a typical cluster if it is distributed according to some lukewarm start ν_N for Shifted IDLA. 

 If ν_N = μ_N then A is said to be a stationary cluster. 

For A ∈Ω, let |A| denote the number of occupied sites above level 0, that is 
	
    |A| := ♯{ (x,y) ∈ A : y>0 }  .

Let further h(A) denote the height of A, that is 
	
    h(A) = max{ y : (x,y) ∈ A x∈_N},

so that h(A) ≥ 0 for all A ∈Ω. 



Our next result is a bound for the height of a typical cluster: it is at most logarithmic in N with high probability. 

[Height of typical clusters]
For any >0, k∈ there exists a constant c_ ,k, depending only on  and k, such that for all k-lukewarm starts ν_N it holds 


	
    ν_N ( { A : h(A) > c_ ,klog N  }) 
    	≤  N^-  .

for N large enough. 

In particular, taking k=0 we see that stationary IDLA clusters have logarithmic height with high probability. This gives nontrivial information on the stationary measure of a nonreversible Markov chain on an infinite state space. 


We believe that this bound is tight, in the sense that for A_N ∼μ_N the ratio h(A_N )/log N converges in probability to a positive constant as N →∞. See <cit.> for some numerical evidence.


We use Theorem <ref> to bound from above the time it takes for IDLA to forget a typical initial profile. 
[The upper bound] 








For any >0, k∈ there exist a constant d_ , k and a set Ω_ ,k⊆Ω, depending only on  and k, such that the following hold for all sufficiently large N. 
For any k-lukewarm start ν_N on _N ×, we have	
	
    ν_N (Ω_ , k ) ≥ 1-N^-.

Moreover, for any A_0, A'_0 ∈Ω_ ,k with |A_0| = |A'_0|, writing t_ ,k = d_ , k N^2 log N for brevity, we have	

    P(t_ ,k ) - P'(t_ , k ) _TV≤ N^-

where (A(t))_t≥ 0 and (A'(t))_t≥ 0 are IDLA processes starting from A_0 and A'_0 respectively, and P(t) and P'(t) denote the laws of A(t) and A'(t) respectively.

Thus IDLA forgets a typical initial state, and hence in particular a stationary initial state, in (N^2 log N) steps with high probability.


The assumption |A_0|=|A'_0| could be relaxed to |A_0| ≡ |A'_0|, by shifting the smaller cluster to include some full rows of N sites each.

To remove the cardinality assumption entirely, one could consider “lazy” IDLA processes: at each discrete time step, a particle is added with probability 1/2, and otherwise nothing happens.  Then the difference |A_t| - |A'_t| is a lazy simple random walk on an N-cycle, so with probability at least 1-N^- there is a time T ≤ d_ N^2 log N such that |A_T| ≡ |A'_T|.




When the initial profiles are stationary, we can complement the upper bound in Theorem <ref> with the following lower bound.


[The lower bound] 
For any ,̣ >0 there exist disjoint subsets Ω_,̣Ω '_$̣ ofΩsuch that 
	
    μ_N ( Ω_)̣≥1/2 -  ,     μ_N ( Ω '_)̣≥1/2 -

and a constant= (,̣ )>0such that the following holds. 
Let(A(t))_t≥0and(A'(t))_t≥0be two IDLA processes on_N ×starting fromA_0 ∈Ω_$̣, A'_0 ∈Ω '_$̣, and denote byP(t) , P'(t)the laws ofA(t),A'(t)respectively. Then 
	
    P( N^2 ) - P'( N^2 ) _TV > 1-

forNlarge enough. 

The above theorem tells us that two independently sampled stationary profilesA,A'are, with probability arbitrarily close to1/2, different enough for IDLA to need orderN^2steps to forget from which one it started. To prove this, we identify a slow-mixing statistic based on the second eigenvector of simple random walk on_N(see Definition <ref> in Section <ref>).




 §.§ Outline of the proofs

We start by showing that IDLA forgets polynomially high profiles in polynomial time, as stated in the following theorem.


Let A_0 , A'_0 be any two clusters in Ω with |A_0|=|A'_0| and define 
	
    h_0 = max{ h(A_0) , h(A'_0) }.
 
Assume that h_0 ≤ N^m for some fixed m ∈. 
Let (A(t))_t≥ 0 and (A'(t))_t≥ 0 be two IDLA processes starting from A_0 , A'_0 and denote the laws of A(t), A'(t) by P(t) , P'(t) respectively. 
Then for any >0 there exists a constant d'_ , m, depending only on  and m, such that for 
	
    t_ , m = h_0 N + d'_ , m  N^2 log N
 
and N large enough, it holds
	
    P(t_ ,m ) - P'(t_ , m ) _TV≤ N^- .




 
 

Theorem <ref> is proved via a coupling argument that we spell out below. 
We then combine it with Theorem <ref> to show that stationary clusters have at most logarithmic height with high probability (cf. Theorem <ref>). The upper bound (cf. Theorem <ref>), is a simple corollary of these two results. 
We sketch here the main ideas behind these proofs. 










  §.§.§ Theorem <ref>: the water level coupling.

LetA_0andA'_0be two clusters inΩwithn_0:=|A_0|=|A'_0|andh_0 = max{ h(A_0) , h(A'_0) } ≤N^m.
We are going to build large IDLA clusters starting fromA_0 , A'_0in a convenient way.
Lett_, m = h_0 N + d'_, m N^2 logNas in Theorem <ref>. 
Introduce a new IDLA clusterW_0, independent of everything else, built by addingt_, mparticles to the flat configurationR_0. Note that sinceW_0contains polynomially many particles, by Theorem <ref> it will be completely filled up to heighth_0+b_, m NlogNfor a suitable constantb_, m with high probability.


We takeW_0to be the initial configuration of two auxiliary processes(W(t))_t≤n_0and(W'(t))_t≤n_0, 


that we think of as water flooding the clusters. Water falling inA_0(resp.A'_0) freezes, and it is only released at a later time. Frozen water particles are released in pairs, and their trajectories are coupled so to make the particles meet with high probability before exiting the respective clusters. 







Clearly, by taking the initial water clusterW_0large enough we can ensure that all pairs of frozen particles meet with high probability before exiting their respective clusters, in which case we haveW(s) = W'(s)for alls≤n_0. 
The theorem then follows by invoking the Abelian property (cf. Section <ref>) for the equalities in law
	
    A(t_ , m ) (d)= W(n_0) ,      
    	A'(t_ , m ) (d)= W'(n_0) .

See Figure <ref> for an illustration of this argument, and Section <ref> for the details.

 


  §.§.§ Theorem <ref>: typical clusters are shallow.

It suffices to prove the result forν_N = μ_N. 
Assume Theorem <ref>, according to which an IDLA process starting from flat has logarithmic fluctuations for polynomially many steps, with high probability. It suffices to show that such process reaches stationarity in polynomial time to conclude.  This would follow from Theorem <ref>, if we knew that stationary clusters have at most polynomial height inN, with high probability. 
To see this, we first observe that stationary clusters are dense, since an IDLA process spends only a small amount of time at low density configurations. Here the density of a clusterA ∈Ωis measured via its excess height(A)=h(A) - |A|/N, that is the difference between the actual height and ideal height ofA. We show that if the excess height is too large, then it has a negative drift under IDLA dynamics. The advantage of measuring the clusters' density via their excess height lies on the fact that a bound on the latter easily translates on a bound on the number of empty sites below the top level. Once we have such bound, we can try to fill the holes below the top level by releasing enough (but at most polynomially many) additional particles. This will leave us with clusters of at most polynomial height. 
Take any deterministic time of the formt=N^kfor large enoughk. Then the clusterA(t)is both stationary and it has at most polynomial height with high probability, which implies that typical clusters have at most polynomial height with high probability, as claimed. 







 


 §.§ Organization of the paper

We start by recalling the Abelian property of Internal DLA in Section <ref>. We then collect some useful preliminary results in Section <ref>. In Section <ref> we prove Theorem <ref>, concerning deterministic initial profiles. 
In Section <ref> we bound the fluctuations of IDLA clusters with polynomially many particles (cf. Theorem <ref>), which we then use in Section <ref> to prove Theorem <ref>. The upper bound (cf. Theorem <ref>) is a simple corollary of Theorems <ref> and <ref>, as we briefly explain in Section <ref>. The corresponding lower bound (cf. Theorem <ref>) is proved in Section <ref>. 

We conclude the paper with a short review of the logarithmic fluctuations result by Jerison, Levine and Sheffield (cf. Theorem <ref>), that we include in Appendix <ref>.



 §.§ Acknowledgement

We are very grateful to Tom Holding, James Norris and Yuval Peres for many valuable comments and suggestions, which substantially improved our results. We are also indebted to the referee for a very careful reading of the paper. 
V.S. would like to thank Cornell University, where this work was initiated, for the kind hospitality. 




§ THE ABELIAN PROPERTY

The Abelian property of Internal DLA was first observed by Diaconis and Fulton <cit.>. More recently, it has been used to generate exact samples of Internal DLA clusters in less time than it takes to run the constitutent random walks <cit.>. For the related model of activated random walkers on, the Abelian property was used to prove existence of a phase transition <cit.>.


To state the version of the Abelian property that will be used in our arguments, let us start by defining the Diaconis-Fulton smash sum in our setting.  Given a setA ∈Ωand a vertexz ∈_N ×, define the setA ⊕{ z }as follows: 

  (i) if z ∉ A, then A ⊕{ z } := A ∪{ z }, 

  (ii) if z ∈ A, then A ⊕{ z } is the random set obtained by adding to A the endpoint of a simple random walk started at z and stopped upon exiting A.  

Note that if A(0) = R_0 and { z_1 , z_2 , … , z_t } are t independent, uniformly distributed vertices at level zero, then we can build an IDLA cluster A(t) by setting 
	
    A(t) = ( (A(0) ⊕{ z_1 } ) ⊕{ z_2 } )⊕⋯⊕{ z_t }  .


The Abelian property, stated below, gives  some freedom on how to build IDLA clusters without changing their laws. 

[Abelian property, <cit.>] 
Given any finite set { z_1 , z_2 , … , z_t } of vertices of _N ×, and a set A ∈Ω, the law of 
	
    ( (A ⊕{ z_1 } ) ⊕{ z_2 } )⊕⋯⊕{ z_t }

does not depend on the order of the z_i's. More precisely, if σ: { 1 , … , t}→{ 1 , … , t} is an arbitrary permutation of { 1 , … , t}, we have the equality in distribution 
	
    ( (A ⊕{ z_1 } ) ⊕{ z_2 } )⊕⋯⊕{ z_t }(d)= 
    	( (A ⊕{ z_ (1)} ) ⊕{ z_ (2)} )⊕⋯⊕{ z_ (t)} .


In light of the above result, givenA ∈Ωand  a finite subsetBof_N ×, we writeA ⊕Bto denote((A ⊕{ z_1 } ) ⊕{ z_2 } ) ⊕⋯⊕{ z_n}, wherez_1 , …z_nis an arbitrary enumeration of the elements ofB. 


We point out that Proposition <ref> is stated and proved in <cit.> for finite sets, while in our setting the set A is infinite. Nevertheless, we can easily reduce to working with finite sets by changing the jump rates of our random walks at level zero to mimic the hitting distribution of a simple random walk after an excursion below level zero. This has the effect of contracting all excursions below level zero to a single step, and it clearly does not change the law of the model. 


§ PRELIMINARIES


 §.§ A mixing bound

Forx∈_N, letP_x^tdenote the law of a lazy[A lazy walk stays in place with probability 1/2, and otherwise takes a simple random walk step.] simple random walk on_Nstarting fromx, and denote its stationary measure, uniform on_N, byπ_N. For>0define
	
    τ_N ( ) := inf{ t≥ 0 : max_x∈_N P^t_x - π_N _TV≤} .

The Total Variation (TV) mixing time of this walk is defined to beτ_N(1/4), which we simply denote byτ_N. It is well known that 
	
    _N ≤ N^2 ,

and moreover 
	
    τ_N ( N^-) ≤⌈log_2 N^⌉τ_N
    	≤ 3  N^2 log N

for any>0(see e.g. <cit.>). 
Letø= (x(t) , y(t))_t≥0be a simple random walk on_N ×and define 
	
    τ^y_n := inf{ t≥ 0 : y(t) = n }

to be the first time it reaches leveln.  
The next lemma tells us that by the time the walker has travelled for aboutNlogNlevels in the vertical coordinate, it has mixed well in the horizontal one. 

For all >0 and all n ≥ 10   N log N, it holds 
	
    max_x∈_N_(x,0) (τ_n^y < 3 N^2 log N) ≤ N^-

for N large enough. 



Let (x̂ (t))_t≥ 0 be the jump process associated to the motion of the horizontal coordinate, obtained by only looking at (x(t))_t≥ 0 when the random walk makes a horizontal step. Similarly, let (ŷ (t))_t≥ 0 be the jump process associated to the motion of the vertical coordinate. 
Let
	
    ^y_n := inf{ t≥ 0 : ŷ (t) =n }

denote the number of vertical steps made by the walk to reach level n. 
For i≥ 0, let G_i -1 denote the number of moves in the x coordinates between the i^th and the (i+1)^th move in the y coordinate. Then (G_i)_i≥ 0 is a collection of i.i.d. Geometric 
random variables of mean 2, and we have 

	
    τ^y_n  = ∑_i=1^τ̂^y_n -1 G_i .

It follows that
	
    max_x∈_N _(x,0)  (  τ^y_n     < N^2 log N^3  ) 
    	 = _0( ∑_i=1^τ̂^y_n -1 G_i   < N^2 log N^3) 
    
    
    	   ≤_0(  ∑_i=1^8  N^2 log N  G_i < 3  N^2 log N  ) + _0 ( ^y_n ≤ 9  N^2 log N  ) .

We estimate the two terms separately: the first one is controlled by large deviations estimates, while the second one by using the explicit expression for the moment generating function of ^y_n. More precisely, we have 
	
    _0(  ∑_i=1^8  N^2log N  G_i < 3 N^2 log N )     = 
    	_0( 2 ^ - ∑_i=1^8  N^2 log N G_i  >  2^- 3  N^2 log N )
    	
       ≤[ 2  ( 2^- G_1 )^8/3]^3 N^2 log N≤( 2/9)^3  N^2 log N ≤ N^-3 ,

where we have used that (2^-G_1) = 1/3 for the second inequality.
For the second term, it is simple to check that, for z ∈ (0,1),
	
    _0 ( z^^y_1 ) = 1-√(1-z^2)/z , 
    	    _0 ( z^^y_n ) 
    	= _0( z^^y_1 )^n.

This gives, for any z ∈ (0,1),
	
    _0 ( ^y_n < 9  N^2 log N   ) 
    	   ≤_0 ( z^^y_n )  z^-9  N^2 log N  
        = ( 1-√(1-z^2)/z)^n ·( 1/z)^9  N^2 log N   .

Choose z∈ (0,1) of the form z^2 = 1-1/^2 for some ≫ 1 as N→∞, to have that 
	
    ( 1-√(1-z^2)/z)^n ·( 1/z)^9  N^2 log N     ≤( 1-1/)^n/2 ( 1-1/^2)^-9/2 N^2log N 
       ≤exp( -n/2 + 5/^2 N^2 log N ) .

To have the far r.h.s. smaller than, say,  N^-5/4 it suffices to take 
	
    n ≥10 / N^2log N +  5/2log N .

Optimizing over  suggests to take = 2N, to get n ≥ 10  N log N. 


 §.§ The role of starting locations

The following result tells us that if the walkers have time to mix in the horizontal coordinate before exiting the cluster, the resulting IDLA configuration does not depend too much on their initial positions. 

Fix any T>0  such that T≤ N^m for some finite m ∈. Let { (x_i , y_i ) }_1≤ i ≤ T and { (x'_i , y'_i ) }_1≤ i ≤ T denote two fixed collections of vertices of _N × such that y_i , y_i' ≤ 0 for all i≤ T. Let, moreover, (A(t))_t≤ T and (A'(t))_t≤ T be two IDLA processes with starting configurations A(0) = A'(0), and such that the i^th walkers start from (x_i , y_i) and (x_i' , y_i') respectively. Then there exists a coupling of the two processes such that the following holds. For any >0 there exists a finite constant C_ , m, depending only on  and m, such that if 
	
    A(0) = A'(0) ⊇ R_ C_ , m  Nlog N

then 
	
    ( A(t) = A'(t) t≤ T ) ≥ 1 - N^-.

In particular, this tells us that, as long as the IDLA cluster is filled up to level C_ , m  Nlog N, releasing the next T walkers from fixed initial locations below level 0 or from uniform locations at level 0  results in the same final cluster with high probability. 
 
This is an easy consequence of Lemma <ref>. 
For i≤ T, let ø_i = ( (x_i(k) , y_i(k) ) )_k≥ 0 and ø'_i = ( ( x '_i(k) , y'_i(k) ) )_k≥ 0 denote the simple random walk trajectories of the i^th walkers starting from (x_i , y_i ) and (x_i' , y_i') respectively. 
These are coupled as follows. If, say, y_i < y_i ' then ø_i ' stays in place until ø_i reaches level y_i ' (and vice versa if y_i > y_i '). We can therefore assume that y_i = y_i ' without loss of generality. If, moreover, N is even and |x_i - x_i '| is odd, then the first time that ø_i moves in the horizontal coordinate we keep ø_i ' in place. Since the probability of ø_i reaching level N before making a horizontal step is o(2^-N) for large N, we can assume that |x_i - x_i '| is even without loss of generality. 

The walks move as follows.


If ø_i moves in the y coordinate, then so does ø_i ', and the two walks take the same step. Thus y_i(0) = y_i '(0) implies that y_i(k) = y_i '(k) for all k≥ 0. 
If, on the other hand, ø_i moves in the x coordinate, then so does ø_i ', and the two walks move according to the reflection coupling on the N-cycle (cf. Section <ref>). 
 Finally, the walkers ø_i and ø '_i stick together upon meeting, that is if ø_i(k) = ø_i '(k) for some k≥ 0 then ø_i(j) = ø_i '(j) for all j≥ k. Note that if A(i-1) = A'(i-1) and the i^th walkers meet before exiting the identical clusters, then A(i) = A'(i). 

Let, consistently with the notation introduced in the proof of the previous result, (x̂_i(k))_k≥ 0 and (x̂_i '(k))_k≥ 0 be the jump processes associated to (x_i(k))_k≥ 0 and (x_i'(k))_k≥ 0. 
Then, if 
	
    _x := inf{ k≥ 0 : x̂_i(k) = x̂'_i(k) }

we have, by comparison with a simple random walk,

	
    ( _x > 3 N^2 log N ) ≤ N^-
 
for all >0 and N large enough. 
Moreover, by setting 
	
    _x := inf{ k≥ 0 : x_i(k ) = x'_i(k  ) }  ,

we see that 
x_i(_x  ) = x'(_x ) = x̂ ( _x ) = x̂'(_x ) 
and 	
	
    _x =  ∑_k=1^_x -1 G_i ,

for (G_i)_i≥ 1 i.i.d. Geometric random variables of mean 2. Let ' = 6( +m ) and ” =  '/3. Recall that R_n denotes the infinite rectangle of height n, and assume that A(0) = A'(0) ⊇ R_n for n =10  ' N log N. Denote  by _n the first time both walkers reach level n. 
Then by Lemma <ref> and (<ref>) we have 
	
    ( ø_i ø '_i     R_n  ) 
    	 =  ( _x > _n ) 
    	= ( ∑_k=1^_x -1 G_k > _n ) 
    	
       ≤( ∑_k=1^_x  G_k > 3 ' N^2 log N ) 
    	+  (_n < 3  ' N^2 log N ) 
    	
       ≤( ∑_k=1^3 ” N^2 log N G_k 
    	> 3  ' N^2 log N  ) ) + 
    	( _x > 3 ” N^2 log N)
    	+ N^- ' 
       ≤( ∑_k=1^3 ” N^2 log N   G_k 
    	> 9 ” N^2 log N  ) + 
    	 N^-” + N^- '
       ≤[  ( e^ł G_k  ) /e^3ł]^ 3” N^2 log N  + 2N^-”,

where the third inequality follows from (<ref>).
Finally, taking ł = log (3/2) >0 makes the term in the square brackets equal to 8/9, from which we conclude that 
	
    ( ø_i ø '_i   R_n  ) 
    	 ≤ N^-3 ” N^2 log9/8  + 2 N^-”≤ N^-( +m)

for N large enough.  
In all, we have found that 
	
    ( ∃ t ≤ T  A(t) ≠ A'(t) ) 
    	   ≤ ( ∃ i ≤ T ø_i ø_i '  R_n  ) 
    	
       ≤ T N^-( + m ) ≤ N^- .

This shows that we can take C_ , m = 60(  + m ) in (<ref>) to have (<ref>), thus concluding the proof. 

 
 


§ THE WATER LEVEL COUPLING

In this section we prove Theorem <ref>. 

Let A_0 ,   A'_0 be any two clusters in Ω with |A_0| = |A'_0| = n_0 and such that 
	
    h_0 = max{ h(A_0) , h(A'_0)}≤ N^m .

Let C_ +1 , m+1 and b_+1, m+2 be defined as in Proposition <ref> and Theorem <ref> respectively, and define 
	
    d'_ , m := 2 max{ C_ +1 , m+1 ,    b_+1, m+2} .
 
We build an auxiliary water cluster W_0 by adding t_ , m  = h_0 N + d'_ , m  N^2 log N particles to the flat configuration R_0 according to IDLA rules. Then, since t_ , m≤ N^m+2, by Theorem <ref> we have 
	
    (  W_0 ⊇ R_t_ , m/N - b_ +1 ,m+2log N ) ≥ 1-N^-( +1)

for N large enough. In particular, since d'_ , m≥ C_ +1 , m+1 + b_ +1 ,m+2, this gives 
	
    (  W_0 ⊇ R_h_0 + C_ +1 ,m+1  Nlog N ) ≥ 1-N^-( +1) ,

i.e. the water cluster is completely filled up to height h_0 + C_ +1 ,m+1  Nlog N with high probability. 
Write 
	
    A_0 = { z_1 , z_2 , … , z_n_0} ,      
    	A'_0 = { z'_1 , z'_2 , … , z'_n_0}

for arbitrary enumerations of the sites in A_0, A'_0 above level 0. We 
define two auxiliary processes  (W(t))_t≤ n_0, (W'(t))_t≤ n_0 by setting W(0) = W'(0) = W_0 and inductively defining for t≤ n_0
    W(t) = W(t-1) ∪{ Z_t } ,      W'(t) = W'(t-1) ∪{ Z'_t },

where Z_t, Z'_t denote the exit locations from W(t-1), W'(t-1) of simple random walks on _N × starting from z_t, z'_t. These walks are coupled as follows. If z_t is at a lower level than z'_t, then the walk starting from z_t moves freely (independently of everything else) until it reaches the level of z'_t, while the other walk stays in place. Once at the same level, the walks move together in the vertical coordinate, whereas the horizontal coordinates evolve according to the reflection coupling: if one steps to the left, the other one steps to the right, and vice versa[Here we again use the first horizontal step of the walks to adjust the parity of the difference of the horizontal coordinates, if needed, as explained in the proof of Proposition <ref>.]. 
Once the walks meet, they move together in both coordinates.
 Since n_0 ≤ h_0 N ≤ N^m+1, and all the walks start at distance at least C_ +1 , m+1N log N from the boundary of the cluster,  Proposition <ref> gives[Although the particles' starting positions were taken to be below level 0 in Proposition <ref> for notational convenience, the result applies in this setting by invariance under vertical shifts.]
    ( W(n_0) ≠ W'(n_0) ) 
    	≤    ( W(n_0) ≠ W'(n_0) | W_0 ⊇  R_t_ , m/N + C_ +1 ,m+1log N ) + 
        + ( W_0 ⊉  R_t_ , m/N + C_ +1 ,m+1log N ) 
    	≤ 2N^-( + 1)≤ N^-

for N large enough. The result then follows by observing that if (A(t))_t≥ 0 and (A'(t))_t≥ 0 denote two IDLA processes starting from A_0 and A'_0 respectively, then 
	
    A(t_ , m ) (d)= W(n_0) ,      
    	A'(t_ , m ) (d)= W'(n_0)

by the Abelian property. Indeed, if we denote by w_1 , w_2 , … , w_t_ , m the starting locations of the t_ , m walkers used to grow W_0, then, with the notation introduced in Section <ref>, we have 
	
    W(n_0) = ((( R_0 ⊕{ w_1 } ) ⊕{ w_2 } )⊕⋯⊕{ w_t_ , m} ) ⊕ A_0 ,

while 
	
    A(t_ , m ) = (( R_0 ⊕ A_0 ) ⊕{ w_1 } ) ⊕{ w_2 } ) ⊕⋯⊕{ w_t_ , m} .

The claimed equality in law is then given by Proposition <ref>. 

Note that to prove Theorem <ref> we have constructed a coupling of the final clusters A(t_ ,m), A'(t_ ,m), not of the whole processes (A(t))_t≥ 0, (A'(t))_t≥ 0. 


§ LOGARITHMIC FLUCTUATIONS FOR LARGE CLUSTERS
 
In this section we bound the fluctuations of an IDLA cluster with polynomially many particles, thus proving Theorem <ref>. 
To start with, we claim that the following holds. 

Let (A(t))_t≥ 0 denote an IDLA process on _N × starting from the flat configuration A(0) = R_0. Fix any T≤ (N log N)^2. 

Then for any >0 there exists a finite constant a_, depending only on , such that 
	
    ( R_T/N -a_log N⊆ A(T) ⊆ R_T/N + a_log N ) ≥ 1 - N^-

for N large enough. 

The above theorem is stated forT=N^2in <cit.>, where the authors use it to show convergence of space-time averages of IDLA fluctuations to the Gaussian free field. It can be proved by the same arguments used in <cit.> for planar IDLA, which are in fact rather simplified by the structure of the cylinder graph. 
Since this proof does not appear anywhere, and since we need to extend it to larger values of T, we give it in Appendix <ref>. 

Assuming Theorem <ref>, we can proceed with the proof of Theorem <ref>. 



It suffices to show that (<ref>) holds for any fixed T ≤ N^m. The result will then follow by replacing  with +m and using the union bound over all T≤ N^m.

If T =  (N^2 log N ) then we are done by Theorem <ref>, so assume T≫ N^2 log N. We are going to iteratively reduce the size of the cluster, until it becomes (N^2 log N). To this end, 

let a_+2+m and C_+2 , m denote the constants in Theorem <ref> and Proposition <ref> respectively, and set a:= a_+2+m, c:= C_+2 , m for brevity. At cost of increasing these constants, we can assume that 2c ≥ 1 and both a log N and c  log N are integers. Define 
	
    n:= a N log N + 2c N^2 log N .

We build a large cluster, with the same law of A(T), by using the water processes mentioned in the introduction. To this end, let W_1 denote the cluster obtained by adding n particles to A(0)=R_0 according to IDLA rules. Then by Theorem <ref>
    ( R_2cNlog N⊆ W_1 ⊆ R_2a log N + 2cNlog N)
    	  ≥ 1-N^-(+2+m)

for N large enough. Let  
	
    W^f_1 := W_1 ∩ R_2cNlog N

denote the region which is filled with high probability after n releases.  Write further  
	
    F_1 := W_1 ∖ W_1^f

for the fluctuation region. Water particles in the fluctuation region are declared frozen, and they will be released at a later time.
On top of the water-filled region W_1^f we are going to build a second cluster with again n particles, so to fill a rectangle of height 4cNlog N with high probability.  Let W_2 denote such a cluster,  obtained by adding n particles to W_1^f according to IDLA rules (thus, new water particles can, and will, settle inside F_1). Write W_2^f and F_2 for the filled region and fluctuation region of such cluster. Then, as in (<ref>), we have 
	
    ( R_4cNlog N⊆ 
    	W_1^f ∪ W_2 ⊆ R_2a N log N + 4cNlog N) ≥ 1-2N^-( +2+m) .

We again declare particles in F_2 frozen, and treat their locations as empty for subsequent walkers. This procedure is iterated for k= ⌊ T/n ⌋ -1 rounds.

Let Ω_1 denote the event that the fluctuations bound (<ref>) holds for all k rounds, that is 
	
    Ω_1 := { W_1^f ∪ W_2^f ∪…∪ W_k^f  = R_2kcNlog N}∩⋂_l=1^k { F_l ⊆ 
    	R_2alog N + 2lcNlog N∖  R_2lcNlog N} .

Then by (<ref>)
    ( Ω_1 ) ≥ 1-kN^-( +2+ m)≥ 1-N^-( +2 ) .


Let us restrict to this good event. It remains to release the akNlog N frozen particles from their locations, plus T- k n new ones uniformly from level 0. Denote by W(T) the cluster obtained after all the released particles have settled, so that |W(T)|=T. By the Abelian property, W(T) has the same distribution as A(T). 
Write T' = T-kn + akNlog N for brevity, 

and let W'(T') denote the cluster obtained by adding T' particles to the filled rectangle R_2kcNlog N according to IDLA rules (more precisely, we start T' random walks  uniformly from level zero, independently of everything else, and add their exit locations to the cluster). We argue that we can couple W(T) and W'(T') so that they coincide with high probability. To see this, we proceed as follows. First release T-kn new particles uniformly from level 0, and note that, since T-kn ≥ n, on the event Ω_1 these will fill a rectangle of height 2cNlog N with probability at least 1-N^-( +2+m). If this happens, then all the frozen particles are at distance at least cNlog N from the boundary of the cluster. Thus by Proposition <ref> we can couple W(T) and W'(T') so that 
	
    ( W(T) = W'(T') ) 
    	≥ 1-  (Ω_1) - N^-( +2+m) - N^-( +2) ≥ 1 - N^-( +1 ) .

In all, we have reduced the problem of bounding the fluctuations of W(T)(d)=A(T) to the same one for the smaller cluster 
	
    A(T') (d)= W'(T') ∖ R_2kcNlog N ,

at the price of a small probability of failure. Since T' ≤ 2 max{ 2n , aT/N }, this either makes the number of particles ((N log N )^2), in which case we stop, or it decreases it by a multiplicative factor 2a/N. Thus after at most m iterations of the above procedure we are back to clusters with ((N log N)^2) particles, which we know to have logarithmic fluctuations. This shows that 
	
    (  R_T/N - a log N ⊆  A(T) ⊆
    	R_T/N + a  log N  ) ≥ 1-m N^-( +1 ) ≥ 1-N^- ,

so (<ref>) holds with b_ , m = a, as wanted.  
	
	




































§ TYPICAL PROFILES ARE SHALLOW

In this section we show that typical IDLA profiles have at most logarithmic height, thus proving Theorem <ref>.  This is achieved by combining Theorem <ref> with a control on the density of stationary clusters. 



 §.§ Decay of the excess height

We distinguish between high and low density clusters by looking at their excess height, that we now define. 

Recall thatΩdenotes the set of clusters completely filled up to level0, so thath(A) ≥0for allA∈Ω, while|A|denotes the total number of sites inAstrictly above level0.  
[Excess height]
For A∈Ω, the excess height of A, denoted by (A),  is defined as the difference between the height of A and the minimum possible height, i.e., 
    (A) := h(A) - |A|/N  .

Note that(A) ≥0 . We say that a clusterAhas high density if (A) ≤^*, where^* is a constant to be chosen later depending only onN. If instead(A) > ^*, thenAis said to have low density. 



To start with, we prove that, for a suitable choice of^*, the excess height drops below^*quickly under the IDLA dynamics.


Let (A(t))_t≥ 0 denote an IDLA process on _N× with A(0) ⊇ R_0. For t≥ 0 let (t) := (A(t)) denote the excess height of A(t). 
Then for any η∈ (0,1) there exists a constant ^* = ^* (N, η ), depending only on N and η,  such that if 
	
    T_^*:= inf{ t≥ 0 :  (t) ≤^* }

denotes the first time that the excess height drops below ^*, then 
	
    ( T_^* >t ) ≤  e^-η^2/8 N^2 t ,

for t> N/η ((0) - ^*) and N large enough.




Lemma <ref> is an easy consequence of the following result, which tells us that if a cluster has low density then its excess height has a negative drift under the IDLA dynamics. 
	


Let _t := σ{ A(s) : s≤ t }, and write h(t) in place of h(A(t)) for brevity. Then for all η∈ (0, 1 ) there exists a constant ^* = ^* (N ,η ), depending only on N and η, such that if  (t) >  ^* then  it holds 
	
    ( h(t+1) - h(t) | _t ) < 1-η/N

for N large enough.

Fix η∈ (0,1) throughout. 
For k≤ h(t), we say that level k is bad if it contains at least one empty site, that is if A(t)^c ∩{ y=k}≠∅. 
We claim that if (t) ≥^* then there are at least ^* bad levels between 0 and the top one h(t). Indeed, since h(t) ≥|A(t)|/N +^* then there are at least |A(t)|/N +^* levels above level 0 in the cluster, and at most ⌊|A(t)|/N⌋ of them can be completely filled. 

Recall from (<ref>) the definition of _N(N^-), and note that by (<ref>) and  Lemma <ref> with =2 we have 
	
    max_x∈_N_(x,0) ( τ_n^y < τ_N (N^-2) ) 
    	≤max_x∈_N_(x,0) ( τ_n^y < 6 N^2 log N ) ≤ N^-2
 
as long as n≥ n^*:= 20 N log N. 

Then, if ø = (x(k) , y(k) )_k≥ 0 is a simple random walk on _N×, the above implies that 
	
    min_x,x'∈_N_(x,0)( y (τ_n^*^y ) = (x',n^* ) ) 
    	≥1/N - 1/N^2≥1/2N

for N large enough. 

In words, a simple random walk on _N × starting at level zero has probability at least 1 /2N to reach  level n^* for the first time at any given vertex, uniformly over the starting location. Now, 
since there are at least ^* bad levels, we can find at least ^*/n^* bad levels at distance at least n^* from each other. We treat these as traps. More precisely, for a new particle to increase the height of the cluster A(t), the particle must travel through all the bad levels without exiting the cluster, until it reaches the top. Since we are taking the bad levels sufficiently far apart, the particle has time to mix in between, so whenever it reaches a bad level for the first time it has probability at least 1/2N to fall outside the cluster. By taking enough bad levels, then, we can make the probability for the particle to survive all of them arbitrarily small. 



Formally, since the walker has probability at least 1/2 N to exit the cluster upon reaching a bad level for the first time, we have 
	
    (h(t+1) - h(t) =1 | _t ) ≤( 1-1/2N)^^*/ n^* .

To make this smaller than 1-η/N it suffices to take ^* large enough, precisely 
	
    ^* ≥⌈ 2 n^* N log( N/1-η)  ⌉ ,

which concludes the proof.



Note in particular that 
	
    ^* > 40 (N log N)^2 ,

which will be useful later on. We can now prove that low density clusters tend to decrease their excess height under IDLA dynamics. 


Let n_0 = |A(0) | denote the number of sites in A(0) of positive height, and assume that (0) = h(0) - n_0 /N > ^*, with ^* as in (<ref>). 
It follows from Lemma <ref> that 
	
    M(t) := h(t) - n_0 +(1-η)t/N ,    t≥ 0
 
is a supermartingale up to the stopping time T_^*, with M(0) = (0). 
As a consequence, the stopped process M^*(t) = M(t∧ T_^*) is a supermartingale for all t≥ 0, with M^*(t) = M(t) for t≤ T_^*, and 
	
    |M^*(t+1) - M^*(t) | 
    	≤  |h(t+1) - h(t) | + 1-η/N≤ 2

for all t≥ 0.  
Now, since  |A(t)|= n_0+t, for t< T_^* we have
	
    { (t) >^* }  = { h(t) - n_0+t/N > ^* }⊆{ M(t) >^* + η/N t } 
    	 = {  M^*(t) >^* + η/N t } .

It thus follows from Azuma's inequality that, for t> N/η ((0) - ^*), 
	
    (T_^* >t)    ≤( T_^* >t , (t) > ^* ) 
    	 ≤( T_^* >t , M^*(t) >^* + η/N t ) 
       ≤( M^*(t) - M^*(0) > ^* + η/N t  - M(0) ) 
       ≤exp{ -  ( ^* + η t /N -M(0))^2/8t}
       ≤exp{ -  ( ^*  - (0) )^2+ (η t /N)^2 /8t}
       ≤exp{ - η^2/8 N^2 t }  ,

as claimed. 
 
Lemma <ref> implies that Shifted IDLA is positive recurrent, thus proving the existence of the stationary distribution μ_N. To see this it suffices to show, for example, that the flat configuration R_0 is positive recurrent. 
Let (A (t))_t≥ 0 be an IDLA process with A (0) = R_0, and define  T_0 to be the first time t such that A (t) = R_k for some k≥ 1. Here is a wasteful way to show that _R_0 (T_0) <∞. Fix any η∈ (0,1) and let ^*=^*(N, η ) be the integer constant in Lemma <ref>. Starting from R_0, release ^* N particles: with probability at least N^-^* N the final configuration will be the filled rectangle R_^*. If not, then the excess height has increased by at most ^* N. We keep releasing particles until the excess height falls again below ^*: by Lemma <ref> this takes a random time with exponential tails, and hence finite expectation. Once the excess height is at most ^*, there are at most ^* N empty sites below the top level in the cluster. We release as many particles as the number of the empty sites below the top level: with probability at least N^-^* N the final configuration will be a filled rectangle R_k for some k≥ 1. If not, the excess height is at most ^* + ^* N: we again wait for it to fall below ^*, and iterate. After at most a Geometric(N^-^* N) number of attempts, the final configuration will be a filled rectangle. Each attempt takes ^* N releases, plus the time it takes for the excess height to fall below ^* starting from ^* +^* N, which has exponential tails. 

In all, we conclude that the total time it takes to go from R_0 back to a flat configuration R_k for some k≥ 1 has finite expectation. 


 §.§ Typical clusters are dense

In this section we show that, forNlarge enough,μ_Ngives high probability to high density clusters. This shows that stationary clusters are dense, and hence that typical clusters are dense, with high probability.



For ^*=^*(N , η  ) as in 
(<ref>) and N large enough, it holds 

	
    μ_N ( { A :   (A) > 2 ^*  })  ≤ e^-N/2  .

Recall that for (A(t))_t≥ 0 IDLA process on _N×, we denote by (A^*(t))_t≥ 0 the associated shifted process. Let us denote by Ω^* := { A^* : A∈Ω} its state space.   

Define the sets 
	
    = { A ∈Ω^* :  (A) ≤^* } ,      = { A ∈Ω^* :  (A) ≤ 2^* } .

We seek to bound μ_N(^c). By the Ergodic theorem for positive recurrent Markov chains, 
	
    μ_N (^c ) = lim_t→∞1/t( ∑_i=1^t 1 (A^*(i) ∈^c ) ) .

Define the following stopping times: 
	
    _ ,∂^1 := inf{ t≥ 0 : A^*(t) ∈∂}  , 
    	 
       _∂ , ^1 := inf{ t≥_ ,∂^1 : A^*(t) ∈}  - 
    	_ ,∂^1  ,
    	
       _ ,∂^i := inf{ t≥_∂ , ^i-1 : A^*(t) ∈∂}  
    	- _∂ , ^i-1 ,     i ≥  2, 
       _∂ , ^i := inf{ t≥_ ,∂^i : A^*(t) ∈} 
    	- _ ,∂^i ,    i≥ 2,

where ∂ = { A ∈Ω^* : (A) ∈ [2^* , 2^*+1)}. 
Note that, since the excess height always changes by either 1-1/N or 1/N,

	
    ( ∑_i=1^k (  _ ,∂^i  + _∂ , ^i) ) ≤^*+1 ,
    	     ∀  k≥ 1.

We divide the interval [0,t] into excursions from  to ∂ and then from ∂ to . Since during excursions from  to ∂ the process is in , only excursions from ∂ to  contribute to the expectation in (<ref>). Let us say that the concatenation of an excursion from  to ∂ and from ∂ to  is a complete excursion. In the next lemma we bound the number of complete excursions by time t. 

Let 
	
    K(t) := sup{ k≥ 1 : ∑_i=1^k (  _ ,∂^i  + _∂ , ^i) ≤ t }

denote the number of complete excursions by time t. 
Then for = 6/N e^N and N large enough  it holds 
	
    (K(t) ≥ t) ≤exp( - t/N e^N) .

Let 
	
    K̃(t) := sup{ k≥ 1 : ∑_i=1^k   _ ,∂^i≤ t } .

Then clearly K̃(t) ≥ K(t), and so (K(t) ≥ t ) ≤ (K̃ (t) ≥ t). Moreover, since the excess height changes by at most 1  at each step, at the start of each excursion from  to ∂ the excess height must lie between ^*-1 and ^*. We know (cf. Lemma <ref>) that when the excess height is greater than ^* it has a negative drift, but we do not have any information on its drift when the process is in the set . To overcome this problem, we simply ignore the time spent in . Indeed, we will see that the time spent in ∖ is large enough to give us what we want.


We seek to stochastically bound ^i_ , ∂ from below. To this end, define the following auxiliary random walk on 1/N ={n/N : n∈}, with a reflecting barrier at zero: 
	
    X_0 = 0 ,     ( X_i+1 =1 -1/N | X_i =0 ) =1 , 
        X_i+1 - X_i = 
    	1-1/N , 1-η/N , 
    
    	-1/N ,      X_i > 0.

Note that, while the Shifted IDLA process (A^*(t))_t≥ 0 is in ∖, the walk X away from 0  stochastically dominates the associated excess height process by Lemma <ref>. In particular, let N_0 denote the total number of visits of X to 0 before reaching [^* , ∞ ). Then 
	
    ^i_ , ∂≽ N_0 N ,

since each time the walk reaches 0 it jumps deterministically to 1-1/N, after which it takes at least N steps to reach 0 again.







Now, N_0 is a geometric random variable with success probability _1-1/N ( X  [^* , ∞ )  0 ). The next result tells us that this probability is very small, and so N_0 is typically large. 

For ^* as in (<ref>) and N large enough, it holds 
 	
    _1-1/N ( X  [^* , ∞ )   0 ) ≤  e^-N .

Let us postpone the proof of the above lemma to Appendix <ref>, and explain how from this one can deduce the bound of Lemma <ref>. 
Note that (<ref>) and (<ref>) together imply that 

	
    ( ^i_ , ∂ ) ≥  N e^N

for N large enough. 
Let now  T^X_^* := inf{ i≥ 0 : X_i ≥^* } denote the first hitting time of [^* , ∞ ) for the walk X, and notice that T_^*^X ≥ N_0 N. 	 We define  ( T^X,(i)_^*)_i≥ 1 to be i.i.d. copies of T^X_^*, independent of everything else. 
Recall the definition of K̃ (t), and define further 

    K̃'(t) := sup{ k≥ 1 : ∑_i=1^k   T^X,(i)_^*≤ t } .

Then we have 
	
    (K̃(t) ≥ t )    ≤ ( K̃'(t) ≥ t ) = 
    	( ∑_i=1^ t T^X,(i)_^*≤ t ) .

Let = 6/N e^N. Then for N large enough it holds 
	
    ( ∑_i=1^ t T^X,(i)_^*≤ t )  
    	≤exp( - t/N e^N) .

This lemma is an easy consequence of the fact that T^X_^*≥ N_0 N and Lemma <ref>, so we leave the proof for Appendix <ref>. This finishes the proof of Lemma <ref>. 


Using (<ref>) we can conclude the proof of  Proposition <ref>. Indeed, writing (t) in place of (A^*(t)) for brevity, and taking  as above,  we find

    μ_N (^c )    = lim_t→∞1/t( ∑_i=1^t 1 (  (t) ≥ 2^* ) ) 
    	≤lim_t→∞1/t( t- ∑_i=1^K(t)_ ,∂^i) 
    	
       ≤lim_t→∞[ 1/t( t- ∑_i=1^K(t)_ ,∂^i  ;    K(t) <  t )  +  (K(t) ≥ t ) ] 
    	
       ≤lim_t→∞[ 1/t( ∑_i=1^ t_∂  , ^i) + exp( - t/N e^N) ] 
    	=  ( _∂ ,^1 ) 
    	=  2  ( _∂ ,^1 )/N e^N  .

Lemma <ref> with t_0 := N/η^* then yields 
	
    ( _∂ ,^1 )     
    	=∫_0^∞ ( _∂ ,^1 >t ) dt 
    	≤ t_0  + ∫_t_0 ^∞exp( - η^2 t/8N^2)  dt 
    	
        = N ^*/η  + 8N^2/η^2exp( -η^*/  8N)  
    	≤2N ^*/η

for N large enough, since ^* > (N log N)^2 by (<ref>). 
Thus we conclude that 
	
    μ_N (^c ) ≤4  ^* /η e^-N≤ e^-N/2

for N large enough, as claimed. 



 §.§ From high density to low height

We have shown in the previous section that typical clusters are dense.

While this does not give any information on the height ofA, it provides an upper bound on the number of empty sites, that we will call holes, below the top levelh(A).  
Indeed, if(A) ≤^*then  there can be at mostN^*holes in the cluster.  We now obtain a bound on the time it takes to fill these holes (cf. Proposition <ref>),  showing that it is at most polynomial inN, and use this to prove that stationary clusters have at most polynomial height (cf. Proposition <ref>).


Let (A^*(t))_t≥ 0 denote a Shifted IDLA process on _N ×, and assume that  (A^*(0)) ≤^*, with ^* as in (<ref>).   
Let 
	
    := ⌈ 2N^2 ^*⌉ +1 .
 
Write  h^*(t) in place of h(A^*(t)) for brevity, and assume that h^*(0) >. 
Define  T_ := inf{ t≥ 0 : h^*(t) ≤} to be the first time the height of the Shifted IDLA process drops below . Then there exists a constant C_η >0, depending only on η, such that 
	
    ( T_ > t ) ≤ 4 exp( -  C_η t/ N)

for N large enough. 

Since N is polynomial in N, this tells us that, when starting from a dense configuration,  the height of a Shifted IDLA process drops below  after at most polynomially many releases. 








We argue as follows. Each time we add a new particle to the cluster, the lowest hole has probability at least 1/N to be filled, independently of everything else. Hence it will take at most a geometric number of releases of parameter 1/N to fill the lowest hole. In total, then, it will take at most the sum of N^* i.i.d. Geometric(1/N) to fill all the holes up to the top level  h(A). Some care is needed, though: we cannot let the excess height increase too much while releasing these extra particles. 


Let (G_i)_i=1^N^* be a collection of i.i.d. Geometric(1/N) random variables, and note that since > 2 N^2 ^* we have
	
    ( ∑_i=1^N^* G_i > ) < 1/2  .

It follows that if we release  particles then we have probability at least 1/2 to fill all the holes below the top level. If we fail, then the excess height has increased by at most . If so, we keep on releasing particles until the excess height falls again below ^*, and iterate. 

After a Geometric(1/2) number of attempts we will have filled all the holes below the top level, which implies that the resulting Shifted IDLA cluster will have height at most . 

To formalise the above strategy, write (t) in place of (A^*(t)) and define the following random times: 
	
    _0 := 0 ,  
       _k :=  inf{ t≥_k-1+ :  (t) ≤^* }  ,    k≥ 1, 
        s_k := _k -( _k-1 + )   ,    k≥ 1.

Then, by definition, at times _i there are at most N^* holes below the top level. Since the number of releases needed to fill all these holes is stochastically dominated by the sum of N^* i.i.d. Geometric(1/N ) random variables, (<ref>) implies that at times _i + we have filled all the holes with probability at least 1/2. If this happens, then h^*(_i +) ≤, and we stop. Otherwise (_i +) ≤^* +, and we start again. 

Let 
	
    K := min{ k≥ 0 : h^* (_k +) ≤}

denote the number of attempts needed to succeed. Then, denoting by ≼  stochastic domination, we have  K ≼ K' for K'  Geometric(1/2) random variable.  
Note that the times s_i's are not in general identically distributed. 

It is convenient to make them i.i.d. by assuming that the excess height always starts from the maximum value ^*+. More precisely, let 
	
    ŝ:= inf{ t≥ 0 : (t) ≤^* (0) =^*+} ,

and let (ŝ_i)_i≥ 1 be a sequence of i.i.d. random variables equal in law to ŝ. Then s_i ≼ŝ_i and 
we have that 
	
    T_≼  K + ∑_i=1^K ŝ_i 
    	≼  K' + ∑_i=1^K'ŝ_i .

We use this to estimate the moment generating function of T_. 
For ł∈, set M (ł) :=  ( e^łŝ ). We have
	
    (e^ł T_ )    ≤[ exp{ł( K' + ∑_i=1^K'ŝ_i )}] 
        
    	= ∑_k=1^∞[ exp{ł( k + ∑_i=1^k s_i )}1(K'=k)] 
       ≤∑_k=1^∞( e^ł M(ł)/2)^k  ,

where the first equality above follows from the Monotone Convergence Theorem, and the last inequality from 
the independence of K' and the ŝ_i's.


For ł < η^2/32 N^2 and N large enough, it holds M(ł ) ≤3/2exp( 2 N ł/η). 

The above lemma implies that e^ł M(ł ) /2≤3/4exp{ł( 1 + 2N/η) }, 
which can be made smaller than, say, 4/5 by taking 
	
    ł < log (16/15)/ ( 1+2N/η ) .

Let  C_η = log (16/15)/4η, so that C_η/N <  log (16/15)/ ( 1+2N/η ) for large N. If ł^* = C_η/N then  we have 
	
    ( e^ł^* T_ ) ≤∑_k=1^∞( 4/5)^k 
    	= 4 .

Thus we conclude that 
	
    ( T_ > t ) ≤ ( e^ł^* T_ ) e^-ł^* t≤ 4 e^-ł^* t = 4 exp( -  C_η t /N) ,

as claimed. It remains to prove Lemma <ref>.

Recall the definition of ŝ from (<ref>), so that M(ł ) =  (e^łŝ ). Introduce the auxiliary random walk (X_k)_k≥ 0 defined as in (<ref>), and note that 
	
    ŝ≼_ 
    	:= inf{ t≥ 0 : X_t ≤^* ^* +} .

Then it follows from Lemma <ref> that, for t≥2 N/η and N large enough, it holds 
	
    ( _ > t ) ≤exp( -η^2 t/8N^2).

Therefore, for ł < η^2/32 N^2, we find 
	
    ( e^łŝ )    ≤ (e^ł_  ) 
    	= ∫_0^∞ ( e^ł_≥ t ) dt 
    	= ∫_0^∞( _≥log t/ł) dt 
    	
       ≤exp( 2 N ł/η)  + ∫_exp( 2 N ł/η) ^∞exp( -η^2 log t /8N^2 ł) dt 
    	
        = exp( 2 N ł/η) + 
    	exp( - 2 N ł/η( η^2/8 N^2 ł -1 ) ) /η^2/8 N^2 ł -1 
       ≤3/2exp(  2 N ł/η) ,

where the last inequality holds for N large enough. 

This concludes the proof of Proposition <ref>. 


We use this to show that stationary clusters have at most polynomial height. 

For N large enough, it holds 
	
    μ_N ( { A :  h(A) > N^8 })  
    	≤  2e^-N/2 .

Let (A(t))_t≥ 0 be an IDLA process with A(0) = A ∼μ_N. Then A(t) ∼μ_N for all deterministic t≥ 0. Write h(t) in place of h(A(t)) for brevity. Take ^* = N^2 log^3 N, and note that it satisfies (<ref>). Define  as in (<ref>). Then we have 
	
    ( h(A) > N^8 )     =  (h(N^7) > N^8 | A(0) =A) 
       ≤ ( h(N^7) > N^8 |  (A(0)) ≤ 2^* ) +  ( (A(0)) > 2^* )
    	
       ≤ (T_ > N^7 |  (A(0)) ≤ 2^* ) + e^-N/2≤ 2e^-N/2 ,

where we have used that if T_≤ N^7 then h(N^7) ≤ + N^7 < N^8. 

It is worth pointing out that the proof of Proposition <ref>, and hence of Proposition <ref> above, would also work for driving random walks on _N × with a vertical drift. This would still give a polynomial bound for the height of typical clusters, perhaps with a larger exponent than the one in Proposition <ref>. Reasoning as in Theorem <ref>, such height bound could in turn be translated into a (largely non-optimal) upper bound for the time it takes for IDLA with transient driving walks to forget its initial profile. 


 §.§ Typical clusters are shallow

We now finish the proof of Theorem <ref>. 
To start with, note that it suffices to prove the result for stationary clusters. Indeed, suppose we showed that for any>0there exists a constantc_such that 
	
    μ_N ( { A : h(A) > c_log N }) ≤ N^-

forNlarge enough. Then, ifν_Nis anyk-lukewarm start for Shifted IDLA, we have 
	
    ν_N ( { A : h(A) > c_log N }) ≤ N^-( -k) ,

so that (<ref>) still holds with+kin place of. It thus suffices to prove Theorem <ref> for stationary clusters. We argue as follows.
Let(A(t))_t≥0be an IDLA process starting fromA(0) ∼μ_N, so thatA(t) ∼μ_Nfor all deterministict≥0. Introduce an auxiliary IDLA process(A̅(t))_t≥0starting from the flat profileA̅(0)=R_0. Then, if|A(0)|=n_0, we have 
	
    |A(t) | = |A̅(n_0+t)| = n_0 +t ,     ∀ t≥ 0 .

WriteA'(t) = A̅(n_0+t)to shorten the notation. 
Following the ideas presented in the proof of Theorem <ref>, we will couple the clustersA(N^10)andA'(N^10)so that they match with high probability. SinceA(N^10) ∼μ_N, andA'(N^10)has logarithmic fluctuations with high probability, this will allow us to conclude.

To start with, note that by Proposition <ref> we have 
	
    ( h(A(0)) > N^8 ) ≤ 2e^-N/2

forNlarge enough. In particular this shows that(n_0 >N^9) ≤2e^-N/2. 
We can use this to bound the height ofA'(0). Indeed, foras in the statement of Theorem <ref>, we have 
	
    ( h(A'(0)) > 2N^8 )    ≤ ( h(A̅(n_0)) > 2N^8  , n_0 ≤ N^9) +  ( n_0 > N^9 ) 
    	
       ≤( h(A̅ (N^9) ) > 2N^8 ) + 2e^-N/2≤ N^-2 + 2e^-N/2≤ 2N^-2
 
forNlarge enough, where in the last inequality we have used Theorem <ref> to argue that an IDLA cluster built by addingN^9particles toR_0has height(N^8)with high probability. 
Introduce a water clusterW_0obtained by addingN^10particles to the flat configurationR_0according to IDLA rules, and note that
	
    ( W_0 ⊇ R_3N^8) ≥ 1- N^-2
 
by Theorem <ref> forNlarge enough. 
Define two auxiliary water processes(W(t))_t≥0and(W'(t))_t≥0as follows. SetW(0) = W'(0) = W_0. Particles inW(0) ∩A(0)andW'(0) ∩A'(0)are declared frozen, and will be released at a later time. Note that 
	
    ( max{ h(A(0)) , h(A'(0)) }≤ 2N^8 ;   W_0 ⊇ R_3N^8) 
    	≥ 1-4N^-2 ,
 
which shows that all frozen particles are at distance at leastN^8from the boundary ofW_0with high probability. 
Fix arbitrary enumerations of the two sets of frozen particles, and accordingly denote their locations by{ z_1 , z_2 , …, z_n_0}and{ z'_1 , z'_2 , …, z'_n_0}. 
Fort≥0, then, letW(t)(respectivelyW'(t)) be the cluster obtained by adding toW(t-1)(respectivelyW'(t-1)) the exit location from it of a simple random walk on_N ×starting fromz_t(respectivelyz'_t). The random walks starting fromz_tandz'_tare coupled as explained in the introduction: the higher one stays in place until the other one reaches its level, after which they move together in the vertical coordinate, and according to the reflection coupling in the horizontal one[If needed, we use the first horizontal step to adjust the parity of the difference of the horizontal coordinates, as explained in the proof of Proposition <ref>.]. 
Then, writingE_0for the event appearing in (<ref>) for brevity, by Proposition <ref> we find 
	
    ( W(n_0) ≠  W'(n_0) )    ≤ (  W(n_0) ≠  W'(n_0)  |    E_0 ) + (E_0^c) 
    	
       ≤ N^-2 + 4N^-2 = 5N^-2

forNlarge enough. 
ThusW(n_0) = W'(n_0)with high probability. SinceA(N^10)(d)= W(n_0)andA'(N^10) (d)= W'(n_0), this shows that we can coupleA(N^10)andA'(N^10)so that 
	
    ( A(N^10) = A'(N^10)) ≥ 1-5N^-2 .

Now,A(N^10)is stationary sinceA(0)is. We want to argue thatA'(N^10) = A̅(n_0 + N^10 ) has logarithmic fluctuations. Ifn_0were deterministic, this would follow from Theorem <ref>. Insteadn_0is random since such isA(0), and as already observed it satisfies(n_0 > N^9 )  ≤2e^-N/2 forNlarge enough. 
Moreover, by Theorem <ref> there exists a constantb_, depending only on, such that 
	
    (  R_t/N - b_log N ⊆  A(t) ⊆
    	R_t/N + b_log N    ∀ t ≤ 2N^10) ≥ 1-N^-2

forNlarge enough. We thus conclude that 
	
    ( {  R_n_0+N^10/N - b_log N    ⊆  A'(N^10) ⊆
    	R_n_0+N^10/N + b_log N  }^c ) =
    	
        = ( {  R_n_0+N^10/N - b_log N ⊆A̅(n_0+N^10) ⊆
    	R_n_0+N^10/N + b_log N  }^c )  ≤
    
    
    	
       ≤( { R_t/N - b_log N ⊆A̅(t) ⊆
    	R_t/N + b_log N    ∀ t ≤ 2N^10}^c ) + 
    	 (n_0 > N^9) 
    	
       ≤ N^-2 + 2e^-N/2≤ 2N^-2

forNlarge enough. This shows thatA'(N^10)has logarithmic fluctuations with high probability. Recall that forA ∈Ωwe denote byA^*its shifted version (cf. Definition <ref>). Then we have found that 
	
    μ_N ( { A : h(A) > 2b_log N }) 
    	    = ( h(A^*(N^10)) > 2 b_log N ) 
    	
       ≤( h(A'^*(N^10)) > 2 b_log N )  + 
    	( A(N^10) ≠ A'(N^10) ) 
    	
       ≤ 7 N^-2≤ N^-

forNlarge enough, which concludes the proof. 





§ THE UPPER BOUND

We briefly explain how one can deduce Theorem <ref> from Theorems <ref> and <ref>. For any, k>0letc_, kbe defined as in Theorem <ref>, while we taked'_, 2as in Theorem <ref> withm=2. Set 
	
    d_ , k := c_ ,k + d'_ , 2 ,      
    	t_ , k := d_ ,k N^2 log N .

Then, ifν_Nis anyk-lukewarm distribution, we can define 
	
    Ω_ ,k := { A : h(A) ≤ c_ ,klog N }

to have that, by Theorem <ref>,
	
    ( Ω_ ,k) ≥ 1-N^-

forNlarge enough. 
Take any two clustersA_0,A'_0 inΩ_, kwith|A_0|=|A'_0|, and let(A(t))_t≥0and(A'(t))_t≥0be two IDLA processes starting fromA_0andA'_0respectively. Then Theorem <ref> tells us that we can buildA(t_, k)andA'(t_, k)on the same probability space so that 
	
    ( A(t_ , k) ≠ A'(t_ , k)  ) ≤ N^-

forNlarge enough.  
We thus gather that 
	
    P(t_ , k) - P' (t_ , k  )_TV    = 
    	sup_S⊆Ω|  (A(t_ , k ) ∈ S ) -  (A'(t_ , k )∈ S ) 
    	| 
       ≤ 2 ( A(t_ , k) ≠ A'(t_ , k) ) 
    	≤ 2N^-

forNlarge enough. Sinceis arbitrary, this concludes the proof. 
	






§ THE LOWER BOUND
 
In this section we specialise to stationary initial clusters, and prove that if two such clusters are sampled independently fromμ_N, then the IDLA dynamics will remember from which one it started for at least orderN^2steps, as stated in Theorem <ref>. 
We proceed as follows. We first recall the GFF fluctuations result by Jerison, Levine and Sheffield <cit.>, saying that the average IDLA fluctuations, appropriately measured, converge to the restriction of the Gaussian Free Field to the unit circle. We then use this to define an observable which we show to be large, with positive probability, for stationary IDLA clusters (cf. Proposition <ref>). Finally, we argue that a necessary condition for IDLA to forget the initial configuration is for this observable to reach0, and show that this takes time at leastN^2for some>0, thus proving the result.  



 §.§ Average IDLA fluctuations and the GFF

Let us start by briefly recalling the average IDLA fluctuations result by Jerison, Levine and Sheffield <cit.>.  
Let(A(t))_t≥0be an IDLA process on_N ×starting from flat, i.e.A(0) = R_0. 
Forn=(n_1 , n_2) ∈_N ×, define the rescaled square 
	
    Q_N(n) := { (x,y) ∈× : 
    	x ∈( n_1 -1/N , n_1/N] ,   
    	y ∈( n_2 -1/N , n_2/N] }

with side–length1/Nand( n_1/N , n_2/N )as top–right corner, and set 
	
    A_N(t) := ⋃_n ∈ A(t) Q_N(n) ,

so thatA_N(t) ⊂×. We use the rescaled and filled clusterA_N(t)to define the discrepancy function
    D_N,t (x,y) := N ( _A_N(t) (x,y) - _{ y≤t/N^2} (x,y) )

for(x,y) ∈×. Note thatD_N,tis supported on the symmetric differenceA_N(t) ΔR_t/N^2. 
Finally, letφ∈C^∞ (×)be of the form 
	
    φ (x,y) = ∑_|k|≤ K_k(y) e^2π i kx

for some finite integerKand with_-k = _k, so thatφis real–valued. Jerison, Levine and Sheffield proved the following. 

[Theorem 3, <cit.>] 
Let T=y_0 N^2  and φ be as above. Then, as N →∞, 
	
    D_N,T(φ ) := ∫_× D_N,T(x,y) φ(x,y)  x  y

converges in distribution to a Gaussian random variable with mean zero and variance 
	
    v(φ ) = ∑_0<|k|≤ K |_k(y_0)|^2 
    	(  1-e^-4 π |k| y_0/4π |k|) .
 

The next result tells us that the above theorem can be generalised to larger times. 


Let T=CN^2 log N for some absolute constant C large enough. Then, 
as N→∞, 
	
    ∫_× D_N,T(x,y) φ( x,y - T/N^2)  x  y

converges in distribution to a Gaussian random variable with mean zero and variance
	
    v_μ (φ ) = ∑_0<|k|≤ K|_k(0)|^2/4π |k|  .

Note that, as observed in <cit.>, the exponential term in v(φ ) is due to the fact that the process started from flat. Indeed, this term does not appear in the limiting variance v_μ (φ ), since T is large enough for the process to have reached stationarity. 
 
The above result can be proved exactly as in <cit.>, Theorem 3, by replacing the maximal fluctuations result with Theorem <ref> above. For this reason we choose to skip the proof.  

We now use the fact thatA(T)is close to a stationary cluster to control the size of the average fluctuations at stationarity. LetA^μdenote a stationary cluster, that isA^μ∼μ_N, and denote byA_N^μits rescaled and filled version as in (<ref>). We start an IDLA process(A^μ(t))_t≥0fromA^μ(0) = A^μ. Letn_0 = |A^μ(0) |be the number of particles inA^μ(0)above level zero. Then, if(A(t))_t≥0is an IDLA process starting from flat, we have 
	
    |A(n_0)| = |A^μ (0) |=n_0

and hence|A(n_0 +t)| = |A^μ(t)|=n_0+tfor allt≥0. 
Moreover, by Theorems <ref> and <ref>, for any>0there existsa_<∞such that, withh_0 =  max{ h(A(n_0)) , h(A^μ(0) ) } , it holds 
	
    ( h_0 > a_log N ) ≤ 2N^-

forNlarge enough. Consider the time–shifted IDLA processA'(t) = A(n_0 +t)starting from logarithmic height with high probability. 
Then by Theorem <ref> for any>0there exists a finite constantd_such that fort_= d_N^2 logNwe can couple the clustersA^μ(t_) , A'(t_)so that 
	
    ( A^μ (t_ ) ≠ A'(t_) ,   h_0 ≤ a_log N ) ≤ 3N^-

forNlarge enough. 
LetT= t_+ n_0. Recall from (<ref>) the definition ofD_N,T, and define 
	
    D_N,t_^μ (x,y) :=  N ( _A_N^μ (t_)  (x,y) - 
    	 _{ y≤T/N^2} (x,y) ) .

Forφas above, introduce the random variables 
	
    X_N^φ    : = ∫_× D_N,T(x,y) 
    	φ( x,y-T/N^2)  x  y , 
    
    	X_N^μ , φ    :=  ∫_× D^μ _N,t_(x,y) 
    	φ( x,y-T/N^2)  x  y .

Then for any>̣0we have 
	
    ( X_N^μ , φ >)̣≥ ( X_N^φ >,̣ A^μ (t_ ) = A (T)) 
    	≥ ( X_N^φ >)̣ - 5N^- .

Moreover, by Theorem <ref> for any>0we can takeNlarge enough to ensure that, ifis a standard Gaussian random variable,  
	
    (  	X_N^φ >)̣≥( > /√(v(φ ))) -≥1/2 - ( /√(2π v_μ (φ )) +) ,

from which 
	
    ( X_N^μ , φ >)̣≥1/2 - ( /√(2π v_μ (φ )) + + 5N^-) ,

for any,,̣ >0andNlarge enough. 





























 §.§ The initial imbalance

We now make a choice for the test functionφin the above discussion. Let 
	
    ϕ (x,y) := sin(2π x ) = e^2π i x  - e^-2π i x /2 ,

for whichv_μ(ϕ) = 1/8π. Then by (<ref>) we can take= $̣ and N large enough to get 
	
    ( X_N^μ , ϕ >)̣≥1/2 - 4.̣

On the other hand, 
	
    X_N^μ , ϕ    
    	 = ∫_× D_N,t_^μ (x,y) ϕ (x,y)  x  y 
    	= N ∫_×ϕ (x,y) _A_N^μ (t_) (x,y)  x  y 
    	
        = N ∫_A^μ_N(t_)ϕ (x,y)  x  y 
    	(d)= N ∫_A^μ_Nϕ (x,y)  x  y ,
 
where A^μ∼μ_N and the last equality holds in distribution. 
In order to build a martingale, we now approximate ϕ by its discrete harmonic extension ψ away from the line { y=0 } on the high probability event 
	
    E_μ  = { h(A^μ ) ≤ c_log N } ,

with c_ as in Theorem <ref> with k=0.
Following <cit.>, to define ψ we introduce q_N solution of 
	
    cosh (q_N/N) = 2-cos (2π /N) ,

so that q_N = 2π +  (N^-2), and for n=(n_1 , n_2) ∈_N × set 
	
    ψ (n) := e^q_N n_2/Nsin( 2π n_1/N) .

It is easy to check that ψ is discrete harmonic on _N ×. Moreover, for n=(n_1,n_2) ∈ A^μ and (x,y)∈ Q_N(n) we have that on the good event E_μ  
	
    | ϕ (x,y) - ψ (n) | = | sin (2π  x ) - e^q_N n_2/Nsin( 2π n_1/N) | 
    	≤12π c_log N/N ,

from which 
	
    N ∫_A^μ_Nϕ (x,y)  x  y 
    	= 1/N∑_n∈ A^μψ (n) 
    	+ ( log^2 N/N)

for N large enough.
Combining this with (<ref>), we get 
	
    ( 1/N∑_n∈ A^μψ (n) > /2) 
    	≥(  N ∫_A^μ_Nϕ (x,y)  x  y >,̣ E_μ)  
    	≥1/2 - 4-̣ (E_μ) ≥1/2 - 5
    for any >̣0 and N large enough. 
    The same arguments can be used to prove the reverse inequality, thus obtaining  the following. 
    
    Let A^μ∼μ_N be a stationary IDLA cluster. For any >̣0 and N large enough, it holds 
    	
        ( 1/N∑_n∈ A^μψ (n) > 
        	) ≥1/2 - 10,̣    ( 1/N∑_n∈ A^μψ (n) < 
        	-) ≥1/2 -10 .̣
    
    Let  c_2 be defined as in Theorem <ref> with k=0. We define
    	
        Ω_ := { A ∈Ω : h(A) ≤ c_2 log N 1/N∑_n∈ Aψ (n) >/20}  , 
        	
        Ω '_ := { A ∈Ω : h(A) ≤ c_2 log N 1/N∑_n∈ Aψ (n) < -/20}
     
    to have that 
    	
        μ_N ( Ω_)̣   ≥ 1- μ_N ( { A : h(A)>c_2 log N } ) 
        	- ( 1/N∑_n∈ A^μψ (n) > 
        	) 
           ≥1/2 - 1/N^2 - /2≥1/2-
    
    for N large enough. Similarly, μ_N (Ω_'̣) ≥1/2 -$̣ forNlarge enough, and thus (<ref>) in Theorem <ref> is satisfied. 
    
    
    It follows from the above result that if A and A' are two independent samples of μ_N, then  for any >̣0 we can take N large enough so that 
    	
        ( | 1/N∑_n∈ Aψ (n)
        	- 1/N∑_n∈ A'ψ (n) | > 2) 
        	≥ 2( 1/2 - 10 )^2 
        	≥1/2 - 20,̣
    
    which can be made arbitrarily close to 1/2 by taking $̣ small enough. 
    
    
     §.§ The observable
    
    We use the above remark to define a convenient observable which, loosely speaking, measures the difference in the horizontal imbalance of two IDLA processes. TakeA_0 ∈Ω_$̣ and A'_0 ∈Ω '_$̣, and assume|A_0| = |A'_0|without loss of generality, as if not then two IDLA processes starting fromA_0andA'_0will never meet. We takeA_0 , A'_0as starting configurations of two IDLA processes(A(t))_t≥ 0and(A'(t))_t≥ 0. 
     [Imbalance] 
    For A ∈Ω, define the horizontal imbalance of A by
    	
        u_A := 1/N∑_n∈ Aψ (n) 
        	= 1/N∑_n∈ A e^q_N n_2/Nsin( 2π n_1/N) ,
    
    with q_N as in (<ref>). 
    
    We use this to define an observableu(t)which measures the difference in the imbalance ofA(t)andA'(t), namely 
    	
        u(t) := u_A(t)  - u_A'(t) = 1/N∑_n∈ A(t)ψ (n) - 
        	1/N∑_n∈ A'(t)ψ (n) .
    
    Since ψ is discrete harmonic on _N ×, we have that (u(t))_t≥ 0 is a discrete time martingale. 
      
    By Proposition <ref> and Remark <ref> we have 
    	
        ( |u(0)| > )̣≥1/2 - 10
     
    for any>̣0andNlarge enough. ClearlyA(t) = A'(t) impliesu(t) =0, so if we define 
    	
        T_0 = inf{ t≥ 0 : u(t) =0 }
    
    then for any >0we have 
    	
        ( T_0 ≤ N^2  , |u(0)|>)̣   ≤( sup_t≤ N^2  |u(t) - u(0) | > ) 
           ≤1/^̣2( sup_t≤ N^2 |u(t) - u(0)|^2 ) 
        	≤c(Q) /^̣2
    
    forcabsolute constant and 
    	
        Q:= ∑_t=1^ N^2 ( |u(t) -u(t-1)|^2 | _t-1 )  ,
    
    where the last inequality in (<ref>) follows by the Burkholder-Davis-Gundy inequality. Now, if we letn_t,n'_tdenote the settling locations of thet^thwalkers in the two IDLA processes, we have 
    	
        Q = 1/N^2 ∑_t=1^ N^2( | ψ (n_t) - ψ (n'_t) |^2 
        	| _t-1) ,
    
    so 
    	
        (Q) ≤( 2/N^2∑_t=1^ N^2 | ψ (n_t) |^2 ) 
        	+ ( 2/N^2∑_t=1^ N^2 | ψ (n'_t) |^2 )  .
    
    To estimate the above expectations we have to control the height of the clustersA( N^2 )andA'( N^2), as the functionψgrows exponentially with them. We explain how to control the first expectation, the second one following from the same arguments. 
    Introduce the good event 
    	
        E := { h(A( N^2 )) ≤ 100 N }⊇{h(A( N^2 )) ≤ h(A_0) + 60 N } .
    
    Then the a priori bound in Lemma <ref> withm=60gives 
    	
        (E^c ) ≤   e^-100 N
    
    forNlarge enough. OnEwe have 
    	
        1/N^2∑_t=1^ N^2 | ψ (n_t)|^2 
        	≤( max_n∈ A ( N^2 ) |ψ (n)|^2 ) 
        	≤exp{2 q_N/N h(A( N^2)) }≤ C_
    
    for some constantC_depending only on, andNlarge enough. 
    OnE^c, on the other hand, we trivially have thath(A( N^2)) ≤ h(A_0) +  N^2  ≤ 2 N^2 , from which 
    	
        1/N^2∑_t=1^ N^2 | ψ (n_t)|^2 
        	≤( max_n∈ A ( N^2 ) |ψ (n)|^2 ) 
        	≤exp{2 q_N/N h(A( N^2)) }≤αexp{ 32  N }  ,
    
    sinceq_N ≤ 8forNlarge enough. In all, we have found 
    	
        ( 1/N^2∑_t=1^ N^2 | ψ (n_t)|^2  ) 
        	    ≤( 1/N^2∑_t=1^ N^2 | ψ (n_t)|^2  ;   E )  
        	 +( 1/N^2∑_t=1^ N^2 | ψ (n_t)|^2  ;   E^c ) 
        	 
           ≤ C_ +  e^32  N  (E^c) 
        	 ≤ C_ +  e^-68  N≤ 2C_
    
    forNlarge enough. Similarly one can control the same expectation involvingA'( N^2). 
    Thus 
    	
        ( T_0 ≤ N^2  , |u(0)|>)̣≤8c C_/^̣2  ,
    
    wherecis the absolute constant in (<ref>). Letbe as in Theorem <ref>. SinceC_→ 0as→ 0, we can takesmall enough so that8c C_/^̣2≤( 1/2 - 10 ), to find 
    	
        ( T_0 ≤ N^2  , |u(0)|>)̣≤( 1/2 - 10 ) .
    
    Finally, putting this together with (<ref>) we gather that 
    	
        ( T_0 ≤ N^2 |  |u(0)|>) 
        	=   ( T_0 ≤ N^2  , |u(0)|>)̣/ (  |u(0)|>)̣≤ ,
    
    which concludes the proof of Theorem <ref>. 
    
    
    
    
    
    
    § PROOF OF LEMMA <REF>
    
    Recall that we consider a random walkXon1/N, with a reflecting barrier at0, with transition probabilities given by 
    	
        X_0 = 0 ,     ( X_i+1 =1 -1/N | X_i =0 ) =1 , 
            X_i+1 - X_i = 
        	1-1/N , 1-η/N , 
        
        	-1/N ,    X_i > 0.
    
    We aim to show that 
    	
        q:= _1-1/N ( X  [^* ,∞ )  0 ) 
        	≤ e^-N
    
    forNlarge enough. 
    Denote_1-1/Nsimply byto shorten the notation, and letT_0,^*^Xbe the first timeXreaches either0or[^* ,∞ ). Then  we have 
    	
        q  = ( X_T_0,^*^X≥^* ) 
        	   ≤( X_T^X_0,^*≥^* , 
        	T^X_0,^*≤  N^3 log N ) + 
        	( T^X_0,^* > N^3 log N ) 
        	
           ≤( sup_t≤  N^3 log N X_t^T^X_0,^*≥^* ) 
        	+ ( T^X_0 >  N^3 log N  )   ,
    
    whereT^X_0is the first time the random walkXreaches0, andX^T_0,^*^Xdenotes the processXstopped upon reaching0or[^* , ∞ ). We bound the two  terms above separately. 
    
    For the rightmost term, it is easy to check thatM(t) = X_t + η t/Nis a martingale up to timeT_0^X. If we thus defineM_0(t) = M(t∧ T_0^X), then(M_0(t))_t≥ 0is a martingale for all times, with increments bounded by1. It therefore follows from Azuma's inequality that fort≥ 2N/η, 
    	
        ( T_0^X > t )     =  ( T_0^X > t , X_t ≥ 1/N) 
        	= ( T_0^X >t , X_t - X_0 ≥ -1+2/N) 
            
        	= ( T_0^X > t , M(t)-M(0) ≥η t+2/N -1 ) 
        	≤( M_0(t) - M_0(0) > η t/N -1 ) 
           ≤exp( -  ( η t/N -1 )^2/8t) ≤exp( - η^2 t/32 N^2) ,
     
    which can be made smaller thane^-2Nby choosingt ≥ N^3log N.  
    
    
    For the remaining term, 
    again by Azuma we have
    	
        ( sup_t≤ N^3 log N X_t^T^X_0,^*≥^* ) ≤( sup_t≤ N^3 log N  M (t ∧T^X_0,^* )  
        	≥^* ) ≤exp( -  (^* )^2/8 N^3 log N ) 
        	≤ e^-2N
    
    forNlarge enough. In all, we have found that 
    	
        q  = ( X_T_0,^*^X≥^* )  
        	≤ e^-2N + e^-2N≤ e^-N
    
    forNlarge enough. 
    This concludes the proof of Lemma <ref>. 
    
    
    § PROOF OF LEMMA <REF>
    
    We have, for anył >0, 
    	
        ( ∑_i=1^ t T^X,(i)_^*≤ t )  ≤( exp( - ł∑_i=1^ t T^X,(i)_^*) ≥ e^-ł t)  
        	≤ e^ł t[ ( e^-ł T_^*^X) ]^ t .
    
    To bound the right hand side above, recall thatT_^*^X ≥ N_0 NforN_0 ∼Geometric(p), withp ≤ e^-N. Thus if we letN̂_0 be a Geometric random variable of parameterp̂ := e^-N, then we find 
    	
        ( e^-ł T_^*^X)     = 
        	∫_0^∞( e^-ł T_^*^X≥ t )  t 
        	= ∫_0^1 ( T_^*^X ≤ -log t/ł)  t 
        	
           ≤∫_0^1 ( N̂_0 ≤ -log t/ł N )  t 
        	≤∫_0^1 ( 1 - (1-p̂ )^-log t /ł N )  t 
        	
           ≤  1- ∫_0^1  exp( 2log t /ł N e^N)  t 
        	= 1- ł N e^N /ł N e^N +2  ,
    
    where for the last inequality we have used thatlog (1-x) ≥ -2x forx∈ (0,1/2). 
    Thus 
    	
        ( ∑_i=1^ t T^X,(i)_^*≤ t )    ≤ 
        	e^ł t ( 1- ł N e^N /ł N e^N +2 )^ t
            =  exp{ł t +  t log( 1- ł N e^N /ł N e^N +2 )  }
            = exp{ -ł t ( -1 +  N e^N/ł N e^N +2) }
    
    sincelog (1-x) ≤ -x. 
    Takingł = 1/N e^Nand recalling that = 6/N e^N, it is then easy to check that  
    	
        exp{ -ł t ( -1 +  N e^N/ł N e^N +2) }≤exp (-ł t) =
        	 exp( - t/ N e^N) ,
    
    which concludes the proof.
    
    
    
    
    
    § LOGARITHMIC FLUCTUATIONS FOR IDLA AT LARGE TIMES
    
    
    
    We survey the proof of the logarithmic fluctuations bound by Jerison, Levine and Sheffield for IDLA on the cylinder graph_N ×, and extend it to larger times to prove Theorem <ref>. 
    
    
    
     §.§ A priori bound
    
    We obtain an a priori bound on the height ofA(T)following the outer bound argument by Lawler, Bramson and Griffeath <cit.>, for arbitrary starting configurations.  
    
    Let (A(t))_t≥ 0 denote an IDLA process on _N ×, and let h_0 = h(A(0)) denote its initial height. Then for any m≥ 3 there exists =̱(̱m) ∈ (0,1) such that, for T≫ N log N and N large enough, it holds 
    	
        ( A(T) ⊈ R_h_0 + mT/N) ≤^̱T/N .
    
    Thus if, in particular, the process starts from the flat configuration A(0)=A_0, then h(A(T)) ≤ mT/N with high probability for N large enough. 
    
    Let Z_k (t) := | A(t) ∩{ y=k} | denote the number of particles in A(t) at level k, and set μ_k(t) :=  (Z_k(t)). Then 
    	
        ( A(T) ⊈ R_h_0 + mT/N)
        	 ≤( Z_h_0 +mT/N+1(T) ≥ 1 ) 
        	≤μ_h_0 + mT/N+1 (T) .
    
    We claim that 
    	
        μ_k(t) ≤( 1/N)^k-h_0-1t^k-h_0/(k-h_0)!
    
    for all k>h_0 and t≥ 0. 
    Indeed, clearly μ_1(t) ≤ N and μ_k(0) =0  for all k>h_0. For other values of k,j  we have 
    	
        μ_k(t+1) - μ_k(t)     =  ( Z_k (t+1)  - Z_k (t) ) 
        	=  ( Y_t+1∈ A(t)^c ∩{ y=k} ) 
        	
           ≤1/N ( | A(t) ∩{ y=k-1} | ) 
        	= 1/Nμ_k-1 (t) ,
    
    where in the above inequality we have used that the probability that the (t+1)^th walker reaches level k-1 inside A(t) is maximised when A(t) is completely filled up to level k-2. Thus for k>h_0
        μ_k ( t) = ∑_s=0^t-1 ( μ_k(s+1) - μ_k(s) ) ≤1/N∑_s=0^t-1μ_k-1(s) ,
    
    and (<ref>) follows by a simple iteration. 
    Now take t=T, k =h_0 +mT/N+1 and recall that k! ≥ k^k e^-k to get 
    	
        μ_h_0 +mT/N+1 (T) 
        	≤( 1/N)^mT/NT^mT/N+1/(mT/N +1)!≤ N [ ( e/m)^m ]^T/N≤^̱T/N
     
    for any ∈̱((e/m)^m , 1) and N large enough. 
    
    By the above result with h_0=0, it suffices to prove Theorem <ref> for large T. Suppose, indeed, that 
    
    there exists a finite constant b such that T ≤ b N log N. Since T/N≤ b log N, it suffices to take a > b to have that the inner bound is trivially satisfied. For the outer bound we set c= a+b/3 and note that, as long as a ≥ 2b, it holds 
    	
        ( { R_T/N -alog N⊆ A(T) ⊆ R_T/N + a log N }^c
        	)     = (  A(T) ⊈ R_(a+b) log N )
        	
           ≤(  A(cNlog N ) ⊈ R_3c log N )  
        	
           ≤β ^c log N  = N^-c log1/,
    
    which can be made smaller than N^- by taking a ≥max{ 2b ; 3/log 1/ -b }. In light of this observation, from now on we can assume that T≫ N log N as N→∞. 
    
     The proof of Theorem <ref> follows an iterative argument, which we now sketch. 
    
    A point (x,y) with y≥ 0 is said to be: 
    
      * m-early if (x,y) ∈ A((y-m)N), 
     
      * ℓ-late if (x,y) ∉ A((y+ℓ ) N).  
     
    Fort≤ T, let 
    	
        _m [t] := ⋃_(x,y) ∈ A(t) { (x,y)  m} , 
        	    _ℓ [t] := ⋃_(x,y) ∈ R_t/N{ (x,y) ℓ} .
    
    Clearly, 
    	
        { R_T/N -alog N⊆ A(T) ⊆ R_T/N + a log N }^c 
        	⊆_alog N  [T] ∪_alog N  [T] ,
    
    so we bound the probability of the right hand side. Note that the a priori bound in the previous section (cf. Lemma <ref>) withm=3tells us that there exists an absolute constantβ∈ (0,1)such that 
    
    	
        ( _2T/N[T] ) ≤^̱T/N≪^̱log N
    
    forNlarge enough.  We use this to initialise the iteration, which consists of showing that, in turn, 
    
      *  no m-early point implies no ℓ-late point (ℓ≪ m), and 
    
      *  no ℓ-late point implies no m'-early point (m' ≍ℓ). 
    
    To perform the above steps, we will use an explicit discrete harmonic function with a pole close to the early/late point to build a martingale, which will be then controlled via its quadratic variation. 
    
    
    
    
    
    
    
    
     §.§ No early points implies no late points
    
    The main goal of this section is to prove the following. 
    
    For any >0 there exists a finite constant C=C(), depending only on ,  such that, if ℓ≥ C log N and m ≤ℓ^2 / Clog N, then 
    	
        ( _ℓ [T] ∩_m [T]^c ) ≤ N^-( +1)
    
    for N large enough. 
    
    The above result tells us that on the event that there is nom-early point, there is noℓ-late point with high probability, withℓ = ⌈√(Cmlog N)⌉≪ m . 
    
    
    To prove this, we argue as follows. For∈_N ×, letL( ) = {ℓ}. Then, since  
    	
        _ℓ [T] = ⋃_∈ R_T/N-ℓ L(  ) ,
    
    we have 
    	
        ( _ℓ [T] ∩_m [T]^c ) ≤∑_∈ R_T/N-ℓ ( L( ) ∩_m [T]^c ) .
    
    It therefore suffices to show that 
    	
        ( L( ) ∩_m [T]^c ) ≤ N^-( +4 )
     
    for arbitrary∈ R_T/N-ℓ. 
    To see this, we use a discrete harmonic function to build a martingale with pole at. We then show that on the eventL( )this martingale is large and negative, while on the event_m[T]^c its quadratic variation is small. This will then imply that the probability that bothL( ) and_m[T]^chold is small. 
    
    Recall that(A(t))_t≥ 0denotes the IDLA process.  For = (_x , _y ) andz ∈_N ×_+define
    	
        H_ (z) := _z (_y ) ,
    
    where SRW stands for simple random walk on_N ×. 
    ThenH_ (z) ∈ [0,1]for allzandH_ (z) → 1/Nasz_y → -∞. Moreover,H_is discrete harmonic up to level_y (in fact, it is the discrete harmonic extension of the function1 (x=_x )at level_yto the region{ (x,y) : y≤_y }). 
    
    We embed the driving random walks in continuous time by mean of time-changed Brownian motions on the lattice (see <cit.> for a precise definition), that we denote by{ (B_n(t))_t∈ [0,1] , n≥ 1}, so thatB_n(0)andB_n(1)are the starting and settling location of then^thrandom walk respectively. This turns out to be technically convenient, since it makes our discrete time martingales into continuous time ones. Finally, 
    for realt∈ [0,∞ )we define
    	
        M_ (t) := ∑_n=1^⌊ t ⌋( H_ ( B_n(1) ) - 1/N) 
        	+ ( H_ (B_⌊ t ⌋ ( t- ⌊ t ⌋ ) ) - 1/N) .
    
    Note that the first sum represents the contribution of the settled walkers, while the last term gives the contribution of the active one at timet. Since the functionH_is discrete harmonic up to level_y,M_above is a continuous-time martingale up to the first time the cluster reaches level_y . 
    
    We split it into a continuous part and a jump part, namely we setM_ (t) = M^1_  (t) + M^2_ (t) with 
    	
        M^1_  (t) = ∑_n=1^⌊ t ⌋ -1 ( H_ (B_n(1)) - H_ (B_n(0)) ) 
        	+  H_ (B_⌊ t ⌋ ( t- ⌊ t ⌋ ) ) - B_⌊ t ⌋(0) ,
    
    and 
    	
        M^2_ (t) = ∑_n=1^⌊ t ⌋( H_ (B_n(0)) - 1/N) .
    
    LetS_,S_^1 andS_^2denote the quadratic variation ofM_,M_^1andM_^2respectively. SinceM_^1is a continuous martingale starting from0, it is  a time-changed Brownian Motion, that is 
    	
        M_^1 (t) = B (S_^1 (t))
    
    forBone-dimensional Brownian motion. Moreover, sinceM_^2is piecewise constant and by independence of the starting locations, we have 
    	
        S_^2 (t) = ∑_n=1^⌊ t ⌋[ ( H_ (B_n(0)) - 1/N)^2] .
    
    Recall that we want to bound the quadratic variation ofM_on the event that no point ism-early, which means that the cluster has a controlled height. 
    The next lemma shows how a control on the shape of the cluster can be translated into a control of the quadratic variation of the martingale. 
    
    
    Assume that m≫ 1 and that _y ≥t/N + 2m +1. Then 
    	
        ( e^S_ (t) 1__m+1 [t]^c ) ≤ e^2 t^800 .
    
    We have S_ (t) ≤ 2( S_^1(t) + S_^2(t)), from which 
    	
        (e^S_ (t) 1__m+1 [t]^c  ) 
        	≤ (e^2(S_^1 (t) + S_^2(t) ) 1__m+1 [t]^c  )  ) 
        	≤[  (e^4S_^1 (t) 1__m+1 [t]^c  ) 
        	 (e^4S_^2 (t) 1__m+1 [t]^c ) ]^1/2.
    
    Let us  estimate the two factors separately. 
    As a technical trick, we will assume that the driving random walks are released from a uniformly chosen location at level - N^2, so that 
    	
        | H_ (B_n(0)) - 1/N| ≤1/N log N .
     
    This clearly does not change the law of the process, and it has the technical advantage of transferring some amount of the quadratic variation of M_ from S_^2 to S_^1. 
     We have: 
     	
        (e^4S_^2 (t) 1__m+1 [t]^c )    ≤( exp{ 4∑_n=1^⌊ t ⌋( H_(B_n(0)) - 1/N)^2 }) 
         	
           ≤( exp{4 ⌊ t ⌋/(N log N)^2}) 
         	≤ e^4 .
      
    Note that the above bound does not depend on m, but only on the assumption (<ref>). 
    It remains to show that 
    	
        (e^4S_^1 (t) 1__m+1 [t]^c  )  ≤ t^1600 .
    
    To this end, we use that on the event _m+1 [t]^c the height on the cluster is controlled, which in turn implies that the quadratic variation of the continuous martingale part cannot be too large. Let us take t to be integer to simplify the writing. Then we find 
    	
        (e^4S_^1 (t) 1__m+1 [t]^c  )  
        	≤( exp{ 4∑_n=1^t ( S_^1 (n) - S_^1 (n-1) ) 1__m+1[t]^c}) .
    
    We claim that on the event _m+1[t]^c the martingale increments are bounded, that is 
    	
        M_^1(s) - M_^1(⌊ s ⌋ ) ∈ [-a , b_n ]
    
    for all s ∈ [n,n+1) and some (non-random) a,b_n. Indeed, 
    	
        M_^1(s) - M_^1(⌊ s ⌋ )  =
        	H_ ( B_⌊ s ⌋ ( s - ⌊ s ⌋ ) ) - 
        	H_ (B_⌊ s ⌋ (0)) 
        	≥ - H_ (B_⌊ s ⌋ (0))  ≥ - 2/N =: -a .
    
    Moreover, on the event _m+1 [t]^c we have that for all n≤ t the cluster A(n) is contained in R_n/N + m+1, from which 
    	
        M_^1(s) - M_^1(⌊ s ⌋ )     =
        	H_ ( B_⌊ s ⌋ ( s - ⌊ s ⌋ ) ) - 
        	H_ (B_⌊ s ⌋ (0))  
           ≤max_ z : z_y ≤n/N +m+1 ( H_ (z) - H_ ( B_n(0)) ) 
           ≤10/_y - n/N -m-1  =: b_n ,
    
    where the last inequality follows from the explicit computation of H_(z) for large N, and it holds as long as m≫ 1 (see <cit.> for details). By a standard argument on Brownian motion,  
    
    this implies that 
    
        S_^1(n) - S_^1(n-1) ∈_n (-a , b_n) ,
    
    where _n(a,b) denotes the exit time from the interval (-a , b) for a one-dimensional Brownian motion starting from 0. We thus have that 
    	
        log( exp{ 4∑_n=1^t ( S_^1 (n) - S_^1 (n-1) ) 1__m+1[t]^c})    ≤log( exp{ 4∑_n=1^t _n(-a , b_n) })
        	
           ≤∑_n=1^t log( e^4_n (-a , b_n)) .
     
    It is easy to check (cf. <cit.>, Lemma 5) that (e^ł (-a , b ) ) ≤ 1+ 10ł a b provided √(ł) (a+b) ≤ 3. For our choice of parameters ł =4 and 
    	
        a+b_n =  2/N + 10/_y - n/N -m-1 ≤2/N + 10/t-n/N + m ≤ 1
    
    for N large enough, since m≫ 1. Thus 
    	
        ∑_n=1^t log( e^4_n (-a , b_n)) 
        	   ≤∑_n=1^t log ( 1+ 40a b_n ) 
        	≤ 40 a ∑_n=1^t b_n 
        	 ≤  400 a ∑_n=1^t 1/t-n/N +1
           ≤800/N( 1 + ∫_1^t dx/x/N) 
        	= 800/N ( 1 + N log t ) ≤ 1600 log t ,
    
    which concludes the proof.
    
    
    
    We can now show that no early points implies no late points. 
    
    Take m= ⌊ℓ^2/Clog N ⌋ without loss of generality, with C as in the statement, and note that m≥ℓ since ℓ≥ Clog N by assumption. Let =(_x , _y ) be such that _y ≤T/N-ℓ, and set T_1 = N(_y + ℓ ). Note that T_1 ≤ T. Recall that L( ) denotes the event that  is ℓ-late, that is ∉ A(T_1). 
    As already observed, it will suffice to show that 
    	
        ( L( ) ∩_m [T]^c ) ≤ N^-( +4 )
     
    for arbitrary ∈ R_T/N-ℓ. On the event L( ) we use the martingale M_ with pole at . We will show that both M_ (T_1) is large and negative, and S_ (T_1) is small, so that the probability of both happening simultaneously is tiny. 
    
    Let A_ (t) denote the IDLA cluster at time t with points stopped upon reaching level _y, counted with multiplicity. We have 
    	
        M_ (T_1) = ∑_A_ (T_1) ( H_ (z) - 1/N) .
    
    On the event L( ), no particle reaches  by time T_1. Moreover, H_ (z) =0 for all z ≠ at level _y, while H_ (z)>0 if z_y < _y. It follows that the sum defining M_ (T_1) is maximised when as many particles as possible are below level _y, that is when the cluster is completely filled up to level _y -1. Hence 
    	
        M_ (T_1)    ≤∑_z ∈ R__y -1( H_ (z) - 1/N) _0 
        	+ ∑_z ∈ A_(T_1) ,   z_y = _y ( H_ (z) - 1/N) 
        	
            = -1/N♯{_y }_T_1 - N(_y -1 ) = N(ℓ +1 ) ≤ -ℓ .
    
    To show that, on the other hand, the quadratic variation is small, we use the following lemma. 
    
    Assume that m≫ 1 and ℓ≤ m. Fix any , and let t = N(_y + ℓ ). Then 
    	
        ( e^S_ (t) 1__m[t]^c ) ≤ e^200m t^800 .
    
    Using the above with t=T_1 and since T_1 ≤ e^m we gather that
    	
        ( e^S_ (T_1) 1__m[T_1]^c ) ≤ e^200m T_1^800≤ e^1000m .
    
    In conclusion, for any s>0 we have 
    	
        (L( ) ∩_m[T]^c ) ≤ ( _m[T]^c ∩{ S_ (T_1) > s } ) + 
        	 ( { S_ (T_1) ≤  s }∩ L( )  ) ,
    
    with 
    	
        ( _m[T]^c ∩{ S_ (T_1) > s } ) 
        	≤ (S_ (T_1) 1__m[T_1]^c > s ) 
        	≤ ( e^S_ (T_1) 1__m[T_1]^c ) e^-s
        	≤ e^-1000m
    
    taking s=2000m, and 
    	
        ( { S_ (T_1) ≤  s }∩ L( )  ) 
        	≤ (  S_ (T_1) ≤  s ,   M_ (T_1) ≤ - ℓ   ) ≤ e^-ℓ^2 / 2s
    
    by a standard large deviations estimate for Brownian motion. In all, 
    	
        ( L( ) ∩_m[T]^c ) ≤ 
        	e^-1000m  + e^- ℓ^2 / 4000m≤ 2 N^-(+5) ,
    
    as long as m≥ℓ≥ ( +5 ) log N and ℓ^2/4000m≥ ( +5 ) log N. This shows that Proposition <ref> holds with C ≥ 4000 ( +5 ). 
    
    In order to conclude, it remains to prove the above lemma. 
    
    As in the proof of Lemma <ref>, we have 
    	
        (e^S_ (t) 1__m [t]^c  ) 
        	≤ (e^2(S_^1 (t) + S_^2(t) ) 1__m [t]^c  )  ) 
        	≤[  (e^4S_^1 (t) 1__m [t]^c  ) 
        	 (e^4S_^2 (t) 1__m [t]^c ) ]^1/2.
    
    The factor involving S_^2 is bounded above by an absolute constant, so it suffices to show that, say, 
    	
        (e^4S_^1 (t) 1__m+1 [t]^c  ) 
        	≤ e^320m t^1600 .
    
    	Note that _y = t/N -ℓ, so we cannot use Lemma <ref>, which requires _y ≥t/N + 2m+1. On the other hand, note that if t_0 ≤ t then _m[t]^c ⊆_m[t_0]^c. Moreover, for t_0 such that _y ≥t_0/N + 2m+1 we can apply Lemma <ref>. Take therefore t_0 = N(_y -2m-1 ) ∨ 0. Then 
    		
        (e^4S_^1 (t) 1__m+1 [t]^c  )    ≤[  (e^8 ( S_^1 (t) - S_^1(t_0))  1__m+1 [t]^c  ) 
        				 (e^8S_^1 (t_0) 1__m+1 [t]^c  ) _≤ t^3200]^1/2
           ≤[ ( exp{ 8∑_n=t_0+1^t ( S_^1(n) - S_^1(n-1)) 1__m[t_0]^c }) ]^1/2  t^1600
           ≤[ ( e^8  ( -2/N , 1 ) )_≤ 1 + 160/N≤ e^160/N]^t-t_0/2 t^1600≤ e^80/N(t-t_0)  t^1600 .
    
    Now, if t_0=0 then _y ≤ 2m +1, so t/N = _y + ℓ≤ 2m +1+ℓ≤ 4m. Otherwise, t-t_0/N = ℓ + 2m + 2 ≤ 4m. In all, 
    	
        (e^4S_^1 (t) 1__m+1 [t]^c  ) 
        	≤ e^320m t^1600,
    
    as wanted. 
     
    This concludes the proof of Proposition <ref>. 
    
    
     §.§ No late points implies no early points
     
    We prove the following. 
     
    Assume m,ℓ≤√(3C N log N ), with C as in Proposition <ref>. Then 
    for any >0, there exist a finite constant C'=C'(), depending only on ,  and an absolute constant b>0 such that, if m ≥ C' log N and ℓ≤bm/48π, it holds 
    	
        ( _m [T] ∩_ℓ [T]^c ) ≤ N^-( +1)
    
    for N large enough. 
    
    We assume ℓ = bm/48π without loss of generality, with b to be determined. 
    Let 
    	
        Q_z,t  := { z mt} .
    
    Then 
    	
        ( _m [T] ∩_ℓ [T]^c )  = ∑_t=1^T∑_z∈ R_T ( Q_z,t∩_ℓ [T]^c ) .
    
    On the event Q_z,t take = (_x , _y ) such that _y = z_x and _y = z_y + m+1 = t/N + 2m +1. Then for any s>0
        ( Q_z,t∩_ℓ [T]^c )  ≤    ( Q_z,t∩{ S_ (t) > s } ) + 
           ( Q_z,t∩{ M_ (t) < b/1000 m }∩_ℓ [T]^c ) + 
           ( { S_ (t) > s }∩{ M_ (t) ≥b/1000 m })  .
    
    Taking s = (2 + 1000 ) log N, we find 
    	
        ( { S_ (t) > s }∩{ M_ (t) ≥b/1000 m }) 
        	≤ e^-s/2≤ N^- ( +500 ) ,
    
    and, using that Q_z,t⊆_m+1[t]^c, 
    	
        ( Q_z,t∩{ S_ (t) > s } )    ≤ ( _m+1[t]^c ∩{ S_ (t) > s } )  
        	=  ( S_ (t) 1__m+1[t]^c > s ) 
        	
           ≤ ( e^S_ (t) 1__m+1[t]^c ) e^-s≤ e^8 t^800  e^-s ≤ N^-(2 + 100) .
    
    To finish, we show that 
    	
        ( Q_z,t∩{ M_ (t) < b/1000 m }∩_ℓ [T]^c ) ≤ N^-( +5 ) .
    
    Note that on the event Q_z,t we have A(t) ⊆ R_t/N + m+1. Let B_r(z) denote the Euclidean ball of radius r around z. Partition A(t) as follows: 
    	
        A(t) = (  A(t) ∩ R_t/N -ℓ_A_1) ∪(  A(t) ∩ B_m(z) _A_2) ∪( A(t) ∖ ( A_1 ∪ A_2 ) _A_3) .
    
    Then 
    	
        M_ (t) = ∑_z∈ A_1 ( H_ (z) -1/N) + 
        	∑_z∈ A_2 ( H_ (z) -1/N) + 
        	∑_z∈ A_3 ( H_ (z) -1/N) .
    
    Since A_1 = R_t/N - ℓ on the event _ℓ [T]^c, 
    	
        ∑_z∈ A_1 ( H_ (z) -1/N) =0 .
    
    Moreover, 
    	
        ∑_z∈ A_3 ( H_ (z) -1/N) ≥ -|A_3|/N = 
        	- t-(t-ℓ N ) - |A_2|/N≥ - ℓ .
    
    It remains to estimate the contribution to the martingale of points in A_2, which we show to be large. To this end, observe that if i≤ m and m≤ k ≤ 2m+1, then (with m≫ 1) 
    	
        _0 ( k(i,k) ) 
        	   ≥1/4πlog( 1+4k/i^2 + (k-1)^2) + ( 
        	1/N^2) 
           ≥1/2πk/i^2 + (k-1)^2 ≥1/12π m  .
    
    This implies that H_ (z) ≥1/12π m  for z∈ A_2. Moreover, the next lemma shows that A_2 contains a positive proportion of points, and it identifies the absolute constant b in Proposition <ref>. 
     [Thin tentacles, cf. <cit.> Lemma 2]
    Assume m≪ N. Then there exist absolute constants b, C_0 , c_0 such that for all z with z_y ≥ m it holds 
    	
        ( z ∈ A(t) ,   |A(t) ∩ B_m(z)| ≤ bm^2 ) ≤ C_0 e^-c_0 m ,
    
    for all t. 
    
    This can be proven exactly as in the ^2 case treated in <cit.>, as the argument is completely local and m ≪ N. 
    
    This allows us to conclude that, on the event Q_z,t∩_ℓ [T]^c ∩{ |A(t) ∩ B_m(z)| ≤ bm^2 },  it holds 
    	
        M_ (t) ≥∑_z∈ A_2 ( H_ (z) - 1/N) - ℓ≥( 1/12π m - 1/N) |A_2| - ℓ≥bm/12π - bm^2/N - ℓ≥bm/48π   ,
    
    where the last inequality follows by recalling that ℓ = b m/48π and that, by assumption, m^2 ≤ 3C Nlog N and m≥ C'log N, from which 
    	
        bm^2/N≤ 3bC log N  ≤bm/24π
    
    as long as 3C ≤ C' / 24π, which can always be ensured by taking C' large enough, depending only on C. 
    
    In all, we conclude that 
    	
        ( Q_z,t∩{ M_ (t) <    b/1000  m }∩_ℓ [T]^c )    = 
            = 
        	( Q_z,t∩{ M_ (t) < b/1000  m }∩_ℓ [T]^c 
        	∩{ |A(t) ∩ B_m(z)| ≤ bm^2 }) 
           ≤ ( z∈ A(t) , { |A(t) ∩ B_m(z)| ≤ bm^2 } ) 
           ≤ C_0 e^-c_0 m ≤ N^-( +5 ) ,
    
    where the last inequality holds as long as m ≥2/c_0 ( +5 ) log N, which can always be ensured at cost of increasing C', only depending on . This concludes the proof of Proposition <ref>. 
    
    
     §.§ Iterative scheme
    
    To finally prove Theorem <ref> we iteratively apply Propositions <ref> and <ref>, starting withm=2T/N ≫log N and iterating as long asm,ℓ≥ a_log N, witha_ =max{ C ,  C' }. 
    Assume thatT≫ N log N, otherwise the result holds by Remark <ref>. 
    We have from Lemma <ref> withm=3that 
    	
        (A(T) ⊈ R_3T/N ) ≤ (A(N^2 log^2 N ) ⊈ R_3T/N )
        	≤^̱N≤ N^ +1 ,
    
    where, for all fixed >0,  the last inequality holds forNlarge enough. 
    Letm_0 = 3N log^2 N . ForC,C'as in Proposition <ref> and <ref> respectively, iteratively define 
    	
        ℓ_k = √( C m_k-1log N ) , 
        
        	m_k = 48 π/bℓ_k , 
        	   k≥ 1.
    
    Then, as long asm_k , ℓ_k ≥ a_log N, we have 
    	
        ( _m_k-1 [T]^c ∩_ℓ_k [T]^c ) ≤ N^-( +1)  , 
            (  _ℓ_k [T]^c ∩_m_k [T]  ) ≤ N^-( +1)
    
    by Proposition <ref> and <ref> respectively. 
    Thus 
    	
        ( _m_0 [T] ) ≤ N^-(+1) , 
            ( _ℓ_1 [T] ) ≤ ( _ℓ_1 [T] ∩_m_0[T]^c ) 
        	 +  ( _m_0 [T] ) ≤ 2N^-(+1) , 
            ( __1 [T] ) ≤ ( _m_1 [T] ∩_ℓ_1[T]^c ) 
        	 +  ( _ℓ_1 [T] ) ≤ 3N^-(+1) , 
             ⋮
            ( _ℓ_k[T]) ≤ 2k N^-(+1) , 
            ( _m_k[T]) ≤ (2k+1)N^-( +1) .
    
    We want to iterate as much as possible, that is to takekas large as possible so thatℓ_k , m_k ≥ a_log N. 
    
    
    
    
    
    It is easy to check that ifk > c_0 loglog N, for a suitable absolute constantc_0, thenℓ_k < a_log N, so we can iterate at mostc_0 loglog Ntimes. In all, this shows that by takingℓ  = max{ℓ_c_0 loglog N ; a_log N }andm = max{ m_c_0 loglog N ; a_log N }we have 
    	
        ( _m[T] ∪_ℓ [T] ) ≤ ( _m[T] ) +  ( _ℓ [T] ) 
        	≤ 5 c_0  N^-(+1)loglog N ≤ N^- ,
    
    forNlarge enough, as wanted. 
    
    
    
    
    
    
     plain
