This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Active Phase for the Stochastic Sandpile on \mathbb{Z}

Christopher Hoffman and Yiping Hu and Jacob Richey and Douglas Rizzolo
Abstract.

We prove that the critical value of the one-dimensional Stochastic Sandpile Model is less than one. This verifies a conjecture of Rolla and Sidoravicius [16].

Key words and phrases:
stochastic sandpile, Abelian property, self-organized criticality
We would like to thank Lionel Levine for helpful conversations. CH and YH thank the NSF for their support through grant DMS-1954059. DR thanks the NSF for their support through grant DMS-1855568.

1. Introduction

Sandpile models have a long history in the statistical mechanics literature as paradigms of self-organized criticality [2, 12, 6]. Of particular importance is the Stochastic Sandpile Model (SSM). This abelian variant of Manna’s model [12] is widely believed to exhibit universality [5]. Since the SSM gained popularity in the mathematics community the prime challenge has been to prove that the critical density for the one-dimensional Stochastic Sandpile Model is less than one [16]. In this paper we prove this conjecture.

The SSM is an interacting particle system on \operatorname{\mathbb{Z}} defined as follows. At each time, the state of the system is given by a function ηt:{0,1,2,}\eta_{t}:\operatorname{\mathbb{Z}}\to\{0,1,2,\dots\}, where ηt(x)\eta_{t}(x) represents the number of particles at site xx at time tt. Sites xx such that ηt(x)1\eta_{t}(x)\leqslant 1 are considered stable while sites with ηt(x)2\eta_{t}(x)\geqslant 2 are unstable. Unstable sites topple independently at exponential rate 11 and when an unstable site topples two particles from the site independently move to neighboring sites.

Criticality of the SSM is defined with respect to whether or not the system remains active. We say the stochastic sandpile locally fixates if for each xx the function tηt(x)t\mapsto\eta_{t}(x) is eventually constant and stays active otherwise. The main result of [16] about the SSM is that if the initial distribution ν\nu is given by i.i.d.​ Poisson random variables with parameter μ\mu, then there exists a critical value μc[1/4,1]\mu_{c}\in[1/4,1] such that the system locally fixates almost surely if μ<μc\mu<\mu_{c} and stays active almost surely in μ>μc\mu>\mu_{c}, see [16, Theorem 1]. The argument that μc1\mu_{c}\leqslant 1 is essentially trivial and comes down to showing that for trivial reasons if μ>1\mu>1 then the site 0 topples infinitely many times, while the argument that μc1/4\mu_{c}\geqslant 1/4 is subtle. Since [16] improvements have been made on the lower bound, see [14], but the problem posed in [16, Section 7] of finding a non-trivial upper bound has remained open. Our main result is the following theorem, which gives the first non-trivial upper bound on μc\mu_{c}.

Theorem 1.1.

For any independent starting configuration with multiple particles at some sites a.s., the critical value μc\mu_{c} for the SSM is strictly less than 11. In fact, μc1e2×105\mu_{c}\leqslant 1-e^{-2\times 10^{5}}.

In this paper we consider an infinite version of the SSM but there are also finite versions (e.g. driven dissipative and fixed energy [13, 7]). Universality would imply that all the critical values and exponents should be the same across these models. Some sandpile models with deterministic toppling rules have been shown to not exhibit universality [8], while there is numerical evidence for universality in the SSM [5]. Our result should transfer to finite versions of this model [4].

The methods used in this paper are based on those recently developed to study Activated Random Walk (ARW). ARW is a related abelian network that is also believed to exhibit self-organized criticality and universality [10, 16]. See [15] for a nice survey on ARW. While there are many similarities between the SSM and activated random walk, since [16] activated random walk was introduced as it was believed to be a more tractable model to study [10, 3]. For example, the analogue of Theorem 1.1 was established in [9] and, indeed, has recently been extended to higher dimensions [11, 1]. There is also evidence that ARW exhibits universality [17]. Our approach in this paper is similar to the one taken in [9]. However the analysis is much more delicate for the SSM than what was required in previous papers on ARW. The added difficulties arise because in ARW particles move or sleep independently, while in the SSM the particle moves are correlated in pairs. This correlation makes the SSM much more difficult to rigorously analyze.

An essential component of this analysis is to use a half-toppling scheme, defined in Section 2. Half-topplings allow us to follow similar (albeit significantly more complicated) approaches to those that have been used to study ARW. Half-toppling schemes have also been used in the previous lower bound on the critical density for the SSM [16] and the recent improvement that proves μc1/2\mu_{c}\geqslant 1/2 [14]. In the next section we introduce some notation, detail the half-toppling scheme and then outline the rest of the paper.

2. Setup and outline

2.1. Sandpile dynamics

We start by defining the ‘site-wise’ representation for SSM. We identify configurations of particles as functions η:\eta:\operatorname{\mathbb{Z}}\to\operatorname{\mathbb{N}}, i.e. η(x)\eta(x) counts the number of particles at site xx. To run the dynamics on a finite interval II\subset\operatorname{\mathbb{Z}}, every site xIx\in I is assigned an infinite sequence of iid instructions, (ξjx:j)(\xi^{x}_{j}:j\in\operatorname{\mathbb{N}}) each taking one of the two possible values ξ,x\xi_{-,x} or ξ+,x\xi_{+,x} with equal probability, where ξ,x\xi_{-,x} and ξ+,x\xi_{+,x} are operators on the space of particle configurations that act via

ξ,x(η)(y)={η(y),y{x,x1}η(y)±1,y=x1212\xi_{-,x}(\eta)(y)=\begin{cases}\eta(y),&y\notin\{x,x-1\}\\ \eta(y)\pm 1,&y=x-\frac{1}{2}\mp\frac{1}{2}\end{cases}

and

ξ+,x(η)(y)={η(y),y{x,x+1}η(y)±1,y=x+12±12.\xi_{+,x}(\eta)(y)=\begin{cases}\eta(y),&y\notin\{x,x+1\}\\ \eta(y)\pm 1,&y=x+\frac{1}{2}\pm\frac{1}{2}.\end{cases}

In the usual discrete-time setup, the system evolves one step by choosing a site xIx\in I with η(x)2\eta(x)\geqslant 2, and applying the two stack instructions ξjx,ξj+1x\xi^{x}_{j},\xi^{x}_{j+1} where jj is such that all instructions ξjx\xi^{x}_{j^{\prime}} for j<jj^{\prime}<j have already been used, but ξjx\xi^{x}_{j} has not. In this version, particles always topple in pairs. For an initial particle configuration η\eta and a sequence of sites α=(α1,α2,,αk),αiI\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{k}),\alpha_{i}\in I to be toppled, let

ξα=ξj2kαkξj2k1αkξj4α2ξj3α2ξj2α1ξj1α1\xi_{\alpha}=\xi_{j_{2k}}^{\alpha_{k}}\circ\xi_{j_{2k-1}}^{\alpha_{k}}\circ\cdots\circ\xi_{j_{4}}^{\alpha_{2}}\circ\xi_{j_{3}}^{\alpha_{2}}\circ\xi_{j_{2}}^{\alpha_{1}}\circ\xi_{j_{1}}^{\alpha_{1}}

be the operator obtained by performing all topplings of α\alpha in order. The odometer of the pair (η,α)(\eta,\alpha) is the function which records the total number of times each site was toppled, i.e.

mI(η,α,x):=#{j:αj=x}.m_{I}(\eta,\alpha,x):=\#\{j:\alpha_{j}=x\}.

Such a sequence α\alpha is called legal for η\eta if ξ(α1,,α1)η(α)2\xi_{(\alpha_{1},\ldots,\alpha_{\ell-1})}\eta(\alpha_{\ell})\geqslant 2 for every {1,,k}.\ell\in\{1,\ldots,k\}.

The odometer function mIm_{I} is universal in the sense that if α,α\alpha,\alpha^{\prime} are any two legal toppling sequences for a configuration η\eta on interval II such that ξαη\xi_{\alpha}\eta and ξαη\xi_{\alpha^{\prime}}\eta have no sites with at least two particles, then α\alpha is a permutation of α\alpha^{\prime} and thus mI(η,α,)=mI(η,α,)m_{I}(\eta,\alpha,\cdot)=m_{I}(\eta,\alpha^{\prime},\cdot). For our argument, it is only necessary that the half-toppling version of the dynamics gives a lower bound on this odometer; see Lemma 2.2.

We need the following result from [16] which relates the site-wise representation to the continuous-time process (ηt)t0(\eta_{t})_{t\geqslant 0} in Section 1. Define

m(η,x):=supI,αmI(η,α,x)m(\eta,x):=\sup_{I,\alpha}m_{I}(\eta,\alpha,x)

where the supremum is over all finite intervals II and all legal toppling sequences α\alpha for the configuration η\eta on II.

Lemma 2.1 ([16, Lemma 4]).

Suppose the initial state η0\eta_{0} is a translation-invariant, ergodic distribution on \operatorname{\mathbb{Z}} with finite density 𝐄(η0(0))\mbox{$\bf E$}(\eta_{0}(0)), then

((ηt)t0 stays active)=(m(η0,0)=){0,1}.\mathbb{P}\left((\eta_{t})_{t\geqslant 0}\text{ stays active}\right)=\mathbb{P}(m(\eta_{0},0)=\infty)\in\{0,1\}.

The above lemma says that in order to establish the system staying active a.s., it suffices to show that some site is toppled infinitely many times with positive probability.

2.2. Half-topplings

To allow more freedom in our toppling procedure (and retain some independence between particles), we work with an equivalent version of the dynamics. Instead of toppling two particles at a time, we topple single particles, i.e. perform  half-topplings. In the usual dynamics, the number of particles toppled at a given site is always even, so there are restrictions on which half-topplings are allowed. Namely, we must keep track of how many times each site has been half-toppled, and only allow another half-toppling if that number is odd, or if that site has at least two particles.

Thus, in the half-toppling scheme, a configuration of particles consists of two functions, η:\eta:\mathbb{Z}\to\mathbb{N}, the number of particles per site, and a parity sequence ω:{0,1}\omega:\mathbb{Z}\to\{0,1\}. A site xx is legal for a pair of configurations (η,ω)(\eta,\omega) if either η(x)2\eta(x)\geqslant 2 or η(x)=ω(x)=1\eta(x)=\omega(x)=1. At each step of the half-toppling scheme, a legal site xx is chosen for the current pair of configurations, and the first unused instruction ξjx\xi_{j}^{x} acts upon the pair by sending a single particle at xx to a uniform random neighbor and adding 1 (mod 2) to ω(x)\omega(x). A half-toppling sequence of sites α=(α1,α2,,αk)\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{k}) is legal for (η,ω)(\eta,\omega) if the chosen site is legal for every step, that is, α\alpha_{\ell} is legal for

ξj1α1ξj2α2ξj1α1(η,ω)\xi_{j_{\ell-1}}^{\alpha_{\ell-1}}\circ\cdots\circ\xi_{j_{2}}^{\alpha_{2}}\circ\xi_{j_{1}}^{\alpha_{1}}(\eta,\omega)

for every {1,,k}.\ell\in\{1,\ldots,k\}.

One key fact about this version of the dynamics is that it provides a lower bound on the total odometer. Recall the odometer function mIm_{I} for the classical dynamics, and for any sequence α\alpha of half-topplings, let mI(η,ω,α,x)m_{I}(\eta,\omega,\alpha,x) denote the corresponding half-toppling odometer function, after performing all half-topplings in α\alpha started from the configuration (η,ω)(\eta,\omega). We have:

Lemma 2.2.

(Abelian lemma for half-topplings) Fix a particle configuration η\eta on a finite interval II. Let α\alpha be any legal half-toppling sequence for (η,0)(\eta,\vec{0}), and let α¯\overline{\alpha} be any legal toppling sequence for η\eta (in the sense of Section 2.1) such that ξα¯η\xi_{\overline{\alpha}}\eta has no site with at least two particles. Then for any xIx\in I,

mI(η,0,α,x)2mI(η,α¯,x).m_{I}(\eta,\vec{0},\alpha,x)\leqslant 2m_{I}(\eta,\overline{\alpha},x).

We omit the proof, which follows identically to that of [16, Lemma 6].

2.3. Outline

Our strategy is to alternate between two types of legal half-toppling sequences, taking place on a sequence of nested intervals in \mathbb{Z}.

The first of these is called the ‘carpet/hole toppling procedure’ and is essentially a renormalization scheme of the SSM, detailed in Section 3. The procedure starts from and remains in a very particular set of configurations, and runs until it partially stabilizes the interval – when there are no more legal topplings among a small class of marked (‘free’) particles. We will show that each iteration is well behaved – that many particles reach the boundary – with exponentially high probability. The main technical hurdle in analyzing the carpet/hole procedure is the single block estimate Lemma 4.6, which we deal with in Sections 6, 7 and 8. In Section 4 we use the single block estimate to prove a version of the above statement, via an energy-entropy calculation similar to [9].

The carpet/hole procedure needs to start with relatively nice configurations. Thus when partial stabilization is achieved on an interval, before restarting the carpet/hole procedure on the larger interval, it is necessary to perform the other ‘bootstrap’ toppling procedure to restore the configuration. In Section 5 we analyze the alternation of both procedures and prove Theorem 1.1.

In the remaining sections, we focus on the carpet/hole dynamics inside a single block. In Section 6, to exploit the independence among random walks, we introduce an auxiliary process that only reveals partial information about the parity configuration. In Section 7, we turn to the intricate correlation between particles in our toppling procedure, by carefully controlling the typical number of zeros in the auxiliary process. Finally, in Section 8 we combine these results and prove Lemma 4.6.

3. Carpet/hole toppling procedure

The carpet/hole toppling procedure divides the space into blocks as well as long transit regions between blocks. Each particle is designated as one of two types: there are carpet particles which do not move and occupy all sites except for one location per block called the hole, and free particles which are toppled repeatedly and legally (thanks to the carpet particles). At some point, a free particle may turn into a carpet particle and vice versa, but the total number of free particles will be preserved throughout. In view of Lemma 2.2, we will make sure the half-topplings performed during the procedure are always legal. After the definition, we state in Proposition 3.4 the main fact that will be used regarding the carpet/hole toppling procedure.

3.1. Valid configurations

Fix integers a>0a>0 and K=a4K=a^{4}. The procedure described in this section is well-defined for any positive integer aa, although later in Proposition 3.4 and Lemma 4.6 we will need to choose a large enough aa. The toppling procedure needs to start from relatively nice particle configurations on a finite interval, which we call valid configurations.

Definition 3.1.

For any nn\in\operatorname{\mathbb{N}}, a pair of particle configuration and parity sequence (η,ω)(\eta,\omega) on Dn:=(K+a,nK)D_{n}:=(-K+a,nK) is valid if

η=i=K+a+1nK1δiuUδu+i=0n1(bi,0δiK+bi,1δiK+a)\eta=\sum_{i=-K+a+1}^{nK-1}\delta_{i}-\sum_{u\in U}\delta_{u}+\sum_{i=0}^{n-1}(b_{i,0}\delta_{iK}+b_{i,1}\delta_{iK+a})

for some bi,0,bi,10b_{i,0},b_{i,1}\geqslant 0 and some Ui=0n1[iK,iK+a]U\subset\cup_{i=0}^{n-1}[iK,iK+a] satisfying

(3.2) |U[iK,iK+a]|1,for i=0,1,,n1.|U\cap[iK,iK+a]|\leqslant 1,\quad\text{for }i=0,1,\ldots,n-1.

The subinterval [iK,iK+a][iK,iK+a] is called the iith block for i=0,1,,n1i=0,1,\ldots,n-1, and the complement of the blocks are called transit regions. In other words, a valid configuration has single particles everywhere, except for at most one empty spot per block and possibly some additional particles at the boundary of every block.

Fix a valid configuration (η,ω)(\eta,\omega). In order to perform the carpet/hole toppling procedure starting from (η,ω)(\eta,\omega), we need to identify the special site hole in each block based on (η,ω)(\eta,\omega), as well as classify the particles of η\eta into several categories. Note that the definitions given in the current Section 3.1 only apply to the starting configuration (η,ω)(\eta,\omega). In Section 3.2, we will provide rules regarding how the holes move and particles switch types during the procedure.

Every block has exactly one hole, uniquely determined by the pair (η,ω)(\eta,\omega). For each i=0,,n1i=0,\ldots,n-1, if block ii has a position with no particle, then the empty site is the hole of block ii. If block ii has a particle in every position, the leftmost site xx in that block with ω(x)=1\omega(x)=1 is declared the hole. If there is no such xx, then declare iK+aiK+a to be the position of the hole.

With the definition of the holes, we allocate the particles in η\eta into several types. By definition, each site in DnD_{n} (containing both blocks and transit regions) that does not have a hole will have at least one particle. We declare one particle at every such site to be a carpet particle. (If there are multiple particles at a site, we simply pick an arbitrary one and declare it a carpet particle.) All the remaining particles in DnD_{n} are free particles.

In the configuration η\eta, free particles are either in a hole or at an endpoint of a block. Free particles are further divided into two groups. For each i=0,,n1i=0,\ldots,n-1, if block ii has η(x)1\eta(x)\geqslant 1 and ω(x)=0\omega(x)=0 for all x[iK,iK+a]x\in[iK,iK+a], then the hole was defined to be at iK+aiK+a and we declare an arbitrary (free) particle at iK+aiK+a to be a frozen free particle. All the other free particles are thawed. There is always one special thawed particle, the hot particle, that actually gets toppled. We will explain the rule of determining the hot particle in Section 3.2.

3.2. Carpet/hole dynamics

We now formally define the carpet/hole toppling procedure inside a given interval Dn=(K+a,nK)D_{n}=(-K+a,nK). Fix a valid configuration (η,ω)(\eta,\omega). Suppose we’ve picked the starting locations of the holes and labelled the particles as ‘carpet’, ‘free’, ‘frozen’ and ‘thawed’ according to Section 3.1. The toppling procedure works as follows:

  1. (L1)

    We follow a leftmost priority policy for choosing the hot particle, which implies Lemma 4.4 below. Find the leftmost block ii that contains a thawed particle. If no such block exists, the procedure ends and we say the procedure reaches partial stabilization. Among the thawed particles in block ii, we choose the one inside the hole to be the hot particle if there is one. Otherwise, the thawed particles are at the boundary iKiK or iK+aiK+a, and we declare an arbitrary thawed particle the hot one. This particular order of choice is to ensure 2 below. Once we choose the hot particle, we proceed with 2 or 3 depending on whether block ii contains a frozen particle.

  2. (L2)

    Suppose block ii does not contain a frozen particle. If the hot particle is at the hole but the hole is not the leftmost position yy with parity value ω(y)=1\omega(y)=1, then go directly to 2a or 2b. Otherwise, repeatedly topple the hot particle until it returns to the hole of block ii, or hits either (i1)K+a(i-1)K+a or (i+1)K(i+1)K, which could be a boundary point of a neighboring block or a boundary point of the interval DnD_{n}. There are three cases:

    1. (L2a)

      Suppose the hot particle returned to the hole of block ii and there exists some position in the block ii with odd parity. Find the leftmost position yy in block ii with parity value ω(y)=1\omega(y)=1. Declare the hot particle at the hole a carpet particle, move the hole in block ii to position yy, and declare the carpet particle at yy a thawed and hot particle. Return to 2.

    2. (L2b)

      Suppose the hot particle returned to the hole of block ii, but there is no site in block ii with odd parity. Turn the hot particle at the hole into a carpet particle, move the hole to position iK+aiK+a, and declare the carpet particle at iK+aiK+a a frozen free particle. Return to 1.

    3. (L2c)

      If the hot particle reached (i1)K+a(i-1)K+a or (i+1)K(i+1)K, declare it no longer hot but still free and thawed. Return to 1.

  3. (L3)

    If block ii does contain a frozen particle, then every site in block ii has a particle which is not the hot particle. Repeatedly topple the hot particle until it reaches (i1)K+a(i-1)K+a or (i+1)K(i+1)K. Then declare it no longer hot but still free and thawed. If block ii now has the leftmost site yy with parity value ω(y)=1\omega(y)=1, then turn the frozen free particle at iK+aiK+a into a carpet particle, move the hole to yy, and declare the carpet particle at xx free and thawed. Return to 1.

The block size aa is large, so the typical occurrence is 2a: a hot particle makes an excursion inside its block. Our aim is to show that step 2b occurs much less often than 2c.

More broadly, what we will show is that the carpet/hole toppling procedure, as a renormalization scheme of the Stochastic Sandpile Model, ‘converges’ to the Activated Random Walk model (ARW) with a small sleep rate when the block size goes to infinity. Each block and every free particle in our procedure correspond to a single site and a normal particle in the ARW model respectively. Step 2c mimics an ARW particle moving to a neighboring site, whereas the rare 2b step represents an ARW particle becoming sleepy with a small sleep rate. If 2b does happen and a free particle becomes frozen, it can become thawed through 3, just as a sleepy ARW particle gets reactivated by the presence of another particle.

Once we make the ‘convergence’ rigorous in certain sense, the analysis of a 1D ARW-like system with a small sleep rate yields to a classical energy-entropy argument [11]. The overall outcome of these is Proposition 3.4, stated at the end of Section 3.

The following properties hold trivially for the initial configuration (η,ω)(\eta,\omega) and are preserved by the half-toppling sequence, which can be checked by induction.

  1. (P1)

    Each block ii has exactly one hole which is located at some site x[iK,iK+a]x\in[iK,iK+a].

  2. (P2)

    Whenever the hot particle is inside the hole of a block without a frozen particle, we always make sure this hole is located at the leftmost site yy in that block with parity value ω(y)=1\omega(y)=1. If there is no site in block ii with odd parity, then we make sure the hole is at iK+aiK+a and contains a frozen particle.

  3. (P3)

    There is exactly one carpet particle at every site in DnD_{n} except for the holes.

  4. (P4)

    All free particles except the hot particle are in a hole, or at a site iKiK or iK+aiK+a for some ii.

  5. (P5)

    We call a block which contains a frozen particle a frozen block. In a frozen block, both the frozen particle and the hole are at iK+aiK+a. Thus every site in this block has a particle that is not hot.

We also collect some facts that will be useful throughout the paper.

  1. (F1)

    All half-topplings performed during this procedure are legal.

  2. (F2)

    After the first free particle has been designated hot in block ii, all free particles in block ii except the hot particle (if there is one) are at iKiK or iK+aiK+a.

  3. (F3)

    A free particle designated hot in a block with a frozen particle reaches a neighboring block before being declared not hot.

  4. (F4)

    The number of free particles is conserved during the procedure.

  5. (F5)

    When the procedure ends, all free particles are either frozen, with at most one frozen particle per block, or at the boundary points of DnD_{n}. Also, there is at most one particle (either carpet or frozen free particle) at every site inside DnD_{n}.

3.3. Bounds on frozen particles

We prove the following regarding the carpet/hole toppling procedure. Roughly speaking, it says that the dynamics is likely to sustain ‘enough activity’ so that at the end of the procedure, there are few frozen particles left inside every subinterval.

Let (η,ω)(\eta,\omega) be a valid configuration on Dn=(K+a,nK)D_{n}=(-K+a,nK). Run carpet/hole dynamics with initial condition (η,ω)(\eta,\omega) until partial stabilization when there are no more thawed particles inside DnD_{n}. Denote its law by (η,ω)\mathbb{P}_{(\eta,\omega)}. For 0n0n1n10\leqslant n_{0}\leqslant n_{1}\leqslant n-1, define Frozen(n0,n1){\text{Frozen}}(n_{0},n_{1}) to be the number of frozen free particles remaining in the blocks n0,n0+1,,n1n_{0},n_{0}+1,\dots,n_{1} at the end of the carpet/hole dynamics on DnD_{n}. Also let mn(η,ω,x)m_{n}(\eta,\omega,x) be the (half-toppling) odometer function at site xDnx\in D_{n} resulting from the carpet/hole toppling procedure on DnD_{n}, and define

(3.3) Hi:={mn(η,ω,iK)βn},H(n0,n1):=Hn01c(i=n0n1Hi)H_{i}:=\{m_{n}(\eta,\omega,iK)\geqslant\beta n\},\,H(n_{0},n_{1}):=H_{n_{0}-1}^{c}\bigcap\left(\bigcap_{i=n_{0}}^{n_{1}}H_{i}\right)

for some constant β>0\beta>0. The purpose of the event H(n0,n1)H(n_{0},n_{1}) is to ensure each block starting from a nice configuration and to facilitate a bootstrap argument later in the proof of Lemma 5.9. Write H:=H(0,n1)H:=H(0,n-1) and Frozen:=Frozen(0,n1){\text{Frozen}}:={\text{Frozen}}(0,n-1).

Proposition 3.4.

For δ=β=4×104\delta=\beta=4\times 10^{-4} and any L>0L^{\ast}>0, there exist c1>0c_{1}>0 and K=e1.8×105K=e^{1.8\times 10^{5}} such that the following hold for large enough n=n1n0+1n^{\prime}=n_{1}-n_{0}+1. If (η,ω)(\eta,\omega) is valid and the total number of particles xDnη(x)L|Dn|\sum_{x\in D_{n}}\eta(x)\leqslant L^{\ast}|D_{n}|, then we have

(3.5) (η,ω)({Frozen(n0,n1)>δn}H(n0,n1))exp(c1n).\mathbb{P}_{(\eta,\omega)}(\{{\text{Frozen}}(n_{0},n_{1})>\delta n^{\prime}\}\cap H(n_{0},n_{1}))\leqslant\exp(-c_{1}n^{\prime}).

In particular,

(3.6) (η,ω)({Frozen>δn}H)exp(c1n).\mathbb{P}_{(\eta,\omega)}(\{{\text{Frozen}}>\delta n\}\cap H)\leqslant\exp(-c_{1}n).

Proposition 3.4 will be proved in the next section. We will rely on Proposition 3.4 to do the analysis in Section 5.

4. Filtrations and coarse-grained particle flows

Fix any initial configuration (η,ω)(\eta,\omega) on DnD_{n}. Consider one iteration of the carpet/hole dynamics on an interval Dn=(K+a,nK)D_{n}=(-K+a,nK) with nn blocks. Recall our aim is to prove Proposition 3.4. The ‘single block estimate’ Lemma 4.6 roughly says that the probabilities of a block being frozen at certain stopping times are small. To combine these estimates for different blocks, it is necessary to introduce some independence between the blocks, and enumerate the possible trajectories of the system. Section 4 is devoted to these goals, and then giving a proof of Proposition 3.4 by using Lemma 4.6. Though more technical, the argument in this section follows a similar approach as the one in [9].

4.1. Decorated stacks and filtration

Whenever a free particle is designated as the hot particle in step 1, we designate the block ii it is in as the hot block. For each yDny\in D_{n} in a transit region, we split the stack instructions for yy into two independent stacks of independent instructions, ξy=(ξy,L,ξy,R)\xi^{y}=(\xi^{y,L},\xi^{y,R}). The hot particle toppled at site yy uses instructions from the LL stack if the nearest block to the left of yy is the hot block, and from the RR stack if the nearest block to the right of yy is the hot block. Sites yy in a block have just a single instruction stack, ξy\xi^{y}. We work with the filtration i\mathcal{F}_{i} of all the stack instructions decorated by blocks jij\leqslant i, i.e.

(4.1) i=σ[{ξy:y(K+a,iK+a]}{ξy,L:y[iK+a,(i+1)K)}].\mathcal{F}_{i}=\sigma[\{\xi^{y}:y\in(-K+a,iK+a]\}\cup\{\xi^{y,L}:y\in[iK+a,(i+1)K)\}].

4.2. Coarse-grained particle flows and mass balance equations

To index possible ‘trajectories’ of the carpet/hole dynamics, we count the flow of particles between blocks. For each i{0,,n1}i\in\{0,\ldots,n-1\} and s0s\geqslant 0 let

(4.2) η+(s,i)=η+sδiK+a\eta^{+}(s,i)=\eta+s\delta_{iK+a}

be the configuration η\eta with ss additional particles at the right edge of block ii. We define the following ‘coarse-grained counters’:

Definition 4.3.

For each j{0,,n1}j\in\{0,\ldots,n-1\}, run carpet/hole dynamics started from configuration (η+(s,j),ω)(\eta^{+}(s,j),\omega) until there are no legal topplings of free particles in (K+a,jK)(-K+a,jK), the first jj blocks. Define

  • for any iji\leqslant j, the total number of times Lij(s)L_{i}^{j}(s) during this toppling procedure that a free particle goes left using an instruction from the stack ξ(i1)K+a+1,R\xi^{(i-1)K+a+1,R};

  • for any iji\leqslant j, the number of frozen particles Fij(s)F_{i}^{j}(s) in block ii at the end of the toppling procedure (either 0 or 1 by 5);

  • Fi:=Fin1(0)F_{i}:=F_{i}^{n-1}(0) and Li:=Lin1(0)L_{i}:=L_{i}^{n-1}(0). Set Ln:=0L_{n}:=0.

Note that Fij(s),Lij(s)jF_{i}^{j}(s),L_{i}^{j}(s)\in\mathcal{F}_{j}. Our leftmost priority policy for choosing the hot particle guarantees the next lemma.

Lemma 4.4.

We have, for each i{0,,n1}i\in\{0,\ldots,n-1\},

(4.5) Fi=Fii(Li+1)andLi=Lii(Li+1).F_{i}=F_{i}^{i}(L_{i+1})\quad\text{and}\quad L_{i}=L_{i}^{i}(L_{i+1}).

See the corresponding lemma in [9] for a proof. This allows us to study the number of frozen free particles in block ii at the end of the procedure by running the carpet/hole dynamics up to block ii, plus some random number of extra particles input from the right.

To avoid dependence, we make a uniform argument over all possible values of the input from the right. A vector of integers 𝒔=(s0,s1,,sn=0)\boldsymbol{s}=(s_{0},s_{1},\cdots,s_{n}=0) is said to satisfy the mass balance equations if

Lii(si+1)=si for i=0,,n1.L_{i}^{i}(s_{i+1})=s_{i}\text{ for }i=0,\ldots,n-1.

Note that the random vector (L0,L1,,Ln=0)(L_{0},L_{1},\ldots,L_{n}=0) satisfies the mass balance equations by definition. In what follows, we will sum over the random set of possible vectors 𝒔\boldsymbol{s} satisfying these random mass balance equations.

4.3. Single block estimate

The following Lemma is an upper bound on the number of frozen particles FiF_{i} in a fixed block. Sections 6, 7 and 8 are devoted to its proof.

Lemma 4.6.

For δ=4×104\delta=4\times 10^{-4}, there exist constant K=e1.8×105K=e^{1.8\times 10^{5}} and sufficiently large c,cc,c^{\prime} such that logc<δc\log c^{\prime}<\delta c, and the following holds for any ini\leqslant n. If the initial configuration (η,ω)(\eta,\omega) on Dn=(K+a,nK)D_{n}=(-K+a,nK) is valid, then

(4.7) supl0s2𝐄(η,ω)[ecFii(s)1{Lii(s)=l}|i1]<c.\sup_{l\geqslant 0}\sum_{s\geqslant 2}\mbox{$\bf E$}_{(\eta,\omega)}[e^{cF_{i}^{i}(s)}1\{L_{i}^{i}(s)=l\}|\mathcal{F}_{i-1}]<c^{\prime}.

Additionally, for any k0k\geq 0,

(4.8) supl0(η,ω)(s01{Lii(s)=l}>k|i1)θk\sup_{l\geqslant 0}\mathbb{P}_{(\eta,\omega)}\left(\sum_{s\geqslant 0}1\{L_{i}^{i}(s)=l\}>k\bigg{|}\mathcal{F}_{i-1}\right)\leqslant\theta^{k}

for some θ(0,1)\theta\in(0,1) independent of kk.

Note the lower limit of the summation over ss in the first statement. Since we only assume the starting configuration to be valid, we need at least two input particles to ‘fix’ the configuration – see the proof of Lemma 4.6 in Section 8.

In this section we use the single block estimate to prove Proposition 3.4.

Proof of Proposition 3.4. We start by treating the special case where n0=0n_{0}=0 and n1=n1n_{1}=n-1. Let η\eta be any valid carpet, and recall the events HiH_{i} that the odometer of site iKiK is at least βn\beta n and HH that all HiH_{i}’s occur (note that H1=H_{-1}=\emptyset). Also let JiJ_{i} be the event that among the first βn\beta n many times a hot particle is toppled at site iKiK, at least twice it takes a step left and then reaches site (i1)K+a(i-1)K+a before returning to site iKiK. Note that JiiJ_{i}\in\mathcal{F}_{i} and

(4.9) (Jici1)βn(112K)βn1exp(c2n)\mathbb{P}(J_{i}^{c}\mid\mathcal{F}_{i-1})\leqslant\beta n\left(1-\frac{1}{2K}\right)^{\beta n-1}\leqslant\exp(-c_{2}n)

for some c2>0c_{2}>0 depending only on KK and β\beta.

To bound Frozen, the number of frozen free particles remaining in DnD_{n} after the carpet/hole dynamics, we use the fact that Hi{Li2}JicH_{i}\subset\{L_{i}\geqslant 2\}\cup J_{i}^{c}. Since Frozen=iFi{\text{Frozen}}=\sum_{i}F_{i},

(4.10) 𝐄[ecFrozen1H]\displaystyle\mbox{$\bf E$}[e^{c{\text{Frozen}}}1_{H}] ec𝐄[i=0n2ecFi1Hi+1]\displaystyle\leqslant e^{c}\cdot\mbox{$\bf E$}\left[\prod_{i=0}^{n-2}e^{cF_{i}}1_{H_{i+1}}\right]
(4.11) ec𝐄[i=0n2(ecFi1{Li+12}+ec1Ji+1c1{Li+1<2})].\displaystyle\leqslant e^{c}\cdot\mbox{$\bf E$}\left[\prod_{i=0}^{n-2}\left(e^{cF_{i}}1\{L_{i+1}\geqslant 2\}+e^{c}1_{J_{i+1}^{c}}1\{L_{i+1}<2\}\right)\right].

Recall there are at most L|Dn|L^{\ast}|D_{n}| particles inside DnD_{n} at the beginning. Let c4=L(K+1).c_{4}=L^{\ast}(K+1). Using Lemma 4.4, we may rewrite the expectation as

(4.12) 𝐄[s0=0c4ns1sn1i=0n2(ecFii(si+1)1{Li+12}+ec1Ji+1c1{Li+1<2})1{Lii(si+1)=si}1{Li=si}]\displaystyle\mbox{$\bf E$}\left[\sum_{s_{0}=0}^{c_{4}n}\sum_{s_{1}}\cdots\sum_{s_{n-1}}\prod_{i=0}^{n-2}\left(e^{cF_{i}^{i}(s_{i+1})}1\{L_{i+1}\geqslant 2\}+e^{c}1_{J_{i+1}^{c}}1\{L_{i+1}<2\}\right)1\{L_{i}^{i}(s_{i+1})=s_{i}\}1\{L_{i}=s_{i}\}\right]
(4.13) 𝐄[s0=0c4ns1sn1πn1]=𝒮(n1),\displaystyle\leqslant\mbox{$\bf E$}\left[\sum_{s_{0}=0}^{c_{4}n}\sum_{s_{1}}\cdots\sum_{s_{n-1}}\pi_{n-1}\right]=\mathcal{S}(n-1),

where

(4.14) πk:=i=0k1(ecFii(si+1)1{Lii(si+1)=si}1{si+12}+ec1Ji+1c1{si+1<2})k\pi_{k}:=\prod_{i=0}^{k-1}\left(e^{cF_{i}^{i}(s_{i+1})}1\{L_{i}^{i}(s_{i+1})=s_{i}\}1\{s_{i+1}\geqslant 2\}+e^{c}1_{J_{i+1}^{c}}1\{s_{i+1}<2\}\right)\in\mathcal{F}_{k}

and

(4.15) 𝒮(k):=𝐄[s0=0c4ns1skπk].\mathcal{S}(k):=\mbox{$\bf E$}\left[\sum_{s_{0}=0}^{c_{4}n}\sum_{s_{1}}\cdots\sum_{s_{k}}\pi_{k}\right].

We will inductively show that 𝒮(k)(c4n+1)(c+4e2cc2c3n)k\mathcal{S}(k)\leqslant(c_{4}n+1)(c^{\prime}+4e^{2c-c_{2}\wedge c_{3}n})^{k} for constants c2,c3,c4c_{2},c_{3},c_{4}. The base case k=0k=0 is trivial and the case k=1k=1 follows from Lemma 4.6 and the estimate (4.9). Suppose that the inequality is true for k2k-2 and k1k-1. Let

(4.16) Ui(si+1,si):=ecFii(si+1)1{Lii(si+1)=si}iandVi:=ec1Jici.U_{i}(s_{i+1},s_{i}):=e^{cF_{i}^{i}(s_{i+1})}1\{L_{i}^{i}(s_{i+1})=s_{i}\}\in\mathcal{F}_{i}\quad\text{and}\quad V_{i}:=e^{c}1_{J_{i}^{c}}\in\mathcal{F}_{i}.

Decomposing the last two sums depending on whether Sk12S_{k-1}\geq 2 and Sk2S_{k}\geq 2, we get

(4.17) 𝒮(k)=\displaystyle\mathcal{S}(k)= 𝐄[s0=0c4ns1sk1πk1sk=0,1Vk]\displaystyle\,\mbox{$\bf E$}\left[\sum_{s_{0}=0}^{c_{4}n}\sum_{s_{1}}\cdots\sum_{s_{k-1}}\pi_{k-1}\cdot\sum_{s_{k}=0,1}V_{k}\right]
(4.18) +𝐄[s0=0c4ns1sk2πk2sk12Uk2(sk1,sk2)sk2Uk1(sk,sk1)]\displaystyle+\mbox{$\bf E$}\left[\sum_{s_{0}=0}^{c_{4}n}\sum_{s_{1}}\cdots\sum_{s_{k-2}}\pi_{k-2}\cdot\sum_{s_{k-1}\geqslant 2}U_{k-2}(s_{k-1},s_{k-2})\sum_{s_{k}\geqslant 2}U_{k-1}(s_{k},s_{k-1})\right]
(4.19) +𝐄[s0=0c4ns1sk2πk2sk1=0,1sk2Vk1Uk1(sk,sk1)].\displaystyle+\mbox{$\bf E$}\left[\sum_{s_{0}=0}^{c_{4}n}\sum_{s_{1}}\cdots\sum_{s_{k-2}}\pi_{k-2}\cdot\sum_{s_{k-1}=0,1}\sum_{s_{k}\geqslant 2}V_{k-1}U_{k-1}(s_{k},s_{k-1})\right].

By conditioning on k1\mathcal{F}_{k-1} and using (4.9), the first sum is bounded above by 𝒮(k1)2ecc2n\mathcal{S}(k-1)\cdot 2e^{c-c_{2}n}. Similarly, the second sum is at most 𝒮(k1)c\mathcal{S}(k-1)\cdot c^{\prime} by conditioning on k2\mathcal{F}_{k-2} and using the first part of Lemma 4.6. For the last sum, we have

(4.20) 𝐄[sk1=0,1sk2Vk1Uk1(sk,sk1)|k2]\displaystyle\mbox{$\bf E$}\left[\sum_{s_{k-1}=0,1}\sum_{s_{k}\geqslant 2}V_{k-1}U_{k-1}(s_{k},s_{k-1})\bigg{|}\mathcal{F}_{k-2}\right]
(4.21) 2e2c𝐄[(sk1{Lk1k1(sk)=sk1})1Jk1c|k2].\displaystyle\leqslant 2e^{2c}\mbox{$\bf E$}\left[\left(\sum_{s_{k}}1\{L_{k-1}^{k-1}(s_{k})=s_{k-1}\}\right)\cdot 1_{J_{k-1}^{c}}\bigg{|}\mathcal{F}_{k-2}\right].

It follows from (4.9) and the second part of Lemma 4.6 that the third sum is upper bounded 𝒮(k2)2e2cc3n\mathcal{S}(k-2)\cdot 2e^{2c-c_{3}n} for some c3>0c_{3}>0. Combining all three bounds finishes the inductive step.

To bound Frozen, we apply Markov’s inequality together with the bound on 𝒮(n1)\mathcal{S}(n-1) to get

(4.22) ({Frozen>δn}H)(c4n+1)exp(c+(log(c+4e2cc2c3n)δc)n).\mathbb{P}(\{{\text{Frozen}}>\delta n\}\cap H)\leqslant(c_{4}n+1)\exp(c+(\log(c^{\prime}+4e^{2c-c_{2}\wedge c_{3}n})-\delta c)n).

By the assumption logc<δc\log c^{\prime}<\delta c, the event in question is exponentially unlikely in nn. This completes the proof of the case n0=0n_{0}=0 and n1=n1n_{1}=n-1.

The proof of the general case is almost the same as the above case. The main difference is that when n00n_{0}\neq 0, the counter Ln0L_{n_{0}} no longer enjoys the deterministic upper bound as L0c4nL_{0}\leqslant c_{4}n. Instead it suffices to argue that Hn01cH_{n_{0}-1}^{c} and Ln0>4β/(1θ)L_{n_{0}}>4\beta/(1-\theta) occur simultaneously with probability exponentially small in nn. By the second part of Lemma 4.6, out of every two added particles at (n01)K+a(n_{0}-1)K+a, with probability at least 1θ1-\theta some particle reaches (n02)K+a(n_{0}-2)K+a and thus visits (n01)K(n_{0}-1)K. Then a standard concentration bound gives the claim. \square

5. Independent starting configurations

In this section we shall use Proposition 3.4 to prove Theorem 1.1. The main challenge is that Proposition 3.4 requires a valid initial configuration, as well as sufficient activity in every block as stipulated in the event HH, whereas in Theorem 1.1 we directly start from an independent configuration. We bridge the gap by giving an explicit toppling procedure, alternating between legal IDLA steps and the carpet/hole toppling procedure run on a nested sequence of intervals. The particles collected at the boundary of a smaller interval help restore a valid configuration and ensure sufficient activity on a larger interval, which, in turn, guarantees that enough particles reach the endpoints of the larger interval. We will show that this procedure runs forever with positive probability.

Recall that K=a4K=a^{4} is the period of the blocks in the carpet/hole procedure. Throughout Section 5, we use the same K=e1.8×105K=e^{1.8\times 10^{5}} from Proposition 3.4 and Lemma 4.6. We will prove the following re-statement of Theorem 1.1.

Theorem 5.1.

Let μ\mu be a probability distribution supported on finitely many non-negative integers with mean p(113K,1)p\in(1-\frac{1}{3K},1) and j2μ(j)>0\sum_{j\geqslant 2}\mu(j)>0. Let {X(i)}i\{X(i)\}_{i\in\operatorname{\mathbb{Z}}} be i.i.d. random variables with distribution μ\mu. Then the system with starting configuration {X(i)}i\{X(i)\}_{i\in\operatorname{\mathbb{Z}}} stays active a.s.

Proof of Theorem 1.1. Theorem 5.1 is a quantitative version of Theorem 1.1 with μc113K1exp(2×105)\mu_{c}\leqslant 1-\frac{1}{3K}\leqslant 1-\exp(-2\times 10^{5}). It causes no loss of generality to assume that μ\mu is supported on finitely many integers and 𝐄(μ)<1\mbox{$\bf E$}(\mu)<1. To see this, note that for any probability distribution μ\mu on \operatorname{\mathbb{N}} satisfying 𝐄(μ)>113K\mbox{$\bf E$}(\mu)>1-\frac{1}{3K} and j2μ(j)>0\sum_{j\geqslant 2}\mu(j)>0, one can find another distribution μ~\tilde{\mu} stochastically dominated by μ\mu, such that μ~\tilde{\mu} is supported on finitely many integers, 𝐄(μ~)(113K,1)\mbox{$\bf E$}(\tilde{\mu})\in(1-\frac{1}{3K},1) and j2μ~(j)>0\sum_{j\geqslant 2}\tilde{\mu}(j)>0. By monotonicity, if the stochastic sandpile with independent initial distributions μ~\tilde{\mu} does not fixate, then the model with distribution μ\mu also does not fixate. \square

Throughout the rest of this section, we assume μ\mu and {X(i)}i\{X(i)\}_{i\in\operatorname{\mathbb{Z}}} satisfy all the conditions in Theorem 5.1.

5.1. Partial stabilization on nested intervals

Define a sequence {M~i}i0\{\tilde{M}_{i}\}_{i\geqslant 0} with M~i+1=(M~i)(1+)\tilde{M}_{i+1}=\lfloor(\tilde{M}_{i})(1+\ratio)\rfloor for some large M~0\tilde{M}_{0} with γ=.02\gamma=.02. Let Mi=(M~i+1)Ka/2M_{i}=(\tilde{M}_{i}+1)K-a/2. Consider a sequence of intervals of integers

Intervali:={Mi,,Mi},{\text{Interval}_{i}}:=\{-M_{i},\dots,M_{i}\},

which is a shifted version of the interval D2M~i+1=(K+a,(2M~i+1)K)D_{2\tilde{M}_{i}+1}=(-K+a,(2\tilde{M}_{i}+1)K) with 2M~i+12\tilde{M}_{i}+1 many blocks. For i1i\geqslant 1, write

Intervalleft={Mi,,Mi11}{\text{Interval}_{\text{left}}}=\{-M_{i},\dots,-M_{i-1}-1\}

and

Intervalright={Mi1+1,,Mi}.{\text{Interval}_{\text{right}}}=\{M_{i-1}+1,\dots,M_{i}\}.

Also define Si+:=jIntervalrightjX(j)S^{+}_{i}:=\sum_{j\in{\text{Interval}_{\text{right}}}}jX(j) and Si:=jIntervalleftjX(j)S^{-}_{i}:=\sum_{j\in{\text{Interval}_{\text{left}}}}jX(j). Then

𝐄(Si±)=±E(μ)(MiMi1)(Mi+Mi1+1)/2.\mbox{$\bf E$}(S^{\pm}_{i})=\pm E(\mu)(M_{i}-M_{i-1})(M_{i}+M_{i-1}+1)/2.

Finally, let Event4,i±{\text{Event}^{\pm}_{4,i}} be the event that

|Si±𝐄(Si±)|.01γM~iMi.|S^{\pm}_{i}-\mbox{$\bf E$}(S^{\pm}_{i})|\leqslant.01\gamma\tilde{M}_{i}M_{i}.

The above notation Intervali{\text{Interval}_{i}} works for all i0i\geqslant 0. For i=1i=-1, we use the convention that Interval1:={a/2}{\text{Interval}_{-1}}:=\{-a/2\}. Here a/2-a/2 is the left endpoint of the center block containing site zero. For i=0i=0, we write Intervalleft={M0,,a/21}{\text{Interval}_{\text{left}}}=\{-M_{0},\dots,-a/2-1\} and Intervalright={a/2+1,,M0}{\text{Interval}_{\text{right}}}=\{-a/2+1,\dots,M_{0}\}.

We will inductively define partial stabilization procedures on the nested sequence of intervals {Intervali}i0\{{\text{Interval}_{i}}\}_{i\geqslant 0} and the resulting configurations {Yi(z)}zIntervali\{Y_{i}(z)\}_{z\in{\text{Interval}_{i}}}. Set Y1(a/2)=X(a/2)Y_{-1}(-a/2)=X(-a/2). Suppose {Yi1(z)}zIntervali1\{Y_{i-1}(z)\}_{z\in{\text{Interval}_{i-1}}} is defined, we may extend the definition Yi1(z):=X(z)Y_{i-1}(z):=X(z) for all zIntervali1z\notin{\text{Interval}_{i-1}}, and then define {Yi(z)}zIntervali\{Y_{i}(z)\}_{z\in{\text{Interval}_{i}}} to be the configuration after the partial stabilization of Intervali{\text{Interval}_{i}} with initial configuration {Yi1(z)}zIntervali\{Y_{i-1}(z)\}_{z\in{\text{Interval}_{i}}} and particles frozen when they get to the boundary of the interval. Let ui(z)u_{i}(z) be the site odometer at zz in the partial stabilization of Intervali{\text{Interval}_{i}} from Yi1Y_{i-1}.

For i1i\geqslant 1, to go from Yi1Y_{i-1} to YiY_{i} we do the partial stabilization in the following order:

  • Run IDLA on the particles in the two intervals

    Intervalleft{Mi} and Intervalright{Mi}{\text{Interval}_{\text{left}}}\setminus\{-M_{i}\}\text{ and }{\text{Interval}_{\text{right}}}\setminus\{M_{i}\}

    and freeze particles at the boundaries Mi,Mi1,Mi1-M_{i},-M_{i-1},M_{i-1} or MiM_{i}. In other words, keep toppling every particle inside both intervals until it either becomes alone at its site or reaches the boundary.

  • Run IDLA on the particles at Mi1-M_{i-1} and Mi1M_{i-1}, freezing particles at Mi-M_{i} and MiM_{i}, until Intervalleft{Mi}{\text{Interval}_{\text{left}}}\setminus\{-M_{i}\} and Intervalright{Mi}{\text{Interval}_{\text{right}}}\setminus\{M_{i}\} are completely filled or we run out of particles at Mi1-M_{i-1} and Mi1M_{i-1}.

  • If the configuration inside Intervali{\text{Interval}_{i}} becomes valid after the previous two steps, stabilize Intervali{\text{Interval}_{i}} according to the carpet/hole dynamics, freezing particles at Mi-M_{i} and MiM_{i}.

For i=0i=0, we perform a similar procedure by replacing the interval endpoints Mi1-M_{i-1} and Mi1M_{i-1} in the first and second steps by a/2-a/2.

Let Zi,1Z_{i,1}, Zi,2Z_{i,2} and Zi,3=YiZ_{i,3}=Y_{i} the configurations after each of these three steps at stage ii respectively. Each of these configurations has at most one particle per site inside Intervali{\text{Interval}_{i}} except at Mi1-M_{i-1} and Mi1M_{i-1} (or a/2-a/2 when i=0i=0).

Let L:=max{j:μ(j)>0}2L^{\ast}:=\max\{j:\ \mu(j)>0\}\geqslant 2, and let Stage1{\text{Stage}_{-1}} be the event that

  • every site in Interval0{\text{Interval}_{0}} contains LL^{\ast} particles initially,

which occurs with small but positive probability. Suppose Stagei1{\text{Stage}_{i-1}} happens, we will define the event Stagei{\text{Stage}_{i}} inductively. Conditioned on Stagei1{\text{Stage}_{i-1}}, we will observe the following typical behavior during the partial stabilization on Intervali{\text{Interval}_{i}}:

  • After we run IDLA on the particles in

    Intervalleft{Mi} and Intervalright{Mi},{\text{Interval}_{\text{left}}}\setminus\{-M_{i}\}\text{ and }{\text{Interval}_{\text{right}}}\setminus\{M_{i}\},

    the density of sites inside each of those intervals that is covered by a particle is between 11/(3K)1-1/(3K) and 1. We also expect that Event4,i+Event4,i{\text{Event}^{+}_{4,i}}\cap{\text{Event}^{-}_{4,i}} occurs when i1i\geqslant 1. Call the intersection of these three events to be Event1,i{\text{Event}_{1,i}}.

  • Then we run IDLA on the particles at Mi1-M_{i-1} and Mi1M_{i-1} (or a/2-a/2 when i=0i=0) until Intervalleft{Mi}{\text{Interval}_{\text{left}}}\setminus\{-M_{i}\} and Intervalright{Mi}{\text{Interval}_{\text{right}}}\setminus\{M_{i}\} are completely filled. We expect that there are at least .2M~i.2\tilde{M}_{i} particles left at both Mi1-M_{i-1} and Mi1M_{i-1} (or a/2-a/2 when i=0i=0) at the end of this step. Call this event Event2,i{\text{Event}_{2,i}}.

  • If the typical events occur up to this point, by definition the configuration inside Intervali{\text{Interval}_{i}} will be valid and thus we may carry out the carpet/hole toppling procedure. After we stabilize according to the carpet/hole dynamics, there will be less than δ(2M~i+1)=.0004(2M~i+1)\delta(2\tilde{M}_{i}+1)=.0004(2\tilde{M}_{i}+1) blocks without a hole in Intervali{\text{Interval}_{i}}. At both Mi-M_{i} and MiM_{i} there will be at least M~i/4\tilde{M}_{i}/4 particles. Moreover, the odometer ui(z)u_{i}(z) at the left endpoint z=a/2+mKz=-a/2+m^{\prime}K of every block m{M~i,,M~i}m^{\prime}\in\{-\tilde{M}_{i},\dots,\tilde{M}_{i}\} during this carpet/hole procedure is at least β(2M~i+1)=.0004(2M~i+1)\beta(2\tilde{M}_{i}+1)=.0004(2\tilde{M}_{i}+1). Call this event Event3,i{\text{Event}_{3,i}}.

When all these three events happen, we call the procedure successful at stage ii and define inductively

Stagei:=Stagei1Event1,iEvent2,iEvent3,i.{\text{Stage}_{i}}:={\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}}\cap{\text{Event}_{2,i}}\cap{\text{Event}_{3,i}}.

We will show that the event Stage:=i1Stagei{\text{Stage}_{\infty}}:=\cap_{i\geqslant-1}{\text{Stage}_{i}} happens with positive probability. Once this is proved, we can show that the odometer lower bound in the definition of Event3,i{\text{Event}_{3,i}} implies the system stays active almost surely, thus proving Theorem 5.1.

The goal of the rest of Section 5 is to show that (Stage)>0\mathbb{P}({\text{Stage}_{\infty}})>0. The first two steps of each stage are straightforward IDLA processes. We will give lower bounds on the probabilities of Event1,i{\text{Event}_{1,i}} and Event2,i{\text{Event}_{2,i}} in Lemmata 5.2 and 5.4. The stabilization in the third step is more involved and most of the work in this section will come in bounding the probability of Event3,i{\text{Event}_{3,i}}. Other than Proposition 3.4, we will need the ‘center of mass’ calculation in Lemmata 5.55.7 that guarantees enough particles reaching both endpoints. In the proof of Lemma 5.9 we will also carry out a bootstrap argument which, starting from the blocks ±M~i1\pm\tilde{M}_{i-1}, proves the odometer of every block is high. Since the definition and analysis of stage 0 are slightly different from those of stages i1i\geqslant 1, we only treat stage i1i\geqslant 1 in all lemmata of Section 5 but discuss the modifications for stage 0 at the end of the section.

5.2. IDLA steps

We start by bounding the probability that the first step is successful.

Lemma 5.2.

Let X(i)X(i) be i.i.d. with distribution μ\mu satisfying the conditions in Theorem 5.1. There exists c>0c>0 such that for MiM_{i} large enough,

(Event1,i)=(Event1,i|Stagei1)>1ecMi.\mathbb{P}\left({\text{Event}_{1,i}}\right)=\mathbb{P}\left({\text{Event}_{1,i}}\ |\ {\text{Stage}_{i-1}}\right)>1-e^{-cM_{i}}.
Proof.

First note that Event1,i{\text{Event}_{1,i}} and Stagei1{\text{Stage}_{i-1}} are independent as they were defined on disjoint sets of independent random variables. This justifies the equality.

Next, notice that Si+S_{i}^{+} and SiS_{i}^{-} are the sums of less than MiM_{i} independent random variables each bounded by CMiCM_{i} for some CC, as μ\mu is finitely supported. Since MiM_{i} and M~i\tilde{M}_{i} differ by a constant, standard concentration bounds give that

(Event4,i+Event4,i)>1ecMi\mathbb{P}\left({\text{Event}^{+}_{4,i}}\cap{\text{Event}^{-}_{4,i}}\right)>1-e^{-cM_{i}}

for some c>0c>0.

Recall {Zi,1(j)}j{Mi1,,Mi}\{Z_{i,1}(j)\}_{j\in\{M_{i-1},\dots,M_{i}\}} is the sequence generated by running IDLA on {X(j)}j{Mi1,,Mi}\{X(j)\}_{j\in\{M_{i-1},\dots,M_{i}\}} with particles frozen on the boundaries. If Zi,1(Mi1)=kZ_{i,1}(M_{i-1})=k, then there exists y0y\geqslant 0 such that

Mi1Mi1+yX(j)y+k.\sum_{M_{i-1}}^{M_{i-1}+y}X(j)\geqslant y+k.

The random variables {X(i)}\{X(i)\} have mean less than 1 and are bounded and i.i.d. So the probability of the previous inequality is decreasing exponentially in kk and yy. Summing up over all yy gives that the probability that Zi,1(Mi1)=kZ_{i,1}(M_{i-1})=k is exponentially small in kk.

If

(5.3) Mi1+1Mi1Zi,1(j)(11/(3K))(MiMi11),\sum_{M_{i-1}+1}^{M_{i}-1}Z_{i,1}(j)\leqslant(1-1/(3K))(M_{i}-M_{i-1}-1),

then one of the following events must be true:

  1. (1)

    Mi1+1Mi1Xi(j)(1/2)(𝐄(μ)+11/(3K))(MiMi11)\sum_{M_{i-1}+1}^{M_{i}-1}X_{i}(j)\leqslant(1/2)(\mbox{$\bf E$}(\mu)+1-1/(3K))(M_{i}-M_{i-1}-1);

  2. (2)

    there exists k(1/4)(𝐄(μ)(11/(3K)))(MiMi11)k\geqslant(1/4)(\mbox{$\bf E$}(\mu)-(1-1/(3K)))(M_{i}-M_{i-1}-1) and y0y\geqslant 0 such that Mi1Mi1+yX(j)=y+k\sum_{M_{i-1}}^{M_{i-1}+y}X(j)=y+k;

  3. (3)

    there exists k(1/4)(𝐄(μ)(11/(3K)))(MiMi11)k\geqslant(1/4)(\mbox{$\bf E$}(\mu)-(1-1/(3K)))(M_{i}-M_{i-1}-1) and y0y\geqslant 0 such that MiyMiX(j)=y+k\sum_{M_{i}-y}^{M_{i}}X(j)=y+k.

By standard estimates on sums of independent bounded random variables, the probability of the first event is decreasing exponentially in MiM_{i}. The probabilities of the second and third events are decreasing exponentially in MiM_{i} by the argument earlier in the lemma. This completes the proof for Intervalright{\text{Interval}_{\text{right}}}. The proof for Intervalleft{\text{Interval}_{\text{left}}} is similar. ∎

Next we condition on Stagei1Event1,i{\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}} and bound the probability that the second step is successful.

Lemma 5.4.

For γ=.02\gamma=.02, there exists c>0c>0 such that for MiM_{i} large enough,

(Event2,iC|Stagei1Event1,i)<ecMi.\mathbb{P}({\text{Event}_{2,i}}^{C}\ |\ {\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}})<e^{-cM_{i}}.
Proof.

By the definition of Event1,i{\text{Event}_{1,i}} and Stagei1{\text{Stage}_{i-1}} respectively,

#{jIntervalright{Mi}:Zi,1(j)=0}<(M~iM~i1)/3,\#\{j\in{\text{Interval}_{\text{right}}}\setminus\{M_{i}\}\ :\ Z_{i,1}(j)=0\}<(\tilde{M}_{i}-\tilde{M}_{i-1})/3,

and

#{j{Mi1(MiMi1),,Mi1}:Zi,1(j)=0}M~iM~i1,\#\{j\in\{M_{i-1}-(M_{i}-M_{i-1}),\dots,M_{i-1}\}\ :\ Z_{i,1}(j)=0\}\leqslant\tilde{M}_{i}-\tilde{M}_{i-1},

since Zi,1(j)=Yi1(j)Z_{i,1}(j)=Y_{i-1}(j) for jIntervali1j\in{\text{Interval}_{i-1}} and the configuration Yi1Y_{i-1} remains valid after the carpet/hole dynamics of stage i1i-1.

If Event2,i{\text{Event}_{2,i}} fails, then there are less than .2M~i.2(1+γ)M~i1.2\tilde{M}_{i}\leqslant.2(1+\gamma)\tilde{M}_{i-1} particles at Mi1M_{i-1} (or Mi1-M_{i-1} when i=0i=0) when the second step ends. We only treat the case where the event is violated at Mi1M_{i-1} because the other case would be similar. On the event Stagei1{\text{Stage}_{i-1}} we have at least .25M~i1.25\tilde{M}_{i-1} particles initially at Mi1M_{i-1}, so on Stagei1Event1,iEvent2,iC{\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}}\cap{\text{Event}_{2,i}}^{C}, the number of particles released from Mi1M_{i-1} during the second step must be at least

.25M~i1.2(1+γ)M~i1\displaystyle.25\tilde{M}_{i-1}-.2(1+\gamma)\tilde{M}_{i-1} >\displaystyle> .045M~i1\displaystyle.045\tilde{M}_{i-1}
>\displaystyle> 2γM~i1\displaystyle 2\gamma\tilde{M}_{i-1}
=\displaystyle= 2((1+γ)M~i1M~i1)\displaystyle 2((1+\gamma)\tilde{M}_{i-1}-\tilde{M}_{i-1})
\displaystyle\geqslant 2(M~iM~i1)\displaystyle 2(\tilde{M}_{i}-\tilde{M}_{i-1})

for γ=0.02\gamma=0.02. After M~iM~i1\tilde{M}_{i}-\tilde{M}_{i-1} particles have settled to the left of Mi1M_{i-1}, every site in {Mi1(MiMi1),,Mi1}\{M_{i-1}-(M_{i}-M_{i-1}),\dots,M_{i-1}\} has one particle. Thus the nearest vacancy to the right of Mi1M_{i-1} (if it exists) is at least as close as the nearest vacancy to the left of Mi1M_{i-1}, and the probability that each subsequent particle settles to the right of Mi1M_{i-1} is at least 1/2. The probability that it takes at least (M~iM~i1)(\tilde{M}_{i}-\tilde{M}_{i-1}) particles to get less than (M~iM~i1)/3(\tilde{M}_{i}-\tilde{M}_{i-1})/3 of them settling to the right of Mi1M_{i-1} is exponentially unlikely in M~iM~i1\tilde{M}_{i}-\tilde{M}_{i-1} and thus in MiM_{i}. ∎

5.3. Center of mass

In this subsection, we carry out the ‘center of mass’ calculation, which is useful for bounding the probability that the third step is successful. Define

Ni:=jIntervaliX(j)[(2Mi+1)(2M~i+1)].N_{i}:=\sum_{j\in{\text{Interval}_{i}}}X(j)-[(2M_{i}+1)-(2\tilde{M}_{i}+1)].

This is the number of excess particles in Intervali{\text{Interval}_{i}} above the level of one hole per block.

Lemma 5.5.

If Stagei1Event1,i{\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}} occurs, then

jIntervalijZi1,3(j)\displaystyle\sum_{j\in{\text{Interval}_{i}}}jZ_{i-1,3}(j) \displaystyle\geqslant (2M~i1+1)(a/2)+.25M~i1Mi1\displaystyle-(2\tilde{M}_{i-1}+1)(a/2)+.25\tilde{M}_{i-1}M_{i-1}
(Ni1.25M~i1)Mi1.02γM~iMi.\displaystyle-(N_{i-1}-.25\tilde{M}_{i-1})M_{i-1}-.02\gamma\tilde{M}_{i}M_{i}.
Proof.

We break this sum up into sums over particles in Intervali1{\text{Interval}_{i-1}}, Intervalleft{\text{Interval}_{\text{left}}} and Intervalright{\text{Interval}_{\text{right}}}. For the particles in Intervali1{\text{Interval}_{i-1}}, we further partition them into three groups. The first group consists of all the carpet particles in Intervali1{Mi1,Mi1}{\text{Interval}_{i-1}}\setminus\{-M_{i-1},M_{i-1}\}, with one particle at every location except for the holes. The second group is all the particles at Mi1M_{i-1}. The third group consists of all the remaining particles, which are all of the free particles in Intervali1{Mi1,Mi1}{\text{Interval}_{i-1}}\setminus\{-M_{i-1},M_{i-1}\} plus all the particles at Mi1-M_{i-1}.

The absolute value of the sum over the first group is at most

(2M~i1+1)(a/2).(2\tilde{M}_{i-1}+1)(a/2).

As Stagei1{\text{Stage}_{i-1}} occurs, we get that the sum of the locations over the second group is at least

.25M~i1Mi1..25\tilde{M}_{i-1}M_{i-1}.

in absolute value. By 4, the number of particles in the third group is Ni1N_{i-1} minus the number of particles in the second group, which is at least Ni1.25M~i1N_{i-1}-.25\tilde{M}_{i-1}. Thus the sum over the third group is at least

(Ni1.25M~i1)(Mi1).(N_{i-1}-.25\tilde{M}_{i-1})(-M_{i-1}).

For the particles in Intervalleft{\text{Interval}_{\text{left}}} and Intervalright{\text{Interval}_{\text{right}}}, since Event1,i{\text{Event}_{1,i}} occurs, so does Event4,i+Event4,i{\text{Event}^{+}_{4,i}}\cap{\text{Event}^{-}_{4,i}}. By the definition of those events, we get that the absolute value of the both sums combined is at most .02γM~iMi..02\gamma\tilde{M}_{i}M_{i}. Combining these estimates proves the lemma. ∎

Let i{{\daleth}_{i}} be the event that there are at most δ(2M~i+1)\delta(2\tilde{M}_{i}+1) blocks without a hole at the end of stage ii. The next lemma says that if the majority of free particles exit through the endpoints, the proportion of the particles leaving from each side cannot become more unbalanced without causing a significant shift in the center of mass.

Lemma 5.6.

Let γ=.02\gamma=.02. The following holds for δ=4×104\delta=4\times 10^{-4} and sufficiently large MiM_{i}. On the event

Stagei1Event1,iEvent2,ii{Zi,3(Mi)<.25M~i},{\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}}\cap{\text{Event}_{2,i}}\cap{{\daleth}_{i}}\cap\{Z_{i,3}(M_{i})<.25\tilde{M}_{i}\},

we have

Di:=jIntervalijZi1,3(j)jZi,3(j)>(γ/10K)Mi2.D_{i}:=\sum_{j\in{\text{Interval}_{i}}}jZ_{i-1,3}(j)-jZ_{i,3}(j)>(\gamma/10K)M_{i}^{2}.
Proof.

First we show that under the same hypotheses,

jIntervalijZi,3(j)\displaystyle\sum_{j\in{\text{Interval}_{i}}}jZ_{i,3}(j) <\displaystyle< (2M~i+1)(a/2)+(.25M~i+δ(2M~i+1))Mi\displaystyle(2\tilde{M}_{i}+1)(a/2)+(.25\tilde{M}_{i}+\delta(2\tilde{M}_{i}+1))M_{i}
(Ni1+(4/3)(M~iM~i1).25M~iδ(2M~i+1))Mi.\displaystyle-\left(N_{i-1}+(4/3)(\tilde{M}_{i}-\tilde{M}_{i-1})-.25\tilde{M}_{i}-\delta(2\tilde{M}_{i}+1)\right)M_{i}.

The proof of this fact proceeds in a similar manner to Lemma 5.5. We decompose the particles into three groups: the carpet particles in Intervali{M~i,M~i}{\text{Interval}_{i}}\setminus\{-\tilde{M}_{i},\tilde{M}_{i}\}, the free particles in Intervali{M~i,M~i}{\text{Interval}_{i}}\setminus\{-\tilde{M}_{i},\tilde{M}_{i}\} plus the particles at MiM_{i}, and the particles at Mi-M_{i}. The sum of the locations of the carpet particles is at most

(2M~i+1)(a/2).(2\tilde{M}_{i}+1)(a/2).

Since i{Zi,3(Mi)<.25M~i}{{\daleth}_{i}}\cap\{Z_{i,3}(M_{i})<.25\tilde{M}_{i}\} occurred, the sum of the locations of the second group is at most

(.25M~i+δ(2M~i+1))Mi.(.25\tilde{M}_{i}+\delta(2\tilde{M}_{i}+1))M_{i}.

By Event1,i{\text{Event}_{1,i}} we have NiNi1+2(2/3)(M~iM~i1)N_{i}\geqslant N_{i-1}+2(2/3)(\tilde{M}_{i}-\tilde{M}_{i-1}), so there are at least

Ni1+(4/3)(M~iM~i1)(.25M~i+δ(2M~i+1))N_{i-1}+(4/3)(\tilde{M}_{i}-\tilde{M}_{i-1})-(.25\tilde{M}_{i}+\delta(2\tilde{M}_{i}+1))

many particles at Mi-M_{i}, each contributing Mi-M_{i} to the sum. Putting these estimates together gives the desired upper bound.

Combining this result with Lemma 5.5, we get

jIntervalijZi1,3(j)jZi,3(j)\displaystyle\sum_{j\in{\text{Interval}_{i}}}jZ_{i-1,3}(j)-jZ_{i,3}(j)
>\displaystyle> (4/3)(M~iM~i1)Mi.5(M~iMiM~i1Mi1)+Ni1(MiMi1)\displaystyle(4/3)(\tilde{M}_{i}-\tilde{M}_{i-1})M_{i}-.5(\tilde{M}_{i}M_{i}-\tilde{M}_{i-1}M_{i-1})+N_{i-1}(M_{i}-M_{i-1})
2δ(2M~i+1)Mi.02γM~iMi(2M~i+1)a\displaystyle-2\delta(2\tilde{M}_{i}+1)M_{i}-.02\gamma\tilde{M}_{i}M_{i}-(2\tilde{M}_{i}+1)a
>\displaystyle> (1.31.1+0.08.02)γM~iMi\displaystyle(1.3-1.1+0-.08-.02)\gamma\tilde{M}_{i}M_{i}
>\displaystyle> (γ/10K)Mi2,\displaystyle(\gamma/10K)M_{i}^{2},

for δ=0.0004=0.02γ\delta=0.0004=0.02\gamma and MiM_{i} sufficiently large. ∎

Lastly, we show that with high probability there is not enough time for the center of mass to reach a displacement of the size implied by Lemma 5.6. Recall the notation DiD_{i} from the last lemma.

Lemma 5.7.

There exists c>0c>0 such that for all large enough MiM_{i},

(|Di|>Mi1.6|Stagei1)ecMi0.1.\mathbb{P}(|D_{i}|>M_{i}^{1.6}\ |\ {\text{Stage}_{i-1}})\leqslant e^{-cM_{i}^{0.1}}.

Before proving Lemma 5.7, we also state the following variant of it which will be useful in another instance of this ‘center of mass’ argument. For m0,m1m_{0}^{\prime},m_{1}^{\prime}\in\operatorname{\mathbb{Z}} such that M~im0m1M~i-\tilde{M}_{i}\leqslant m_{0}^{\prime}\leqslant m_{1}^{\prime}\leqslant\tilde{M}_{i}, let m^0:=(m01)K+a/2\hat{m}_{0}:=(m_{0}^{\prime}-1)K+a/2 and m^1:=(m1+1)Ka/2\hat{m}_{1}:=(m_{1}^{\prime}+1)K-a/2, and define ρm0,m1(j):Intervali\rho_{m_{0}^{\prime},m_{1}^{\prime}}(j):{\text{Interval}_{i}}\to\operatorname{\mathbb{Z}} to be the piecewise linear function ρm0,m1(j):=j\rho_{m_{0}^{\prime},m_{1}^{\prime}}(j):=j when j{m^0,,m^1}j\in\{\hat{m}_{0},\dots,\hat{m}_{1}\} and ρm0,m1(j):=m^0\rho_{m_{0}^{\prime},m_{1}^{\prime}}(j):=\hat{m}_{0} (resp. m^1\hat{m}_{1}) when j<m^0j<\hat{m}_{0} (resp. j>m^1j>\hat{m}_{1}). Finally, we define

Di,m0,m1:=jIntervaliρm0,m1(j)Zi,2(j)ρm0,m1(j)Zi,3(j).D^{\prime}_{i,m_{0}^{\prime},m_{1}^{\prime}}:=\sum_{j\in{\text{Interval}_{i}}}\rho_{m_{0}^{\prime},m_{1}^{\prime}}(j)Z_{i,2}(j)-\rho_{m_{0}^{\prime},m_{1}^{\prime}}(j)Z_{i,3}(j).

Different from DiD_{i}, the above definition records the change of a restricted version of center of mass in the third step of stage ii. Also, recall that ui(z)u_{i}(z) denotes the odometer at zIntervaliz\in{\text{Interval}_{i}} during the third step of stage ii.

Lemma 5.8.

For M~im0m1M~i-\tilde{M}_{i}\leqslant m_{0}^{\prime}\leqslant m_{1}^{\prime}\leqslant\tilde{M}_{i}, there exists c>0c>0 such that for all large enough MiM_{i},

(|Di,m0,m1|>Mi1.6+max{ui(m^0),ui(m^1)}|Stagei1Event1,iEvent2,i)ecMi0.1.\mathbb{P}(|D^{\prime}_{i,m_{0}^{\prime},m_{1}^{\prime}}|>M_{i}^{1.6}+\max\{u_{i}(\hat{m}_{0}),u_{i}(\hat{m}_{1})\}\ |\ {\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}}\cap{\text{Event}_{2,i}})\leqslant e^{-cM_{i}^{0.1}}.
Proof of Lemmata 5.7 and 5.8.

We start with Lemma 5.8. If the inequality in question occurs, then either (1) the carpet/hole dynamics from Zi,2Z_{i,2} to Zi,3Z_{i,3} takes more than Mi3.1M_{i}^{3.1} many topplings, or (2) the restricted center of mass, i.e. the sum of ρm0,m1\rho_{m_{0}^{\prime},m_{1}^{\prime}} function values of all particles’ locations, moves by at least Mi1.6+max{ui(m^0),ui(m^1)}M_{i}^{1.6}+\max\{u_{i}(\hat{m}_{0}),u_{i}(\hat{m}_{1})\} during the carpet/hole dynamics, which undergoes at most Mi3.1M_{i}^{3.1} topplings. It suffices to bound the probabilities of both (1) and (2).

On one hand, since μ\mu is finitely supported, there is a deterministic upper bound on the number of particles inside Intervali{\text{Interval}_{i}} that is linear in MiM_{i}. So if the system takes at least Mi3.1M_{i}^{3.1} steps, then there exists one particle that moved CMi2.1CM_{i}^{2.1} many times for some C>0C>0. As particles are frozen at ±Mi\pm M_{i}, it must have done so without hitting these two points. For each particle, this has probability at most ecMi0.1e^{-cM_{i}^{0.1}} for some c>0c>0. By a union bound over all particles in Intervali{\text{Interval}_{i}}, the first event has probability at most ecMi0.1e^{-cM_{i}^{0.1}} for some c>0c>0 and large enough MiM_{i}.

For the second event, let τ\tau be the total number of topplings taken during the third step of stage ii, and let (t)Intervali\mathcal{L}(t)\in{\text{Interval}_{i}} and σ(t){1,+1}\sigma(t)\in\{-1,+1\} be the starting location and direction of the ttth toppling respectively. We may write

Di,m0,m1=\displaystyle D^{\prime}_{i,m_{0}^{\prime},m_{1}^{\prime}}= t=1τσ(t)1{m^0<(t)<m^1}\displaystyle\sum_{t=1}^{\tau}\sigma(t)1\{\hat{m}_{0}<\mathcal{L}(t)<\hat{m}_{1}\}
+t=1τ1{(t)=m^0,σ(t)=1}t=1τ1{(t)=m^1,σ(t)=1}.\displaystyle+\sum_{t=1}^{\tau}1\{\mathcal{L}(t)=\hat{m}_{0},\sigma(t)=1\}-\sum_{t=1}^{\tau}1\{\mathcal{L}(t)=\hat{m}_{1},\sigma(t)=-1\}.

The first sum with the upper limit τ\tau replaced by some time variable τ=0,,τ\tau^{\prime}=0,\dots,\tau is a martingale with bounded differences. So by applying the Azuma’s inequality and a union bound over times, the probability that τMi3.1\tau\leqslant M_{i}^{3.1} and the first sum exceeds Mi1.6M_{i}^{1.6} is at most ecMi0.1e^{-cM_{i}^{0.1}} for some c>0c>0 and large enough MiM_{i}. Since both sums in the second line above are at most ui(m^0)u_{i}(\hat{m}_{0}) and ui(m^1)u_{i}(\hat{m}_{1}) respectively, we get the desired bound on the second event. This completes the proof of Lemma 5.8.

For Lemma 5.7, note that by an almost identical argument, one could state and prove an analog of Lemma 5.8 that applies to the partial stabilization of the whole stage ii (from Zi1,3Z_{i-1,3} to Zi,3Z_{i,3}) instead of just the third step (Zi,2Z_{i,2} to Zi,3Z_{i,3}). So Lemma 5.7 is the special case where m0=M~im^{\prime}_{0}=-\tilde{M}_{i} and m1=M~im^{\prime}_{1}=\tilde{M}_{i}. Note that the odometer term in the inequality disappears because no toppling starts from the boundary. ∎

5.4. Carpet/hole step

Finally, we bound the probability that the third step is successful.

Lemma 5.9.

Let γ=.02\gamma=.02. There exist some α,c>0\alpha,c>0 such that for δ=β=4×104\delta=\beta=4\times 10^{-4} and sufficiently large K,MiK,M_{i}, we have

(Event3,iC|Stagei1Event1,iEvent2,i)<ecMiα.\mathbb{P}({\text{Event}_{3,i}}^{C}\ |\ {\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}}\cap{\text{Event}_{2,i}})<e^{-cM_{i}^{\alpha}}.
Proof.

We pick constants γ,δ,β,K\gamma,\delta,\beta,K and MiM_{i} as stated so that Proposition 3.4 and all previous lemmata in Section 5 are true. If Event3,iC{\text{Event}_{3,i}}^{C} occurs, then one of these three events during the third step of stage ii must happen:

  1. (1)

    the odometer ui(a/2+mK)u_{i}(-a/2+m^{\prime}K) at the left endpoint of some block mm^{\prime} is less than β(2M~i+1)\beta(2\tilde{M}_{i}+1);

  2. (2)

    the odometer ui(a/2+mK)β(2M~i+1)u_{i}(-a/2+m^{\prime}K)\geqslant\beta(2\tilde{M}_{i}+1) for every block mm^{\prime} but Frozen>δ(2M~i+1){\text{Frozen}}>\delta(2\tilde{M}_{i}+1);

  3. (3)

    Frozenδ(2M~i+1){\text{Frozen}}\leqslant\delta(2\tilde{M}_{i}+1) but there are less than .25M~i.25\tilde{M}_{i} particles at either Mi-M_{i} or MiM_{i}.

The second event is exponentially unlikely in MiM_{i} by the second statement of Proposition 3.4. For the third event which we denote as 𝒯\mathcal{T}, the ‘center of mass’ calculation, Lemmata 5.6 and 5.7, as well as its symmetric version shows that (Event1,iEvent2,i𝒯|Stagei)\mathbb{P}({\text{Event}_{1,i}}\cap{\text{Event}_{2,i}}\cap\mathcal{T}\ |\ {\text{Stage}_{i}}) is exponentially small in Mi0.1M_{i}^{0.1}. So by Lemmata 5.2 and 5.4 we get the desired bound on (𝒯|StageiEvent1,iEvent2,i)\mathbb{P}(\mathcal{T}\ |\ {\text{Stage}_{i}}\cap{\text{Event}_{1,i}}\cap{\text{Event}_{2,i}}). In the remainder of the proof, we focus on the bootstrap argument which bounds the first event.

As we are conditioning on Stagei1Event1,iEvent2,i{\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}}\cap{\text{Event}_{2,i}}, there are a large number (at least .2M~i.2\tilde{M}_{i}) of initial particles at Mi1-M_{i-1} right before the third step of stage ii. By the second statement of Lemma 4.6, with probability exponentially close to one, the odometer ui(Mi1a)u_{i}(-M_{i-1}-a) at the left endpoint of the block containing Mi1-M_{i-1} must be at least β(2M~i+1)\beta(2\tilde{M}_{i}+1). So if there is some block whose left endpoint odometer is less than β(2M~i+1)\beta(2\tilde{M}_{i}+1), then there exists some largest interval I={m0,,m1}I^{\prime}=\{m^{\prime}_{0},\dots,m^{\prime}_{1}\} such that M~i1I-\tilde{M}_{i-1}\in I^{\prime} and ui(a/2+mK)β(2M~i+1)u_{i}(-a/2+m^{\prime}K)\geqslant\beta(2\tilde{M}_{i}+1) for any block mIm^{\prime}\in I^{\prime}.

First, we claim it is exponentially unlikely in MiM_{i} that Frozen(m0,m1)>δ(2M~i+1){\text{Frozen}}(m^{\prime}_{0},m^{\prime}_{1})>\delta(2\tilde{M}_{i}+1). Indeed, by Proposition 3.4 for any interval I′′=(m0′′,m1′′)I^{\prime\prime}=(m_{0}^{\prime\prime},m_{1}^{\prime\prime}) satisfying |I′′|δ(2M~i+1)|I^{\prime\prime}|\geqslant\delta(2\tilde{M}_{i}+1), the probability that m0′′=m0m_{0}^{\prime\prime}=m_{0}^{\prime} and m1′′=m1m_{1}^{\prime\prime}=m_{1}^{\prime} but Frozen(m0′′,m1′′)>δ(2M~i+1){\text{Frozen}}(m_{0}^{\prime\prime},m_{1}^{\prime\prime})>\delta(2\tilde{M}_{i}+1) is exponentially small in MiM_{i}. The inequality Frozen(m0′′,m1′′)<δ(2M~i+1){\text{Frozen}}(m_{0}^{\prime\prime},m_{1}^{\prime\prime})<\delta(2\tilde{M}_{i}+1) holds trivially for other intervals I′′=(m0′′,m1′′)I^{\prime\prime}=(m_{0}^{\prime\prime},m_{1}^{\prime\prime}) such that |I′′|<δ(2M~i+1)|I^{\prime\prime}|<\delta(2\tilde{M}_{i}+1), so taking a union bound over all such intervals proves the claim.

Next, we show that with exponentially high probability either m0=M~im^{\prime}_{0}=-\tilde{M}_{i} or m1=M~im^{\prime}_{1}=\tilde{M}_{i}. Suppose not, then by definition both ui(a/2+(m01)K)u_{i}(-a/2+(m^{\prime}_{0}-1)K) and ui(a/2+(m1+1)K)u_{i}(-a/2+(m^{\prime}_{1}+1)K) are less than β(2M~i+1)\beta(2\tilde{M}_{i}+1). So with the notation m^0\hat{m}_{0} and m^1\hat{m}_{1} from Lemma 5.8, the number of free particles that stayed inside (m^0,m^1)(\hat{m}_{0},\hat{m}_{1}) before the third step of stage ii but become at or to the right of m^1\hat{m}_{1} afterwards is at most β(2M~i+1)+1\beta(2\tilde{M}_{i}+1)+1 by 5. The same also holds for those becoming at or to the left of m^0\hat{m}_{0}. Since there are at least .2M~i.2\tilde{M}_{i} particles inside (m^0,m^1)(\hat{m}_{0},\hat{m}_{1}) before the third step, at least .2M~i2β(2M~i+1)2.19M~i.2\tilde{M}_{i}-2\beta(2\tilde{M}_{i}+1)-2\geqslant.19\tilde{M}_{i} particles remain frozen in this interval at the end of the carpet/hole procedure. This is exponentially unlikely in MiM_{i} by the above claim.

Thus we may assume, without loss of generality, that m0=M~im^{\prime}_{0}=-\tilde{M}_{i}, as the case m1=M~im^{\prime}_{1}=\tilde{M}_{i} would follow from a symmetric argument. By the claim above we may also assume that Frozen(m0,m1)δ(2M~i+1){\text{Frozen}}(m^{\prime}_{0},m^{\prime}_{1})\leqslant\delta(2\tilde{M}_{i}+1) which happens with exponentially high probability. Our next goal is to show that if m0=M~im^{\prime}_{0}=-\tilde{M}_{i} and Frozen(m0,m1)δ(2M~i+1){\text{Frozen}}(m^{\prime}_{0},m^{\prime}_{1})\leqslant\delta(2\tilde{M}_{i}+1), then we have m1=M~im^{\prime}_{1}=\tilde{M}_{i} with exponentially high probability. This would give the bound on the first event, thus proving Lemma 5.9.

From now on we suppose that m0=M~im^{\prime}_{0}=-\tilde{M}_{i} and Frozen(m0,m1)δ(2M~i+1){\text{Frozen}}(m^{\prime}_{0},m^{\prime}_{1})\leqslant\delta(2\tilde{M}_{i}+1) but m1<M~im^{\prime}_{1}<\tilde{M}_{i}. We will show that this is exponentially unlikely in Mi0.1M_{i}^{0.1} by carrying out another ‘center of mass’ calculation. Recall the notations from Lemma 5.8. By assumption, we have m^0=Mi\hat{m}_{0}=-M_{i}. Let Vi,2V^{\prime}_{i,2} (resp. Vi,3V^{\prime}_{i,3}) be the set of locations of the carpet particles of Zi,2Z_{i,2} (resp. Zi,3Z_{i,3}) inside (m^0,m^1)(\hat{m}_{0},\hat{m}_{1}). Similar to Lemma 5.6,

|jIntervaliρm0,m1(j)δVi,2(j)ρm0,m1(j)δVi,3(j)|(m1m0+1)a.\left|\sum_{j\in{\text{Interval}_{i}}}\rho_{m^{\prime}_{0},m^{\prime}_{1}}(j)\delta_{V^{\prime}_{i,2}}(j)-\rho_{m^{\prime}_{0},m^{\prime}_{1}}(j)\delta_{V^{\prime}_{i,3}}(j)\right|\leqslant(m^{\prime}_{1}-m^{\prime}_{0}+1)a.

For the rest of the particles, we consider a new kind of sum with each location shifted by m^0-\hat{m}_{0} for simplicity. Let Ri,2R_{i,2} (resp. Ri,3R_{i,3}) be the number of particles of Zi,2Z_{i,2} (resp. Zi,3Z_{i,3}) in Intervali{\text{Interval}_{i}} at or to the right of m^1\hat{m}_{1}. On one hand, as there are at least .2M~i.2\tilde{M}_{i} particles at Mi1-M_{i-1} initially, we get

jIntervali(ρm0,m1(j)m^0)(Zi,2(j)δVi,2(j))(.2M~i1)(MiMi1)+Ri,2(m^1m^0).\sum_{j\in{\text{Interval}_{i}}}(\rho_{m^{\prime}_{0},m^{\prime}_{1}}(j)-\hat{m}_{0})(Z_{i,2}(j)-\delta_{V^{\prime}_{i,2}}(j))\geqslant(.2\tilde{M}_{i}-1)(M_{i}-M_{i-1})+R_{i,2}(\hat{m}_{1}-\hat{m}_{0}).

On the other hand, by assumption we have

jIntervali(ρm0,m1(j)m^0)(Zi,3(j)δVi,3(j))(Ri,3+δ(2M~i+1))(m^1m^0).\sum_{j\in{\text{Interval}_{i}}}(\rho_{m^{\prime}_{0},m^{\prime}_{1}}(j)-\hat{m}_{0})(Z_{i,3}(j)-\delta_{V^{\prime}_{i,3}}(j))\leqslant(R_{i,3}+\delta(2\tilde{M}_{i}+1))(\hat{m}_{1}-\hat{m}_{0}).

By the definition of (m0,m1)(m^{\prime}_{0},m^{\prime}_{1}), we have ui(m^1)<β(2M~i+1)u_{i}(\hat{m}_{1})<\beta(2\tilde{M}_{i}+1), which implies Ri,3Ri,2<β(2M~i+1)+1R_{i,3}-R_{i,2}<\beta(2\tilde{M}_{i}+1)+1 by 5. Using this fact and the inequality m^1m^0<2Mi\hat{m}_{1}-\hat{m}_{0}<2M_{i}, we combine the above estimates into

Di,m0,m1\displaystyle D^{\prime}_{i,m_{0}^{\prime},m_{1}^{\prime}} >\displaystyle> (.2M~i1)(MiMi1)2(β+δ)(2M~i+1)Mi2M~ia\displaystyle(.2\tilde{M}_{i}-1)(M_{i}-M_{i-1})-2(\beta+\delta)(2\tilde{M}_{i}+1)M_{i}-2\tilde{M}_{i}a
>\displaystyle> (.19.16)γM~iMi\displaystyle(.19-.16)\gamma\tilde{M}_{i}M_{i}
>\displaystyle> (γ/40K)Mi2,\displaystyle(\gamma/40K)M_{i}^{2},

for β=δ=0.02γ\beta=\delta=0.02\gamma and MiM_{i} sufficiently large.

Lastly, since ui(m^0)=0u_{i}(\hat{m}_{0})=0 and ui(m^1)<β(2M~i+1)u_{i}(\hat{m}_{1})<\beta(2\tilde{M}_{i}+1), Lemma 5.8 and a union bound over all intervals I′′=(m0′′,m1′′)I^{\prime\prime}=(m^{\prime\prime}_{0},m^{\prime\prime}_{1}) imply the above event occurs with exponentially small probability in Mi0.1M_{i}^{0.1}. This completes the ‘center of mass’ argument and thus the proof of Lemma 5.9. ∎

Proof of Theorem 5.1. As mentioned above, we’ve only proved Lemmata 5.25.9 for stage i1i\geqslant 1. We briefly discuss the counterparts and proofs for stage i=0i=0 before putting everything together. Recall the different definitions of Intervali1{\text{Interval}_{i-1}}, Intervalleft{\text{Interval}_{\text{left}}}, Intervalright{\text{Interval}_{\text{right}}}, Stagei1{\text{Stage}_{i-1}}, Event1,i{\text{Event}_{1,i}} and Event2,i{\text{Event}_{2,i}} when i=0i=0. If Stage1{\text{Stage}_{-1}} occurs, i.e. there are exactly L2L^{\ast}\geqslant 2 particles at every location in Interval0{\text{Interval}_{0}} before stage 0, then Event1,i{\text{Event}_{1,i}} occurs almost surely as there will be exactly one particle at every site of Intervalleft{M0}{\text{Interval}_{\text{left}}}\setminus\{-M_{0}\} and Intervalright{M0}{\text{Interval}_{\text{right}}}\setminus\{M_{0}\}. Also, the second step of stage 0 will be trivial, so by a concentration bound on the IDLA particles in the first step, there will be at least 0.49(L1)(2M0)0.49(L^{\ast}-1)(2M_{0}) particles at a/2-a/2 with probability exponentially close to one. This shows that Lemmata 5.2 and 5.4 hold for i=0i=0.

For Lemma 5.5, in fact on the event Stage1{\text{Stage}_{-1}} we have jInterval0jX(j)=0.\sum_{j\in{\text{Interval}_{0}}}jX(j)=0. In the proof of Lemma 5.6, by using the fact N0(L1)(2Mi+1)N_{0}\geqslant(L^{\ast}-1)(2M_{i}+1) and the counterpart of Lemma 5.5, we get Di>Mi2D_{i}>M_{i}^{2}. Lemmata 5.7 and 5.8 work for all i0i\geqslant 0. Finally, essentially the same proof works for Lemma 5.9 by using the above counterparts of Lemmata 5.5 and 5.6 and replacing Mi1-M_{i-1} by a/2-a/2. In other words, Lemma 5.9 also holds for i=0i=0.

From the definition of Stagei{\text{Stage}_{i}} and Lemmata 5.2, 5.4, and 5.9 we get

(StageiC|Stagei1)\displaystyle\mathbb{P}({\text{Stage}_{i}}^{C}\ |\ {\text{Stage}_{i-1}})
=\displaystyle= (Event1,iC|Stagei1)\displaystyle\mathbb{P}({\text{Event}_{1,i}}^{C}\ |\ {\text{Stage}_{i-1}})
+(Event2,iC|Stagei1Event1,i)\displaystyle+\,\mathbb{P}({\text{Event}_{2,i}}^{C}\ |\ {\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}})
+(Event3,iC|Stagei1Event1,iEvent2,i)\displaystyle+\,\mathbb{P}({\text{Event}_{3,i}}^{C}\ |\ {\text{Stage}_{i-1}}\cap{\text{Event}_{1,i}}\cap{\text{Event}_{2,i}})
(5.11) <\displaystyle< ecMi+ecMi+ecMiα\displaystyle e^{-cM_{i}}+e^{-cM_{i}}+e^{-cM_{i}^{\alpha}}

for some c,α>0c,\alpha>0 and sufficiently large MiM_{i}. We have that Stage1{\text{Stage}_{-1}} happens with small but positive probability and MiM_{i} grows exponentially, so there exists a large enough M0M_{0} such that

(i1Stagei)>0.\mathbb{P}(\cap_{i\geqslant-1}{\text{Stage}_{i}})>0.

Thus by the definition of Event3,i{\text{Event}_{3,i}} the odometer at site z=a/2z=-a/2 is infinite with positive probability. By Lemmata 2.1 and 2.2 and 1, this implies

(stochastic sandpile stays active)=1.\mathbb{P}(\text{stochastic sandpile stays active})=1.

\square

6. Carpet processes

We now turn to analyzing the dynamics within a single block, which involves keeping track of the parity configuration as it evolves during the carpet/hole procedure. At a high level, our aim is to show that the parity configuration typically has many 11’s. Sections 6 and 7 are devoted to analyzing an auxiliary version of the particle dynamics, which allow us to unravel the complex combinatorics of our half-toppling procedure, by retaining some independence throughout the process. In particular, Section 6 provides a formulation of such independence, while Section 7 controls the possible impact of the remaining correlation. The outcomes are Lemmata 6.18 and 7.1. Finally, these two lemmata are used in Section 8 to prove Lemma 4.6 by bounding the probability that a block becomes frozen.

6.1. Carpet process and excursions

We focus on the dynamics happening inside a single block, with the hot particle at the hole initially. In Section 6.1, we shall recall some relevant aspects of the dynamics from Section 3 and provide the notations that will be used throughout Sections 6, 7 and 8.

Recall that the block is made up of a string of aa carpet particles, except for a single empty site – the hole – and some parity configuration, ω~Ω~={0,1}[a]\tilde{\omega}\in\tilde{\Omega}=\{0,1\}^{[a]}. For the remainder of the analysis we shift coordinates so that the leftmost point of the block is position 0. For any such ω~\tilde{\omega}, denote by L(ω~)L(\tilde{\omega}) the location of the leftmost 1 of ω~\tilde{\omega},

(6.1) L(ω~):=inf{i:ω~(i)=1},L(\tilde{\omega}):=\inf\{i:\tilde{\omega}(i)=1\},

which is the position of hole when the hot particle is inside the hole. If ω~\tilde{\omega} is identically zero then we write L(ω~)=a+1L(\tilde{\omega})=a+1. Let Q:[length(Q)]Q:[\mathrm{length}(Q)]\to\operatorname{\mathbb{Z}} denote the path taken by the hot particle starting at position L(ω~)L(\tilde{\omega}) and ending on the first return to that site, where length(Q)\mathrm{length}(Q) is the number of steps taken in the path QQ and Q(u)Q(u) is the position of QQ at step uu. Define LocalQ{\text{Local}}_{Q}, the local time of QQ, by

LocalQ(i):=#{u[length(Q)1]:Q(u)=i}.{\text{Local}}_{Q}(i):=\#\{u\in[\mathrm{length}(Q)-1]:\ Q(u)=i\}.

Then define ParityQ{\text{Parity}_{Q}}, the parity of the local time of QQ, by

ParityQ(i):=LocalQ(i)mod2.{\text{Parity}_{Q}}(i):={\text{Local}}_{Q}(i)\bmod 2.

Recall from Section 3 that our carpet process inside a single block is a Markov chain ω~t\tilde{\omega}^{t}, one step of which is defined as follows: Let Lt=L(ω~t)[0,a]L^{t}=L(\tilde{\omega}^{t})\in[0,a].

  • (Do an excursion) The hot particle at LtL^{t} performs a random walk QtQ^{t} on \operatorname{\mathbb{Z}} that starts at LtL^{t} and ends on its first return to LtL^{t}.

  • (Update the parity configuration) For each i[a]i\in[a], set

    (6.2) ω~t+1(i)=ω~t(i)+ParityQt(i)mod2.\tilde{\omega}^{t+1}(i)=\tilde{\omega}^{t}(i)+{\text{Parity}_{Q^{t}}}(i)\bmod 2.

We will be only interested in the carpet process ω~t\tilde{\omega}^{t} until the first time the block gets frozen. In Lemma 8.10, we will deal with what happens thereafter by using the renewal property of carpet processes.

To describe the random walk path QtQ^{t}, we introduce three types of random walk paths, with a right (resp. left) version for each kind, namely: for L[0,a]L\in[0,a],

  1. (Type 1)

    a simple random walk started from LL and conditioned to hit KK (resp. K+a-K+a) without returning to LL;

  2. (Type 2)

    a simple random walk started at aa (resp. 0) and conditioned to hit LL without reaching KK (resp. K+a-K+a);

  3. (Type 3)

    a right (resp. left) type 1 walk followed by a corresponding version of type 2 walk.

Most of the time, QtQ^{t} is a simple random walk excursion on \operatorname{\mathbb{Z}} starting and ending at LtL^{t}. However, when the hot particle reaches a neighboring block, by 2 it respawns from one of the boundary points: QtQ^{t} could also be

  1. (1)

    ‘long excursion’: an emission to the left (resp. right) from LtL^{t} followed by a re-arrival from the left (resp. right) boundary, i.e. a path of type 3;

  2. (2)

    ‘double-sided path’: an emission to the left (resp. right) followed by a re-arrival from the right (resp. left) boundary, a union of type 1 and type 2 paths on opposite sides of LtL^{t};

  3. (3)

    ‘failed re-arrival’: after the emission, the newly designated hot particle fails to arrive at LtL^{t} but makes another emission to a neighboring block.

Among the three corner cases, the ‘long excursion’ is very similar to a random walk excursion in terms of their change of the parities inside the block. In the following, we will simply refer to a long excursion as an ‘excursion’.

6.2. Random walk parities

We will need the following lemma regarding the parity function for a single random walk excursion. Note that the lemma no longer holds at i=Extremei={\text{Extreme}} for excursions to the right, or at i=L1i=L-1 for those to the left – the parity in such case is determined by the conditioning.

Lemma 6.3.

Let QQ be a SRW excursion on \operatorname{\mathbb{Z}} starting and ending at LL. Let

Range={i:u with Q(u)=i}.{\text{Range}}=\{i:\exists\,u\text{ with }Q(u)=i\}.

Let Extreme be its other extreme value of Range (besides LL). If Extreme>L{\text{Extreme}}>L, then for any iRange{L,Extreme}i\in{\text{Range}}\setminus\{L,{\text{Extreme}}\},

(6.4) 16<(ParityQ(i)=0|{ParityQ(j)}j[L,i),Extreme)<56.\frac{1}{6}<\mathbb{P}\bigg{(}{\text{Parity}_{Q}}(i)=0\ |\ \{{\text{Parity}_{Q}}(j^{\prime})\}_{j^{\prime}\in[L,i)},{\text{Extreme}}\bigg{)}<\frac{5}{6}.

Instead if Extreme<L{\text{Extreme}}<L, then for any iRange{L1,L}i\in{\text{Range}}\setminus\{L-1,L\},

(6.5) 16<(ParityQ(i)=0|{ParityQ(j)}j[Extreme,i),Extreme)<56.\frac{1}{6}<\mathbb{P}\bigg{(}{\text{Parity}_{Q}}(i)=0\ |\ \{{\text{Parity}_{Q}}(j^{\prime})\}_{j^{\prime}\in[{\text{Extreme}},i)},{\text{Extreme}}\bigg{)}<\frac{5}{6}.
Proof.

We only treat the case where the excursion goes to the right from LL so that LQ(u)ExtremeL\leqslant Q(u)\leqslant{\text{Extreme}} for all 0ulength(Q)0\leqslant u\leqslant\mathrm{length}(Q), as the proof of the other case would be similar. Fix ii, a sequence of parities (xj)j=Li1(x_{j})_{j=L}^{i-1}, and an extreme value E>iE>i. For a deterministic excursion qq away from LL, we let τ0(q)=τ0(q):=0\tau_{0}(q)=\tau^{\prime}_{0}(q):=0 and recursively define

τj(q):=inf{t>τj1(q):q(t)=i}\tau_{j}(q):=\inf\{t>\tau^{\prime}_{j-1}(q):q(t)=i\}

and

τj(q):=inf{t>τj(q):q(t){i1,i+2}}.\tau^{\prime}_{j}(q):=\inf\{t>\tau_{j}(q):q(t)\in\{i-1,i+2\}\}.

Note that between τj(q)\tau_{j}(q) and τj(q)\tau^{\prime}_{j}(q), the excursion qq might bounces back and forth between ii and i+1i+1.

We will count the number of visits to ii in these intervals conditioning on the entire rest of the path. Let B=j(τj(q),τj(q))B=\cup_{j}(\tau_{j}(q),\tau^{\prime}_{j}(q)) and define Γ(0)=0\Gamma(0)=0 and Γ(j)=inf{j>Γ(j1):jB}\Gamma(j)=\inf\{j>\Gamma(j-1):j\notin B\}. We then define Reduceq(j)=q(Γ(j))Reduce_{q}(j)=q(\Gamma(j)), which is the result of removing the bounces of qq back and forth between ii and i+1i+1. Let q~\tilde{q} be any deterministic excursion away from LL such that Parityq~(j)=xj\text{Parity}_{\tilde{q}}(j)=x_{j} for Lji1L\leqslant j\leqslant i-1 and max(q~)=Emax(\tilde{q})=E. Let q^=Reduceq~\hat{q}=Reduce_{\tilde{q}} and k~=max{k:τk(q~)<}\tilde{k}=\max\{k:\tau^{\prime}_{k}(\tilde{q})<\infty\}. Consider Q~\tilde{Q} being distributed like QQ conditioned on ReduceQ=q^Reduce_{Q}=\hat{q}. For 1jk~1\leqslant j\leqslant\tilde{k}, let NjN_{j} be the number of visits of Q~\tilde{Q} to ii in [τj(Q~),τj(Q~))[\tau_{j}(\tilde{Q}),\tau^{\prime}_{j}(\tilde{Q})).

When Ei+2E\geqslant i+2, a direct computation shows that N1,,Nk~N_{1},\dots,N_{\tilde{k}} are independent Geometric(3/4)\textrm{Geometric}(3/4) random variables. Let

N=j=1k~𝟏{Nj is odd}.N=\sum_{j=1}^{\tilde{k}}\mathbf{1}\{N_{j}\textrm{ is odd}\}.

Then NN has a Binomial(4/5)\textrm{Binomial}(4/5) distribution and a direct computation shows that 1/5(N is even)4/51/5\leqslant\mathbb{P}(N\textrm{ is even})\leqslant 4/5. Since ParityQ~(i)=Parity(N){\text{Parity}}_{\tilde{Q}}(i)={\text{Parity}}(N), the result follows by unwinding the conditioning.

When E=i+1E=i+1, we always have q(τj(q))=i1q(\tau^{\prime}_{j}(q))=i-1 and there must exist some k0[1,k~]k_{0}\in[1,\tilde{k}] with Nk0>1N_{k_{0}}>1. So conditioned on each NkN_{k} being either equal to or greater than one with at least one inequality Nk0>1N_{k_{0}}>1 for some k0k_{0}, we have N1,,Nk~N_{1},\dots,N_{\tilde{k}} distributed either as 1 almost surely or as Geometric(3/4)\text{Geometric}(3/4) random variables. The result then follows from a similar argument. ∎

In Section 6.1, we introduced the random walk paths of Type 1–3, with a right (resp. left) version for each kind. We also require a similar result for these paths.

Lemma 6.6.

Define Extreme as in Lemma 6.3. For a right version walk QQ of any type and any i[L+1,a]{Extreme}i\in[L+1,a]\setminus\{{\text{Extreme}}\},

16<(ParityQ(i)=0|{ParityQ(j)}j[L,i),Extreme)<56.\frac{1}{6}<\mathbb{P}\bigg{(}{\text{Parity}_{Q}}(i)=0\ |\ \{{\text{Parity}_{Q}}(j^{\prime})\}_{j^{\prime}\in[L,i)},{\text{Extreme}}\bigg{)}<\frac{5}{6}.

For a left version walk QQ of any type and any i[0,L2]i\in[0,L-2],

16<(ParityQ(i)=0|{ParityQ(j)}j[K+a,i),Extreme)<56.\frac{1}{6}<\mathbb{P}\bigg{(}{\text{Parity}_{Q}}(i)=0\ |\ \{{\text{Parity}_{Q}}(j^{\prime})\}_{j^{\prime}\in[-K+a,i)},{\text{Extreme}}\bigg{)}<\frac{5}{6}.
Proof.

The proof follows similarly to that of Lemma 6.3. ∎

We shall give a description of the cases where Lemma 6.3 or 6.6 fails when applied to the random walk path QtQ^{t} defined in 6.1. Following the comment above Lemma 6.3, we consider the event that the random variable Z{0,1}Z\in\{0,1\} is uniquely determined by the σ\sigma-algebra \mathcal{R}, that is,

(6.7) (Z=1){0,1}.\mathbb{P}\left(Z=1\mid\mathcal{R}\right)\in\{0,1\}.

Let 𝒯(Q)\mathcal{T}(Q) denote whether the random walk path QQ is an excursion, a double-sided path, or a failed re-arrival. Let

Range(Q):={i:u with Q(u)=i}.{\text{Range}}(Q):=\{i:\exists\,u\text{ with }Q(u)=i\}.
Lemma 6.8.

Consider the σ\sigma-algebra t,i\mathcal{R}_{t,i} generated by

𝒯(Qt),Lt,Range(Qt) and {ParityQt(j)}j<i.\mathcal{T}(Q^{t}),L^{t},{\text{Range}}(Q^{t})\text{ and }\{{\text{Parity}_{Q^{t}}}(j^{\prime})\}_{j^{\prime}<i}.

Suppose QtQ^{t} is not a failed re-arrival. Almost surely, the random variable ParityQt(i){\text{Parity}_{Q^{t}}}(i), for some i(Range(Qt){Lt})[0,a]i\in({\text{Range}}(Q^{t})\setminus\{L^{t}\})\cap[0,a], is uniquely determined by t,i\mathcal{R}_{t,i} if and only if one of the following is true:

  • QtQ^{t} is an excursion to the left or a double-sided path, and i=Lt1i=L^{t}-1;

  • QtQ^{t} is an excursion to the right or a double-sided path, and i=max(Range(Qt))i=max({\text{Range}}(Q^{t})).

Otherwise, a.s.

(6.9) (ParityQt(i)=1t,i)(1/6,5/6).\mathbb{P}({\text{Parity}_{Q^{t}}}(i)=1\mid\mathcal{R}_{t,i})\in(1/6,5/6).
Proof.

This is a consequence of the discussion in this section. ∎

6.3. Auxiliary carpet process ωt\omega^{t}

We start with the following heuristic. Suppose we had the following two facts:

  1. (1)

    there exist ϵ,D>0\epsilon,D>0 such that if L(ω~t)>ϵaL(\tilde{\omega}^{t})>\epsilon a then

    𝐄(L(ω~t+1)L(ω~t)ω~t)<D;\mbox{$\bf E$}\left(L(\tilde{\omega}^{t+1})-L(\tilde{\omega}^{t})\mid\tilde{\omega}^{t}\right)<-D;
  2. (2)

    there exists G>0G>0 such that for all aa and all ω~t\tilde{\omega}^{t},

    𝐄(L(ω~t+1)L(ω~t)ω~t)<G.\mbox{$\bf E$}\left(L(\tilde{\omega}^{t+1})-L(\tilde{\omega}^{t})\mid\tilde{\omega}^{t}\right)<G.

Since the process ω~t\tilde{\omega}^{t} is a Markov process, the above two facts, together with some regularity conditions, would be sufficient to show that the expected value of the smallest tt with L(ω~t)=a+1L(\tilde{\omega}^{t})=a+1 is growing exponentially in aa, that is, the block does not get frozen for a long time. Unfortunately neither of the facts above is true.

To make this heuristic rigorous we will introduce an auxiliary carpet process {ωt}t0\{\omega^{t}\}_{t\geqslant 0} and a related filtration {Revealt}t0\{{\textbf{Reveal}}^{t}\}_{t\geqslant 0}, where we do not reveal the full information about the state of ω~t\tilde{\omega}^{t}. It turns out that

𝐄(L(ωt+1)L(ωt)Revealt)\mbox{$\bf E$}\left(L(\omega^{t+1})-L(\omega^{t})\mid{\textbf{Reveal}}^{t}\right)

will have a more uniform drift, which allows us to make the counterparts of the above heuristic rigorous.

We inductively define an increasing family of σ\sigma-algebras (Revealt)t0({\textbf{Reveal}}^{t})_{t\geqslant 0} and the auxiliary carpet process (ωt)t0(\omega^{t})_{t\geqslant 0}. Recall the notations from Section 6.1 and Lemma 6.8. Every σ\sigma-algebra Revealt{\textbf{Reveal}}^{t} will be generated by {s,i(s,t)}s<t\{\mathcal{R}_{s,\,i(s,t)}\}_{s<t} for some random i(s,t)i(s,t). At each time tt, the process ωt\omega^{t} takes values in the space consisting of all

ωΩ{0,1,?}[a]\omega\in\Omega\subset\{0,1,?\}^{[a]}

such that ω(j)=0\omega(j)=0 for j<L(ω),j<L(\omega), where

L(ω):=inf{i:ω(i)=1}.L(\omega):=\inf\{i:\omega(i)=1\}.

In particular, if ω\omega contains no 1, then ω=(0,0,,0)\omega=(0,0,\ldots,0). The variable ωt\omega^{t} will be defined as a function of the paths {Qs}s<t\{Q^{s}\}_{s<t} and measurable in Revealt{\textbf{Reveal}}^{t}.

To keep track of the information in Revealt{\textbf{Reveal}}^{t}, we also define a family of 0/10/1-valued random variables, Hidden(s,i,t){\text{Hidden}}(s,i,t), that are indexed by triples

(s,i,t)0×[a]×>0 with s<t.(s,i,t)\in\operatorname{\mathbb{Z}}_{\geqslant 0}\times[a]\times\operatorname{\mathbb{Z}}_{>0}\text{ with }s<t.

Our definition will ensure that a.s. Hidden(s,i,t)=1{\text{Hidden}}(s,i,t)=1 if and only if ParityQs(i){\text{Parity}_{Q^{s}}}(i) is not uniquely determined by Revealt{\textbf{Reveal}}^{t}, that is,

(ParityQs(i)=1Revealt){0,1}.\mathbb{P}\left({\text{Parity}_{Q^{s}}}(i)=1\mid{\textbf{Reveal}}^{t}\right)\notin\{0,1\}.

Set ω0=ω~0\omega^{0}=\tilde{\omega}^{0} and Reveal0=σ(ω~0){\textbf{Reveal}}^{0}=\sigma(\tilde{\omega}^{0}). Suppose we have defined the σ\sigma-algebra Revealt{\textbf{Reveal}}^{t}, the state ωt\omega^{t} and the family of random variables Hidden(,,t){\text{Hidden}}(\cdot,\cdot,t) after the tt-th random walk path Qt1Q^{t-1}. We start by including Revealt{\textbf{Reveal}}^{t} and 𝒯(Qt)\mathcal{T}(Q^{t}) in Revealt+1{\textbf{Reveal}}^{t+1}, i.e. all the previously revealed plus whether QtQ^{t} is an excursion, a double-sided path, or a failed re-arrival. For any s<ts<t, set

Hidden(s,i,t+1)=0 if Hidden(s,i,t)=0.{\text{Hidden}}(s,i,t+1)=0\text{ if }{\text{Hidden}}(s,i,t)=0.

If QtQ^{t} is an excursion or a double-sided path, then ωt+1\omega^{t+1}, Revealt+1{\textbf{Reveal}}^{t+1} and Hidden(,,t+1){\text{Hidden}}(\cdot,\cdot,t+1) are further defined via the three-step procedure:

  1. (1)

    Refresh the range of QtQ^{t} (other than LtL^{t}) with ?’s as follows to get ωt+1{0,1,?}[a]\omega_{\ast}^{t+1}\in\{0,1,?\}^{[a]}:

    If max(Range(Qt))Lt+1\max({\text{Range}}(Q^{t}))\neq L^{t}+1 and min(Range(Qt))Lt1\min({\text{Range}}(Q^{t}))\neq L^{t}-1, then

    (6.10) ωt+1(i)={?,iRange(Qt){Lt}0,i=Ltωt(i),otherwise.\omega_{\ast}^{t+1}(i)=\left\{\begin{array}[]{lr}?,&i\in{\text{Range}}(Q^{t})\setminus\{L^{t}\}\\ 0,&i=L^{t}\\ \omega^{t}(i),&\text{otherwise}.\end{array}\right.

    Include the random variable Range(Qt){\text{Range}}(Q^{t}) in Revealt+1{\textbf{Reveal}}^{t+1} and set Hidden(t,i,t+1)=0{\text{Hidden}}(t,i,t+1)=0 for all iRange(Qt)c{Lt}i\in{\text{Range}}(Q^{t})^{c}\cup\{L^{t}\}.

    If max(Range(Qt))=Lt+1\max({\text{Range}}(Q^{t}))=L^{t}+1, then we define ωt+1\omega_{\ast}^{t+1} similarly but change the symbol at Lt+1L^{t}+1 to

    (6.11) ωt+1(Lt+1)={?,if ωt(Lt+1)=?(ωt(Lt+1)+1)mod2,otherwise.\omega_{\ast}^{t+1}(L^{t}+1)=\left\{\begin{array}[]{lr}?,&\text{if }\omega^{t}(L^{t}+1)=\,?\\ (\omega^{t}(L^{t}+1)+1)\bmod 2,&\text{otherwise}.\end{array}\right.

    Additionally, set Hidden(t,Lt+1,t+1)=0{\text{Hidden}}(t,L^{t}+1,t+1)=0. If min(Range(Qt))=Lt1\min({\text{Range}}(Q^{t}))=L^{t}-1, then we do the similar change at Lt1L^{t}-1.

  2. (2)

    Find the leftmost one to get ωt+1Ω\omega^{t+1}\in\Omega:

    (6.12) ωt+1(i)={0,i<Lt+11,i=Lt+1ωt+1(i),iLt+1+2.\omega^{t+1}(i)=\left\{\begin{array}[]{lr}0,&i<L^{t+1}\\ 1,&i=L^{t+1}\\ \omega_{\ast}^{t+1}(i),&i\geqslant L^{t+1}+2.\end{array}\right.

    We leave the definition of ωt+1(Lt+1+1)\omega^{t+1}(L^{t+1}+1) to the last step. Include in Revealt+1{\textbf{Reveal}}^{t+1} all the random variables ParityQs(i){\text{Parity}_{Q^{s}}}(i) for sts\leqslant t and iLt+1i\leqslant L^{t+1} which have not been in Revealt{\textbf{Reveal}}^{t}. Set Hidden(s,i,t)=0{\text{Hidden}}(s,i,t)=0 for any such s,is,i.

  3. (3)

    Inspect the bit at Lt+1+1L^{t+1}+1 to see if it is uniquely determined by Revealt+1{\textbf{Reveal}}^{t+1}. More specifically, for any sts\leqslant t such that Hidden(s,Lt+1+1,t+1){\text{Hidden}}(s,L^{t+1}+1,t+1) has not been set to zero, set Hidden(s,Lt+1+1,t+1)=0{\text{Hidden}}(s,L^{t+1}+1,t+1)=0 if one of the two cases from Lemma 6.8 holds with QsQ^{s} and i=Lt+1+1i=L^{t+1}+1. If after this, we have Hidden(s,Lt+1+1,t+1)=0{\text{Hidden}}(s,L^{t+1}+1,t+1)=0 for all sts\leqslant t, then we define ωt+1(Lt+1+1)=ω~t+1(Lt+1+1)\omega^{t+1}(L^{t+1}+1)=\tilde{\omega}^{t+1}(L^{t+1}+1); otherwise, let ωt+1(Lt+1+1)=?\omega^{t+1}(L^{t+1}+1)=\,?. Finally, we set all the undefined Hidden(,,t+1){\text{Hidden}}(\cdot,\cdot,t+1) to one.

If QtQ^{t} is a failed re-arrival, then we simply leave ωt\omega^{t^{\prime}}, Revealt{\textbf{Reveal}}^{t^{\prime}} and Hidden(,,t){\text{Hidden}}(\cdot,\cdot,t^{\prime}) undefined for tt+1t^{\prime}\geqslant t+1. This completes the inductive definition of all three items.

The last definition implies that all results about the auxiliary carpet process ωt\omega^{t}, including but not limited to the key Lemmata 6.18, 7.1 and 8.9 below, only apply until the first occurrence of a failed re-arrival. However, since the auxiliary process ω0=ω~0\omega^{0}=\tilde{\omega}^{0} may start from an arbitrary configuration, we could restart the definition of {ωT+t}t0\{\omega^{T+t}\}_{t\geqslant 0} with ωT=ω~T\omega^{T}=\tilde{\omega}^{T}, at some stopping time TT close enough to the time in question. This is done in Lemma 8.10.

6.4. Properties of the process ωt\omega^{t}

We now state several consequences of these definitions before proving Lemma 6.18, which summarizes our progress in Section 6. For s<ts<t, let

ih(s,t)=inf{i:Hidden(s,i,t)=1}.i_{h}(s,t)=\inf\{i:{\text{Hidden}}(s,i,t)=1\}.

Also let

HiddenL(s,t):={i:Hidden(s,i,t)=1}(,Lt){\text{Hidden}}_{L}(s,t):=\{i:{\text{Hidden}}(s,i,t)=1\}\cap(-\infty,L^{t})

and

HiddenR(s,t):={i:Hidden(s,i,t)=1}(Lt,).{\text{Hidden}}_{R}(s,t):=\{i:{\text{Hidden}}(s,i,t)=1\}\cap(L^{t},\infty).
Lemma 6.13.

The following are true.

  1. (1)

    ωt(i)=ω~t(i)\omega^{t}(i)=\tilde{\omega}^{t}(i) if ωt(i)?\omega^{t}(i)\neq\,?.

  2. (2)

    L(ωt)=L(ω~t)L(\omega^{t})=L(\tilde{\omega}^{t}).

  3. (3)

    ωt(i)=?\omega^{t}(i)=\,? if and only if there exists some s<ts<t such that Hidden(s,i,t)=1.{\text{Hidden}}(s,i,t)=1.

Proof.

All items follow from the definition of ωt\omega_{\ast}^{t} and ωt\omega^{t} by induction on tt. ∎

Lemma 6.14.

The following are true.

  1. (1)

    ωt\omega^{t} is measurable in Revealt.{\textbf{Reveal}}^{\,t}.

  2. (2)

    Revealt{\textbf{Reveal}}^{\,t} is generated by {t,ih(s,t)}s<t\{\mathcal{R}_{t,\,i_{h}(s,t)}\}_{s<t} where Rt,iR_{t,\,i} is defined in Lemma 6.8.

  3. (3)

    For any s<ts<t, both HiddenL(s,t){\text{Hidden}}_{L}(s,t) and HiddenR(s,t){\text{Hidden}}_{R}(s,t) are either empty or a connected set of size at least two.

Proof.

The proof of each item goes by induction. In particular, for item (1) and (2) we use Lemma 6.8 in the ‘inspect’ step and trivially in the two corner cases of the ‘refresh’ step. Item (3) is guaranteed by the definition of Hidden, both from the two corner cases in the ‘refresh’ step and from the cases of Lemma 6.8 in the ‘inspect’ step. ∎

For the purpose of Lemma 6.18, it is more convenient to study the intermediate state ωt\omega_{\ast}^{t} defined in the ‘refresh’ step of the procedure. We consider the corresponding Revealt{\textbf{Reveal}}_{\ast}^{t} and Hidden(,,t){\text{Hidden}}_{\ast}(\cdot,\cdot,t) associated with ωt\omega_{\ast}^{t}. Let Revealt+1{\textbf{Reveal}}_{\ast}^{t+1} (resp. Hidden(,,t+1){\text{Hidden}}_{\ast}(\cdot,\cdot,t+1) ) be Revealt+1{\textbf{Reveal}}^{t+1} (resp. Hidden(,,t+1){\text{Hidden}}(\cdot,\cdot,t+1)\,) at the end of the ‘refresh’ step without performing the changes in the subsequent two steps. All undefined Hidden(,,t+1){\text{Hidden}}_{\ast}(\cdot,\cdot,t+1) are set to one. We also define ih,(s,t)i_{h,\ast}(s,t), HiddenL,(s,t){\text{Hidden}}_{L,\ast}(s,t) and HiddenR,(s,t){\text{Hidden}}_{R,\ast}(s,t) by replacing Hidden(s,i,t){\text{Hidden}}(s,i,t) in the original definitions with Hidden(s,i,t){\text{Hidden}}_{\ast}(s,i,t). The next lemma follows as a by-product of the inductive proof of the last two lemmata.

Lemma 6.15.

Except for Lemma 6.13 (2), Lemmata 6.13 and 6.14 still hold if we replace ωt\omega^{t}, Revealt{\textbf{Reveal}}^{\,t} and Hidden(,,t){\text{Hidden}}(\cdot,\cdot,t) with the corresponding ωt\omega_{\ast}^{t}, Revealt{\textbf{Reveal}}_{\ast}^{\,t} and Hidden(,,t){\text{Hidden}}_{\ast}(\cdot,\cdot,t). ∎

Lemma 6.16.

If ωt(i)=?\omega_{\ast}^{t}(i)=\,?, then a.s.

(ω~t(i)=1Revealt,{s,i1}s<t)(1/6,5/6).\mathbb{P}\left(\tilde{\omega}^{t}(i)=1\mid{\textbf{Reveal}}^{\,t}_{\ast},\{\mathcal{R}_{s,i-1}\}_{s<t}\right)\in(1/6,5/6).
Proof.

In the following, when we refer to the items in Lemmata 6.13 and 6.14, we actually mean their counterparts in Lemma 6.15. Since ωt(i)=?\omega_{\ast}^{t}(i)=\,?, by Lemma 6.13 (3) there exists some s0<ts_{0}<t with Hidden(s0,i,t)=1{\text{Hidden}}_{\ast}(s_{0},i,t)=1. By Lemma 6.14 (3), we must have

(6.17) {j,j+1}HiddenL,(s0,t)HiddenR,(s0,t)\{j,j+1\}\subseteq{\text{Hidden}}_{L,\ast}(s_{0},t)\cup{\text{Hidden}}_{R,\ast}(s_{0},t)

holds for either (1) j=ij=i, or (2) j=i1j=i-1 with i=max(HiddenL,(s0,t))i=\max({\text{Hidden}}_{L,\ast}(s_{0},t)) or i=max(HiddenR,(s0,t))i=\max({\text{Hidden}}_{R,\ast}(s_{0},t)).

In the first case, neither of the events in Lemma 6.8 occurs with Qs0Q^{s_{0}} at ii. So by combining Lemma 6.14 (2), the fact that ih,(s0,t)ii_{h,\ast}(s_{0},t)\leqslant i, independence and Lemma 6.8, we obtain that a.s.

(ParityQs0(i)=1Revealt,{s,i}s<t)(1/6,5/6).\mathbb{P}\left({\text{Parity}_{Q^{s_{0}}}}(i)=1\mid{\textbf{Reveal}}_{\ast}^{t},\{\mathcal{R}_{s,i}\}_{s<t}\right)\in(1/6,5/6).

Since ω~t(i)=ω~0(i)+s<tParityQs(i)\tilde{\omega}^{t}(i)=\tilde{\omega}^{0}(i)+\sum_{s<t}{\text{Parity}_{Q^{s}}}(i), this proves Lemma 6.16 in the first case.

For the second case, the display from the first case can be shown similarly if we replace both ii’s with i1i-1’s. The assumption also implies ParityQs0(i){\text{Parity}_{Q^{s_{0}}}}(i) is uniquely determined by s0,i\mathcal{R}_{s_{0},i}, so a.s.

(ParityQs0(i)=1Revealt,{s,i1}s<t)(1/6,5/6).\mathbb{P}\left({\text{Parity}_{Q^{s_{0}}}}(i)=1\mid{\textbf{Reveal}}_{\ast}^{t},\{\mathcal{R}_{s,i-1}\}_{s<t}\right)\in(1/6,5/6).

Lemma 6.16 then follows. ∎

For ω{0,1,?}[a]\omega\in\{0,1,?\}^{[a]}, define

N(ω):=#{i[0,a]:ω(i)0}.N(\omega):=\#\{i\in[0,a]:\omega(i)\neq 0\}.

One key part of our analysis is to show that when L(ωt)L(\omega^{t}) is large, N(ωt)N(\omega^{t}) behaves like a random walk biased to increase, see Lemma 8.1. Lemma 6.18 says that N(ωt)N(\omega^{t}) is unlikely to decrease dramatically by erasing many ?s.

Lemma 6.18.

For any t,kt,k\in\operatorname{\mathbb{N}}, a.s.

(N(ωt)N(ωt)k|Revealt)(5/6)(k1)/2.\mathbb{P}\left(N(\omega_{\ast}^{t})-N(\omega^{t})\geqslant k\ |\ {\textbf{Reveal}}^{\,t}_{\ast}\right)\leqslant(5/6)^{(k-1)/2}.
Proof.

Let ini_{n} be the location of the nnth leftmost ? in ωt\omega_{\ast}^{t} (if it exists). Since we might lose one more ? in the ‘inspect’ step, the above conditional probability is at most

(ω~t(i1)=0,ω~t(i2)=0,,ω~t(ik1)=0|Revealt).\mathbb{P}\left(\tilde{\omega}^{t}(i_{1})=0,\tilde{\omega}^{t}(i_{2})=0,\dots,\tilde{\omega}^{t}(i_{k-1})=0\ |\ {\textbf{Reveal}}^{t}_{\ast}\right).

The above expression is at most (5/6)(k1)/2(5/6)^{\lceil(k-1)/2\rceil} by repeated conditioning and use of Lemma 6.16 at every other ini_{n}. This proves the desired estimate. ∎

7. Zeros of auxiliary carpet process

With Lemma 6.18, we will show that when L(ωt)L(\omega^{t}) is large, the number of nonzero symbols N(ωt)N(\omega^{t}) has a bias to increase. However, this does not rule out the possibility that N(ωt)N(\omega^{t}) becomes small when L(ωt)L(\omega^{t}) is small. The main goal of Section 7 is to show that with a nice initial configuration, this is unlikely to occur for an exponentially long time.

To state Lemma 7.1, the main result of this section, we fix a few notations. First we introduce several special states in the space Ω\Omega, defined in Section 6.3. Let

 Base=01????\text{ Base}=01??\cdots??
 Exit=000000.\;\,\text{ Exit}=0000\cdots 00.

The ‘Base’ state starts with 0101 followed by a1a-1 many ?, whereas the ‘Exit’ state is the all-zero state which occurs exactly when the block becomes frozen. Define

τExit:=inf{t0:ωt=Exit}.\tau_{\text{Exit}}:=\inf\{t\geqslant 0:\omega^{t}=\text{Exit}\}.

For ϵ=1/200\epsilon=1/200, define an ‘ϵ\epsilon-Base’ state to be any configuration of the form

0001????00\cdots 01??\cdots??

starting with at most ϵa\epsilon a many 0’s from the left. In particular, the Base state is an ϵ\epsilon-Base state.

Since ωt\omega^{t} is not a Markov chain with respect to its natural filtration, we consider the carpet processes {ω~t}tt0\{\tilde{\omega}^{t}\}_{t\geqslant t_{0}} and {ωt}tt0\{\omega^{t}\}_{t\geqslant t_{0}} that start from some negative t0t_{0} instead of zero, and use the shorthand notation ¯ω0(A)x\overline{\mathbb{P}}_{\omega_{0}}(A)\leqslant x to mean that

supRReveal0(A|ω0=ω0,R)x.\sup_{R\,\in\,{\textbf{Reveal}}^{0}}\mathbb{P}\left(A\ |\ \omega^{0}=\omega_{0},R\right)\leqslant x.

Write ¯\underline{\mathbb{P}} similarly for the infimum. In fact, all results in Section 7 are true in a stronger sense where the supremum/infimum is over all Rσ({Qs}s<0)R\in\sigma(\{Q^{s}\}_{s<0}), but the above notation has the advantage of working for both Sections 7 and 8. We also write ¯ϵ-Base\overline{\mathbb{P}}_{\epsilon\text{-Base}} in the case that the statement holds for any initial ϵ\epsilon-Base state ω0\omega_{0}.

Lemma 7.1.

Consider the event

B={L(ωt)ϵa and N(ωt)ϵa for some 0t<τExit}.B=\left\{L(\omega^{t})\leqslant\epsilon a\text{ and }N(\omega^{t})\leqslant\epsilon a\text{ for some }0\leqslant t<\tau_{\text{Exit}}\right\}.

For ϵ=1/200\epsilon=1/200 and sufficiently large aa,

¯ϵ-Base(B)exp(a/100).\overline{\mathbb{P}}_{\epsilon\text{-Base}}(B)\leqslant\exp(-a/100).

The rest of Section 7 is devoted to the proof of Lemma 7.1. In order to produce so many zeros in ωt\omega^{t}, the auxiliary carpet process needs to follow certain scheme – it has to work from right to left and generate the zeros without refreshing the pre-existing zeros to its right. The proof then goes by identifying such schemes and bounding each scheme’s probability, via estimates mimicking those for birth-death chains.

7.1. History of zeros in ωt\omega^{t}

We start by studying how zeros are generated in the auxiliary carpet process. Write

Visited(t,i)=1{iRange(Qt)}.{\text{Visited}}(t,i)=1\{i\in{\text{Range}}(Q^{t})\}.

Recall that the process ωt\omega^{t} starts from some negative time t0t_{0}. For any time t0t\geqslant 0, define

Right Zerost:={i>L(ωt):ωt(i)=0}.{\text{Right Zeros}}^{t}:=\{i>L(\omega^{t}):\ \omega^{t}(i)=0\}.

For any time t0t\geqslant 0 and i[L(ωt),a]i\in[L(\omega^{t}),a], define

Lastt(i):=sup{t[0,t):Visited(t,i)=1}1,{\text{Last}}^{t}(i):=\sup\{t^{\prime}\in[0,t):{\text{Visited}}(t^{\prime},i)=1\}\vee-1,

which is the last nonnegative time tt^{\prime} before tt when ii gets visited by a random walk path.

Lemma 7.2.

For any ss and ii with L(ωs+1)<iL(ωs)L(\omega^{s+1})<i\leq L(\omega^{s}), we have Visited(s,i)=1{\text{Visited}}(s,i)=1

Proof.

QsQ^{s} cannot be an excursion to the right, since necessarily L(ωs+1)>L(ωs)L(\omega^{s+1})>L(\omega^{s}) in that case. If QsQ^{s} is a double-side path, then Visited(s,i)=1{\text{Visited}}(s,i)=1 for all ii. So assume QsQ^{s} is an excursion to the left. Then L(ωs+1)min(Range(Qs))L(\omega^{s+1})\geqslant\min({\text{Range}}(Q^{s})) and thus min(Range(Qs))<iL(ωs)\min({\text{Range}}(Q^{s}))<i\leq L(\omega^{s}). This implies Visited(s,i)=1{\text{Visited}}(s,i)=1. ∎

Lemma 7.3.

For any t0t\geqslant 0, iRight Zerosti\in{\text{Right Zeros}}^{t} and t[Lastt(i)+1,t]t^{\prime}\in[{\text{Last}}^{t}(i)+1,t],

L(ωt)<i.L(\omega^{t^{\prime}})<i.
Proof.

Suppose that L(ωt)iL(\omega^{t^{\prime}})\geqslant i. Since iRight Zerosti\in{\text{Right Zeros}}^{t}, we have L(ωt)<iL(ωt)L(\omega^{t})<i\leq L(\omega^{t^{\prime}}). Thus there exists some ss such that ts<tt^{\prime}\leqslant s<t with L(ωs+1)<iL(ωs)L(\omega^{s+1})<i\leq L(\omega^{s}). But by Lemma 7.2 we must have a time s(Lastt(i),t)s\in({\text{Last}}^{t}(i),t) with Visited(s,i)=1{\text{Visited}}(s,i)=1, which contradicts the definition of Lastt(i){\text{Last}}^{t}(i). Therefore L(ωt)<iL(\omega^{t^{\prime}})<i. ∎

Lemma 7.4.

Suppose L(ωs){i,i+1}Range(Qs)L(\omega^{s})\notin\{i,i+1\}\subseteq{\text{Range}}(Q^{s}), and L(ωt)<iL(\omega^{t^{\prime}})<i for any t[s+1,t]t^{\prime}\in[s+1,t], then

ωt(i)=ωt(i+1)=?.\omega^{t}(i)=\omega^{t}(i+1)=\,?.
Proof.

Recall the definition of the procedure in Section 6.3. By the first assumption, Hidden(s,i,s+1){\text{Hidden}}(s,i^{\prime},s+1) has not been set to zero at the end of the ‘refresh’ step for i{i,i+1}i^{\prime}\in\{i,i+1\}. By the second assumption, Hidden(s,i,t){\text{Hidden}}(s,i^{\prime},t^{\prime}) will remain to be one for i{i,i+1}i^{\prime}\in\{i,i+1\} and t[s+1,t]t^{\prime}\in[s+1,t]. So Hidden(s,i,t)=Hidden(s,i+1,t)=1{\text{Hidden}}(s,i,t)={\text{Hidden}}(s,i+1,t)=1 and the lemma follows by Lemma 6.13 (3). ∎

Lemma 7.5.

Let imax:=max{i>L(ωt):ωt(i)=0}.i_{\max}:=\max\{i>L(\omega^{t}):\omega^{t}(i)=0\}. We have

  1. (1)

    the function Lastt(i){\text{Last}}^{t}(i) is decreasing on the set [L(ωt),a][L(\omega^{t}),a];

  2. (2)

    for any i,jRight Zerosti,j\in{\text{Right Zeros}}^{t} with j<ij<i and Lastt(j)=Lastt(i)Lastt(imax){\text{Last}}^{t}(j)={\text{Last}}^{t}(i)\neq{\text{Last}}^{t}(i_{\max}), we have i=j+1i=j+1 and at time Lastt(i){\text{Last}}^{t}(i), there was an excursion to its left Qs=QLastt(i)Q^{s}=Q^{{\text{Last}}^{t}(i)} starting from ii such that Visited(s,i2)=1{\text{Visited}}(s,i-2)=1 and ParityQs(i1)=0{\text{Parity}}_{Q^{s}}(i-1)=0;

  3. (3)

    there do not exist three distinct values i,j,kRight Zerosti,j,k\in{\text{Right Zeros}}^{t} with Lastt(i)=Lastt(j)=Lastt(k)Lastt(imax){\text{Last}}^{t}(i)={\text{Last}}^{t}(j)={\text{Last}}^{t}(k)\neq{\text{Last}}^{t}(i_{\max}).

  4. (4)

    if ω0\omega^{0} is an ϵ\epsilon-Base state, then there do not exist four distinct values in Right Zerost{\text{Right Zeros}}^{t} with the same function value Lastt(){\text{Last}}^{t}(\cdot).

Proof.

Since the random walk always starts from the leftmost one, a straightforward induction on the time tt proves item (1). Item (3) follows directly from item (2), so it remains to show items (2) and (4).

For item (2), write s=Lastt(j)=Lastt(i)s={\text{Last}}^{t}(j)={\text{Last}}^{t}(i). By item (1), we have s>Lastt(imax)1s>{\text{Last}}^{t}(i_{\max})\geqslant-1, so s0s\geqslant 0 and Visited(s,j)=Visited(s,i)=1{\text{Visited}}(s,j)={\text{Visited}}(s,i)=1. Thus {j,j+1}Range(Qs)\{j,j+1\}\subseteq{\text{Range}}(Q^{s}). We claim that L(ωs){j,j+1}L(\omega^{s})\in\{j,j+1\}. Suppose not, then Lemmata 7.3 and 7.4 combined imply that ωt(j)=?\omega^{t}(j)=\,?, which is a contradiction. This proves the claim.

We consider all the possible cases of QsQ^{s} satisfying L(ωs){j,j+1}L(\omega^{s})\in\{j,j+1\}. First, QsQ^{s} cannot be a double-sided path: otherwise, we would have Lastt(i)=Lastt(imax){\text{Last}}^{t}(i)={\text{Last}}^{t}(i_{\max}). Secondly, QsQ^{s} cannot be an excursion to the right: otherwise, from L(ωs){j,j+1}L(\omega^{s})\in\{j,j+1\} we must have L(ωs+1)>jL(\omega^{s+1})>j, which contradicts Lemma 7.3. Lastly, if QsQ^{s} is an excursion to the left, then we must have L(ωs)=j+1L(\omega^{s})=j+1 to guarantee Visited(s,j+1)=1{\text{Visited}}(s,j+1)=1. This implies i=j+1i=j+1. Since no random walk after time ss visits jj, it follows that ParityQs(j)=ω~s(j)=ωs(j)=0{\text{Parity}}_{Q^{s}}(j)=\tilde{\omega}^{s}(j)=\omega^{s}(j)=0, which in turn implies that Visited(s,i2)=1{\text{Visited}}(s,i-2)=1. This proves item (2).

For item (4), we first show that for any s0s\geqslant 0, |Right Zerost(s)|3|{\text{Right Zeros}}^{t}(s)|\leqslant 3, where

Right Zerost(s):={iRight Zerost:Lastt(i)=s}.{\text{Right Zeros}}^{t}(s):=\{i\in{\text{Right Zeros}}^{t}:{\text{Last}}^{t}(i)=s\}.

Suppose not, then out of any four such elements we can find iRight Zerost(s)i\in{\text{Right Zeros}}^{t}(s) such that L(ωs){i,i+1}Range(Qs)L(\omega^{s})\notin\{i,i+1\}\subseteq{\text{Range}}(Q^{s}), which leads to a similar contradiction to that in the proof of item (2). This proves the bound for s0s\geqslant 0.

It remains to check the case where s=1s=-1. We show that |Right Zerost(1)|1|{\text{Right Zeros}}^{t}(-1)|\leqslant 1 again by contradiction. Suppose not and there exist i,jRight Zerost(1)i,j\in{\text{Right Zeros}}^{t}(-1) with i<ji<j. Since Lastt(j)=1{\text{Last}}^{t}(j)=-1, by item (1) we have j>L(ω0)j>L(\omega^{0}) and thus ω0(j)=?\omega^{0}(j)=\,? due to the definition of an ϵ\epsilon-Base state. Moreover, by Lemma 7.3 we get L(ωt)<iL(\omega^{t^{\prime}})<i for any t[0,t]t^{\prime}\in[0,t], so it follows from the definition of ωt\omega^{t} that ωt(j)=?\omega^{t^{\prime}}(j)=\,? for any t[0,t]t^{\prime}\in[0,t]. This contradicts with the fact that ωt(j)=0\omega^{t}(j)=0, which proves item (4). ∎

We introduce some more notation. For p<ap<a write [p,a]=[p,a].[p,a]=[p,a]\cap\operatorname{\mathbb{Z}}. We call a sequence x{0,,?/1}[p,a]x\in\{0,*,?/1\}^{[p,a]} good if for all jj such that x(j)=x(j)=* we have x(j+1)=0x(j+1)=0. The good sequences capture different ways in which zeros may be generated in ωt\omega^{t}, with adjacent * and 0 representing a pair of zeros generated as described in Lemma 7.5 (2).

Given a good xx and p<ap<a, we partition the zeros in xx as follows:

Set0:={j[p,a]:x(j)=0}=Set1Set2Set3{M~(x)},{\text{Set}_{0}}:=\{j\in[p,a]:x(j)=0\}={\text{Set}_{1}}\cup{\text{Set}_{2}}\cup{\text{Set}_{3}}\cup\{\tilde{M}(x)\},

where

M~(x)\displaystyle\tilde{M}(x) :=\displaystyle:= max{j:x(j)=0}\displaystyle\max\{j:\ x(j)=0\}
N~(x)\displaystyle\tilde{N}(x) :=\displaystyle:= max{j<M~(x):x(j)=0}\displaystyle\max\{j<\tilde{M}(x):\ x(j)=0\}

and

Set1\displaystyle{\text{Set}_{1}} :=\displaystyle:= {j[p,a]:x(j)=0,x(j+1)?/1 and x(j1)}{N~(x)}\displaystyle\{j\in[p,a]:x(j)=0,x(j+1)\neq\,?/1\text{ and }x(j-1)\neq*\}\ \setminus\{\tilde{N}(x)\}
Set2\displaystyle{\text{Set}_{2}} :=\displaystyle:= {j[p,a]:x(j)=0,x(j+1)?/1 and x(j1)=}{N~(x)}\displaystyle\{j\in[p,a]:x(j)=0,x(j+1)\neq\,?/1\text{ and }x(j-1)=*\}\ \setminus\{\tilde{N}(x)\}
Set3\displaystyle{\text{Set}_{3}} :=\displaystyle:= {j[p,a]:x(j)=0,x(j+1)=?/1}{N~(x)}{M~(x)}.\displaystyle\{j\in[p,a]:x(j)=0,x(j+1)=\,?/1\}\cup\{\tilde{N}(x)\}\setminus\{\tilde{M}(x)\}.

For jSet0{M~(x)}j\in{\text{Set}_{0}}\setminus\{\tilde{M}(x)\}, let k(j)k(j) be such that

j+k(j)=inf{j>j:jSet0}j+k(j)=\inf\{j^{\prime}>j:j^{\prime}\in{\text{Set}_{0}}\}

and let r(j)r(j) be such that

j+r(j)=inf{j>j:x(j)=0 or },j+r(j)=\inf\{j^{\prime}>j:x(j^{\prime})=0\text{ or }*\},

except when j=N~(x)j=\tilde{N}(x), we have r(N~(x))=M~(x)+1N~(x)r(\tilde{N}(x))=\tilde{M}(x)+1-\tilde{N}(x) instead. Note that in a good sequence, for jN~(x)j\neq\tilde{N}(x) we always have r(j)=k(j) or k(j)1r(j)=k(j)\text{ or }k(j)-1.

Finally, for r2r\geqslant 2 divide Set3{\text{Set}_{3}} into pieces

Set3,r:=Set3{j:r(j)=r}.{\text{Set}_{3,r}}:={\text{Set}_{3}}\cap\{j:\ r(j)=r\}.

7.2. Counters, stopping times and events

In this section, we outline the proof of Lemma 7.1. Suppose we’re given a good sequence xx. To bound the probability of the right-to-left dynamics generating xx, we will inductively define a counter ys(i)y^{s}(i) at every vertex iSet0i\in{\text{Set}_{0}} starting from M~(x)\tilde{M}(x). The goal of the counters is twofold. On one hand, given a sequence zSet0z\in\operatorname{\mathbb{N}}^{{\text{Set}_{0}}} the counters can be used to identify a sequence of stopping times T~(i)\tilde{T}(i) for every iSet0i\in{\text{Set}_{0}}. We will tailor our definitions so that T~(i)=Lastt(i)+1\tilde{T}(i)={\text{Last}}^{t}(i)+1 with the right choice of zz (in most cases), see Lemma 7.8. On the other hand, the counters also give us bounds on the probability of the key events Ax,zA_{x,z}, see Lemma 7.7.

We start with the definition of ys(i)y^{s}(i) and T~(i)\tilde{T}(i) at i=M~(x)i=\tilde{M}(x).

  • For i=M~(x)i=\tilde{M}(x), the counter y0(i)y^{0}(i) starts at zero. For any s0s\geqslant 0, the counter ys+1(i)=ys(i)+1y^{s+1}(i)=y^{s}(i)+1 increases by one if at time ss the random walk starts from L(ωs)M~(x)L(\omega^{s})\geqslant\tilde{M}(x) and either s=0s=0 or the previous random walk path Qs1Q^{s-1} was from L(ωs1)<M~(x)L(\omega^{s-1})<\tilde{M}(x); otherwise, the counter stays put and we have ys+1(i)=ys(i)y^{s+1}(i)=y^{s}(i). Given z(i)z(i), define the stopping time T~(M~(x))\tilde{T}(\tilde{M}(x)) to be the smallest ss such that ys(i)=z(i)y^{s}(i)=z(i) and the next path starts at L(ωs)<M~(x)L(\omega^{s})<\tilde{M}(x) if such ss exists; in this case, we say T~(M~(x))\tilde{T}(\tilde{M}(x)) is well-defined.

In order to define other counters we will work inductively. Suppose that the stopping time T~(i+k(i))\tilde{T}(i+k(i)) is well-defined, we shall define ys(i)y^{s}(i) for all sT~(i+k(i))s\geqslant\tilde{T}(i+k(i)).

  • For iSet1Set2i\in{\text{Set}_{1}}\cup{\text{Set}_{2}}, then initially at s=T~(i+k(i))s=\tilde{T}(i+k(i)), we set the counter ys(i)=ω~s(i)1y^{s}(i)=\tilde{\omega}^{s}(i)-1. For any sT~(i+k(i))s\geqslant\tilde{T}(i+k(i)), let

    ys+1(i)=ys(i)+LocalQs(i).y^{s+1}(i)=y^{s}(i)+{\text{Local}}_{Q^{s}}(i).

    In words, the counter increases by one every time a particle moves from ii.

  • For iSet3i\in{\text{Set}_{3}}, then the counter yT~(i+k(i))(i)y^{\tilde{T}(i+k(i))}(i) starts at zero and for sT~(i+k(i))s\geqslant\tilde{T}(i+k(i)), we have

    ys+1(i)={ys(i)+1,L(ωs)[i,i+r(i))ys(i)+LocalQs(i),L(ωs)<i.y^{s+1}(i)=\begin{cases}y^{s}(i)+1,&L(\omega^{s})\in[i,i+r(i))\\ y^{s}(i)+{\text{Local}}_{Q^{s}}(i),&L(\omega^{s})<i.\end{cases}

    In words, the counter increases by one every time a random walk path starts at a location belonging to [i,i+r(i))[i,i+r(i)) or every time a particle moves from ii in a path that starts to the left of ii.

Given z(i)z(i), let T~(i)\tilde{T}(i) be the smallest ss such that ys(i)=z(i)y^{s}(i)=z(i) if such ss exists; in this case, we say T~(i)\tilde{T}(i) is well-defined. This completes the definition of the counter ys(i)y^{s}(i) and stopping time T~(i)\tilde{T}(i) at every iSet0i\in{\text{Set}_{0}}.

Finally, we define the key events Ax,zA_{x,z} in the analysis of counters. For a good sequence xx and zSet0z\in\operatorname{\mathbb{N}}^{{\text{Set}_{0}}}, define Ax,zA_{x,z} to be the event that

  1. (1)

    the stopping times T~(i)\tilde{T}(i) are well-defined for all iSet0i\in{\text{Set}_{0}};

  2. (2)

    T~(M~(x))<τExit\tilde{T}(\tilde{M}(x))<\tau_{\text{Exit}};

  3. (3)

    for any iSet0{M~(x)}i\in{\text{Set}_{0}}\setminus\{\tilde{M}(x)\}, none of QsQ^{s} visits i+r(i)i+r(i) during T~(i+k(i))s<T~(i)\tilde{T}(i+k(i))\leq s<\tilde{T}(i);

  4. (4)

    for iSet2i\in{\text{Set}_{2}}, just before T~(i)\tilde{T}(i) the particle made an excursion to the left Qs=QT~(i)1Q^{s}=Q^{\tilde{T}(i)-1} starting from ii where Visited(s,i2)=1{\text{Visited}}(s,i-2)=1 and ParityQs(i1)=0{\text{Parity}}_{Q^{s}}(i-1)=0.

Lemma 7.6.

If the event BB in Lemma 7.1 occurs, then there exists

  • pϵap\leqslant\epsilon a,

  • a good x{0,,?/1}[p,a]x\in\{0,*,?/1\}^{[p,a]} and

  • zSet0z\in\operatorname{\mathbb{N}}^{{\text{Set}_{0}}}

such that

  • the event Ax,zA_{x,z} occurs and

  • all the z(i)z(i)’s are odd for iSet1Set2i\in{\text{Set}_{1}}\cup{\text{Set}_{2}}.

Lemma 7.7.

Fix any pap\leqslant a. Fix any good sequence x{0,,?/1}[p,a]x\in\{0,*,?/1\}^{[p,a]}. Fix any sequence zSet0z\in\operatorname{\mathbb{N}}^{{\text{Set}_{0}}}. We have

¯ϵ-Base(Ax,z)(1p12M~(x)+a+1)z(M~(x))iSet1(12)z(i)iSet216(12)z(i)1r>1iSet3,r(112r)z(i),\displaystyle\overline{\mathbb{P}}_{\epsilon\text{-Base}}(A_{x,z})\leqslant\left(1-p_{\frac{1}{2}}^{\,-\tilde{M}(x)+a+1}\right)^{z(\tilde{M}(x))}\prod_{i\in{\text{Set}_{1}}}\left(\frac{1}{2}\right)^{z(i)}\prod_{i\in{\text{Set}_{2}}}\frac{1}{6}\left(\frac{1}{2}\right)^{z(i)-1}\prod_{r>1}\prod_{i\in{\text{Set}_{3,r}}}\left(1-\frac{1}{2r}\right)^{z(i)},

where p12=121a4p_{\frac{1}{2}}=\frac{1}{2}-\frac{1}{a^{4}}.

In Section 7.3, we will first prove the above two lemmata, and then combine them to prove Lemma 7.1 using a union bound.

7.3. Analysis of zero generation in ωt\omega^{t}

We start by proving Lemma 7.6. Assume the event BB from Lemma 7.1 occurs, that is, L(ωt)ϵa and N(ωt)ϵa for some 0t<τExitL(\omega^{t})\leqslant\epsilon a\text{ and }N(\omega^{t})\leqslant\epsilon a\text{ for some }0\leqslant t<\tau_{\text{Exit}}. We define the corresponding pp, xx and zz as follows. Recall imax=max{i>L(ωt):ωt(i)=0}.i_{\max}=\max\{i>L(\omega^{t}):\omega^{t}(i)=0\}.

  • Let p:=L(ωt)ϵap:=L(\omega^{t})\leqslant\epsilon a.

  • Set M~:=min{iRight Zerost:Lastt(i)=Lastt(imax)}.\tilde{M}:=\min\{i\in{\text{Right Zeros}}^{t}:{\text{Last}}^{t}(i)={\text{Last}}^{t}(i_{\max})\}.

  • Define a sequence xx in {0,,?/1}[p,a]\{0,*,?/1\}^{[p,a]} by first setting x(M~):=0x(\tilde{M}):=0 and x(i):=?/1x(i):=\,?/1 for i>M~i>\tilde{M}. For i<M~i<\tilde{M}, let

    x(i):={?/1if ωt(i)=?/1,if ωt(i)=ωt(i+1)=0andLastt(i)=Lastt(i+1),0otherwise.x(i):=\begin{cases}?/1&\text{if }\omega^{t}(i)=\,?/1,\\ *&\text{if }\omega^{t}(i)=\omega^{t}(i+1)=0\ \text{and}\ {\text{Last}}^{t}(i)={\text{Last}}^{t}(i+1),\\ 0&\text{otherwise}.\end{cases}

    Note that xx is good due to Lemma 7.5 (3).

  • For i=M~(x)i=\tilde{M}(x) let z(M~(x)):=yt(M~(x))z(\tilde{M}(x)):=y^{t}(\tilde{M}(x)). Note that T~(M~(x))\tilde{T}(\tilde{M}(x)) is well-defined by our definition of z(M~(x))z(\tilde{M}(x)) and the fact that L(ωt)<M~(x)L(\omega^{t})<\tilde{M}(x). To define z(i)z(i) for iSet0{M~(x)}i\in{\text{Set}_{0}}\setminus\{\tilde{M}(x)\} we will work inductively. Suppose that z(i+k(i))z(i+k(i)) is given and T~(i+k(i))\tilde{T}(i+k(i)) is well-defined. Then we let z(i):=yt(i)z(i):=y^{t}(i). Again T~(i)\tilde{T}(i) is well-defined by our choice of z(i)z(i). This completes the definition of zz.

Lemma 7.8.

Let pp, xx and zz be defined as above. For i=M~(x)i=\tilde{M}(x), we have Lastt(i+1)+1T~(i)Lastt(i)+1{\text{Last}}^{t}(i+1)+1\leq\tilde{T}(i)\leq{\text{Last}}^{t}(i)+1. For any iSet0{M~(x)}i\in{\text{Set}_{0}}\setminus\{\tilde{M}(x)\}, we have T~(i)=Lastt(i)+1\tilde{T}(i)={\text{Last}}^{t}(i)+1.

Proof.

We shall prove Lemma 7.8 by induction on ii. We start with the base case where i=M~(x)i=\tilde{M}(x). If z(i)=yt(i)=0z(i)=y^{t}(i)=0, then T~(i)=0\tilde{T}(i)=0 and the upper bound on T~(i)\tilde{T}(i) is trivial. If yt(i)>0y^{t}(i)>0, then by the definition of T~(M~(x))\tilde{T}(\tilde{M}(x)) we have L(ωT~(i))<iL(ωT~(i)1)L(\omega^{\tilde{T}(i)})<i\leq L(\omega^{\tilde{T}(i)-1}). Lemma 7.2 implies Visited(T~(i)1,i)=1{\text{Visited}}(\tilde{T}(i)-1,i)=1 and thus T~(i)1Lastt(i)\tilde{T}(i)-1\leq{\text{Last}}^{t}(i). This proves the upper bound.

To show T~(i)Lastt(i+1)+1\tilde{T}(i)\geqslant{\text{Last}}^{t}(i+1)+1 for i=M~(x)i=\tilde{M}(x), we argue by contradiction. Suppose for some sT~(M~(x))s\geqslant\tilde{T}(\tilde{M}(x)), the path QsQ^{s} visits M~(x)+1\tilde{M}(x)+1. Since sT~(M~(x))s\geqslant\tilde{T}(\tilde{M}(x)), by definition L(ωt)<M~(x)L(\omega^{t^{\prime}})<\tilde{M}(x) for any t[s,t]t^{\prime}\in[s,t], so the conditions of Lemma 7.4 are satisfied. This implies ωt(M~(x))=?\omega^{t}(\tilde{M}(x))=\,?, which is a contradiction. This completes the proof of the base case.

Now suppose T~(i+k(i))Lastt(i+k(i))+1\tilde{T}(i+k(i))\leq{\text{Last}}^{t}(i+k(i))+1 holds for some iSet0{M~(x)}i\in{\text{Set}_{0}}\setminus\{\tilde{M}(x)\}, we will prove T~(i)=Lastt(i)+1\tilde{T}(i)={\text{Last}}^{t}(i)+1. First, note that Lastt(i)Lastt(i+k(i)){\text{Last}}^{t}(i)\neq{\text{Last}}^{t}(i+k(i)); otherwise, Lemma 7.5 (2) would imply k(i)=1k(i)=1 and x(i)=x(i)=*, which contradicts iSet0i\in{\text{Set}_{0}}. So by Lemma 7.5 (1) and the induction hypothesis we have Lastt(i)>Lastt(i+k(i))T~(i+k(i))1{\text{Last}}^{t}(i)>{\text{Last}}^{t}(i+k(i))\geqslant\tilde{T}(i+k(i))-1. Thus Lastt(i)T~(i+k(i)){\text{Last}}^{t}(i)\geqslant\tilde{T}(i+k(i)) and it makes sense to talk about yLastt(i)y^{{\text{Last}}^{t}(i)}.

In order to prove T~(i)=Lastt(i)+1\tilde{T}(i)={\text{Last}}^{t}(i)+1, it suffices to check

(7.9) yLastt(i)+1>yLastt(i)y^{{\text{Last}}^{t}(i)+1}>y^{{\text{Last}}^{t}(i)}

and for any t[Lastt(i)+1,t)t^{\prime}\in[{\text{Last}}^{t}(i)+1,t),

(7.10) yt+1(i)=yt(i).y^{t^{\prime}+1}(i)=y^{t^{\prime}}(i).

Since QLastt(i)Q^{{\text{Last}}^{t}(i)} visits ii, the inequality (7.9) follows from the definition of counter directly if iSet1Set2i\in{\text{Set}_{1}}\cup{\text{Set}_{2}} or iSet3i\in{\text{Set}_{3}} and L(ωLastt(i))<i+r(i)L(\omega^{{\text{Last}}^{t}(i)})<i+r(i). The remaining case that iSet3i\in{\text{Set}_{3}} and L(ωLastt(i))i+r(i)L(\omega^{{\text{Last}}^{t}(i)})\geqslant i+r(i) cannot happen due to the fact that Lastt(i)>Lastt(i+r(i)){\text{Last}}^{t}(i)>{\text{Last}}^{t}(i+r(i)) and Lemma 7.3. For (7.10), QtQ^{t^{\prime}} does not visit ii for t[Lastt(i)+1,t)t^{\prime}\in[{\text{Last}}^{t}(i)+1,t), so it follows that yt+1(i)=yt(i)y^{t^{\prime}+1}(i)=y^{t^{\prime}}(i) for any such tt^{\prime}. ∎

Proof of Lemma 7.6.

We finish the proof by checking all requirements on xx and zz. We’ve checked that xx is a good sequence.

We check that z(i)=yt(i)0z(i)=y^{t}(i)\geqslant 0 for all iSet1Set2i\in{\text{Set}_{1}}\cup{\text{Set}_{2}}. In the proof of Lemma 7.8, we’ve shown Lastt(i)T~(i+k(i)){\text{Last}}^{t}(i)\geqslant\tilde{T}(i+k(i)), so yt(i)yLastt(i)+1yLastt(i)+1yT~(i+k(i))+10y^{t}(i)\geqslant y^{{\text{Last}}^{t}(i)+1}\geqslant y^{{\text{Last}}^{t}(i)}+1\geqslant y^{\tilde{T}(i+k(i))}+1\geqslant 0.

To see why z(i)=yt(i)z(i)=y^{t}(i) is odd for iSet1Set2i\in{\text{Set}_{1}}\cup{\text{Set}_{2}}, note that by definition yT~(i+1)(i)=ω~T~(i+1)(i)1y^{\tilde{T}(i+1)}(i)=\tilde{\omega}^{\tilde{T}(i+1)}(i)-1. Also yt(i)yT~(i+1)(i)y^{t}(i)-y^{\tilde{T}(i+1)}(i) has the same parity as ω~t(i)ω~T~(i+1)(i)\tilde{\omega}^{t}(i)-\tilde{\omega}^{\tilde{T}(i+1)}(i). Combining these with ω~t(i)=ωt(i)=0\tilde{\omega}^{t}(i)=\omega^{t}(i)=0 proves yt(i)y^{t}(i) is odd.

Finally, we show Ax,zA_{x,z} occurs by checking every item of its definition: we’ve checked item (1) in the definition of zz above; item (2) holds because t<τExitt<\tau_{\text{Exit}}; item (3) follows from the lower bound on T~(i)\tilde{T}(i) in Lemma 7.8; item 4 follows from Lemma 7.5 (2) and Lemma 7.8. ∎

Next we prove Lemma 7.7.

Proof of Lemma 7.7.

We will estimate the probability inductively. We start with p=M~(x)p=\tilde{M}(x) and then progressively lower it until we get the full result.

For p=M~(x)p=\tilde{M}(x), x|[M~(x),a]\left.x\right|_{[\tilde{M}(x),a]} and z|[M~(x),a]\left.z\right|_{[\tilde{M}(x),a]}, define the jj-th iteration of the counter ys(M~(x))y^{s}(\tilde{M}(x)) to be the set of paths QsQ^{s} such that ys+1(M~(x))=jy^{s+1}(\tilde{M}(x))=j and L(ωs)M~(x)L(\omega^{s})\geqslant\tilde{M}(x), for any j[1,z(M~(x)]j\in[1,z(\tilde{M}(x)]. For each iteration of the counter, we may sample an infinite sequence of paths and reveal as many of them as needed. In each iteration we cannot have the first aM~(x)+1a-\tilde{M}(x)+1 paths all being excursions to their right; otherwise, the leftmost one in the configuration would exceed aa, which contradicts the definition of Ax,zA_{x,z} item 2. Since the probability of any path reaching a neighboring block is at most 2/a42/a^{4} (see the proof of Lemma 8.10), the probability of each path being an excursion to the right (including a long excursion to the right, but excluding the double-sided path and the failed re-arrival) is at least 1/21/a41/2-1/a^{4}. Thus we get the following upper bound on the probability of Ax,zA_{x,z}

(1(1/21/a4)M~(x)+a+1)z(M~(x)).\left(1-(1/2-1/a^{4})^{\,-\tilde{M}(x)+a+1}\right)^{z(\tilde{M}(x))}.

Suppose we have established the upper bound UBx,z,pU\!B_{x,z,p} for pp, x|[p,a]\left.x\right|_{[p,a]} and z|[p,a]\left.z\right|_{[p,a]}. Let p=max{j<p:x(j)=0}.p^{\prime}=\max\{j<p:x(j)=0\}. We will establish the bound UBx,z,p′′U\!B_{x,z,p^{\prime\prime}} for p′′p^{\prime\prime}, x|[p′′,a]\left.x\right|_{[p^{\prime\prime},a]} and z|[p′′,a]\left.z\right|_{[p^{\prime\prime},a]}, where p′′=pp^{\prime\prime}=p^{\prime} if pSet1Set3p^{\prime}\in{\text{Set}_{1}}\cup{\text{Set}_{3}} and p′′=p1p^{\prime\prime}=p^{\prime}-1 if pSet2p^{\prime}\in{\text{Set}_{2}}.

If pSet1p^{\prime}\in{\text{Set}_{1}}, i.e. r(p)=1r(p^{\prime})=1 and x(p1)x(p^{\prime}-1)\neq*, then by the definition of Ax,zA_{x,z} item 3 we know that every movement of a particle from pp^{\prime} in the time interval [T~(p),T~(p))[\tilde{T}(p),\tilde{T}(p^{\prime})) must be to the left. By the definition of the counter, there are

yT~(p)yT~(p)=z(p)(ω~s(i)1)z(p)y^{\tilde{T}(p^{\prime})}-y^{\tilde{T}(p)}=z(p^{\prime})-(\tilde{\omega}^{s}(i)-1)\geqslant z(p^{\prime})

many such movements. Thus we get an upper bound of

UBx,z,p 2z(p).U\!B_{x,z,p}\,2^{-z(p^{\prime})}.

If pSet2p^{\prime}\in{\text{Set}_{2}}, i.e. r(p)=1r(p^{\prime})=1 and x(p1)=x(p^{\prime}-1)=*, then the same analysis as in the last case pSet1p^{\prime}\in{\text{Set}_{1}} implies that there are at least z(p)z(p^{\prime}) many movements from pp^{\prime} during [T~(p),T~(p))[\tilde{T}(p),\tilde{T}(p^{\prime})), all of which are to the left. Moreover, by the definition of Ax,zA_{x,z} item 4, at the last such movement from pp^{\prime} the particle makes an excursion to the left (including a long excursion to the left, but excluding the double-sided path and failed re-arrival) that visits p1p^{\prime}-1 an even number of times. This happens with probability at most 1/61/6. In fact, for a usual random walk excursion starting from zero, the probability of going to the left and visiting site 1-1 even times is exactly 1/61/6. For our purpose, the random walk respawns at either the left or the right endpoint of the current block after reaching a neighboring block. In either case, a straightforward coupling argument gives the 1/61/6 upper bound. Therefore, we obtain a slightly improved bound of

UBx,z,p(1/6)(1/2)z(p)1.U\!B_{x,z,p}\,(1/6)(1/2)^{z(p^{\prime})-1}.

If pSet3,rp^{\prime}\in{\text{Set}_{3,r}}, i.e. r(p)=rr(p^{\prime})=r with r2r\geqslant 2, then by the definition of Ax,zA_{x,z} item 3, we know that every time a random walk path starts at a location in [p,p+r)[p^{\prime},p^{\prime}+r) during [T~(p),T~(p))[\tilde{T}(p),\tilde{T}(p^{\prime})), the first step either moves to the left or moves to the right without hitting p+rp^{\prime}+r. This has probability at most 11/2r1-1/2r. Also, every time during [T~(p),T~(p))[\tilde{T}(p),\tilde{T}(p^{\prime})) the particles moves from pp^{\prime} in a path that starts to the left of pp^{\prime}, the particle either moves to the left or moves to the right and does not hit p+rp^{\prime}+r before returning to pp^{\prime}, which also has probability at most 11/2r1-1/2r. Combining these with the definition of the counter, we get the bound

UBx,z,p(11/2r)z(p).U\!B_{x,z,p}(1-1/2r)^{z(p^{\prime})}.

Putting these together gives us the lemma. ∎

Finally, we complete the argument by proving Lemma 7.1.

Corollary 7.11.

If BB occurs and p,xp,x are defined as in Lemma 7.6, then x(p)=?/1x(p)=\,?/1 and

(7.12) M~(x)aN(ωt)1a(1ϵ)1,\tilde{M}(x)\geqslant a-N(\omega^{t})-1\geqslant a(1-\epsilon)-1,
(7.13) |Set1|+2|Set2|+2|Set3|aL(ωt)N(ωt)2a(12ϵ)2,|{\text{Set}_{1}}|+2|{\text{Set}_{2}}|+2|{\text{Set}_{3}}|\geqslant a-L(\omega^{t})-N(\omega^{t})-2\geqslant a(1-2\epsilon)-2,
(7.14) |Set3|r(r1)|Set3,r|N(ωt)aϵ,|{\text{Set}_{3}}|\leqslant\sum\nolimits_{r}(r-1)|{\text{Set}_{3,r}}|\leq N(\omega^{t})\leq a\epsilon,
(7.15) |Set?/1|:=|{j[p,a]:x(j)=?/1}|N(ωt)+2ϵa+2.|{\text{Set}_{\,?/1}}|:=|\{j\in[p,a]:x(j)=?/1\}|\leqslant N(\omega^{t})+2\leqslant\epsilon a+2.
Proof.

For (7.12), there are only ?/1?/1’s to the right of M~(x)\tilde{M}(x): at most N(ωt)1N(\omega^{t})-1 of them correspond to ??’s and 11’s in ωt\omega^{t}, and at most two of them come from zeros in ωt\omega^{t} by the choice of M~\tilde{M} in the definition of xx and Lemma 7.5 (1)(4). For (7.14), notice the convention that N~(x)Set3\tilde{N}(x)\in{\text{Set}_{3}} and r(N~(x))=M~(x)+1N~(x)r(\tilde{N}(x))=\tilde{M}(x)+1-\tilde{N}(x). ∎

Proof of Lemma 7.1.

By Lemma 7.6, it suffices to bound

x goodz(Ax,z),\sum_{x\text{ good}}\sum_{z}\mathbb{P}(A_{x,z}),

where the sum is taken over all good xx’s satisfying the bounds in Corollary 7.11 and all zSet0z\in\operatorname{\mathbb{N}}^{\text{Set}_{0}} satisfying the parity constraint in Lemma 7.6.

By (7.12), the leading term of the product in Lemma 7.7 is at most

(12.12aϵ)z(M~(x))(1-2.1^{-2-a\epsilon})^{z(\tilde{M}(x))}

for sufficiently large aa. Summing up over all possible values of z(M~(x))z(\tilde{M}(x)) gives us

(7.16) 11(12.12aϵ)52.1aϵ.\frac{1}{1-(1-2.1^{-2-a\epsilon})}\leqslant 5\cdot 2.1^{a\epsilon}.

From (7.13) and (7.14), we get

(7.17) |Set1|a(14ϵ)2|Set2|2.|{\text{Set}_{1}}|\geqslant a(1-4\epsilon)-2|{\text{Set}_{2}}|-2.

Finally, from (7.14) we have

(7.18) r(2r)|Set3,r|2rr|Set3,r|2r2(r1)|Set3,r|22aϵ.\prod_{r}(2r)^{|{\text{Set}_{3,r}}|}\leqslant 2^{\sum_{r}r|{\text{Set}_{3,r}}|}\leqslant 2^{\sum_{r}2(r-1)|{\text{Set}_{3,r}}|}\leqslant 2^{2a\epsilon}.

Fix xx and write m:=|Set2|m:=|{\text{Set}_{2}}|. By Lemma 7.7 and the distributive property, we have

z(Ax,z)\displaystyle\sum_{z}\mathbb{P}(A_{x,z})
\displaystyle\leqslant 52.1aϵiSet1(z1212z)iSet2(z11/3212z)riSet3,r(z0(112r)z)\displaystyle 5\cdot 2.1^{a\epsilon}\prod_{i\in{\text{Set}_{1}}}\left(\sum_{z\geqslant 1}2^{1-2z}\right)\prod_{i\in{\text{Set}_{2}}}\left(\sum_{z\geqslant 1}1/3\cdot 2^{1-2z}\right)\prod_{r}\prod_{i\in{\text{Set}_{3,r}}}\left(\sum_{z\geqslant 0}\left(1-\frac{1}{2r}\right)^{z}\right)
\displaystyle\leqslant 52.1aϵ(2/3)a(14ϵ)2m2(2/9)mr(2r)|Set3,r|\displaystyle 5\cdot 2.1^{a\epsilon}(2/3)^{a(1-4\epsilon)-2m-2}(2/9)^{m}\prod_{r}(2r)^{|{\text{Set}_{3,r}}|}
\displaystyle\leqslant 152.1aϵ(2/3)a(14ϵ)(1/2)m22aϵ\displaystyle 15\cdot 2.1^{a\epsilon}(2/3)^{a(1-4\epsilon)}(1/2)^{m}2^{2a\epsilon}
\displaystyle\leqslant 1550ϵa(2/3)a(1/2)m,\displaystyle 15\cdot 50^{\epsilon a}(2/3)^{a}(1/2)^{m},

where we’ve used the fact that all z(i)z(i)’s are odd for iSet1Set2i\in{\text{Set}_{1}}\cup{\text{Set}_{2}} and equations (7.16), (7.17) and (7.18).

Note that the bound we just developed only depends on m=|Set2|m=|{\text{Set}_{2}}|. For mm\in\operatorname{\mathbb{N}} let

𝒲(m):={x:x is good, x(p)=?/1,|Set2|=m and |Set?/1|ϵa+2}.\mathcal{W}(m):=\{x:x\text{ is good, }x(p)=\,?/1,|{\text{Set}_{2}}|=m\text{ and }|{\text{Set}_{?/1}}|\leqslant\epsilon a+2\}.

Write

Sn,k=i=0k(ni).S_{n,k}=\sum_{i=0}^{k}\binom{n}{i}.

Also note that by the binomial theorem, for a2ma\geqslant 2m and λ0\lambda\geqslant 0 we have

(7.19) (amm)(1/2)mλa2m(λ+1/2)am.\binom{a-m}{m}(1/2)^{m}\lambda^{a-2m}\leq(\lambda+1/2)^{a-m}.

Then by (7.15) we have

x goodz(Ax,z)\displaystyle\sum_{x\text{ good}}\sum_{z}\mathbb{P}(A_{x,z}) =\displaystyle= mx𝒲(m)z(Ax,z)\displaystyle\sum_{m}\sum_{x\in\mathcal{W}(m)}\sum_{z}\mathbb{P}(A_{x,z})
\displaystyle\leqslant maSa,ϵa+1(amm)2ϵa1550ϵa(2/3)a(1/2)m\displaystyle\sum_{m}aS_{a,\epsilon a+1}\binom{a-m}{m}2^{\epsilon a}\cdot 15\cdot 50^{\epsilon a}(2/3)^{a}(1/2)^{m}
=\displaystyle= 102ϵaSa,ϵa15a2(2/3)am(amm)(1/2)m\displaystyle 10^{2\epsilon a}S_{a,\epsilon a}\cdot 15a^{2}(2/3)^{a}\sum_{m}\binom{a-m}{m}(1/2)^{m}
\displaystyle\leqslant 102ϵaSa,ϵa15a2(2/3)am(7/4)am(4/5)a2m\displaystyle 10^{2\epsilon a}S_{a,\epsilon a}\cdot 15a^{2}(2/3)^{a}\sum_{m}(7/4)^{a-m}(4/5)^{a-2m}
\displaystyle\leqslant 102ϵaSa,ϵa150a2(14/15)a,\displaystyle 10^{2\epsilon a}S_{a,\epsilon a}\cdot 150a^{2}(14/15)^{a},

where in the second last inequality, we use (7.19) by picking the suitable λ=5/4\lambda=5/4.

We complete the proof of Lemma 7.1 by taking a small enough ϵ\epsilon. Indeed, recall the Chernoff bound

logSa,ϵaH(ϵ)a\log S_{a,\epsilon a}\leqslant H(\epsilon)a

where H()H(\cdot) is the binary entropy function H(x)=xlogx(1x)log(1x)H(x)=-x\log x-(1-x)\log(1-x). For ϵ=1/200\epsilon=1/200,

log(14/15)+2ϵlog10+H(ϵ)<1100,\log(14/15)+2\epsilon\log 10+H(\epsilon)<-\frac{1}{100},

so the above probability is upper bounded by exp(a/100)\exp(-a/100) for all aa sufficiently large. ∎

8. Single block estimate

Using the results of the previous sections, which show that the carpet process ω\omega is well behaved in terms of the number of ?’s and 1s, we return to the main task of bounding the probability that a particle is frozen and proving Lemma 4.6.

Define

A={L(ω)ϵa and N(ω)>ϵa}Ω.A=\{L(\omega)\leqslant\epsilon a\text{ and }N(\omega)>\epsilon a\}\subset\Omega.

Recall

Base=01????\text{Base}=01??\cdots??
 Exit=000000\text{ Exit}=0000\cdots 00
τExit=inf{t0:ωt=Exit}\tau_{\text{Exit}}=\inf\{t\geqslant 0:\omega^{t}=\text{Exit}\}

as well as the definition of an ϵ\epsilon-Base state.

Our first lemma is obtained by analyzing the bias in the process N(ωt)N(\omega^{t}). It says that starting with a large enough N(ω0)N(\omega_{0}), the process is much more likely to return to a state L(ω)ϵaL(\omega)\leqslant\epsilon a than become frozen.

Lemma 8.1.

For any state ω0A\omega_{0}\in A and sufficiently large aa,

¯ω0(τExit<a3inf{t>0:L(ωt)ϵa})e13106a.\overline{\mathbb{P}}_{\omega_{0}}(\tau_{\text{Exit}}<a^{3}\wedge\inf\{t>0:L(\omega^{t})\leqslant\epsilon a\})\leqslant e^{-\frac{1}{3}10^{-6}\sqrt{a}}.
Proof.

Consider the value of

ΔtN:=N(ωt+1)N(ωt)=(N(ωt+1)N(ωt))+(N(ωt+1)N(ωt+1)).\Delta_{t}N\vcentcolon=N(\omega^{t+1})-N(\omega^{t})=(N(\omega^{t+1}_{\ast})-N(\omega^{t}))+(N(\omega^{t+1})-N(\omega^{t+1}_{\ast})).

Let (Qt):=Ltmin(Range(Qt))\ell(Q^{t}):=L^{t}-\min({\text{Range}}(Q^{t})) be the maximum distance reached by the random walk path QtQ^{t} to its left. By the definition of the ‘refresh’ step, the first term

N(ωt+1)N(ωt)((Qt)Lt)2.N(\omega_{\ast}^{t+1})-N(\omega^{t})\geqslant(\ell(Q^{t})\wedge L^{t})-2.

When Lt>ϵaL^{t}>\epsilon a and (Qt)>0\ell(Q^{t})>0, this is at least ((Qt)ϵa)2(\ell(Q^{t})\wedge\epsilon a)-2; otherwise, we have the lower bound 2-2. Using Lemma 6.18, the second term

N(ωt+1)N(ωt+1)Geo(p)1,N(\omega^{t+1})-N(\omega^{t+1}_{\ast})\succ-\text{Geo}(p)-1,

where p=15/6p=1-\sqrt{5/6} and \succ is stochastic domination.

Combining both estimates, we obtain that for t<inf{s>0:L(ωs)ϵa}t<\inf\{s>0:L(\omega^{s})\leqslant\epsilon a\}, N(ωt)N(ω0)N(\omega^{t})-N(\omega^{0}) stochastically dominates a sum of the form

St=i=1Bt1Zii=1t(Yi+3),S_{t}=\sum_{i=1}^{B_{t-1}}Z_{i}-\sum_{i=1}^{t}(Y_{i}+3),

where Bt1B_{t-1}\sim Binomial(t1,1/2)(t-1,1/2), YiY_{i}\sim Geo(p)(p) are iid, and ZiZ_{i} are iid positive variables with tail (Z=q)12q2\mathbb{P}(Z=q)\geqslant\frac{1}{2q^{2}} for q[1,ϵa]q\in[1,\epsilon a]. Our aim is to show that for t<a3t<a^{3}, StϵaS_{t}\geqslant-\epsilon a with high probability, which implies that with the same probability, for t<a3inf{s>0:L(ωs)ϵa}t<a^{3}\wedge\inf\{s>0:L(\omega^{s})\leqslant\epsilon a\}, N(ωt)>0N(\omega^{t})>0, i.e. τExit\tau_{\text{Exit}} has not occurred.

To prove this, first observe that throwing out the positive sum in StS_{t} and using a tail bound for a sum of Geometric random variables,

(8.2) (Sϵa/100<ϵa/2)(i=1ϵa/100Yi>ϵa/3)exp(ϵa/100).\mathbb{P}(S_{\epsilon a/100}<-\epsilon a/2)\leqslant\mathbb{P}(\sum_{i=1}^{\epsilon a/100}Y_{i}>\epsilon a/3)\leqslant\exp(-\epsilon a/100).

To see that N(ωt)N(\omega^{t}) stays away from 0 at later times, we carry out the following concentration bound for the sum of ZiZ_{i}. Observe that by standard tail bounds for Binomials (e.g. a Chernoff bound), for any q=1,2,,a1/4q=1,2,\ldots,a^{1/4} and any t>ϵa/100t>\epsilon a/100,

(8.3) (#{iBt1:Zi=q}112tq2)\displaystyle\mathbb{P}\left(\#\{i\leqslant B_{t-1}:Z_{i}=q\}\leqslant\frac{1}{12}tq^{-2}\right) (Bin(t1,1212q2)112tq2)\displaystyle\leqslant\mathbb{P}(\text{Bin}(t-1,\,\frac{1}{2}\cdot\frac{1}{2}q^{-2})\leqslant\frac{1}{12}tq^{-2})
(8.4) exp(tq2/72)\displaystyle\leqslant\exp(-tq^{-2}/72)
(8.5) exp(ϵa/7200).\displaystyle\leqslant\exp(-\epsilon\sqrt{a}/7200).

By a union bound over all such qq, none of these events occurs with probability at least 1exp(a2106)1-\exp(-\frac{\sqrt{a}}{2*10^{6}}) if aa is sufficiently large, and if none of them occurs, we have

i=1Bt1Ziq=1a1/4112tq1150tloga.\sum_{i=1}^{B_{t-1}}Z_{i}\geqslant\sum_{q=1}^{a^{1/4}}\frac{1}{12}tq^{-1}\geqslant\frac{1}{50}t\log a.

For the negative part of StS_{t}, again using a similar tail bound for a sum of Geometrics, for any t>ϵa/100t>\epsilon a/100,

(i=1t(Yi+3)t(3+10p1))exp(a/104).\mathbb{P}\left(\sum_{i=1}^{t}(Y_{i}+3)\geqslant t(3+10p^{-1})\right)\leqslant\exp(-a/10^{4}).

Combining these bounds, since we can take sufficiently large ae6000a\geqslant e^{6000} so that 150log(a)>3+10p1\frac{1}{50}\log(a)>3+10p^{-1}, we obtain for any t>ϵa/100t>\epsilon a/100,

(St<ϵa)exp(12106a).\mathbb{P}(S_{t}<-\epsilon a)\leqslant\exp(-\frac{1}{2}10^{-6}\sqrt{a}).

Taking a union bound over all values ta3t\leqslant a^{3} gives the result.

The next lemma gives a lower bound on the frequency at which the carpet process ωt\omega^{t} refreshes by returning to the Base state.

Lemma 8.6.

The following hold for aa sufficiently large. If ω0\omega_{0} satisfies L(ω0)aL(\omega_{0})\leqslant a,

(8.7) ¯ω0(ω1=Base or ω2=Base)1600a2.\underline{\mathbb{P}}_{\omega_{0}}(\omega^{1}=\text{Base}\text{ or }\omega^{2}=\text{Base})\geqslant\frac{1}{600a^{2}}.

Additionally,

(8.8) ¯ω0(τBase>a3)exp(a/2000),\overline{\mathbb{P}}_{\omega_{0}}(\tau_{\text{Base}}>a^{3})\leqslant\exp(-a/2000),

where τBase=inf{t>0:ωt=Base}.\tau_{\text{Base}}=\inf\{t>0:\omega^{t}=\text{Base}\}.

Proof.

The second claim follows immediately by repeated application of the first claim, bounding the probability of hitting the Base state independently for every successive pair of times:

¯ω0(τBase>a3)(11600a2)a3/2exp(a/2000).\overline{\mathbb{P}}_{\omega_{0}}(\tau_{\text{Base}}>a^{3})\leqslant(1-\frac{1}{600a^{2}})^{a^{3}/2}\leqslant\exp(-a/2000).

One way to return to the base state is by first taking an excursion to the left beyond 0 and not matching the parity at 1 – this makes L(ω1)=1L(\omega^{1})=1 – and then, at the next step, taking an excursion to the right beyond aa and not matching the parity at 2. Recall that the probability for a simple random walk excursion to reach distance at least \ell^{\prime} is 1\frac{1}{\ell^{\prime}}, so the probability for an excursion to reach distance [a,a2)\ell^{\prime}\in[a,a^{2}) is at least 12a\frac{1}{2a}. Note that by the choice of KK, an excursion that reaches maximum distance [a,a2)\ell^{\prime}\in[a,a^{2}) visits every point in the block but does not reach any neighboring block. Thus if L(ω0)2L(\omega_{0})\geqslant 2, then by Lemma 6.3

¯ω0(ω2=Base)(1212a16)21600a2.\underline{\mathbb{P}}_{\omega_{0}}(\omega^{2}=\text{Base})\geqslant\left(\frac{1}{2}\cdot\frac{1}{2a}\cdot\frac{1}{6}\right)^{2}\geqslant\frac{1}{600a^{2}}.

If L(ω0)=1L(\omega_{0})=1, only the second step is necessary. ∎

Now we are ready to state Lemma 8.9 which is the culmination of the previous two sections. It shows that in a typical scenario, the carpet process keeps refreshing itself by returning to the Base rather than become frozen.

Lemma 8.9.

For aa sufficiently large,

¯ϵ-Base(τExit<τBase)e14106a\overline{\mathbb{P}}_{\epsilon\text{-Base}}(\tau_{\text{Exit}}<\tau_{Base})\leqslant e^{-\frac{1}{4}10^{-6}\sqrt{a}}
Proof.

By Lemma 8.6, the process hits the Base in time at most a3a^{3} with exponentially high probability. So it suffices to bound the event that τExit<a3\tau_{\text{Exit}}<a^{3}.

If τExit<a3\tau_{\text{Exit}}<a^{3} occurs, then either

  1. (1)

    there exists a time t<τExitt<\tau_{\text{Exit}} with L(ωt)ϵaL(\omega^{t})\leqslant\epsilon a and N(ωt)ϵaN(\omega^{t})\leqslant\epsilon a or

  2. (2)

    there exists a time t<τExit<a3t<\tau_{\text{Exit}}<a^{3} with ωtA\omega^{t}\in A and L(ωs)>ϵaL(\omega^{s})>\epsilon a for any ss such that t<s<τExitt<s<\tau_{\text{Exit}}.

By Lemma 7.1 the first event occurs with exponentially small probability in aa. By Lemma 8.1 and a union bound over all t<a3t<a^{3}, the probability of the second event is exponentially small in a\sqrt{a}. Combining these estimates, we obtain that the process reaches the Exit after a3a^{3} steps with exponentially high probability. ∎

8.1. Proof of Lemma 4.6

Following [9], we first re-parameterize the process by the number of attempted emissions from block ii, instead of the number of additional input particles from the right. Each attempted emission, as a portion of the carpet/hole toppling procedure described in Section 3.2, is defined as the evolution until the hot particle reaches a new block or until the hot particle becomes frozen.

Denote by Left(k)(k) and F(k)F(k) the number of particles emitted to the left from block ii and the number of frozen particles in block ii right after the kkth attempted emission respectively (a slight abuse of notation). Let e(0)=0e(0)=0 and e(k)e(k) denote the number of steps taken by the auxiliary carpet process ωt\omega^{t} until the completion of the kkth attempted emission. Note that e(k)e(k) counts steps of the chain ωt\omega^{t}, not individual topplings in the carpet/hole procedure.

The following lemma gives a conclusion in the same spirit as Lemma 8.9, but for a process not necessarily started from the Base or ϵ\epsilon-Base state.

Lemma 8.10.

The following holds for aa sufficiently large. If the initial carpet (η,ω)(\eta,\omega) is valid, for any k2k\geqslant 2, almost surely,

(8.11) (η,ω)(F(k)=1|i1)8a1.\mathbb{P}_{(\eta,\omega)}(F(k)=1|\mathcal{F}_{i-1})\leqslant 8a^{-1}.
Proof.

We consider three cases.

Case I: F(k2)=0F(k-2)=0 and F(k1)=0F(k-1)=0. Note that the probability of each attempted emission being followed by a failed re-arrival is at most a/K=1/a3a/K=1/a^{3}. In the following, we also assume that Qe(k2)1Q^{e(k-2)-1} and Qe(k1)1Q^{e(k-1)-1} are not failed re-arrivals.

Under those assumptions, during the k1k-1th and kkth attempted emissions, the carpet process keeps performing random walk excursions from the hole, until one such excursion reaches a neighboring block. Recall that the probability that a random walk excursion reaches maximum distance at least ll is 1l\frac{1}{l}, and the distance from any point in block ii to a neighboring block is at most KK and at least K/2K/2. Thus each excursion of the hot particle in block ii has probability at least a4a^{-4} and at most 2a42a^{-4} of reaching a neighboring block, uniformly over the initial position of the excursion (inside block ii). Elementary estimates give that

(8.12) ¯ω0(e(k1)e(k2)<a3)a32a42a1\overline{\mathbb{P}}_{\omega_{0}}(e(k-1)-e(k-2)<a^{3})\leqslant{a^{3}}\cdot 2a^{-4}\leq 2a^{-1}

and

(8.13) ¯ω0(e(k)e(k2)>2a5)\displaystyle\overline{\mathbb{P}}_{\omega_{0}}(e(k)-e(k-2)>2a^{5}) (1a4)2a5+2a(1a4)2a51\displaystyle\leqslant(1-a^{-4})^{2a^{5}}+2a(1-a^{-4})^{2a^{5}-1}
(8.14) a1.\displaystyle\leq a^{-1}.

Following the comment in Section 6.3, we consider the auxiliary carpet process started at e(k2)e(k-2), and due to the assumption on Qe(k1)1Q^{e(k-1)-1} all results since Section 6 apply until time e(k)e(k). By Lemma 8.6, for any k2k\geqslant 2 we have

(8.15) ¯ω0(ωtBase, t[e(k2),e(k2)+a3])exp(a/2000).\overline{\mathbb{P}}_{\omega_{0}}(\omega^{t}\neq\text{Base, }t\in[e(k-2),e(k-2)+a^{3}])\leqslant\exp(-a/2000).

By Lemma 8.9 and the previous line, since there are at most 2a52a^{5} returns to the Base state up to time 2a52a^{5}, for any k2k\geqslant 2,

(8.16) ¯ω0(ωt=Exit for some t[e(k2)+a3,e(k2)+2a5])2a5exp(14106a).\overline{\mathbb{P}}_{\omega_{0}}(\omega^{t}=\text{Exit for some }t\in[e(k-2)+a^{3},e(k-2)+2a^{5}])\leqslant 2a^{5}\exp(-\frac{1}{4}10^{-6}\sqrt{a}).

Combining all these estimates and taking aa sufficiently large gives an upper bound 4a14a^{-1} in the first case.

Case II: F(k2)=1F(k-2)=1. By 3, we have e(k1)=e(k2)+1e(k-1)=e(k-2)+1, cf. (8.12), and in the (k1)(k-1)th attempted emission, we topple the hot particle started from 0 or aa until it reaches a neighboring block. Since we’ve chosen K=a4K=a^{4}, the probability that the hot particle reaches a neighboring block without visiting the entire block [0,a][0,a] is at most a/K=1/a3a/K=1/a^{3}: it must arrive at one endpoint of [0,a][0,a] first, and then reach a neighboring block without touching the other endpoint. By Lemma 6.6 for type 1 paths,

(8.17) ¯ω0(ωe(k1) is not ϵ-Base[0,a]Range(Qe(k1)1))(5/6)ϵaexp(a/1200).\overline{\mathbb{P}}_{\omega_{0}}(\omega^{e(k-1)}\text{ is not }\epsilon\text{-Base}\mid[0,a]\subset\text{Range}(Q^{e(k-1)-1}))\leqslant(5/6)^{\epsilon a}\leqslant\exp(-a/1200).

Moreover, a similar argument using an upper tail bound on e(k)e(k1)e(k)-e(k-1) and Lemma 8.9 as in Case I shows that

(8.18) ¯ω0(F(k)=1ωe(k1) is ϵ-Base)a5exp14106a.\overline{\mathbb{P}}_{\omega_{0}}(F(k)=1\mid\omega^{e(k-1)}\text{ is }\epsilon\text{-Base})\leqslant a^{5}\exp{\frac{1}{4}10^{-6}\sqrt{a}}.

Combining all these, we obtain an upper bound 2a12a^{-1} for sufficiently large aa in the second case.

Case III: F(k1)=1F(k-1)=1. By 3 and Lemma 6.6, with probability at least 12/a31-2/a^{3} we have ωe(k)\omega^{e(k)} is not an all-zero configuration and thus F(k)=0F(k)=0.

Taking a union bound over the three cases completes the proof. ∎

Proof of Lemma 4.6.

We use Lemma 8.10 to prove the single block estimate. We will focus on the first statement because the second one will be shown in (8.23) as an intermediate step. Fix an l0l\geqslant 0, and block i{0,,n1}i\in\{0,\ldots,n-1\}. Our aim is to uniformly bound the expression

(8.19) 𝐄[s2ecFii(s)1{Lii(s)=l}|i1].\mbox{$\bf E$}\left[\sum_{s\geqslant 2}e^{cF_{i}^{i}(s)}1\{L_{i}^{i}(s)=l\}\middle|\mathcal{F}_{i-1}\right].

Note that each particle added at site iK+aiK+a causes at least one attempted emission in block ii (possibly more if additional particles arrive from the left of block ii as a result). Thus the sum is upper bounded by

(8.20) 𝐄~[k2ecF(k)1{Left(k)=l}],\widetilde{\mbox{$\bf E$}}\left[\sum_{k\geqslant 2}e^{cF(k)}1\{\text{Left}(k)=l\}\right],

where we use 𝐄~\widetilde{\mbox{$\bf E$}} for the conditional expectation w.r.t. i1\mathcal{F}_{i-1}. Set

(8.21) τl=inf{k0:Left(k)=l},\tau_{l}=\inf\{k\geqslant 0:\text{Left}(k)=l\},

and re-write the latter sum (over k2k\geqslant 2) as

(8.22) 𝐄~[k=τl2τl+11ecF(k)]=𝐄~[k01{τl+1(τl2)>k}ecF((τl2)+k)].\widetilde{\mbox{$\bf E$}}\left[\sum_{k=\tau_{l}\vee 2}^{\tau_{l+1}-1}e^{cF(k)}\right]=\widetilde{\mbox{$\bf E$}}\left[\sum_{k\geqslant 0}1\{\tau_{l+1}-(\tau_{l}\vee 2)>k\}e^{cF((\tau_{l}\vee 2)+k)}\right].

We claim that for any k,l0k,l\geqslant 0,

(8.23) ~(τl+1τlk)(2/3)k/2\widetilde{\mathbb{P}}(\tau_{l+1}-\tau_{l}\geqslant k)\leqslant(2/3)^{\lfloor k/2\rfloor}

and

(8.24) 𝐄~[ecF((τl2)+k)]1+100eca1(k+log(a)).\widetilde{\mbox{$\bf E$}}[e^{cF((\tau_{l}\vee 2)+k)}]\leqslant 1+100e^{c}a^{-1}(k+\log(a)).

For (8.23), note that either the k+1k+1st attempted emission is a successful emission, or it is frozen in which case the k+2k+2nd attempted emission is emitted to a neighboring block with probability 1 by 3. By gambler’s ruin, the probability to be emitted to the right in either case is at most K2Ka2/3\frac{K}{2K-a}\leqslant 2/3. Thus

(8.25) ~(Left(k+2)=Left(k))2/3.\widetilde{\mathbb{P}}(\text{Left}(k+2)=\text{Left}(k))\leqslant 2/3.

This proves the first claim.

For (8.24), when l=0l=0, we have τl=0\tau_{l}=0 and the claim follows directly from Lemma 8.10. For l2l\geqslant 2, note that τlτl2+2\tau_{l}\geqslant\tau_{l-2}+2. By (8.23),

(8.26) ~(τlτl2>k)2(23)k/4\widetilde{\mathbb{P}}(\tau_{l}-\tau_{l-2}>k^{\prime})\leqslant 2(\frac{2}{3})^{\lfloor k^{\prime}/4\rfloor}

Moreover, Lemma 8.10 implies that

(8.27) ~(F(j)=1 for some j[τl2+2,τl2+k+k])8(k+k)a1.\widetilde{\mathbb{P}}(F(j)=1\text{ for some }j\in[\tau_{l-2}+2,\tau_{l-2}+k^{\prime}+k])\leqslant 8(k+k^{\prime})a^{-1}.

Combining these two estimates into a union bound by setting k=12log(a)k^{\prime}=\lceil 12\log(a)\rceil yields the result. When l=1l=1, a similar argument works by replacing τl2\tau_{l-2} with 0. This proves (8.24).

Now we turn back to the task of bounding the sum (8.22). Putting the above bounds (8.23) and (8.24) together, we get

(8.28) 𝐄~[1{τl+1(τl2)>k}ecF((τl2)+k)]min{1+100eca1(k+log(a)),(2/3)k/2ec}.\widetilde{\mbox{$\bf E$}}\left[1\{\tau_{l+1}-(\tau_{l}\vee 2)>k\}e^{cF((\tau_{l}\vee 2)+k)}\right]\leqslant\min\{1+100e^{c}a^{-1}(k+\log(a)),(2/3)^{\lfloor k/2\rfloor}e^{c}\}.

Splitting the sum (8.22) at k=6log(a)k=\lceil 6\log(a)\rceil, and using both bounds, the original sum is bounded by

(8.29) c=7log(a)+2500eclog2(a)a1c^{\prime}=7\log(a)+2500e^{c}\log^{2}(a)a^{-1}

Finally, we pick a=e1.1ca=e^{1.1c} and large enough c4×104c\geqslant 4\times 10^{4} so that the condition δc=0.0004c>logc\delta c=0.0004c>\log c^{\prime} holds, which proves Lemma 4.6 for large enough aa.

It remains to obtain the explicit values for aa and KK. Note that throughout Sections 7 and 8, we’ve taken aa sufficiently large multiple times. Two sharpest constraints, however, are ae6000a\geqslant e^{6000} in the proof of Lemma 8.1 to achieve the bias of the random walk, and ae4.4×104a\geqslant e^{4.4\times 10^{4}} above for Lemma 4.6 to work under a very small δ=.0004\delta=.0004. Thus, we conclude that Lemma 4.6 holds for ae4.4×104a\geqslant e^{4.4\times 10^{4}} and K=a4e1.76×105.K=a^{4}\geqslant e^{1.76\times 10^{5}}.

References

  • [1] Amine Asselah, Nicolas Forien, and Alexandre Gaudillière. The critical density for activated random walks is always less than 1. arXiv preprint arXiv:2210.04779, 2022.
  • [2] P. Bak, C. Tang, and K. Wiesenfeld. Self-organized criticality: An explanation of the 1/f1/f noise. Phys. Rev. Lett., 59:381, 1987.
  • [3] Riddhipratim Basu, Shirshendu Ganguly, and Christopher Hoffman. Non-fixation for conservative stochastic dynamics on the line. Comm. Math. Phys., 358:1151–1185, 2018.
  • [4] Riddhipratim Basu, Shirshendu Ganguly, Christopher Hoffman, and Jacob Richey. Activated random walk on a cycle. Ann. Inst. Henri Poincaré Probab. Stat., 55:1258–1277, 2019.
  • [5] Ofer Biham, Erel Milshtein, and Ofer Malcai. Evidence for universality within the classes of deterministic and stochastic sandpile models. Phys. Rev. E, 63:061309, May 2001.
  • [6] Deepak Dhar. The abelian sandpile and related models. Physica A: Statistical Mechanics and its applications, 263(1-4):4–25, 1999.
  • [7] A. Fey and R. Meester. Critical densities in sandpile models with quenched or annealed disorder. Markov Process. Related Fields, 21:57–83, 2015. arXiv.
  • [8] Anne Fey, Lionel Levine, and David B. Wilson. Driving sandpiles to criticality and beyond. Phys. Rev. Lett., 104:145703, 2010.
  • [9] Christopher Hoffman, Jacob Richey, and Leonardo T Rolla. Active phase for activated random walk on \mathbb{Z}. Comm. Math. Phys., to appear, 2023. arXiv preprint arXiv:2009.09491.
  • [10] Christopher Hoffman and Vladas Sidoravicius. Directed activated random walks, 2004. Unpublished.
  • [11] Yiping Hu. Active phase for activated random walk on 2\mathbb{Z}^{2}. arXiv preprint arXiv:2203.14406, 2022.
  • [12] Subhrangshu Sekhar Manna. Two-state model of self-organized criticality. Journal of Physics A: Mathematical and General, 24(7):L363, 1991.
  • [13] Miguel A Munoz, Ronald Dickman, Romualdo Pastor-Satorras, Alessandro Vespignani, and Stefano Zapperi. Sandpiles and absorbing-state phase transitions: recent results and open problems. In AIP Conference Proceedings, volume 574, pages 102–110. AIP, 2001.
  • [14] Moumanti Podder and Leonardo T. Rolla. Uniform threshold for fixation of the stochastic sandpile model on the line. arXiv preprint arXiv:2001.04268, 2020.
  • [15] Leonardo T Rolla. Activated random walks on d\mathbb{Z}^{d}. Probability Surveys, 17:478–544, 2020.
  • [16] Leonardo T. Rolla and Vladas Sidoravicius. Absorbing-state phase transition for driven-dissipative stochastic dynamics on {\mathbb{Z}}. Invent. Math., 188(1):127–150, 2012.
  • [17] Leonardo T. Rolla, Vladas Sidoravicius, and Olivier Zindy. Universality and sharpness in activated random walks. Ann. Henri Poincaré, 20:1823–1835, 2019.