Active Phase for the Stochastic Sandpile on
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 criticality1. 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 defined as follows. At each time, the state of the system is given by a function , where represents the number of particles at site at time . Sites such that are considered stable while sites with are unstable. Unstable sites topple independently at exponential rate 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 the function is eventually constant and stays active otherwise. The main result of [16] about the SSM is that if the initial distribution is given by i.i.d. Poisson random variables with parameter , then there exists a critical value such that the system locally fixates almost surely if and stays active almost surely in , see [16, Theorem 1]. The argument that is essentially trivial and comes down to showing that for trivial reasons if then the site topples infinitely many times, while the argument that 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 .
Theorem 1.1.
For any independent starting configuration with multiple particles at some sites a.s., the critical value for the SSM is strictly less than . In fact, .
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 [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 , i.e. counts the number of particles at site . To run the dynamics on a finite interval , every site is assigned an infinite sequence of iid instructions, each taking one of the two possible values or with equal probability, where and are operators on the space of particle configurations that act via
and
In the usual discrete-time setup, the system evolves one step by choosing a site with , and applying the two stack instructions where is such that all instructions for have already been used, but has not. In this version, particles always topple in pairs. For an initial particle configuration and a sequence of sites to be toppled, let
be the operator obtained by performing all topplings of in order. The odometer of the pair is the function which records the total number of times each site was toppled, i.e.
Such a sequence is called legal for if for every
The odometer function is universal in the sense that if are any two legal toppling sequences for a configuration on interval such that and have no sites with at least two particles, then is a permutation of and thus . 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 in Section 1. Define
where the supremum is over all finite intervals and all legal toppling sequences for the configuration on .
Lemma 2.1 ([16, Lemma 4]).
Suppose the initial state is a translation-invariant, ergodic distribution on with finite density , then
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, , the number of particles per site, and a parity sequence . A site is legal for a pair of configurations if either or . At each step of the half-toppling scheme, a legal site is chosen for the current pair of configurations, and the first unused instruction acts upon the pair by sending a single particle at to a uniform random neighbor and adding 1 (mod 2) to . A half-toppling sequence of sites is legal for if the chosen site is legal for every step, that is, is legal for
for every
One key fact about this version of the dynamics is that it provides a lower bound on the total odometer. Recall the odometer function for the classical dynamics, and for any sequence of half-topplings, let denote the corresponding half-toppling odometer function, after performing all half-topplings in started from the configuration . We have:
Lemma 2.2.
(Abelian lemma for half-topplings) Fix a particle configuration on a finite interval . Let be any legal half-toppling sequence for , and let be any legal toppling sequence for (in the sense of Section 2.1) such that has no site with at least two particles. Then for any ,
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 .
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 and . The procedure described in this section is well-defined for any positive integer , although later in Proposition 3.4 and Lemma 4.6 we will need to choose a large enough . 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 , a pair of particle configuration and parity sequence on is valid if
for some and some satisfying
(3.2) |
The subinterval is called the th block for , 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 . In order to perform the carpet/hole toppling procedure starting from , we need to identify the special site hole in each block based on , as well as classify the particles of into several categories. Note that the definitions given in the current Section 3.1 only apply to the starting configuration . 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 . For each , if block has a position with no particle, then the empty site is the hole of block . If block has a particle in every position, the leftmost site in that block with is declared the hole. If there is no such , then declare to be the position of the hole.
With the definition of the holes, we allocate the particles in into several types. By definition, each site in (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 are free particles.
In the configuration , free particles are either in a hole or at an endpoint of a block. Free particles are further divided into two groups. For each , if block has and for all , then the hole was defined to be at and we declare an arbitrary (free) particle at 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 . Fix a valid configuration . 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:
-
(L1)
We follow a leftmost priority policy for choosing the hot particle, which implies Lemma 4.4 below. Find the leftmost block 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 , we choose the one inside the hole to be the hot particle if there is one. Otherwise, the thawed particles are at the boundary or , 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 contains a frozen particle.
-
(L2)
Suppose block does not contain a frozen particle. If the hot particle is at the hole but the hole is not the leftmost position with parity value , then go directly to 2a or 2b. Otherwise, repeatedly topple the hot particle until it returns to the hole of block , or hits either or , which could be a boundary point of a neighboring block or a boundary point of the interval . There are three cases:
-
(L2a)
Suppose the hot particle returned to the hole of block and there exists some position in the block with odd parity. Find the leftmost position in block with parity value . Declare the hot particle at the hole a carpet particle, move the hole in block to position , and declare the carpet particle at a thawed and hot particle. Return to 2.
-
(L2b)
Suppose the hot particle returned to the hole of block , but there is no site in block with odd parity. Turn the hot particle at the hole into a carpet particle, move the hole to position , and declare the carpet particle at a frozen free particle. Return to 1.
-
(L2c)
If the hot particle reached or , declare it no longer hot but still free and thawed. Return to 1.
-
(L2a)
-
(L3)
If block does contain a frozen particle, then every site in block has a particle which is not the hot particle. Repeatedly topple the hot particle until it reaches or . Then declare it no longer hot but still free and thawed. If block now has the leftmost site with parity value , then turn the frozen free particle at into a carpet particle, move the hole to , and declare the carpet particle at free and thawed. Return to 1.
The block size 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 and are preserved by the half-toppling sequence, which can be checked by induction.
-
(P1)
Each block has exactly one hole which is located at some site .
-
(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 in that block with parity value . If there is no site in block with odd parity, then we make sure the hole is at and contains a frozen particle.
-
(P3)
There is exactly one carpet particle at every site in except for the holes.
-
(P4)
All free particles except the hot particle are in a hole, or at a site or for some .
-
(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 . 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.
-
(F1)
All half-topplings performed during this procedure are legal.
-
(F2)
After the first free particle has been designated hot in block , all free particles in block except the hot particle (if there is one) are at or .
-
(F3)
A free particle designated hot in a block with a frozen particle reaches a neighboring block before being declared not hot.
-
(F4)
The number of free particles is conserved during the procedure.
-
(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 . Also, there is at most one particle (either carpet or frozen free particle) at every site inside .
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 be a valid configuration on . Run carpet/hole dynamics with initial condition until partial stabilization when there are no more thawed particles inside . Denote its law by . For , define to be the number of frozen free particles remaining in the blocks at the end of the carpet/hole dynamics on . Also let be the (half-toppling) odometer function at site resulting from the carpet/hole toppling procedure on , and define
(3.3) |
for some constant . The purpose of the event 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 and .
Proposition 3.4.
For and any , there exist and such that the following hold for large enough . If is valid and the total number of particles , then we have
(3.5) |
In particular,
(3.6) |
4. Filtrations and coarse-grained particle flows
Fix any initial configuration on . Consider one iteration of the carpet/hole dynamics on an interval with 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 it is in as the hot block. For each in a transit region, we split the stack instructions for into two independent stacks of independent instructions, . The hot particle toppled at site uses instructions from the stack if the nearest block to the left of is the hot block, and from the stack if the nearest block to the right of is the hot block. Sites in a block have just a single instruction stack, . We work with the filtration of all the stack instructions decorated by blocks , i.e.
(4.1) |
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 and let
(4.2) |
be the configuration with additional particles at the right edge of block . We define the following ‘coarse-grained counters’:
Definition 4.3.
For each , run carpet/hole dynamics started from configuration until there are no legal topplings of free particles in , the first blocks. Define
-
•
for any , the total number of times during this toppling procedure that a free particle goes left using an instruction from the stack ;
-
•
for any , the number of frozen particles in block at the end of the toppling procedure (either 0 or 1 by 5);
-
•
and . Set .
Note that . Our leftmost priority policy for choosing the hot particle guarantees the next lemma.
Lemma 4.4.
We have, for each ,
(4.5) |
See the corresponding lemma in [9] for a proof. This allows us to study the number of frozen free particles in block at the end of the procedure by running the carpet/hole dynamics up to block , 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 is said to satisfy the mass balance equations if
Note that the random vector satisfies the mass balance equations by definition. In what follows, we will sum over the random set of possible vectors satisfying these random mass balance equations.
4.3. Single block estimate
The following Lemma is an upper bound on the number of frozen particles in a fixed block. Sections 6, 7 and 8 are devoted to its proof.
Lemma 4.6.
For , there exist constant and sufficiently large such that , and the following holds for any . If the initial configuration on is valid, then
(4.7) |
Additionally, for any ,
(4.8) |
for some independent of .
Note the lower limit of the summation over 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 and . Let be any valid carpet, and recall the events that the odometer of site is at least and that all ’s occur (note that ). Also let be the event that among the first many times a hot particle is toppled at site , at least twice it takes a step left and then reaches site before returning to site . Note that and
(4.9) |
for some depending only on and .
To bound Frozen, the number of frozen free particles remaining in after the carpet/hole dynamics, we use the fact that . Since ,
(4.10) | ||||
(4.11) |
Recall there are at most particles inside at the beginning. Let Using Lemma 4.4, we may rewrite the expectation as
(4.12) | |||
(4.13) |
where
(4.14) |
and
(4.15) |
We will inductively show that for constants . The base case is trivial and the case follows from Lemma 4.6 and the estimate (4.9). Suppose that the inequality is true for and . Let
(4.16) |
Decomposing the last two sums depending on whether and , we get
(4.17) | ||||
(4.18) | ||||
(4.19) |
By conditioning on and using (4.9), the first sum is bounded above by . Similarly, the second sum is at most by conditioning on and using the first part of Lemma 4.6. For the last sum, we have
(4.20) | |||
(4.21) |
It follows from (4.9) and the second part of Lemma 4.6 that the third sum is upper bounded for some . Combining all three bounds finishes the inductive step.
To bound Frozen, we apply Markov’s inequality together with the bound on to get
(4.22) |
By the assumption , the event in question is exponentially unlikely in . This completes the proof of the case and .
The proof of the general case is almost the same as the above case. The main difference is that when , the counter no longer enjoys the deterministic upper bound as . Instead it suffices to argue that and occur simultaneously with probability exponentially small in . By the second part of Lemma 4.6, out of every two added particles at , with probability at least some particle reaches and thus visits . Then a standard concentration bound gives the claim.
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 , 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 is the period of the blocks in the carpet/hole procedure. Throughout Section 5, we use the same from Proposition 3.4 and Lemma 4.6. We will prove the following re-statement of Theorem 1.1.
Theorem 5.1.
Let be a probability distribution supported on finitely many non-negative integers with mean and . Let be i.i.d. random variables with distribution . Then the system with starting configuration stays active a.s.
Proof of Theorem 1.1. Theorem 5.1 is a quantitative version of Theorem 1.1 with . It causes no loss of generality to assume that is supported on finitely many integers and . To see this, note that for any probability distribution on satisfying and , one can find another distribution stochastically dominated by , such that is supported on finitely many integers, and . By monotonicity, if the stochastic sandpile with independent initial distributions does not fixate, then the model with distribution also does not fixate.
Throughout the rest of this section, we assume and satisfy all the conditions in Theorem 5.1.
5.1. Partial stabilization on nested intervals
Define a sequence with for some large with . Let . Consider a sequence of intervals of integers
which is a shifted version of the interval with many blocks. For , write
and
Also define and . Then
Finally, let be the event that
The above notation works for all . For , we use the convention that . Here is the left endpoint of the center block containing site zero. For , we write and .
We will inductively define partial stabilization procedures on the nested sequence of intervals and the resulting configurations . Set . Suppose is defined, we may extend the definition for all , and then define to be the configuration after the partial stabilization of with initial configuration and particles frozen when they get to the boundary of the interval. Let be the site odometer at in the partial stabilization of from .
For , to go from to we do the partial stabilization in the following order:
-
•
Run IDLA on the particles in the two intervals
and freeze particles at the boundaries or . 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 and , freezing particles at and , until and are completely filled or we run out of particles at and .
-
•
If the configuration inside becomes valid after the previous two steps, stabilize according to the carpet/hole dynamics, freezing particles at and .
For , we perform a similar procedure by replacing the interval endpoints and in the first and second steps by .
Let , and the configurations after each of these three steps at stage respectively. Each of these configurations has at most one particle per site inside except at and (or when ).
Let , and let be the event that
-
•
every site in contains particles initially,
which occurs with small but positive probability. Suppose happens, we will define the event inductively. Conditioned on , we will observe the following typical behavior during the partial stabilization on :
-
•
After we run IDLA on the particles in
the density of sites inside each of those intervals that is covered by a particle is between and 1. We also expect that occurs when . Call the intersection of these three events to be .
-
•
Then we run IDLA on the particles at and (or when ) until and are completely filled. We expect that there are at least particles left at both and (or when ) at the end of this step. Call this event .
-
•
If the typical events occur up to this point, by definition the configuration inside 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 blocks without a hole in . At both and there will be at least particles. Moreover, the odometer at the left endpoint of every block during this carpet/hole procedure is at least . Call this event .
When all these three events happen, we call the procedure successful at stage and define inductively
We will show that the event happens with positive probability. Once this is proved, we can show that the odometer lower bound in the definition of implies the system stays active almost surely, thus proving Theorem 5.1.
The goal of the rest of Section 5 is to show that . The first two steps of each stage are straightforward IDLA processes. We will give lower bounds on the probabilities of and 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 . Other than Proposition 3.4, we will need the ‘center of mass’ calculation in Lemmata 5.5–5.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 , proves the odometer of every block is high. Since the definition and analysis of stage are slightly different from those of stages , we only treat stage in all lemmata of Section 5 but discuss the modifications for stage 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 be i.i.d. with distribution satisfying the conditions in Theorem 5.1. There exists such that for large enough,
Proof.
First note that and are independent as they were defined on disjoint sets of independent random variables. This justifies the equality.
Next, notice that and are the sums of less than independent random variables each bounded by for some , as is finitely supported. Since and differ by a constant, standard concentration bounds give that
for some .
Recall is the sequence generated by running IDLA on with particles frozen on the boundaries. If , then there exists such that
The random variables have mean less than 1 and are bounded and i.i.d. So the probability of the previous inequality is decreasing exponentially in and . Summing up over all gives that the probability that is exponentially small in .
If
(5.3) |
then one of the following events must be true:
-
(1)
;
-
(2)
there exists and such that ;
-
(3)
there exists and such that .
By standard estimates on sums of independent bounded random variables, the probability of the first event is decreasing exponentially in . The probabilities of the second and third events are decreasing exponentially in by the argument earlier in the lemma. This completes the proof for . The proof for is similar. ∎
Next we condition on and bound the probability that the second step is successful.
Lemma 5.4.
For , there exists such that for large enough,
Proof.
By the definition of and respectively,
and
since for and the configuration remains valid after the carpet/hole dynamics of stage .
If fails, then there are less than particles at (or when ) when the second step ends. We only treat the case where the event is violated at because the other case would be similar. On the event we have at least particles initially at , so on , the number of particles released from during the second step must be at least
for . After particles have settled to the left of , every site in has one particle. Thus the nearest vacancy to the right of (if it exists) is at least as close as the nearest vacancy to the left of , and the probability that each subsequent particle settles to the right of is at least 1/2. The probability that it takes at least particles to get less than of them settling to the right of is exponentially unlikely in and thus in . ∎
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
This is the number of excess particles in above the level of one hole per block.
Lemma 5.5.
If occurs, then
Proof.
We break this sum up into sums over particles in , and . For the particles in , we further partition them into three groups. The first group consists of all the carpet particles in , with one particle at every location except for the holes. The second group is all the particles at . The third group consists of all the remaining particles, which are all of the free particles in plus all the particles at .
The absolute value of the sum over the first group is at most
As occurs, we get that the sum of the locations over the second group is at least
in absolute value. By 4, the number of particles in the third group is minus the number of particles in the second group, which is at least . Thus the sum over the third group is at least
For the particles in and , since occurs, so does . By the definition of those events, we get that the absolute value of the both sums combined is at most Combining these estimates proves the lemma. ∎
Let be the event that there are at most blocks without a hole at the end of stage . 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 . The following holds for and sufficiently large . On the event
we have
Proof.
First we show that under the same hypotheses,
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 , the free particles in plus the particles at , and the particles at . The sum of the locations of the carpet particles is at most
Since occurred, the sum of the locations of the second group is at most
By we have , so there are at least
many particles at , each contributing to the sum. Putting these estimates together gives the desired upper bound.
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 from the last lemma.
Lemma 5.7.
There exists such that for all large enough ,
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 such that , let and , and define to be the piecewise linear function when and (resp. ) when (resp. ). Finally, we define
Different from , the above definition records the change of a restricted version of center of mass in the third step of stage . Also, recall that denotes the odometer at during the third step of stage .
Lemma 5.8.
For , there exists such that for all large enough ,
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 to takes more than many topplings, or (2) the restricted center of mass, i.e. the sum of function values of all particles’ locations, moves by at least during the carpet/hole dynamics, which undergoes at most topplings. It suffices to bound the probabilities of both (1) and (2).
On one hand, since is finitely supported, there is a deterministic upper bound on the number of particles inside that is linear in . So if the system takes at least steps, then there exists one particle that moved many times for some . As particles are frozen at , it must have done so without hitting these two points. For each particle, this has probability at most for some . By a union bound over all particles in , the first event has probability at most for some and large enough .
For the second event, let be the total number of topplings taken during the third step of stage , and let and be the starting location and direction of the th toppling respectively. We may write
The first sum with the upper limit replaced by some time variable is a martingale with bounded differences. So by applying the Azuma’s inequality and a union bound over times, the probability that and the first sum exceeds is at most for some and large enough . Since both sums in the second line above are at most and 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 (from to ) instead of just the third step ( to ). So Lemma 5.7 is the special case where and . 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 . There exist some such that for and sufficiently large , we have
Proof.
We pick constants and as stated so that Proposition 3.4 and all previous lemmata in Section 5 are true. If occurs, then one of these three events during the third step of stage must happen:
-
(1)
the odometer at the left endpoint of some block is less than ;
-
(2)
the odometer for every block but ;
-
(3)
but there are less than particles at either or .
The second event is exponentially unlikely in by the second statement of Proposition 3.4. For the third event which we denote as , the ‘center of mass’ calculation, Lemmata 5.6 and 5.7, as well as its symmetric version shows that is exponentially small in . So by Lemmata 5.2 and 5.4 we get the desired bound on . In the remainder of the proof, we focus on the bootstrap argument which bounds the first event.
As we are conditioning on , there are a large number (at least ) of initial particles at right before the third step of stage . By the second statement of Lemma 4.6, with probability exponentially close to one, the odometer at the left endpoint of the block containing must be at least . So if there is some block whose left endpoint odometer is less than , then there exists some largest interval such that and for any block .
First, we claim it is exponentially unlikely in that . Indeed, by Proposition 3.4 for any interval satisfying , the probability that and but is exponentially small in . The inequality holds trivially for other intervals such that , so taking a union bound over all such intervals proves the claim.
Next, we show that with exponentially high probability either or . Suppose not, then by definition both and are less than . So with the notation and from Lemma 5.8, the number of free particles that stayed inside before the third step of stage but become at or to the right of afterwards is at most by 5. The same also holds for those becoming at or to the left of . Since there are at least particles inside before the third step, at least particles remain frozen in this interval at the end of the carpet/hole procedure. This is exponentially unlikely in by the above claim.
Thus we may assume, without loss of generality, that , as the case would follow from a symmetric argument. By the claim above we may also assume that which happens with exponentially high probability. Our next goal is to show that if and , then we have with exponentially high probability. This would give the bound on the first event, thus proving Lemma 5.9.
From now on we suppose that and but . We will show that this is exponentially unlikely in by carrying out another ‘center of mass’ calculation. Recall the notations from Lemma 5.8. By assumption, we have . Let (resp. ) be the set of locations of the carpet particles of (resp. ) inside . Similar to Lemma 5.6,
For the rest of the particles, we consider a new kind of sum with each location shifted by for simplicity. Let (resp. ) be the number of particles of (resp. ) in at or to the right of . On one hand, as there are at least particles at initially, we get
On the other hand, by assumption we have
By the definition of , we have , which implies by 5. Using this fact and the inequality , we combine the above estimates into
for and sufficiently large.
Proof of Theorem 5.1. As mentioned above, we’ve only proved Lemmata 5.2–5.9 for stage . We briefly discuss the counterparts and proofs for stage before putting everything together. Recall the different definitions of , , , , and when . If occurs, i.e. there are exactly particles at every location in before stage , then occurs almost surely as there will be exactly one particle at every site of and . Also, the second step of stage will be trivial, so by a concentration bound on the IDLA particles in the first step, there will be at least particles at with probability exponentially close to one. This shows that Lemmata 5.2 and 5.4 hold for .
For Lemma 5.5, in fact on the event we have In the proof of Lemma 5.6, by using the fact and the counterpart of Lemma 5.5, we get . Lemmata 5.7 and 5.8 work for all . Finally, essentially the same proof works for Lemma 5.9 by using the above counterparts of Lemmata 5.5 and 5.6 and replacing by . In other words, Lemma 5.9 also holds for .
From the definition of and Lemmata 5.2, 5.4, and 5.9 we get
(5.11) |
for some and sufficiently large . We have that happens with small but positive probability and grows exponentially, so there exists a large enough such that
Thus by the definition of the odometer at site is infinite with positive probability. By Lemmata 2.1 and 2.2 and 1, this implies
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 ’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 carpet particles, except for a single empty site – the hole – and some parity configuration, . For the remainder of the analysis we shift coordinates so that the leftmost point of the block is position . For any such , denote by the location of the leftmost 1 of ,
(6.1) |
which is the position of hole when the hot particle is inside the hole. If is identically zero then we write . Let denote the path taken by the hot particle starting at position and ending on the first return to that site, where is the number of steps taken in the path and is the position of at step . Define , the local time of , by
Then define , the parity of the local time of , by
Recall from Section 3 that our carpet process inside a single block is a Markov chain , one step of which is defined as follows: Let .
-
•
(Do an excursion) The hot particle at performs a random walk on that starts at and ends on its first return to .
-
•
(Update the parity configuration) For each , set
(6.2)
We will be only interested in the carpet process 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 , we introduce three types of random walk paths, with a right (resp. left) version for each kind, namely: for ,
-
(Type 1)
a simple random walk started from and conditioned to hit (resp. ) without returning to ;
-
(Type 2)
a simple random walk started at (resp. ) and conditioned to hit without reaching (resp. );
-
(Type 3)
a right (resp. left) type 1 walk followed by a corresponding version of type 2 walk.
Most of the time, is a simple random walk excursion on starting and ending at . However, when the hot particle reaches a neighboring block, by 2 it respawns from one of the boundary points: could also be
-
(1)
‘long excursion’: an emission to the left (resp. right) from followed by a re-arrival from the left (resp. right) boundary, i.e. a path of type 3;
-
(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 ;
-
(3)
‘failed re-arrival’: after the emission, the newly designated hot particle fails to arrive at 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 for excursions to the right, or at for those to the left – the parity in such case is determined by the conditioning.
Lemma 6.3.
Let be a SRW excursion on starting and ending at . Let
Let Extreme be its other extreme value of Range (besides ). If , then for any ,
(6.4) |
Instead if , then for any ,
(6.5) |
Proof.
We only treat the case where the excursion goes to the right from so that for all , as the proof of the other case would be similar. Fix , a sequence of parities , and an extreme value . For a deterministic excursion away from , we let and recursively define
and
Note that between and , the excursion might bounces back and forth between and .
We will count the number of visits to in these intervals conditioning on the entire rest of the path. Let and define and . We then define , which is the result of removing the bounces of back and forth between and . Let be any deterministic excursion away from such that for and . Let and . Consider being distributed like conditioned on . For , let be the number of visits of to in .
When , a direct computation shows that are independent random variables. Let
Then has a distribution and a direct computation shows that . Since , the result follows by unwinding the conditioning.
When , we always have and there must exist some with . So conditioned on each being either equal to or greater than one with at least one inequality for some , we have distributed either as 1 almost surely or as 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 of any type and any ,
For a left version walk of any type and any ,
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 defined in 6.1. Following the comment above Lemma 6.3, we consider the event that the random variable is uniquely determined by the -algebra , that is,
(6.7) |
Let denote whether the random walk path is an excursion, a double-sided path, or a failed re-arrival. Let
Lemma 6.8.
Consider the -algebra generated by
Suppose is not a failed re-arrival. Almost surely, the random variable , for some , is uniquely determined by if and only if one of the following is true:
-
•
is an excursion to the left or a double-sided path, and ;
-
•
is an excursion to the right or a double-sided path, and .
Otherwise, a.s.
(6.9) |
Proof.
This is a consequence of the discussion in this section. ∎
6.3. Auxiliary carpet process
We start with the following heuristic. Suppose we had the following two facts:
-
(1)
there exist such that if then
-
(2)
there exists such that for all and all ,
Since the process 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 with is growing exponentially in , 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 and a related filtration , where we do not reveal the full information about the state of . It turns out that
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 -algebras and the auxiliary carpet process . Recall the notations from Section 6.1 and Lemma 6.8. Every -algebra will be generated by for some random . At each time , the process takes values in the space consisting of all
such that for where
In particular, if contains no 1, then . The variable will be defined as a function of the paths and measurable in .
To keep track of the information in , we also define a family of -valued random variables, , that are indexed by triples
Our definition will ensure that a.s. if and only if is not uniquely determined by , that is,
Set and . Suppose we have defined the -algebra , the state and the family of random variables after the -th random walk path . We start by including and in , i.e. all the previously revealed plus whether is an excursion, a double-sided path, or a failed re-arrival. For any , set
If is an excursion or a double-sided path, then , and are further defined via the three-step procedure:
-
(1)
Refresh the range of (other than ) with ?’s as follows to get :
If and , then
(6.10) Include the random variable in and set for all .
If , then we define similarly but change the symbol at to
(6.11) Additionally, set . If , then we do the similar change at .
-
(2)
Find the leftmost one to get :
(6.12) We leave the definition of to the last step. Include in all the random variables for and which have not been in . Set for any such .
-
(3)
Inspect the bit at to see if it is uniquely determined by . More specifically, for any such that has not been set to zero, set if one of the two cases from Lemma 6.8 holds with and . If after this, we have for all , then we define ; otherwise, let . Finally, we set all the undefined to one.
If is a failed re-arrival, then we simply leave , and undefined for . This completes the inductive definition of all three items.
The last definition implies that all results about the auxiliary carpet process , 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 may start from an arbitrary configuration, we could restart the definition of with , at some stopping time close enough to the time in question. This is done in Lemma 8.10.
6.4. Properties of the process
We now state several consequences of these definitions before proving Lemma 6.18, which summarizes our progress in Section 6. For , let
Also let
and
Lemma 6.13.
The following are true.
-
(1)
if .
-
(2)
.
-
(3)
if and only if there exists some such that
Proof.
All items follow from the definition of and by induction on . ∎
Lemma 6.14.
The following are true.
-
(1)
is measurable in
-
(2)
is generated by where is defined in Lemma 6.8.
-
(3)
For any , both and 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 defined in the ‘refresh’ step of the procedure. We consider the corresponding and associated with . Let (resp. ) be (resp. ) at the end of the ‘refresh’ step without performing the changes in the subsequent two steps. All undefined are set to one. We also define , and by replacing in the original definitions with . The next lemma follows as a by-product of the inductive proof of the last two lemmata.
Lemma 6.15.
Lemma 6.16.
If , then a.s.
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 , by Lemma 6.13 (3) there exists some with . By Lemma 6.14 (3), we must have
(6.17) |
holds for either (1) , or (2) with or .
In the first case, neither of the events in Lemma 6.8 occurs with at . So by combining Lemma 6.14 (2), the fact that , independence and Lemma 6.8, we obtain that a.s.
Since , 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 ’s with ’s. The assumption also implies is uniquely determined by , so a.s.
Lemma 6.16 then follows. ∎
For , define
One key part of our analysis is to show that when is large, behaves like a random walk biased to increase, see Lemma 8.1. Lemma 6.18 says that is unlikely to decrease dramatically by erasing many ?s.
Lemma 6.18.
For any , a.s.
Proof.
Let be the location of the th leftmost ? in (if it exists). Since we might lose one more ? in the ‘inspect’ step, the above conditional probability is at most
The above expression is at most by repeated conditioning and use of Lemma 6.16 at every other . This proves the desired estimate. ∎
7. Zeros of auxiliary carpet process
With Lemma 6.18, we will show that when is large, the number of nonzero symbols has a bias to increase. However, this does not rule out the possibility that becomes small when 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 , defined in Section 6.3. Let
The ‘Base’ state starts with followed by many ?, whereas the ‘Exit’ state is the all-zero state which occurs exactly when the block becomes frozen. Define
For , define an ‘-Base’ state to be any configuration of the form
starting with at most many 0’s from the left. In particular, the Base state is an -Base state.
Since is not a Markov chain with respect to its natural filtration, we consider the carpet processes and that start from some negative instead of zero, and use the shorthand notation to mean that
Write similarly for the infimum. In fact, all results in Section 7 are true in a stronger sense where the supremum/infimum is over all , but the above notation has the advantage of working for both Sections 7 and 8. We also write in the case that the statement holds for any initial -Base state .
Lemma 7.1.
Consider the event
For and sufficiently large ,
The rest of Section 7 is devoted to the proof of Lemma 7.1. In order to produce so many zeros in , 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
We start by studying how zeros are generated in the auxiliary carpet process. Write
Recall that the process starts from some negative time . For any time , define
For any time and , define
which is the last nonnegative time before when gets visited by a random walk path.
Lemma 7.2.
For any and with , we have
Proof.
cannot be an excursion to the right, since necessarily in that case. If is a double-side path, then for all . So assume is an excursion to the left. Then and thus . This implies . ∎
Lemma 7.3.
For any , and ,
Proof.
Suppose that . Since , we have . Thus there exists some such that with . But by Lemma 7.2 we must have a time with , which contradicts the definition of . Therefore . ∎
Lemma 7.4.
Suppose , and for any , then
Proof.
Lemma 7.5.
Let We have
-
(1)
the function is decreasing on the set ;
-
(2)
for any with and , we have and at time , there was an excursion to its left starting from such that and ;
-
(3)
there do not exist three distinct values with .
-
(4)
if is an -Base state, then there do not exist four distinct values in with the same function value .
Proof.
Since the random walk always starts from the leftmost one, a straightforward induction on the time proves item (1). Item (3) follows directly from item (2), so it remains to show items (2) and (4).
For item (2), write . By item (1), we have , so and . Thus . We claim that . Suppose not, then Lemmata 7.3 and 7.4 combined imply that , which is a contradiction. This proves the claim.
We consider all the possible cases of satisfying . First, cannot be a double-sided path: otherwise, we would have . Secondly, cannot be an excursion to the right: otherwise, from we must have , which contradicts Lemma 7.3. Lastly, if is an excursion to the left, then we must have to guarantee . This implies . Since no random walk after time visits , it follows that , which in turn implies that . This proves item (2).
For item (4), we first show that for any , , where
Suppose not, then out of any four such elements we can find such that , which leads to a similar contradiction to that in the proof of item (2). This proves the bound for .
It remains to check the case where . We show that again by contradiction. Suppose not and there exist with . Since , by item (1) we have and thus due to the definition of an -Base state. Moreover, by Lemma 7.3 we get for any , so it follows from the definition of that for any . This contradicts with the fact that , which proves item (4). ∎
We introduce some more notation. For write We call a sequence good if for all such that we have . The good sequences capture different ways in which zeros may be generated in , with adjacent and representing a pair of zeros generated as described in Lemma 7.5 (2).
Given a good and , we partition the zeros in as follows:
where
and
For , let be such that
and let be such that
except when , we have instead. Note that in a good sequence, for we always have .
Finally, for divide into pieces
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 . To bound the probability of the right-to-left dynamics generating , we will inductively define a counter at every vertex starting from . The goal of the counters is twofold. On one hand, given a sequence the counters can be used to identify a sequence of stopping times for every . We will tailor our definitions so that with the right choice of (in most cases), see Lemma 7.8. On the other hand, the counters also give us bounds on the probability of the key events , see Lemma 7.7.
We start with the definition of and at .
-
•
For , the counter starts at zero. For any , the counter increases by one if at time the random walk starts from and either or the previous random walk path was from ; otherwise, the counter stays put and we have . Given , define the stopping time to be the smallest such that and the next path starts at if such exists; in this case, we say is well-defined.
In order to define other counters we will work inductively. Suppose that the stopping time is well-defined, we shall define for all .
-
•
For , then initially at , we set the counter . For any , let
In words, the counter increases by one every time a particle moves from .
-
•
For , then the counter starts at zero and for , we have
In words, the counter increases by one every time a random walk path starts at a location belonging to or every time a particle moves from in a path that starts to the left of .
Given , let be the smallest such that if such exists; in this case, we say is well-defined. This completes the definition of the counter and stopping time at every .
Finally, we define the key events in the analysis of counters. For a good sequence and , define to be the event that
-
(1)
the stopping times are well-defined for all ;
-
(2)
;
-
(3)
for any , none of visits during ;
-
(4)
for , just before the particle made an excursion to the left starting from where and .
Lemma 7.6.
If the event in Lemma 7.1 occurs, then there exists
-
•
,
-
•
a good and
-
•
such that
-
•
the event occurs and
-
•
all the ’s are odd for .
Lemma 7.7.
Fix any . Fix any good sequence . Fix any sequence . We have
where .
7.3. Analysis of zero generation in
We start by proving Lemma 7.6. Assume the event from Lemma 7.1 occurs, that is, . We define the corresponding , and as follows. Recall
-
•
Let .
-
•
Set
- •
-
•
For let . Note that is well-defined by our definition of and the fact that . To define for we will work inductively. Suppose that is given and is well-defined. Then we let . Again is well-defined by our choice of . This completes the definition of .
Lemma 7.8.
Let , and be defined as above. For , we have . For any , we have .
Proof.
We shall prove Lemma 7.8 by induction on . We start with the base case where . If , then and the upper bound on is trivial. If , then by the definition of we have . Lemma 7.2 implies and thus . This proves the upper bound.
To show for , we argue by contradiction. Suppose for some , the path visits . Since , by definition for any , so the conditions of Lemma 7.4 are satisfied. This implies , which is a contradiction. This completes the proof of the base case.
Now suppose holds for some , we will prove . First, note that ; otherwise, Lemma 7.5 (2) would imply and , which contradicts . So by Lemma 7.5 (1) and the induction hypothesis we have . Thus and it makes sense to talk about .
In order to prove , it suffices to check
(7.9) |
and for any ,
(7.10) |
Since visits , the inequality (7.9) follows from the definition of counter directly if or and . The remaining case that and cannot happen due to the fact that and Lemma 7.3. For (7.10), does not visit for , so it follows that for any such . ∎
Proof of Lemma 7.6.
We finish the proof by checking all requirements on and . We’ve checked that is a good sequence.
We check that for all . In the proof of Lemma 7.8, we’ve shown , so .
To see why is odd for , note that by definition . Also has the same parity as . Combining these with proves is odd.
Next we prove Lemma 7.7.
Proof of Lemma 7.7.
We will estimate the probability inductively. We start with and then progressively lower it until we get the full result.
For , and , define the -th iteration of the counter to be the set of paths such that and , for any . 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 paths all being excursions to their right; otherwise, the leftmost one in the configuration would exceed , which contradicts the definition of item 2. Since the probability of any path reaching a neighboring block is at most (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 . Thus we get the following upper bound on the probability of
Suppose we have established the upper bound for , and . Let We will establish the bound for , and , where if and if .
If , i.e. and , then by the definition of item 3 we know that every movement of a particle from in the time interval must be to the left. By the definition of the counter, there are
many such movements. Thus we get an upper bound of
If , i.e. and , then the same analysis as in the last case implies that there are at least many movements from during , all of which are to the left. Moreover, by the definition of item 4, at the last such movement from 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 an even number of times. This happens with probability at most . In fact, for a usual random walk excursion starting from zero, the probability of going to the left and visiting site even times is exactly . 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 upper bound. Therefore, we obtain a slightly improved bound of
If , i.e. with , then by the definition of item 3, we know that every time a random walk path starts at a location in during , the first step either moves to the left or moves to the right without hitting . This has probability at most . Also, every time during the particles moves from in a path that starts to the left of , the particle either moves to the left or moves to the right and does not hit before returning to , which also has probability at most . Combining these with the definition of the counter, we get the bound
Putting these together gives us the lemma. ∎
Finally, we complete the argument by proving Lemma 7.1.
Corollary 7.11.
Proof.
Proof of Lemma 7.1.
By Lemma 7.6, it suffices to bound
where the sum is taken over all good ’s satisfying the bounds in Corollary 7.11 and all satisfying the parity constraint in Lemma 7.6.
By (7.12), the leading term of the product in Lemma 7.7 is at most
for sufficiently large . Summing up over all possible values of gives us
(7.16) |
From (7.13) and (7.14), we get
(7.17) |
Finally, from (7.14) we have
(7.18) |
Fix and write . By Lemma 7.7 and the distributive property, we have
where we’ve used the fact that all ’s are odd for and equations (7.16), (7.17) and (7.18).
Note that the bound we just developed only depends on . For let
Write
Also note that by the binomial theorem, for and we have
(7.19) |
Then by (7.15) we have
where in the second last inequality, we use (7.19) by picking the suitable .
We complete the proof of Lemma 7.1 by taking a small enough . Indeed, recall the Chernoff bound
where is the binary entropy function . For ,
so the above probability is upper bounded by for all sufficiently large. ∎
8. Single block estimate
Using the results of the previous sections, which show that the carpet process 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
Recall
as well as the definition of an -Base state.
Our first lemma is obtained by analyzing the bias in the process . It says that starting with a large enough , the process is much more likely to return to a state than become frozen.
Lemma 8.1.
For any state and sufficiently large ,
Proof.
Consider the value of
Let be the maximum distance reached by the random walk path to its left. By the definition of the ‘refresh’ step, the first term
When and , this is at least ; otherwise, we have the lower bound . Using Lemma 6.18, the second term
where and is stochastic domination.
Combining both estimates, we obtain that for , stochastically dominates a sum of the form
where Binomial, Geo are iid, and are iid positive variables with tail for . Our aim is to show that for , with high probability, which implies that with the same probability, for , , i.e. has not occurred.
To prove this, first observe that throwing out the positive sum in and using a tail bound for a sum of Geometric random variables,
(8.2) |
To see that stays away from 0 at later times, we carry out the following concentration bound for the sum of . Observe that by standard tail bounds for Binomials (e.g. a Chernoff bound), for any and any ,
(8.3) | ||||
(8.4) | ||||
(8.5) |
By a union bound over all such , none of these events occurs with probability at least if is sufficiently large, and if none of them occurs, we have
For the negative part of , again using a similar tail bound for a sum of Geometrics, for any ,
Combining these bounds, since we can take sufficiently large so that , we obtain for any ,
Taking a union bound over all values gives the result.
∎
The next lemma gives a lower bound on the frequency at which the carpet process refreshes by returning to the Base state.
Lemma 8.6.
The following hold for sufficiently large. If satisfies ,
(8.7) |
Additionally,
(8.8) |
where
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:
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 – and then, at the next step, taking an excursion to the right beyond and not matching the parity at 2. Recall that the probability for a simple random walk excursion to reach distance at least is , so the probability for an excursion to reach distance is at least . Note that by the choice of , an excursion that reaches maximum distance visits every point in the block but does not reach any neighboring block. Thus if , then by Lemma 6.3
If , 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 sufficiently large,
Proof.
By Lemma 8.6, the process hits the Base in time at most with exponentially high probability. So it suffices to bound the event that .
If occurs, then either
-
(1)
there exists a time with and or
-
(2)
there exists a time with and for any such that .
By Lemma 7.1 the first event occurs with exponentially small probability in . By Lemma 8.1 and a union bound over all , the probability of the second event is exponentially small in . Combining these estimates, we obtain that the process reaches the Exit after 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 , 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 and the number of particles emitted to the left from block and the number of frozen particles in block right after the th attempted emission respectively (a slight abuse of notation). Let and denote the number of steps taken by the auxiliary carpet process until the completion of the th attempted emission. Note that counts steps of the chain , 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 -Base state.
Lemma 8.10.
The following holds for sufficiently large. If the initial carpet is valid, for any , almost surely,
(8.11) |
Proof.
We consider three cases.
Case I: and . Note that the probability of each attempted emission being followed by a failed re-arrival is at most . In the following, we also assume that and are not failed re-arrivals.
Under those assumptions, during the th and th 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 is , and the distance from any point in block to a neighboring block is at most and at least . Thus each excursion of the hot particle in block has probability at least and at most of reaching a neighboring block, uniformly over the initial position of the excursion (inside block ). Elementary estimates give that
(8.12) |
and
(8.13) | ||||
(8.14) |
Following the comment in Section 6.3, we consider the auxiliary carpet process started at , and due to the assumption on all results since Section 6 apply until time . By Lemma 8.6, for any we have
(8.15) |
By Lemma 8.9 and the previous line, since there are at most returns to the Base state up to time , for any ,
(8.16) |
Combining all these estimates and taking sufficiently large gives an upper bound in the first case.
Case II: . By 3, we have , cf. (8.12), and in the th attempted emission, we topple the hot particle started from or until it reaches a neighboring block. Since we’ve chosen , the probability that the hot particle reaches a neighboring block without visiting the entire block is at most : it must arrive at one endpoint of first, and then reach a neighboring block without touching the other endpoint. By Lemma 6.6 for type 1 paths,
(8.17) |
Moreover, a similar argument using an upper tail bound on and Lemma 8.9 as in Case I shows that
(8.18) |
Combining all these, we obtain an upper bound for sufficiently large in the second case.
Case III: . By 3 and Lemma 6.6, with probability at least we have is not an all-zero configuration and thus .
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 , and block . Our aim is to uniformly bound the expression
(8.19) |
Note that each particle added at site causes at least one attempted emission in block (possibly more if additional particles arrive from the left of block as a result). Thus the sum is upper bounded by
(8.20) |
where we use for the conditional expectation w.r.t. . Set
(8.21) |
and re-write the latter sum (over ) as
(8.22) |
We claim that for any ,
(8.23) |
and
(8.24) |
For (8.23), note that either the st attempted emission is a successful emission, or it is frozen in which case the nd 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 . Thus
(8.25) |
This proves the first claim.
For (8.24), when , we have and the claim follows directly from Lemma 8.10. For , note that . By (8.23),
(8.26) |
Moreover, Lemma 8.10 implies that
(8.27) |
Combining these two estimates into a union bound by setting yields the result. When , a similar argument works by replacing 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) |
Splitting the sum (8.22) at , and using both bounds, the original sum is bounded by
(8.29) |
Finally, we pick and large enough so that the condition holds, which proves Lemma 4.6 for large enough .
It remains to obtain the explicit values for and . Note that throughout Sections 7 and 8, we’ve taken sufficiently large multiple times. Two sharpest constraints, however, are in the proof of Lemma 8.1 to achieve the bias of the random walk, and above for Lemma 4.6 to work under a very small . Thus, we conclude that Lemma 4.6 holds for and ∎
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 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 . 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 . 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 . Probability Surveys, 17:478–544, 2020.
- [16] Leonardo T. Rolla and Vladas Sidoravicius. Absorbing-state phase transition for driven-dissipative stochastic dynamics on . 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.