Zero-temperature dynamics in the dilute Curie-Weiss model
Reza Gheissari Charles M. Newman Daniel L. Stein
math.PR math-ph math.MP



Zero-temperature dynamics in the dilute Curie–Weiss model]Zero-temperature dynamics in the dilute Curie–Weiss model


R. GheissariCourant Institute
 New York University

251 Mercer Street
 New York, NY 10012, USA.
reza@cims.nyu.edu


C. M. NewmanCourant Institute
 New York University

251 Mercer Street
 New York, NY 10012, USA.
newman@cims.nyu.edu


D. L. SteinCourant Institute
 New York University

251 Mercer Street
 New York, NY 10012, USA.
daniel.stein@nyu.edu


We consider the Ising model on a dense Erdős–Rényi random graph, 𝒢(N,p), with p>0 fixed—equivalently, a disordered Curie–Weiss Ising model with (p) couplings—at zero temperature. The disorder may induce local energy minima in addition to the two uniform ground states. 
In this paper we prove that, starting from a typical initial configuration, the zero-temperature dynamics avoids all such local minima and absorbs into a predetermined one of the two uniform ground states. We relate this to the local MINCUT problem on dense random graphs; namely with high probability, the greedy search for a local MINCUT of 𝒢(N,p) with p>0 fixed, started from a uniform random partition, fails to find a non-trivial cut. In contrast, in the disordered Curie–Weiss model with heavy-tailed couplings, we demonstrate that zero-temperature dynamics has positive probability of absorbing in a random local minimum different from the two homogenous ground states.  





[
    Daniel L. Stein
    
===================



 



§ INTRODUCTION

The disordered Curie–Weiss (CW) model is a mean-field random ferromagnet defined as follows: consider the complete graph on N vertices and for every edge (i,j), assign a random coupling value J_ij=J_ji i.i.d. according to some non-negative distribution μ (i.e., (μ) ∈ [0,∞)). Define the Hamiltonian H(σ) for σ∈{± 1}^N by 

    H(σ)= - 1/N∑ _1≤ i<j≤ N J_ijσ_i σ_j .

If μ were instead symmetric on (-∞,∞), this would be proportional to the Hamiltonian of the Sherrington–Kirkpatrick spin glass; in our setup, where μ is non-negative, it is a mean-field analogue of a random ferromagnet. Specifically, when μ is (p), this corresponds to the Ising model on a dense Erdős–Rényi random graph, referred to as the dilute Curie–Weiss model. In the latter case, the thermodynamics of the model behaves similarly to that of the homogenous Curie–Weiss model, but the coupling disorder induces a more complex energy landscape, whose influence may only manifest itself in the zero-temperature dynamics. The goal of the present paper is to more precisely understand these effects (see Theorem <ref>) and relate them to the random constraint satisfaction problem of finding local MINCUTs of a random graph (see <ref>).  

The zero-temperature limit of the Glauber dynamics <cit.> is called the zero-temperature dynamics and in discrete time, is the Markov chain (X_t)_t∈ℕ with transition matrix given by the following: consider a configuration σ∈{± 1}^N; for every i, if σ^(i) is the configuration with σ^(i)_j=σ_j for all j≠ i and σ^(i)_i=-σ_i, then

    P(σ,σ^(i))= 1/N [ 1{H(σ^(i))<H(σ)}+1/2 1{H(σ^(i))=H(σ)} ] .

The zero-temperature dynamics is a random walk on the hypercube {± 1}^N, that only assigns positive transition rates to moves that do not increase the energy. If the zero-temperature dynamics stops (i.e., is absorbed) in some particular state, the only possible such absorbing states are local minima and uniform ground states of H. For any non-negative (ferromagnetic) coupling distribution μ, the uniform ground states of the disordered CW model are σ=(1,...,1) and σ=(-1,...,-1). We call a state σ∈{± 1}^N a local minimum of H if it is not a uniform ground state ± (1,...,1) and is such that for any σ'∈{±1}^N with Hamming distance d(σ,σ')=1, it satisfies H(σ')≥ H(σ). Notice that if μ has atoms, there could be connected sets of local minima with the same energy, amongst which the zero-temperature dynamics jumps for all sufficiently large time, in which case we call the set an absorbing set of configurations.

Henceforth, we mostly restrict our attention to the dilute Curie–Weiss model, whose analysis ends up being more straightforward than the general J_ij≥ 0 case, by letting J_ij∼(p) for p∈ (0,1)—the case p=1 corresponds to the classical Ising Curie–Weiss model. The Ising model on sparse random graphs (p=p_N≪log N/N) is an extensively studied model with rich relations to random optimization and the theory of spin glasses (e.g. <cit.> and for a more extensive overview, <cit.>); in the context of zero-temperature dynamics, when the random graph has disjoint components, there are many non-trivial absorbing states, and in particular, the zero-temperature dynamics will have positive probability of absorbing into a local minimum (see e.g., <cit.> for a rigorous analysis of zero-temperature dynamics for the Ising model on sparse random graphs). On dense random graphs, the thermodynamics of the Ising model is essentially the same as that of the classical (homogenous) Curie–Weiss model. However, the zero-temperature dynamics is particularly sensitive to small changes in the energy landscape as it can absorb in any local minimum it encounters.

Let ℙ_σ(0) be the product measure over initial configurations, ℙ_𝒥 be the product measure over couplings, and ℙ_ω be the distribution over the evolution of the Markov chain, with corresponding expectations, 𝔼_σ(0), 𝔼_𝒥, and 𝔼_ω; we will also sometimes write ℙ_𝒥,ω=ℙ_𝒥⊗ℙ_ω etc. In the present paper we show that while we believe there exist local minima in the energy landscape of the disordered CW model with general ferromagnetic μ (so that the disorder does indeed make the energy landscape nontrivial—see Question <ref>), in the case of the dilute CW model, the zero-temperature dynamics avoids them with high probability, i.e., with probability going to 1 as N→∞ (w.h.p.). 



For ϵ>0 sufficiently small, the zero-temperature dynamics (X_t)_t≥ 0 of the Ising model on the Erdős–Rényi random graph 𝒢(N,p) with p>0 fixed satisfies the following: for every initial configuration X_0 with magnetization ∑_i X_0(i) ≥ N^1/2-ϵ, 

    lim_N→∞ℙ_𝒥,ω (lim_t→∞ X_t=(1,...,1) )=1 .



Note that by heuristic considerations, one would suspect the same should hold for any non-negative coupling distribution μ that has, for instance, all exponential moments finite. For such distributions, it seems the main obstacle in adapting our argument to give the same result is obtaining some conditional concentration for sums of couplings via an analogue of Proposition <ref>, though we often make use of the convenience of dealing with bounded random variables.

In contrast, if {J_ij}_ij are i.i.d. heavy-tailed random variables we prove that with probability bounded away from 0, the dynamics gets stuck in the exponentially many non-trivial local minima. Results for heavy-tailed couplings are found in <ref>, Theorem <ref>.

In order to study the zero-temperature dynamics from a physical point of view, a zero-temperature dynamical order parameter was introduced <cit.> and has been examined numerically in a number of models with and without disorder <cit.>. Let σ_i(t) be the i'th spin value of X_t, i.e. X_t(i). The quantity

    q_D(N)= 𝔼_σ(0),𝒥 [(𝔼_ω[σ_1(∞)])^2]
 is designed to capture how much the absorbing state depends on the initial state and how much it depends on the realized evolution of the dynamics. In the above, and throughout the paper, σ_i(∞) denotes lim_t→∞σ_i(t) if it exists and similarly with X_∞(i). 

Another way to view the dynamical order parameter q_D(N) is to fix a coupling configuration, and consider a replicated dynamics wherein two replicas σ(t),σ'(t) undergo zero-temperature dynamics independently (ω,ω') from the same initial configuration; one can then ask about the average (under ℙ_ω,ω') evolution of their overlap. The dynamical order parameter is the expectation (under ℙ_σ(0),𝒥) of this average overlap:

    𝔼_σ(0),𝒥[𝔼_ω,ω'[N^-1∑ _j=1^N σ_j(∞) σ_j'(∞)]] = q_D(N) .



In the dilute CW model, the dynamical order parameter (<ref>) has 

    lim_N→∞ q_D(N)=1 .

In fact, we have the stronger result that,

    lim_N→∞𝔼_σ(0)[ (𝔼_𝒥,ω(σ_1(∞)))^2]=1 .




We briefly mention that in the above literature regarding this dynamical order parameter, different graphs have also been considered. In <cit.>, the zero-temperature dynamics of the disordered Curie–Weiss model and random ferromagnet on ℤ^d were studied numerically and heuristically (with light-tailed coupling distributions). There, it was predicted that the zero-temperature dynamics of the disordered Ising model on (ℤ/N ℤ)^d starting from a single state ends up randomly in one of many almost-orthogonal local minima in whose basins of attraction it lies. The numerics suggest that on d-dimensional torii, lim_d→∞lim_N→∞ q_D (N)=0; combined with Corollary <ref>, this suggests the existence of a singularity in the d→∞ behavior of q_D(N). We also note that in the physics literature there has been recent interest in dynamics of the Ising model on networks at low and zero temperatures (e.g., <cit.> study, at the level of physics, absorption and persistence in a densely-connected small world network).

Over the last several years, significant progress has been made in understanding random optimization problems like extremal cuts on random graphs and random instances of constraint satisfaction problems (see e.g., <cit.>) via both heuristic and rigorous connections to spin glasses and other models with quenched disorder. We now discuss a different perspective, related to such random optimization problems, on the fundamental questions underlying Theorem <ref>, which may be of independent interest.



 §.§ The local MINCUT problem

 Consider a dense Erdős–Rényi random graph G∼(N,p) for p>0 fixed; for any subset A⊂{1,...,N}, define _G(A) as the number of edges between A and A^c. A local MINCUT is a partition (A,A^c) of {1,...,N} such that for every A' which consists of the addition or removal of one vertex to or from A (in which case we say the Hamming distance d(A,A')=1), _G(A') ≥_G (A). A nontrivial local MINCUT is one in which both A and A^c are nonempty.  


Consider G∼𝒢(N,p) with p>0 fixed. Is it the case that 

    lim_N→∞ℙ(∃ A:A≠∅, A^c ≠∅, _G(A))=1?



Note that since the Erdős–Rényi graph is dense, all vertices are connected and have high degrees of dependence; if we were considering a graph with multiple connected components for instance it is obvious how to construct nontrivial local MINCUTs. The requirement that a set A be a local MINCUT is equivalent to demanding that every v∈ A have more edges to vertices in A than in A^c, and similarly for vertices in A^c.

Viewed from this perspective, Theorem <ref> can be restated in terms of a greedy search for a local MINCUT defined as follows: start from a uniformly randomly chosen partition (A,A^c) and at every iteration, select a vertex uniformly at random and move it either to A or A^c depending on which move has the lower _G value (if the cut-value is unchanged flip a coin to determine whether to move it). 

With probability going to 1 as N→∞, the greedy search for a local MINCUT of G∼(N,p) with p>0 fixed, started from a uniformly random partition of {1,...,N} terminates in the trivial partition (∅, {1,...,N}).

This suggests the interesting situation where there exist nontrivial local MINCUTs while, with high probability, they are not found by a greedy search algorithm. In fact, there is some numerical evidence in this direction to appear in <cit.>. We call such metastable states, invisible local minima as they typically do not affect the natural dynamics, even at zero-temperature.

Of course, as with the dilute CW model, the local MINCUT problem can be presented in greater generality by assigning edges of the complete graph i.i.d. random weights w_ij and asking the analogous questions about _w (A) = ∑_i∈ A,j∉ A w_ij. In the case where w_ij are symmetric, this corresponds to finding local energy minima of the canonical Sherrington–Kirkpatrick spin glass.  This is an extensively studied question, both at the physics level <cit.> and more rigorously recently in the related problem of multiple peaks <cit.>: there the energy landscape is expected to be complex with exponentially many local minima in the system size— <cit.> developed a complete understanding of the critical points and complexity of the energy landscape in the case where the state space is relaxed to the sphere in dimension N. In the above cases, the rugged energy landscape arises due to frustration, a phenomenon that does not exist in the ferromagnetic setup. We also note that in a similar setup to ours, the algorithmic complexity of the local MAXCUT problem has been studied (most recently in <cit.>), though that problem again has a very different flavor due to the absence of dominant trivial ground states.

If we instead restrict ourselves to ferromagnetic disorder (w_ij are a.s. non-negative), we expect that Corollary <ref> and the techniques of this paper extend to the general case when w_ij have light (e.g., exponential or Gaussian) tails; there is again some numerical evidence in this direction <cit.>. In contrast, our results in <ref> on heavy-tailed disorder imply an affirmative answer to Question <ref> while showing that there, with strictly positive probability, the greedy search terminates in a non-trivial local MINCUT. 



 §.§ Notation

We introduce some notation that we will use throughout the paper. We say two sequences f_N and g_N are such that  f_N≲ g_N if there exists C>0 such that f_N ≤ Cg_N for all N and we say f_N ≍ g_N if f_N≲ g_N≲ f_N. Finally, we write f_N = O(g_N) if f_N≲ g_N and f_N = o(g_N) if f_N ≤ c g_N for large enough N for every c>0. For readability, we will, throughout the paper, omit floors and ceilings, though all our variables will be integer-valued. We will also assume N is sufficiently large.

The discrete-time zero-temperature dynamics chain is alternately denoted by (X_t) and σ(t)= (σ_1(t),...,σ_N(t)) where t is always understood to be integer—clearly, the results of Theorem <ref> and Corollary <ref> would also hold for the analogously defined continuous-time zero-temperature dynamics. The magnetization at time t is given by

    M_t =∑ _i=1^N σ_i(t) .

The effective field on site i at time t is given by

    m_i(t)= ∑ _j≠ i, j=1,...,N J_ijσ_j(t) .

It will be notationally useful to define the related m̅_i(t)=(m_i(t)) so that m̅_i(t)∈{± 1,0} where m̅_i(t)=0 if m_i(t)=0. 
Then we let {𝒮_i(t)}_i=1^∞ be the set of satisfaction random variables

    S_i(t)=m̅_i(t)σ_i(t) ,

so that when the dynamics chooses a site i to update, σ_i(t)=σ_i(t-1) with probability 1 if S_i(t)=S_i(t-1)=1, probability 1/2 if S_i(t)=0, and probability 0 if S_i(t)=-1.

We will use the probability measure ℙ to denote the product measure ℙ_𝒥⊗ℙ_ω, since we will always be fixing X_0=σ(0) and sometimes averging over 𝒥,ω at once.



 §.§ Proof approach

Here we give an overview of our approach to proving Theorem <ref>. To avoid the difficulties present in analyzing systems with quenched disorder, particularly with non-Gaussian disorder, our analysis of the zero-temperature dynamics reveals only partial information about the couplings as the dynamics proceeds. This gradual “revealing scheme" may be of independent interest in analyzing the short-time (t≪ N) dynamics of other systems with quenched disorder. Here it allows us to bound the drift of the magnetization chain (M_t)_t∈ℕ conditioned on this partial information from below, and compare (M_t)_t∈ℕ to a random walk with positive drift. More precisely,



  * In 2.1, we define a revealing scheme to see the evolution of the zero-temperature Markov chain as measurable w.r.t. the σ-algebra ℱ_t generated by the sequence (Y_t)_t of updated sites, their satisfactions at update time (S_Y_t(t))_t, and the couplings ({J_Y_t,Y_k}_k=t+1,...,T)_t for T=N^1/2+δ. To gradually reveal this information, we first fix the update sequence {Y_1,...,Y_T} then sequentially jointly reveal the satisfaction and aforementioned couplings of the next site to update.


  * In 2.2, we compare the joint distribution of ({J_Y_t,Y_k}_k=t+1,...,T)_t given S_Y_t(t) and _t-1 to a product measure. In particular, for all short times t=O( N^1/2+δ) we show that the conditional joint law of the couplings revealed at time t dominates i.i.d. (p-O(N^1/2+2δ)) and is dominated by i.i.d. (p+O(N^1/2+2δ)).


  * In 2.3, we show that for all times t≤ N^1/2+δ, as long as M_t ≥ N^1/2-δ holds, the chain (M_t)_t≥ 0 has a positive drift of at least cN^-δ/2, so that, (M_t)_t≥ 0 typically stochastically dominates a random walk with drift of c N^-δ/2. 


  * By this comparison, at time T=N^1/2+δ, M_T ≥ N^1/2+δ/2 and all sites that have not yet been updated have a positive effective field. This can then be boosted in 2.4 to show that by time T'=N^2/3 all sites have a positive field and the dynamics will thereafter quickly absorb into the all-plus ground state.




§ THE DILUTE CURIE–WEISS MODEL




 §.§ Random mapping representation

Denote by Y_k∈{1,...,N} the site chosen at time step k to be updated so that for every k∈ℕ, (Y_k)=({1,...,N}). Then consider the sequence of update sites and their satisfactions, (Y_k, S_Y_k(k))_k.

In the dilute Curie–Weiss model, μ is atomic and there may be zero-energy flips with positive probability, so (X_t)_t≥ 0 is not measurable with respect to the sigma-algebra generated only by X_0 and (Y_k,S_Y_k(k))_k≤ t. Thus define a sequence of i.i.d. random variables (B_k)_k≥ 0 with B_1∼ 2(1/2)-1 which will determine the spin at site Y_k in the case that m_Y_k(k)=0. Then the history of the chain (X_k)_k≤ t is fully determined by X_0=σ(0) and the sequence (Y_k,𝒮_Y_k(k),B_k)_k≤ t. 

The grand coupling is the coupling of two independent dynamics with different X_0 such that both dynamical realizations use the same random variable sequence (Y_k)_k≥ 1 and (B_k)_k≥ 0 as well as the same couplings {J_ij}. The grand coupling has the added feature that it preserves monotonicity, so that if X_0≽ X_0' then X_k≽ X_k' for all t≥ 0. Moreover, by permutation invariance of the measure ℙ_,ω, we can begin by permuting all initial configurations so that if M_0 ≥ M_0', X_0 ≽ X_0' and identify initial configurations only with their magnetization, then apply the grand coupling of ,ω.




 §.§ Preliminary estimates


We first estimate the probability of the magnetization of X_0 being atypical. The following is a consequence of e.g., Berry–Esseen theorem.

 For every ϵ>0, we have

    ℙ_σ(0) (X_0:|M_0|≥ N^1/2-ϵ)=1-O(N^-ϵ) .



By the grand coupling and permutation symmetry of the model, it suffices to prove Theorem <ref> for a fixed X_0 with M_0=N^1/2-ϵ; for every coupling and dynamical realization in which the chain with that initial configuration absorbs in X_∞ =(1,...,1), via the grand coupling, so does every chain with more positive initial configuration. Moreover, in order to simplify our considerations, by monotonicity we may assume that for all k≥ 1, we always have B_k=-1; via the grand coupling of the dynamics, it suffices to show that this chain absorbs into the all-plus configuration w.h.p. to prove Theorem <ref>. Abusing notation, (X_k)_k will henceforth refer to this new chain with B_k=-1 for all k. In conjunction with this change, whenever m_Y_k(k)=0, we set S_Y_k(k)=-σ_Y_k(k-1).


Fix T=N^1/2 +3ϵ and for every t∈ℕ, let {ℱ_t}_t be the filtration of σ-algebras generated by 

    (Y_1,...,Y_T∨ t), (S_Y_k(k))_k≤ t,  (J_Y_k Y_l)_k ≤ t, l≤ T

The chain X_t is measurable w.r.t. the σ-algebra generated by (Y_k, S_Y_k(k))_k=1,...,t and X_0 (and therefore measurable w.r.t. ℱ_t and X_0).  


It will be crucial to understand the conditional distribution of J_ij given ℱ_t when i∈{Y_k}_k≤ t but j∉{Y_k}_k≤ t, as well as the joint law of such {J_ij}_j. (This is the main reason we restrict ourselves to Bernoulli J_ij, where the distribution is determined by the mean, instead of general light-tailed random variables like half-normal distributed random variables. To extend Theorem <ref> to that setting, the main technical hurdle is obtaining appropriate analogues to Proposition <ref> for exponential moments in order to obtain conditional concentration of sums of couplings, namely (<ref>).)

We will need the following notation: for any sequence of order updates, denote by ℛ_t the set of vertices whose clocks have rung more than once before time t, i.e., 

    ℛ_t= {i:∑_k≤ t 1{Y_k=i}>1} .

 Let t ≤ T=N^1/2+3ϵ, suppose that j=Y_t, j∉ℛ_t, that ℓ∉{Y_k}_k=1^t, and suppose that |M_0| ≤ N^1/2+3ϵ. Then we have that, 

    |𝔼_[J_ℓ jℱ_t-1, S_j(t), {J_ja}_a∈{Y_k}_t+1^T - ℛ_T-{ℓ}] -p| = O(N^-1/2+4ϵ) .



First fix the update sequence {Y_k}_k=1^T and fix any such t and ℓ. 
Let 

    𝔼̃ [ · ]     = 𝔼_[ ·|ℱ_t-1, {J_ja}_a∈{Y_k}_k=t+1^T-ℛ_T-{ℓ}] .

Now we can expand 

    𝔼̃[m_j  (t)  | S_j(t)]-  𝔼_ [m_j(0)]=       σ_ℓ(0) 𝔼̃[J_ℓ j-p | S_j(t)] 
        + ∑_i ∈{Y_k}_k=1^T-{ℓ}[σ_i(t)  𝔼̃[J_i j| S_j(t)] -pσ_i(0)]  
         + ∑_i∉{Y_k}_k=1^T∪{ℓ}σ_i(0)𝔼̃[J_i j-p | S_j(t)] + O(|_T|) .

Since |ℛ_T| ≤ T, we can replace O(_T) by O(T); moreover the second sum consists of at most T terms and is thus bounded in absolute value by 2T. Now suppose without loss of generality that m_j(t) > 0 and σ_ℓ (0)=+1—the same argument carries through in the other cases. We claim, first of all that for every m∉{Y_k}_k=1^T with σ_m(t)=-1,

    𝔼̃ [ J_m j| m_j(t)>0] ≤𝔼̃ [ J_m j]=p .

To see this, we write by Bayes' Theorem, the left hand side above as 

    ℙ̃(m_j(t)>0 | J_m j=1) ℙ̃ (J_m j = 1) ℙ̃ (m_j(t)>0)^-1 .

Observe that since ℙ̃ doesn't condition on m_j nor on m_m at any time, J_m j is independent of the σ-algebra conditioned on under ℙ̃, and thus its conditional distribution is (p) so that 𝔼̃[J_m j]=p. Moreover, expanding out m_j(t)>0, we see that under ℙ̃, all the summands except σ_m(0)J_mj are conditionally independent of J_mj, so that because σ_m(t)=-1, conditioning also on J_mj=1 only decreases m_j(t), implying (<ref>). Analogously, if σ_m(0)=1, and m∉{Y_k}_k=1^T, then 𝔼̃[J_mj| m_j(t)>0] ≥ p. Therefore, every summand in the third term in the right-hand side of (<ref>) is nonnegative. 
As a result, we have

    0 ≤σ_ℓ(0) 𝔼̃[J_ℓ j -p| S_j(t)]+ ∑_i∉{Y_k}_k=1^T    σ_i(0) 𝔼̃[J_ij - p| S_j(t)] 
       ≤ |𝔼̃ [m_j(t) | S_j(t)]|+ |𝔼[m_j(0)]|+O(T) .


We now upper bound the right-hand side of (<ref>). Writing each term out, we see that under ℙ̃, except for at most t=O(N^1/2+3ϵ) summands, m_j(t) is distributed as a difference of two binomial random variables with mean that is M_0 ± O(N^1/2+3ϵ) and variance O(N). (Under the measure ℙ_, m_j(0) is of course just a difference of two binomials.) In that case, standard lower and upper tail estimates, via Chernoff bounds for binomial random variables, along with the fact that |M_0|≤ N^1/2 +3ϵ imply that 

    𝔼̃ [m_j(t) | S_j(t)]      =O(N^1/2 +4ϵ) ,         𝔼_[m_j(0)]  =O(N^1/2 +4ϵ) .


Returning to (<ref>), by (<ref>) we see that when σ_ℓ(0)=+1, we have

    𝔼̃[J_ℓ j - p| S_j(t)] + ∑_i∉{Y_k}_k=1^T, σ_i(0) = +1𝔼̃[J_ij - p| S_j(t)] = O(N^1/2+4ϵ) .

There are deterministically at least N/3 terms in the sum above, so that in order to conclude, it suffices to show that for an i∉{Y_k}_k=1^T with σ_i(0)=1, we have that 𝔼̃ [J_ℓ j| S_j(t)]= 𝔼̃[J_ij| S_j(t)].
(One would then divide both sides by the number of terms in the sum above, and obtain the desired.) If ℓ∉{Y_k}_k=1^T, this is evident by symmetry. Else, write, 

    𝔼̃ [J_ℓ j| m_j(t)>0] = ℙ̃(J_ℓ j=1)ℙ̃(m_j(t)>0| J_ℓ j=1)/ℙ̃(m_j(t)>0) .

The conditioning in ℙ̃ is independent of J_ℓ j as well as J_ij so the first term in the numerator is the same under ℓ↦ i. Likewise, for the other two terms, expanding out m_j(t), one sees that since ℙ̃ conditions on J_kj for every k ∈{Y_1,...,Y_t-1}, the other couplings conditioned on under ℙ̃ do not affect the distribution of m_j(t); moreover σ_i(t)=σ_ℓ(t)=σ_i(0)=σ_ℓ(0), so that those remaining two terms are also unchanged under ℓ→ i. 




 §.§ Short time dynamics

In this section we study the evolution of (X_t)_t∈ℕ started from X_0 such that M_0 =  N^1/2 -ϵ until T= N^1/2 +3ϵ. 

We begin by fixing the update sequence Y_1,...,Y_T, then for each realization of the update sequence, we bound probabilities of evolutions of the chain under ℙ_𝒥. 
Recall the definition of ℛ_k from (<ref>). We define the following good events for the update sequence {Y_k}_k=1^T:

    Γ_ω,t^1:={|ℛ_t| < N^ϵ∨2t^2/N}        Γ_ω,t^2:={|∑_k=1^tσ_Y_k (0)|< t^1/2+ϵ} .

The dynamical good event is then defined as Γ_ω= ⋂_t=N^ϵ^TΓ_ω,t^1 ∩Γ_ω,t^2. 


Let X_0 be such that M_0 = N^1/2 -ϵ. There exists c(ϵ)>0 such that 

    ℙ_ω ( Γ_ω^c) ≲ Te^-cN^2ϵ^2 .




We union bound over the (Γ_ω,t^i)^c for i=1,2 and N^ϵ≤ t≤ T. The bound for i=1 follows from a union bound over all t≤ T and the following. For each t≤ T, the probability of selecting a site that has already been updated at time t is at most t/N≤ N^-1/2 +3ϵ.  Therefore, |ℛ_t| ≼ (t, t/N) so that by the Chernoff inequality, 

    ℙ_ω(|ℛ_t|≥max{N^ϵ, 2t^2 N^-1}) ≤ 2e^-cN^ϵ ,

for some c>0.
For the i=2 bound, because the update order (Y_k)_k≤ T is independent of σ(0) and t≤ N^1/2 +3ϵ, by Hoeffding's inequality,

    ℙ_ω(|∑_k=1^tσ_Y_k (0)|≥ t^1/2+ϵ)≤ 2e^-ct^2ϵ ,

because uniformly in t≤ T, the probabilities of σ_Y_t(0)=± 1  are within M_0/N of 1/2 and M_0= N^1/2-ϵ. Union bounding over all N^ϵ≤ t≤ T yields the desired. 


By Lemma <ref>, without loss, we can now restrict our attention to realizations of ω such that the sequence Y_1,...,Y_T satisfies Γ_ω.

We also define a good coupling event measurable with respect to ℱ_t which we will restrict our attention to. Fix a sequence (Y_1,...,Y_T). Begin by defining

    Z_++(t)= {j∈{Y_k}_k=1^t-1 - ℛ_T : σ_j (0)=+ 1, σ_j(t)=+1}

and the analogously defined Z_–,Z_+-,Z_-+, measurable with respect to (Y_k,S_Y_k(k))_k< t. Then for N^ϵ≤ t ≤ T, let

    Γ_𝒥,t^++ = ⋂_s=N^ϵ^t{|∑_j∈ Z_++(s) [J_Y_s j -p]| ≤ s^1/2+ϵ} .
 
Then let Γ_𝒥,t= Γ^++_𝒥,t∩Γ^+-_𝒥,t∩Γ^-+_𝒥,t∩Γ^–_𝒥,t.


Fix an initial configuration X_0 such that M_0 = N^1/2 - ϵ. There exists c(p)>0 such that for every sequence Y_1,...,Y_T, and every  N^ϵ≤ t≤ T,

    ℙ_𝒥 ( Γ^c_𝒥,t) ≲ te^-cN^2ϵ^2 .



By a union bound over all N^ϵ≤ s ≤ t, it suffices to show that there exists c(p)>0 such that for every such s,

    ℙ_𝒥( | ∑_j∈ Z_++(s) [J_Y_s j-p]| ≥ s^1/2 +ϵ (Y_k,S_Y_k(k))_k<s)    ≲exp(-cs^2ϵ)

and similarly for Z_+-(s), Z_-+(s), Z_–(s), then average over all possible realizations of (S_Y_k(k))_k<s. We use Proposition <ref> to jointly sample the couplings {J_Y_s j}_j∈ Z_++(s) and S_Y_1(1),...,S_Y_s-1(s-1) according to the revealing scheme defined in Definition <ref>. One sees by Proposition <ref> that under this revealing process, independently of the couplings that have already been revealed and the information obtained from (S_Y_k(k))_k<s, the distribution of J_j Y_s dominates (p-cN^-1/2+4ϵ) and is dominated by (p+cN^-1/2+4ϵ).  Therefore, conditional on any actualization of (S_Y_k(k))_k<s and therefore Z_++(s), the joint distribution of {J_Y_s j}_j∈ Z_++(s) is dominated by a product measure of (p+cN^-1/2+4ϵ) and dominates a product measure of (p-cN^-1/2 +4ϵ). At that point, using Chernoff–Hoeffding inequality, we see that (<ref>) holds. 


The main estimate on the effective fields at short times t≤ T is the following.  


Fix X_0 with magnetization M_0= N^1/2 -ϵ. Suppose for t≤ T, we are on a set in ℱ_t-1 such that Γ_ω∩Γ_𝒥,t holds and M_t-1≥ M_0-N^2ϵ.
Suppose also that Y_t ∉ℛ_t. There exists c(p)>0 such that for sufficiently small ϵ>0, we have

    ℙ_𝒥(m_Y_t(t)>0|ℱ_t-1)≥1/2 +cN^-ϵ .

In particular, this estimate holds independent of σ_Y_t(0)=σ_Y_t(t-1).



For ease of notation, let i=Y_t. 
By definition, the σ-algebra ℱ_t-1 reveals information about the couplings {J_i Y_k}_k=1^t-1 and is independent of any other couplings to i. 
Using the fact that if j∉{Y_k}_k<t, σ_j(0)=σ_j(t), the event Γ_ω,t^2 implies

    ∑_j∉{Y_k}_k<tσ_j(0) = ∑_j∉{Y_k}_k<tσ_j(t)≥ N^1/2-ϵ-N^1/4+3ϵ .


Now expanding m_i(t), we obtain

    m_i(t)=∑_j∈{Y_k}_k< tσ_j(t) J_ij+∑_j∉{Y_k}_k< tσ_j(0) J_ij .

We first consider the second sum in (<ref>). As remarked earlier, because j∉{Y_k}_k<t, conditional on ℱ_t-1, these J_ij are distributed as i.i.d. (p). Thus, given Γ_ω,t^2 holds, we have the following conditional (on _t-1) stochastic domination:

    ∑_j∉{Y_k}_k<tσ_j(0) J_ij   ≽(N2+(1-ϵ2)N^ 12-ϵ,p)- (N2-(1-ϵ2)N^ 12-ϵ,p) .

By Berry–Esseen Theorem, we thus obtain for some c(p)>0,

    ℙ_(∑_j∉{Y_k}_k<tσ_j(0)J_ij≥p/2 N^1/2 -ϵ) ≥1/2 +cN^-ϵ + O(N^-1/2) .

We now control the contribution of the first term of (<ref>). Consider separately the case t≤ N^2ϵ and t≥ N^2ϵ. If t≤ N^2ϵ, then clearly the first sum in (<ref>) is bounded above by t ≤ N^2ϵ. Now consider the case t≥ N^2ϵ.

Recall the definitions of Z_++, Z_+-, Z_-+ and Z_– from (<ref>). Then we can expand

    ∑_j∈{Y_k}_k<tσ_j(t) J_ij  =    ∑ _j∈ℛ_tσ_j(t) J_ij + ∑_j∈ Z_++(t) J_ij +∑_j∈ Z_-+(t)J_ij
        - ∑_j∈ Z_+-(t)  J_ij -∑_j∈ Z_–(t)J_ij .

First of all, by the fact that Γ_ω,t^1 holds, |ℛ_t| and in turn the first sum on the right-hand side of (<ref>), are bounded above by N^7ϵ independently of t≤ T.

For the latter four sums in (<ref>), we use the fact that Γ_𝒥,t holds. 
First we bound how many summands there are in each of the four terms. Since Γ_ω,t^1,Γ_ω,t^2 both hold and M_t-1≥ M_0-N^2ϵ, 

    ||Z_++(t)| + |Z_+-(t)|-|Z_–(t)|-|Z_-+(t)||    ≤ N^1/4 +3ϵ+N^7ϵ    
         |Z_+-(t)|-|Z_-+(t)|    ≤ N^2ϵ+N^7ϵ ,

so that |Z_++(t)|+|Z_-+(t)| ≥ |Z_–(t)|+|Z_+-(t)|-N^1/4+3ϵ- 2N^ 7ϵ-N^2ϵ. Now we observe that by definition of Γ_𝒥,t, we have 

    | ∑_j∈ Z_++(t) [J_Y_t j-p]| ≤ t^1/2 +ϵ

and likewise when summing over Z_+-(t),Z_-+(t) and Z_–(t). 
If Z_+(t) = Z_++(t) + Z_-+(t) and Z_-(t) = Z_–(t) + Z_+-(t), by applying (<ref>) separately to Z_+(t) and Z_-(t), we see that under the event Γ_ω∩Γ_𝒥,t, by (<ref>) and the fact that N^2ϵ≤ t≤ N^1/2+3ϵ, for ϵ small,

    ∑_j∈{Y_k}_k<tσ_j(t) J_ij≥ p[Z_+(t)-Z_-(t)]-4t^1/2+ϵ≥ -2N^1/4+3ϵ ,

and if t≤ N^2ϵ the same bound trivially holds.
Combined with (<ref>), this implies that

    ℙ_𝒥(m_Y_t(t)≤ 0 |ℱ_t-1)   ≤ℙ_𝒥(∑_j∉{Y_k}_k<tσ_j(0)J_ij≤ 3 N^1/4 +3 ϵℱ_t-1) 
       ≤1/2 -cN^-ϵ+O(N^-1/2) ,

yielding the desired for all sufficiently small ϵ>0.


The following shows the implications of Proposition <ref> for the magnetization chain.

Fix X_0 with magnetization M_0=N^1/2-ϵ. Suppose that t≤ T, that Γ_ω∩Γ_𝒥,t holds, and that M_t-1≥ M_0 - N^2ϵ. Suppose also that Y_t ∉ℛ_t; if σ_Y_t(0)=-1,

    ℙ_𝒥 (M_t-M_t-1 = +1|ℱ_t-1) = 1-ℙ_𝒥 (M_t-M_t-1 = 0|ℱ_t-1) ≥1/2+cN^-ϵ ,
 
for some uniform c(p)>0 and if σ_Y_t(0)=+1,

    ℙ_𝒥 (M_t-M_t-1 = 0|ℱ_t-1) = 1-ℙ_𝒥 (M_t-M_t-1 = -1|ℱ_t-1) ≥1/2+cN^-ϵ .
 

 
We now use Corollary <ref> to lower bound the magnetization chain (M_t)_t≤ T. Define for ϵ,t,θ>0, the following subset of the filtration ℱ_t:  

    ℬ_ϵ,t,θ    ={ M_k > M_0 - N^2ϵ+θ k N^-ϵ k≤ t} ,

and observe that ℬ_ϵ,t,θ is an  increasing event in the magnetization.

 
Fix X_0 such that M_0= N^1/2-ϵ. Suppose Γ_ω∩Γ_𝒥,T holds for the realization of ℱ_t. Then for all θ>0 sufficiently small, there exists a constant d(p,θ)>0 such that  

    ℙ_𝒥(ℬ^c_ϵ,T,θ)≤ T e^-dN^2ϵ^2 .




We fix any t≤ T and show ℙ_𝒥 (_ϵ,t,θ^c) ≤ te^-dN^2ϵ^2, implying in particular, the desired. In order to do so, we consider two random walk chains, ℳ^+_t which lower bounds the change in magnetization over times when σ_Y_k(0)=+1 and ℳ^-_t which does the same over times when σ_Y_k(0)=-1. The chains ℳ^+_t and _t^- are defined as follows: let B_i^+, B_i^- be i.i.d. (1/2+cN^-ϵ) for c(p)>0 given by Corollary <ref>,

    ℳ^+_t+1-^+_t = 1-B_t^+ ,         ^-_t+1-^-_t = B_t^- ,

and _0^+ = _0^-=0.
Define also t_+= ∑_j=1^t  1{σ_Y_j(0)=+1} and analogously t_-. Clearly t_+ + t_- =t. As long as _ϵ,t-1,θ holds for some θ≥ 0, by Corollary <ref>,

    M_t ≽ℳ_t-|ℛ_t|        _t:= M_0+ℳ_t_+^+ + ℳ_t_-^- .


Let  be the probability distribution over (B_i^+,B_i^-)_i and therefore the random walks _t^+ and _t^-. Moreover, let 𝒜_ϵ,t,θ be the analogue of ℬ_ϵ,t,θ for the random walk ℳ_t-|_t| (note that _t is fully determined by the sequence (Y_k)_k≤ T).
We prove that (_t - |_t| ∈_ϵ,t,θ^c) ≤ t e^-dN^2ϵ^2 for sufficiently small θ>0 for some c(p,θ)>0; this would imply the desired since M_t and _t can be coupled through all realizations of _ϵ,t,θ in a way that M_t≥_t, implying that _ϵ,t,θ also holds. 

To prove this, note first that for all t≤ N^2ϵ, _ϵ,t,θ holds trivially for every θ≥ 0. Thus consider t≥ N^2ϵ. Observe that since Γ_ω holds, for every N^ϵ≤ t≤ T,

    |t_+-t_-| ≤ t^1/2+ϵ ,         |_t| ≤ N^ϵ∨ 2t^2/N .

By Hoeffding's inequality, there exists d>0 such that for every δ>0,

    (|_t_++t_+( 12-cN^-ϵ)|    ≥ t_+^1/2+δ)≤ 2e^-dt_+^2δ , 
    (|_t_--t_-( 12+cN^-ϵ)|    ≥ t_-^1/2+δ) ≤ 2e^-dt_-^2δ .

Combining the above with (<ref>), we see that for some different d>0,

    (|_t_++_t_- - (t_–t_+2 + tcN^-ϵ)| ≥ t_+^1/2+δ+t_-^1/2+δ) ≤ 4e^-dt^2δ

and in particular, letting ϵ=δ, since |t_+ - t_-| ≤ t^1/2+ϵ,

    (_t ≤ M_0-3t^1/2+ϵ+tcN^-ϵ)≤ 2e^-dt^2ϵ .

Now note that by the bound on |ℛ_t| in (<ref>), for all N^ϵ≤ t≤ T, 

    M_0 -3t^1/2+ϵ-(N^ϵ∨ 2t^2/N)+c t N^-ϵ≥ M_0 - N^2ϵ + θ t N^-ϵ
 
for, say, θ=c/2; this implies by a union bound and (<ref>), that for every t≤ T,

    ℙ_(M_t∈_ϵ,t,θ^c)≤(_t - |_t| ∈_ϵ,t,θ^c) ≤ te^-dt^2ϵ^2 .





 §.§ Long time dynamics

Using the bounds in <ref> on the zero-temperature dynamics Markov chain, we can deduce the following conditions at time T=N^1/2+3ϵ. 


If M_0 = N^1/2-ϵ and T=N^1/2+3ϵ, there exists θ(p)>0 such that 

    lim_N→∞ℙ(⋂_i∉{Y_k}_k<T{ m_i(T)>ϵ p θ N^1/2 +2ϵ}) =1 .



We consider a fixed i∉{Y_k}_k<T and
prove the proposition using the decomposition of m_i used in the proof of Proposition <ref> and then union bound over all such i∉{Y_k}_k<T. First note that by a union bound with Lemmas <ref>–<ref> and Proposition <ref>, if θ is as in Proposition <ref>, there exists c(p)>0 so that

    ℙ (M_T∈ℬ_ϵ,T-1,θ,Γ_ω,Γ_,T)≥ 1-O(Te^-cN^2ϵ^2) .

By a union bound, it suffices to prove that there exists c>0 such that for every i∉{Y_k}_k<T, there exists θ>0 such that

    ℙ_(m_i(T)≤ϵ pθ N^1/2+2ϵ|ℱ_T-1,Γ_ω,Γ_,T, _ϵ,T-1,θ) ≤ e^-cN^ϵ .

Now suppose we are on the intersection of ℬ_ϵ,T-1,θ, Γ_ω and Γ_,T.
The couplings between i and sites not in {Y_k}_k<T are independent of ℱ_T-1 and are handled identically to the proof of Proposition <ref>, whence by Hoeffding's inequality applied to the difference of the binomial random variables in (<ref>), there exists c(p,θ)>0 such that

    ℙ_(∑_j∉{Y_k}_k<Tσ_j(0)J_ij≤ -p4θ N^1/2+2ϵ) ≤ e^-cN^ϵ .

We now bound the contribution from couplings to sites j∈{Y_k}_k<T-_T.
Under the event ℬ_ϵ,T-1,θ, the magnetization has M_T-1≥  M_0+ θ N^1/2 +2ϵ-N^2ϵ. Recalling the sets Z_++(T),Z_+-(T),Z_-+(T),Z_–(T), as before, because Γ_ω holds, we have

    ||Z_++(T)| + |Z_+-(T)|-|Z_–(T)|-|Z_-+(T)||    ≤ N^1/4 +3ϵ+N^7ϵ    
         |Z_-+(T)|-|Z_+-(T)|    ≥θ N^1/2+2ϵ -N^2ϵ-N^7ϵ ,

for some θ(p)>0, implying that

    |Z_++(T)|+|Z_-+(T)|-|Z_–(T)|-|Z_+-(T)| ≥θ N^1/2+2ϵ-o(N^1/2) .

In order to reveal jointly the couplings {J_Y_k i}_k<T conditional on the history of the chain (Y_k,S_Y_k(k))_k<T, we use the revealing procedure defined in Definition <ref>, taking i to be Y_T; we know by Proposition <ref> that under this revealing procedure, for every realization of (S_Y_k)_k<T, the joint distribution of {J_l i}_l∈ Z_++(T) is dominated by a product measure of (p+N^-1/2+4ϵ) and dominates independent (p-N^-1/2+4ϵ) and the same holds for {J_l i}_l∈ Z_+-(T), and likewise when l∈ Z_-+(T) and l∈ Z_–(T). 
Then letting Z_+=Z_++(T)+Z_-+(T) and Z_-=Z_–(T)+Z_+-(T), by Hoeffding's inequality,

    ℙ_(∑_j∈{Y_k}_k<T-_T J_ijσ_j(T)  ≤p2 θ    N^1/2+2ϵ_T-1) 
       ≤ℙ_(∑_j∈ Z_+ J_ij≤ p|Z_+|-  p4 θ N^1/2+2ϵ_T-1) 
             + ℙ_(∑_j∈ Z_- J_ij≥ p|Z_-| +  p4 θ N^1/2 +2ϵ_T-1) 
       ≤   2e^-c N^ϵ ,

for some c(p,θ)>0.
Together with the bound of N^7ϵ on ∑_j∈ℛ_T J_ijσ_j(T),  and a union bound, we obtain for some c(p,θ)>0, under _ϵ,T-1,θ∩Γ_ω∩Γ_,T,

    ℙ_(⋃_i∉{Y_k}_k<T{m_i(T)≤ p6 θ N^1/2+2ϵ}) ≲   N e^-cN^ϵ .




If M_0=N^1/2-ϵ and T'= N^2/3, we have 

    lim_N→∞ℙ(⋂_i=1^N { m_i(T')>0}) =1 .



First, consider the update sequence Y_T+1,...,Y_T'. Dominating the number of updates there that are in {Y_k}_k≤ T by (T',T/N), we see that the probability of that being at most N^1/2 is 1-O(e^-c√(n)). At the same time, since T'=o(N) and M_0=N^1/2-ϵ, with probability at least 1-O(e^-cN^2/3) there are at least N^2/3-ϵ distinct sites i∈{Y_k}_k=T+1^T'-{Y_k}_k≤ T that have σ_i(0)=-1. Since both of these happen with ℙ_ω-probability going to 1 as N→∞ and are independent of  and _T, suppose we are on the intersection of these events (and also Γ_ω) and fix any such an update sequence. Then let _1,...,_n∈{Y_k}_k=T+1^T'-{Y_k}_k≤ T be the sequence of updates in Y_T+1,...,Y_T' with initial spin value -1 and not in _T (observe that n≥ N^2/3-ϵ).

Assume also, by Proposition <ref> that every site i∉{Y_k}_k<T has m_i(T)≥ϵ p θ N^1/2 +ϵ, as this occurs w.h.p. Now consider sites i∈{Y_k}_k<T. We will need the following lower bound on m_i(T): if T=N^1/2 +3ϵ and Γ_ω holds,  there exists c(p,θ)>0 such that

    lim_N→∞ℙ_ (  ⋃_i ∈{Y_k}_k≤ T{m_i(T) ≤ -N^1/2 + 4ϵ}) ≲ Te^-cN^2ϵ .

We now define a new ℙ_ event Γ^2_ as 

    Γ^2_ =⋂_i∈{Y_k}_k≤ T{∑_j∈_1,...,_m J_ij≥ (p-ϵ)m, |∑_j∉{Y_k}_k≤ Tσ_j(0)J_ij| ≤ N^1/2+ϵ} .
 
By a union bound and standard applications of Hoeffding's inequality as done before, along with the fact that Γ^2_ω,T holds, we see that for some c>0,

    ℙ_ ((Γ_^2)^c) ≤ 2Te^-cN^2ϵ ,

so without any loss, we also assume we are on the event Γ_^2. 

Recall that for every j∉{Y_k}_k≤ T, σ_j(0)=σ_j(T).
At the same time, we can assume a worst case bound on the couplings between site i and other sites j∈{Y_k}_k≤ T, which is to say we take every such J_ijσ_j(T)=-1, contributing at most -N^1/2 +3ϵ to m_i(T). Putting these together, we see that for update sequences in Γ_ω, under the event Γ_^2 we have deterministically that for every i∈{Y_k}_k≤ T,

    m_i(T) ≥ -N^1/2+ϵ-N^1/2+3ϵ =-o(N^1/2+4ϵ)

so that (<ref>) holds. Under the intersection of the events in (<ref>) and (<ref>), we claim that by time T', deterministically, every site will have positive effective field. Note that our update sequence Y_T+1,...,Y_T' is such that the dynamics only selects at most N^1/2 sites in {Y_k}_k≤ T between times T+1 and T' and as a result, by (<ref>), for every i∉{Y_k}_k≤ T, for every T+1≤ t ≤ T', its field satisfies 

    m_i(t)≥ m_i(T) -N^1/2         m_i(t)>0

(only sites with nonpositive field can flip from +1 to -1 and decrease the field on i). At the same time, every time an update on a site _1,...,_n occurs, that spin has positive field by the above, and so it flips from -1 to +1. Then since n≥ N^2/3-ϵ and Γ_^2 holds, for every i∈{Y_k}_k≤ T, its field satisfies

    m_i(T')≥ m_i(T)-N^1/2+ (p-ϵ)N^2/3-ϵ         m_i(T')>0 ,

whenever ϵ is sufficiently small, concluding the proof of the proposition. 



By Proposition <ref>, by time T'=N^2/3, with high probability, every site i has positive field. In that case by attractivity of the dynamics, whenever a negative site is selected to be updated, it flips to plus and those are the only possible spin flips, so that by the time every site has been updated again after time T', the zero-temperature dynamics will have absorbed into the all-plus state.

Putting this together with the grand coupling of chains starting from every possible M_0 implies that if ϵ>0 is sufficiently small, for every configuration with M_0≥ N^1/2 -ϵ, 

    lim_N→∞ℙ ( M_∞=N)=lim_N→∞ℙ (lim_t→∞ M_t =N)=1 .



By spin flip symmetry, when M_0≤ -N^1/2-ϵ, with high ℙ_,ω-probability, M_∞=-N.
Thus, for every i=1,...,N,

    𝔼_σ(0)[(𝔼_ω,𝒥[σ_1(∞)])^2]     = 𝔼_σ(0)[(𝔼_ω,𝒥[σ_1(∞)])^2( 1{|M_0|≥ N^1/2-ϵ}+ 1{|M_0|< N^1/2-ϵ})] 
       ≥ℙ_σ(0)(|M_0| ≥ N^1/2-ϵ)   min_σ(0):|M_0|≥ N^1/2-ϵ (𝔼_ω,𝒥[σ_1(∞)])^2  .

Upper bounding the left-hand side by 1 and taking limits as N→∞ on both sides, we obtain by Fact <ref> and Theorem <ref> that

    lim_N→∞𝔼_σ(0)[ (𝔼_ω,𝒥 [σ_1(∞)])^2] = 1 .

By Jensen's inequality,   

    q_D(N)= 𝔼_σ(0) [  𝔼_𝒥 [(𝔼_ω[σ_i(∞)])^2]  ] ≥𝔼_σ(0)[(𝔼_ω,𝒥 [ σ_1 (∞)])^2]

and trivially upper bounding q_D(N)≤ 1 implies lim_N→∞ q_D(N)=1.




§ DIFFERENT BEHAVIOR WITH HEAVY TAILS




 §.§ Heavy-tailed disordered CW model

In this section, we demonstrate that the behavior above is not a general consequence of a mean-field disordered ferromagnetic system. We show that when we consider heavy-tailed coupling distributions, a completely different picture, regarding the structure of local-minima and the probability of ending up in them, emerges. One intuition for this comes from the fact that if we had considered an Erdős–Rényi graph with p=λ/N for λ>0 fixed, the results of <ref> on the dilute CW model would no longer hold as the underlying random graph would have many disconnected clusters of influence, and the dynamics would absorb in one of the many possible independent assignments of {± 1} to the disconnected clusters. The arguments here are straightforward but we provide them to emphasize the contrast to the situation with light-tailed couplings.

If J_ij∼μ is non-negative, we say it is heavy-tailed if 

    ℙ(J_ij≥ x)=x^-αL(x)
 for some 0<α<1 and some slowly varying L(x) (i.e., for every a>0, L satisfies lim_x→∞ L(ax)/L(x)=1). 
As before, for σ∈{±1}^N define the Hamiltonian of this disordered Curie–Weiss model by H(σ)= -1/N∑_i,j=1^N J_ijσ_iσ_j.

If {J_ij}_i,j are non-negative heavy-tailed i.i.d. couplings with 0<α<1, then H has at least one non-trivial local minimum on the hypercube {± 1}^N with high probability. Moreover, the zero-temperature dynamics of the corresponding disordered Curie–Weiss model satisfies ϵ<q_D(N)<1-ϵ for some ϵ>0 uniform in N. 


One can also glean from the proof (specifically (<ref>)) that on average, the number of local minima grows exponentially in N as seen in many spin-glass models. While we expect that in the light-tailed setup, also with high probability there exist non-trivial local minima, there we guess the number in fact grows sub-exponentially.

First recall the following classical theorems concerning sums and maxima of i.i.d. random variables with power-law tails (see e.g., <cit.>):


Let Y_i be i.i.d. random variables satisfying the following conditions: there exists 0<α<1 such that x^αℙ(|Y_1| ≥ x)=L(x) is slowly varying and for some β∈ [-1,1], as x→∞,

    ℙ (Y_1 ≥ x)/ℙ(|Y_1| ≥ x) ⟶ (1+β)/2.

Then there exists a sequence a_n given by a_n^-αL(a_n)=n^-1(∫_0^∞ x^-αsin x dx)^-1 so that

    ∑_i=1^n Y_i/a_n⟶ Z_α,β     ,

where Z_α,β is a standard α-stable random variable with asymmetry parameter β.
 


If Y_1,...,Y_n are i.i.d. with ℙ(Y_i≥ x)=x^-α L(x) for 0<α<1 and L(x) is slowly varying, then for each x, as n→∞,

    ℙ(max_i=1,..,n Y_i  ≤ b_n x ) ⟶Φ_α(x)=e^-x^-α1{x> 0}

where b_n is the smallest sequence such that b_n^-α L(b_n) = n^-1.


We prove that with high probability, the Hamiltonian H has non-trivial local minima. In order to proceed we need to define bully bonds. 
For a coupling realization {J_ij}_1≤ i<j≤ N, the coupling J_ij is a bully bond if 

    J_ij > max{∑ _k≠ j |J_ik|,∑_k≠ i |J_jk|} ,

and we define the event, E_ij={J_ij >max{∑_k≠ j |J_ik|, ∑_k≠ i |J_jk|}}.


We begin by proving that with high probability, there exist non-trivial local minima. Notice that if, with probability going to 1 as N→∞, there exist at least two bully bonds, then H has non-trivial local minima: if E_ij, E_kl hold for k,l∉{i,j}, both σ_i=σ_j=+1, σ_k=σ_l=-1 and σ_i=σ_j=-1,σ_k=σ_l=+1 are satisfied independent of σ_V-{i,j,k,l} and neither combination is possible in a ground state of H.
By symmetry between 1≤ i<j ≤ N/2 and N/2<k<l≤ N, and a union bound, it suffices to prove that 

    lim_N→∞ℙ_(∑_i,j=1^N/2 1{E_ij}>0)=1 .

We show this by considering the probability that max_1≤ i<j≤ N/2 J_ij is a bully bond: 

    ℙ_(J_12 >  max{∑_k≠ 1 J_1k,    ∑_k≠ 2 J_2k} J_12=max_1≤ i<j≤ N/2 J_ij) ≥
        1-ℙ_(max_1≤ i<j≤ N/2 J_ij≤ N^2/α-ϵ) - 2ℙ_(∑_k=3^N J_1k≥ N^2/α-ϵ)

for some small ϵ(α)>0. In the inequality, we used a union bound and the fact that the coupling distribution of J_1k is decreased by conditioning on J_1k not being the maximum coupling in a set.
Observe that the first probability above is o(1) by Theorem <ref> and the fact that it is a maximum over order N^2 i.i.d. heavy-tailed random variables, and the second probability is o(1) by Theorem <ref> and the fact that the sum is over O(N) i.i.d. heavy-tailed random variables. By symmetry this implies that with high probability the maximum over all couplings J_ij for 1≤ i<j ≤ N/2 is a bully bond, implying that with high probability there exist non-trivial local minima.  

It remains to prove that q_D(N) is uniformly bounded away from 0 and 1. To do so, we begin by computing the expected number of bully bonds, 

    𝔼_[∑_ij 1{E_ij}]= N(N-1)/2ℙ_(E_12) .

Let Z_α=Z_α,β with β=1 and let the sequence a_N be defined as in Theorem <ref>; by definition of a_N and independence,

    ℙ_(E_12)      ≥ℙ_ ( J_12 > a_2N)ℙ_(∑_k≠ 1 J_1k+∑_k≠ 2 J_2k≤  a_2N-2) 
        ≥c/2N(ℙ_(Z_α≤ 1)+o(1))≥c'/N ,

for constants c(α),c'(α)>0. Note that this implies that 𝔼_[∑_ij 1{E_ij}] ≥ρ N for some ρ(α)>0. Moreover, ∑_ij 1{E_ij} is bounded above by N/2 since every vertex can be adjacent to at most one bully bond. As a consequence, we have that 

    ℙ_(∑_1≤ i<j≤ N 1{E_ij}≥ρ N) ≥ 2 ρ .

We claim that this implies q_D(N) is uniformly bounded away from 0 and 1. If with probability greater than ϵ>0, there are at least δ N sites adjacent to bully bonds, then the probability of a single site i being adjacent a bully bond J_ij is at least ϵδ. The contribution to q_D on that event is 1/2; this is because with ℙ_σ(0),𝒥-probability 1/2, that bully bond is initially satisfied (σ_i(0)=σ_j(0)) and otherwise, it is equally likely that the dynamics absorbs with σ_1=σ_j=+1 as σ_1=σ_j=-1—this is completely determined by whether σ_i or σ_j is updated first. The definition of q_D(N) then implies that ϵδ/2<q_D(N)<1-ϵδ/2 as desired.




 §.§ Heavy–tailed spin glasses

Using the above proof, one can derive similar estimates for heavy–tailed spin glasses, where J_ij is now distributed as a symmetric heavy-tailed random variable with ℙ(|J_ij|≥ x)=x^-α L(x) for L slowly varying and 0<α<1. The proof carries through as in the proof of Theorem <ref>, with the sums becoming sums of absolute values of such random variables, which are in the same basin of attraction of fully asymmetric α-stable random variables. 
Therefore, a straightforward adaptation of the proof of Theorem <ref> shows that for such coupling distributions, the heavy-tailed spin glass has local minima with high probability, and its zero-temperature dynamical order parameter is uniformly bounded away from 0 and 1.

abbrv


