The Spectral Gap of the REM under Metropolis Dynamics

L. R. G. Fontes Universidade de São Paulo

M. Isopi Universitá di Roma 1

Y. Kohayakawa Universidade de São Paulo

P. Picco CPT, CNRS, Marseille

Abstract

We derive upper and lower bounds for the spectral gap of the Random Energy Model under Metropolis dynamics which are sharp in exponential order. They are based on the variational characterization of the gap. For the lower bound, a Poincaré inequality derived by Diaconis and Stroock is used. The scaled asymptotic expression is a linear function of the temperature. The corresponding function for a global version of the dynamics exhibits phase transition instead.

We also study the dependence of lower order terms on the volume. In the global dynamics, we observe a phase transition. For the local dynamics, the expressions we have, which are possibly not sharp, do not change their order of dependence on the volume as the temperature changes.

Mathematics Subject Classification 1991: 60K35, 82B44. Key words and phrases: Disordered systems, spin glasses, random energy model, Metropolis dynamics, Glauber dynamics, convergence to equilibrium, spectral gap, dynamical phase transition

1 Introduction

The Random Energy Model (REM)([1], [2]) is a disordered hamiltonian spin system designed as a caricature of the Sherrington-Kirkpatrick (SK) Spin-Glass Model ([10]). Both models are mean-field ones. While in the SK model one has gaussian pair interactions only, in the REM there are gaussian multibody interactions. The hamiltonian or energy function for the SK model is (for σ a given configuration of spins + or −1 in a volume Λ)

H_{SK}(σ) = −|Λ|^{−1/2} ∑_{i,j∈Λ} J_{ij}σ_{i}σ_{j},  (1.1)

where the sum is over all pairs of distinct sites in Λ and {J_{ij}, i, j} is a family of i.i.d. standard gaussians, whereas that for the REM is

H_{REM}(σ) = −\frac{|Λ|^{1/2}}{2^{|Λ|/2}} ∑_{α⊂Λ} J_{α}σ_{α},  (1.2)

where the sum is over all the 2^{N} subsets α of Λ, {J_{α}, α} is a family of i.i.d. standard gaussians defined on a common probability space (E, Σ, IP) and σ_{α} = ∏_{i∈α} σ_{i} (σ_{∅} = 1).

We observe that for the REM the hamiltonians of all configurations form a family of i.i.d. gaussians with mean zero and variance |Λ|. A proof of this elementary fact is provided in the appendix A. That could be taken as an alternative description of this model. Indeed it is the usual one and we will adopt it in the next section.

The equilibrium statistical mechanics of the REM has been much studied, e.g., in a non rigorous way, in ([1], [2]) and, in a rigorous way, in ([3], [4], [7]). We quote some of the (rigorous) results that will be important for understanding some aspects of the dynamics. Given β ≥ 0, the inverse temperature, taking Λ = {1, …, N}, let us denote by

Z_{N} ≡ Z_{N}(β) = ∑_{σ} e^{−βH_{REM} (σ)}  (1.3)

the finite volume partition function and by

F_{N}(β) = \frac{1}{N} log Z_{N}(β)  (1.4)

the finite volume free energy. It was proved in [4] that for all β ≥ 0 the limit lim_{N→∞} F_{N}(β) = F (β) exists IP -almost surely and in L^{p}(E, IP) for 1 ≤ p < ∞. F (β) is a non random function which is twice differentiable in β but the second derivative has a jump at β_{c} = \sqrt{2 log 2}. In fact, F (β) is equal to β^{2}/2 + β_{c}^{2}/2 for β < β_{c} and β_{c}β for β ≥ β_{c}, as expected from the results of [1]. This is called in the physics literature a third order phase transition.

The point is, depending if we are in a high temperature regime (β < β_{c}) or in a low temperature one (β ≥ β_{c}), not only that the free energy changes from a quadratic function of β to a linear one but that the difference between the finite volume free energy and its infinite volume limit is exponential in the high temperature case and this occurs almost surely, whereas in the low temperature regime this difference behaves as C(ω, β, N)\frac{log N}{N} for some random function C(ω, β, N). This function converges in IP -probability to a non-random limit but does not converge IP -almost surely and an interval where C(ω, β, N) fluctuates IP -almost surely is identified. More precisely, it was proved in [4] that if 0 ≤ β < β_{c} then

F (β) − e^{−λ(β)N} ≤ F_{N}(β) ≤ F (β) + e^{−λ(β)N}  (1.5)

IP -almost surely and in L^{1}(E, IP) for some λ(β) > 0 if β < β_{c}. If β ≥ β_{c} then the rate of convergence is more subtle, depending if we want a IP -almost sure result or one in IP - probablity. Namely, calling

V_{N}(β) = \frac{β_{c}}{β} \frac{log [Z_{N}e^{−NF (β)}]}{log N},  (1.6)

this quantity has a behavior which is radically different in IP -probability and IP almost surely. It was proven in [4] that IP -almost surely

lim sup_{N→∞} V_{N}(β) ≤ \frac{1}{2}  (1.7)

and also IP -almost surely

lim inf_{N→∞} V_{N}(β) ≥ −\frac{1}{2}.  (1.8)

These two results do not imply that V_{N}(β) does not converge IP almost surely, this question was solved later, namely, it was proven in [7] that we have IP -almost surely

lim sup_{N→∞} V_{N}(β) = \frac{1}{2}  (1.9)

and also IP -almost surely

lim inf_{N→∞} V_{N}(β) = −\frac{1}{2}.  (1.10)

The result in IP -probability (and in L^{1}(Ω, IP) ) is simpler. In [7] it is proved that

lim_{N→∞} V_{N}(β) = −\frac{1}{2}  (1.11)

as it was expected from [2].

In this work we consider a dynamical version of the model, namely, the REM undergoing a Glauber dynamics (Metropolis). That is, we are considering a dynamics in random environment. We study the speed of convergence to equilibrium, the exponential rate of which is given by the spectral gap (or just gap) of the dynamics, which is the difference between the first and second eigenvalues of the transition probability matrix of the continuous time Markov chain defining it (see [5] Proposition 3, also [20]). As in other dynamics of spin systems, this gap goes to zero when the volume goes to infinity and one of the main questions in the study of the approach to equilibrium is the exact rate at which it does so. It is natural to consider the inverse of the gap instead of the gap, the former quantity being linked to the relaxation time. In non random mean field models at low temperature, the logarithm of the inverse of the gap grows like the volume. At high temperature, it is o(N) and grows at least as the logarithm of the volume. In short range random systems, it is expected that the inverse of the spectral gap grows in a slower way at low temperature. This is a very active line of research. Therefore, it is important to clarify at least the case of one of the standard random mean field models, where we know very well the statics.

To get bounds for the inverse of the gap, we use a variational characterization and a bound derived by Diaconis and Stroock based on that ([5]). A nice percolation problem in the hypercube with |Λ| dimensions comes into play. We prove that for the REM the logarithm of the inverse of the spectral gap grows like the volume. We give its exact asymptotic behavior by dividing it by the volume and proving that this normalised quantity converges IP -almost surely for all β to the linear non random function β_{c}β (which is also the free energy of the REM at low temperature). We give IP almost sure upper and lower bounds for the finite volume error of approximation of this quantity to its limit, in the very same spirit of (1.7) and (1.8). The magnitude of these bounds are of order \sqrt{\frac{log N}{N}}, which suggests that the actual error may be bigger than that for the free energy (which is of order \frac{log N}{N} for β ≥ β_{c} and exponentially decaying in N for β < β_{c}, as pointed above). We conjecture that this is indeed the case and that the constant of proportionality is random. Also, we do not expect to see any phase transition in the behavior of this constant.

Our first theorem (Theorem 1 on Section 5) implies that there is no dynamical phase transition (interpreted as a change of behavior in the limiting scaled gap as a function of the temperature) for this model. Note that in the Curie-Weiss model, there is a dynamical phase transition for the dynamics induced on the magnetizations, in the sense that, at low temperature, the logarithm of the spectral gap is proportional to the volume times the difference between the canonical free energy computed at magnetization zero and the canonical free energy computed at its minimum, whereas at high temperature it is o(N).

In the final section of this paper, we consider a global Metropolis dynamics for the REM for which the scaled gap behaves asymptotically as a function of the temperature which does undergo a (third order) phase transition. We give also IP -almost sure bounds for the rate at which the scaled gap converges to its limit and we see here also a phase transition on the rate.

As regards other disordered dynamical models, Cassandro et al. have studied a random walk with random traps, with a different approach, using coupling techniques, to get the order of the speed of convergence to equilibrium [6].

Besides being of its own interest, spin glass dynamics has been studied in the hope of getting a better understanding of the phase picture at equilibrium. As a matter of fact the early (nonrigorous) paper by Sompolinsky and Zippelius on dynamics for the SK model ([12], [10]) takes mainly this point of view. They considered a soft spin approach (real valued spin variables in a confining bistable potentials) so that they could work with quantities varying continuously and write down a Langevin equation. Part of their theory has been made rigorous by Ben Arous and Guionnet ([17], [18], [14]). Their study is for time scales shorter than the ones we are dealing with.

The physics literature on the subject of dynamics of disordered systems is now very large and we will not make any reference to it here. The interested reader is referred to Parisi’s Varenna 1996 Lectures for an introductory discussion and some bibliography ([11]).

On a rigorous ground there are at least two type of results one may try to prove. Starting directly with an infinite system the goal is to understand anomalous (e.g. non-exponential) relaxation to equilibrium.

Almost sure and average results in this direction have been obtained by Gielis and Maes ([19]), Cesi, Maes and Martinelli ([8], [9]) and Guionnet and Zegarlinski ([15], [16]).

We note here that some of these results are valid only for (disordered) ferromagnets, while others apply to spin glasses as well.

Here we take a complementary point of view and ask questions on the asymptotic behaviour of a dynamical quantity (the autocorrelation time) in the infinite volume limit. A priori our results are consistent with non-exponential relaxation in infinite volume. We plan to investigate the relationship between the asimptotics of the gap and infinite volume behaviour in a forthcoming paper.

The rest of the paper is organized as follows. In the next section we describe the model in detail and introduce the spectral gap of the Metropolis dynamics in its variational characterization and its relation with relaxation time. In Sections 3 and 4, we derive upper and lower bounds for the inverse of the gap, respectively, leaving Section 5 for the the summing up of those in Theorem 1 and remarks. In Section 6 we consider a modification of this dynamics. Appendices are devoted to auxiliary results.

2 The Model

Throughout we consider the Random Energy Model (REM) as a non-equilibrium system undergoing Metropolis dynamics in finite volume. We want to study the behavior of the gap between the first and second eigenvalues of the infinitesimal generator of the corresponding continuous time Markov process (or of the probability transition matrix; the gap is the same) as the volume goes to infinity.

Let Λ be a nonempty set with |Λ| = N and let Ω denote {−1, 1}^{Λ}. Let H = {H(σ), σ ∈ Ω} be an independent family of Gaussian random variables with common mean zero and common variance N defined on a probability space (E, Σ, IP). H plays the role of the random hamiltonian or energy function. We consider a continuous-time Markov chain with state space Ω with transition probabilities that are reversible with respect to the Gibbs measure μ_{N} on Ω, which is obtained from H and the inverse temperature parameter β in the usual way, that is

μ_{N}(σ) = \frac{1}{Z_{N}} exp\{−βH(σ)\}, σ ∈ Ω.

More specifically, we consider Metropolis type transition probabilities, given by

P (σ, σ′) = exp{−β(H(σ′) − H(σ))^{+}}/N, if ||σ′ − σ|| = 1,
= 0, if ||σ′ − σ|| > 1,
= 1 − ∑_{σ′′≠σ} P (σ, σ′′), if σ′ = σ,  (2.1)

where a^{+} = max\{a, 0\} and ||x|| = \frac{1}{2} ∑_{i=1}^{N} |x_{i}|.

Note that these transition probabilities are random variables defined on (E, Σ, IP). That is, we have an inhomogenous random walk on the hypercube Ω in the random environment defined by the transition probability valued random variables P (σ, σ′). We are interested in properties of this dynamics that are true for almost all realisations of the random hamiltonian H.

We recall now some basic facts about Markov chains. Let P (·, ·) be the transition probability for an irreducible Markov chain in a finite state space S which is reversible with respect to a measure μ on S. That is, μ(x)P (x, y) = μ(y)P (y, x) for all x, y ∈ S.

Let ϕ be a real valued function on S. Let us define

V ar(ϕ) = \frac{1}{2} ∑_{σ,σ′}(ϕ(σ) − ϕ(σ′))^{2}μ(σ)μ(σ′),  (2.2)
E(ϕ, ϕ) = \frac{1}{2} ∑_{σ,σ′}(ϕ(σ) − ϕ(σ′))^{2}Q(σ, σ′),  (2.3)

where Q(σ, σ′) = μ(σ)P (σ, σ′).

V ar(ϕ) is the variance of ϕ and E(ϕ, ϕ) is the Dirichlet form of the Markov semi-group associated to P (·, ·).

Since P (·, ·) has largest eigenvalue 1 and the constant functions are the only eigenvectors with eigenvalue 1, using the minimax characterization of eigenvalues, if we define

τ(ϕ) = \frac{V ar(ϕ)}{E(ϕ, ϕ)},  (2.4)

then the inverse of the gap between the first and second eigenvalues of P (·, ·) is given by ([5])

τ = sup_{ϕ} τ(ϕ),  (2.5)

where the sup is taken over non constant ϕ’s.

We will use this characterization of the gap to derive bounds for it in the case of the dynamics given by (2.1). (Later on, in the final section, we will consider a global modification of it.) In this context, S = Ω and μ = μ_{N}.

We have also the following bound, given in [5], for the distance in variation.

∥P_{t}(x, ·) − μ_{N}(·)∥_{var} ≤ \sqrt{\frac{1 − μ_{N}(x)}{4μ_{N}(x)}}e^{−t/τ}  (2.6)

Here P_{t}(x, y) = e^{−t} ∑_{n=0}^{∞} \frac{t^{n}}{n!}P^{n}(x, y) is the transition kernel. There is a similar lower bound for the maximum in x of the left hand side. See [20].

In the next two sections, we derive upper and lower bounds for τ that are sharp to logarithmic order.

3 Lower Bound for the Inverse of the Gap

From (2.5), as is usual in this kind of variational problem, we take a trial function to get a lower bound.

We choose for ϕ the indicator of a spin configuration, that is, we define ϕ_{σ} by ϕ_{σ}(σ′) = δ(σ, σ′), where δ(·, ·) is the Kronecker delta. We have

τ(ϕ_{σ}) = \frac{exp\{−βH(σ)\}}{Z_{N} ∑_{⟨σ,σ′⟩} Q(σ, σ′)}(1 − μ_{N}(σ)),  (3.1)

where the sum is over the N nearest neighbors of σ, denoted σ′.

For the Metropolis dynamics, Q(σ, σ′) = (NZ_{N}e^{β(H(σ)∨H(σ′))})^{−1} and thus (3.1) equals

\frac{N exp\{−βH(σ)\}}{∑_{⟨σ,σ′⟩} exp\{−β(H(σ) ∨ H(σ′))\}}(1 − μ_{N}(σ)).  (3.2)

Let \underline{σ} be the (unique) spin configuration σ for which H(σ) is minimal. Then we get the bound

τ ≥ max_{σ} τ(ϕ_{σ}) ≥ τ(ϕ\underline{σ}) = \frac{N exp\{−βH(\underline{σ})\}}{∑_{⟨\underline{σ},σ′⟩} exp\{−βH(σ′)\}}(1 − μ_{N}(\underline{σ})).  (3.3)

Proposition 3.1 There exists a positive constant c such that, for all β, with IP -probability 1, for all but a finite number of indices N we have

\frac{1}{N} log τ ≥ β_{c}β − cβ\sqrt{\frac{log N}{N}} ,  (3.4)

where β_{c} = \sqrt{2 log 2}. In particular

lim inf_{N→∞} \frac{1}{N} log τ ≥ β_{c}β  (3.5)

IP -almost surely.

Remark 3.1 Before going to the proof, let us motivate the result by arguing heuristically that τ should be bigger than the time to exit any initial configuration, in particular the configuration of least energy. Under Metropolis, this should be of the order of the exponential of the absolute value of the difference of the global minimum energy to the minimum energy among configurations neighboring the least energy one. The right hand side of (3.4) follows. Although a rigorous proof could be written along these lines, we follow a different route, using (2.5) instead.

Proof.

Let us first consider the term 1 − μ_{N}(\underline{σ}). Let D_{N} = H(\underline{σ}′) − H(\underline{σ}) where \underline{σ}′ is the location of the second minimum of H. Then

(1 − μ_{N}(\underline{σ}))^{−1} = 1 + \frac{e^{−βH(\underline{σ})}}{∑_{σ≠\underline{σ}} e^{−βH(σ)}} ≤ 1 + \frac{e^{−βH(\underline{σ})}}{e^{−βH(\underline{σ}′)}} ≤ 2e^{βD_{N}} .  (3.6)

Now, given ϵ > 0, one has

IP (D_{N} > Nϵ) = ∫_{−∞}^{∞} \frac{F̄(x + Nϵ)}{F̄(x)} dF′_{N}(x),

where F is the gaussian with mean 0 and variance N distribution function, F̄ = 1 − F and F′_{N} is the distribution function of −H(\underline{σ}′). Here we use the elementary fact that for a sequence X_{1}, …, X_{n} of i.i.d. continuous random variables, if Y_{1}, …, Y_{n} are its increasing order statistics, then

IP (Y_{n} > y|Y_{n−1} = x) = \frac{1 − F_{X_{1}}(y)}{1 − F_{X_{1}}(x)}

for all x < y, where F_{X_{1}} is the distribution function of X_{1}.

We break the integral above into an integral over x < 0 and another over x > 0. The former is bounded from above by

IP (H(\underline{σ}′) > 0) = (2^{N} + 1)2^{−2^{N}} ,

where the equality follows from elementary computations. To bound the latter integral, we observe that, since x is positive, F̄(x + Nϵ) ≤ e^{−ϵ^{2}N/2}F̄(x) by a simple linear change of variables. Thus e^{−ϵ^{2}N/2} is an upper bound for this integral. Therefore, given γ > 0, choosing ϵ = \sqrt{\frac{2 log N}{N} (1 + γ)}, we get

IP (\frac{D_{N}}{N} ≥ \sqrt{\frac{2 log N}{N} (1 + γ)}) ≤ (2^{N} + 1)2^{−2^{N}} + \frac{1}{N^{1+γ}} .  (3.7)

Using the first Borel-Cantelli lemma, we then get that for any γ > 0, with IP -probability 1, for all but a finite number of indices N

\frac{1}{N} log(1 − μ_{N}(\underline{σ})) ≥ −\frac{log 2}{N} − β\sqrt{\frac{2 log N}{N} (1 + γ)}.  (3.8)

To bound from below the term exp\{−βH(\underline{σ})\}, we use the easily checked fact that for all ϵ > 0

IP (H(\underline{σ}) ≥ −β_{c}N + \frac{1}{2β_{c}} (1 + ϵ) log N) ≤ e^{−cN^{ϵ}}  (3.9)

for some positive constant c. Thus, using again the Borel-Cantelli lemma, we get that for any ϵ > 0, with IP -probability 1, for all but a finite number of indices N

\frac{1}{N} log exp\{−βH(\underline{σ})\} ≥ ββ_{c} − \frac{β}{2β_{c}} (1 + ϵ)\frac{log N}{N} .  (3.10)

Note that the corrections are of smaller order than the ones in 3.8. It remains to consider the denominator in (3.2). We first bound from above the sum by N times the maximum of the summands. Since \underline{σ} is the configuration where the infimum is reached, these summands are not independent. However, the maximum is stochastically dominated by the maximum of N independent summands. A proof of this fact can be found in the appendix.

Now if m_{N} is the minimum of N independent standard gaussian random variables then if c > 1

IP ( ⋃_{N=N_{o}}^{∞} \{m_{N} ≤ −\sqrt{(1 + ϵ)2 log N}\}) ≤ ∑_{k=k_{0}}^{∞} IP ( ⋃_{N=c^{k}}^{c^{k+1}} \{m_{N} ≤ −\sqrt{(1 + ϵ)2 log c^{k}}\})

≤ ∑_{k=k_{0}}^{∞} e^{−ϵk log c} < ∞.  (3.11)

Therefore we get that with IP -probability 1 for all but a finite of indices N

m_{N} ≥ −\sqrt{2(1 + ϵ) log N}.  (3.12)

We used now the classical fact that if two families (X_{i})_{i∈IN} and (Y_{i})_{i∈IN} of real random variables are such that for any i ∈ IN X_{i} is stochatically dominated by Y_{i}, then we can construct a common probability space such that, IP -almost surely, X_{i} ≤ Y_{i} for all i ∈ IN. Therefore, we get for any ϵ > 0, with IP -probability 1 for all but a finite of indices N

\frac{1}{N} log( ∑_{⟨σ,σ′⟩} exp\{−β(H(σ) ∨ H(σ′))\})^{−1} ≥ −β\sqrt{2(1 + ϵ)\frac{log N}{N}} .  (3.13)

Collecting (3.8), (3.10) and (3.13), we get (3.4). _{□}

Remark 3.2 The bound (3.13) is optimal, in the sense that it can be proved, by restricting the sum to the σ′ which realises the maximum, that with IP -probability 1, infinitely often (in N) we have

\frac{1}{N} log( ∑_{⟨σ,σ′⟩} exp\{−β(H(σ) ∨ H(σ′))\})^{−1} ≤ −β\sqrt{2(1 − ϵ)\frac{log N}{N}} .  (3.14)

Note that it can be also proved, but it is rather long, that

\frac{1}{N} log(1 − μ_{N}(\underline{σ})) ≥ −\frac{log 2}{N} − cβ \frac{log N}{N} (1 + γ)  (3.15)

for all large enough N. Since the proof we gave here is really shorter and, on the other hand, the upper bound for the correction to the upper bound for τ we will get in the next chapter is of order \sqrt{\frac{log N}{N}} and we have no proof of the optimality for that part, we prefer not to argue (3.15) in detail.

4 Upper Bound

In this section, we derive the upper bound for the inverse of the gap. The bound is based on the Poincaré inequality derived in [5]. It is given in terms of the canonical paths of Jerrum and Sinclair [20], [21].

Let C_{N} denote the hypercube in N dimensions obtained from Ω by adding nearest neighbor bonds (the ones over which the transition probabilities are positive) between the points of Ω, that we will call with a little abuse sites, i.e. a site is just a spin configuration. We will call σ_{j} the j-coordinate of the site σ. Let Γ be a complete set of directed paths in C_{N}, that is, Γ is a set of directed paths in C_{N} such that every two distinct sites in C_{N} are ends of a directed path in Γ. The paths are self avoiding i.e. for a given path a bond is visited just once.

¿From Proposition 1′ in [5] one has the bound

τ ≤ max_{b} Q(b)^{−1} ∑_{γ_{η,η′}∋b} |γ_{η,η′}|μ_{N}(η)μ_{N}(η′),  (4.1)

where the max is over the nearest neighbor bonds b = ⟨σ, σ′⟩ of C_{N}, Q(b) = Q(σ, σ′) and the summation is over all paths in Γ (indexed by their endpoints η and η′) which pass through b.

Writing the bound more explicitly, we have

τ ≤ \frac{N}{Z_{N}} max_{b=⟨σ,σ′⟩} e^{β(H(σ)∨H(σ′))} ∑_{γ_{η,η′}∋b} |γ_{η,η′}|e^{−β(H(η)+H(η′))}.  (4.2)

The rest of the section is devoted to estimate the right hand side of (4.2). Since the asymptotics for Z_{N} are known (1.5-1.11), we concentrate on the max expression.

We will choose Γ so as to have the main contribution come from the sum. The factor e^{β(H(σ)∨H(σ′))} will contribute only an error term. The motivation for the choice is the following. Suppose e^{β(H(σ)∨H(σ′))} does not contribute anything, so we are left with

max_{b=⟨σ,σ′⟩} ∑_{γ_{η,η′}∋b} |γ_{η,η′}|e^{−β(H(η)+H(η′))}.  (4.3)

If we choose Γ as Γ_{1} defined in (4.5) below, we first notice that the longest path in Γ will have length N, so we can ignore this contribution to leading order. We are left with

max_{b=⟨σ,σ′⟩} ∑_{γ_{η,η′}∋b} e^{−β(H(η)+H(η′))}.  (4.4)

For any bond b, the sum in (4.4) factors in a product of two sums which can be seen as (sub)partition functions (see (4.15) below). An estimation along the lines of an argument of Olivieri and Picco to estimate the REM partition function (see Subsubsection 4.2.1) produces a sharp bound (see (4.36) below, compare to the lower bound (3.4)).

In order to control e^{β(H(σ)∨H(σ′))} in (4.2) and work out a rigorous argument from the above motivation, the strategy is to have a complete set of paths Γ that avoid as often as possible points of the hypercube that have high (positive) energies. This cannot be done always since there must be paths that visit sites with high positive values of H. This is because the set of paths is complete. On a heuristic level, one wants to take advantage of the fact that the Gibbs measure of such high positive values of the energy is very small. In the Γ we finally choose, high energies occur only at the ends of the paths and therefore their contribution are depressed by the factor e^{−β(H(η)+H(η′))} appearing in (4.2).

High energy points will be relatively rare, but not so rare that we can rule them out of the interior of the paths of Γ_{1}. This motivates the consideration of the family {Γ_{i}, i = 1, …, N} (see (4.5) below), which is formed with ”copies” of Γ_{1}. Choosing from this family, we guarantee the absence of interior high energy points in paths of Γ.

The details of the construction and the above mentioned estimation, as well as how it survives with extra terms of lower order only, will be given in the next subsections and subsubsections of this section.

4.1 A choice of Γ

To choose Γ, we start by considering a family of sets of paths Γ_{i}, i = 1, …, N, as follows.

For i ∈ {1, …, N}, η and η′ ∈ Ω fixed such that η_{i} ≠ η′_{i}, let γ_{η,η′}^{i} be the path from η to η′ obtained by going left to right cyclically from η to η′ successively flipping the disagreeing spins, starting at the coordinate i. Let

Γ_{i} = {γ_{η,η′}^{i}, η, η′ ∈ Ω}.  (4.5)

Given η, η′ and γ_{η,η′}, let \overline{γ_{η,η′}} be the set of points visited by the path γ_{η,η′} and γ_{η,η′}^{o} = \overline{γ_{η,η′}} \ \{η, η′\} the set of interior point of the path γ_{η,η′}. We say that a family of paths γ_{1}, …, γ_{n} is interior-disjoint if γ_{i}^{o} ∩ γ_{j}^{o} = ∅ for all 1 ≤ i ≠ j ≤ n. We will need the following result, which is easy to check but fundamental.

Lemma 4.1 Given η and η′ in Ω at distance n (that is, ||η − η′|| = n), there exist n interiordisjoint paths in {γ_{η,η′}^{i}, i = 1, …, N}.

Sketch of Proof

Indeed, if i_{1}, …, i_{n} are the coordinates where η and η′ disagree, then one easily checks that γ_{η,η′}^{i_{1}}, …, γ_{η,η′}^{i_{n}} are interior-disjoint. Notice all such paths have n − 2 interior points. _{□}

The set Γ will be chosen depending on a positive parameter c_{e} to be chosen later. It will be formed by indicating for each pair (η, η′) the path connecting the respective sites.

We will distinguish between good and bad sites of Ω. Good sites are those σ for which H(σ) ≤ \sqrt{2(1 + c_{e})N log N}; otherwise, they are bad. We say that a path γ is good if all its interior points γ^{o} are good, and that a set of paths is good if all its elements are good.

We construct the random set of paths Γ. For ||η − η′|| ≥ \frac{N}{log N}, if there is a good path in {γ_{η,η′}^{i}, i = 1, …, N}, choose the first such for Γ; otherwise, choose γ_{η,η′}^{1}.

For ||η − η′|| < \frac{N}{log N}, if there exists a good site η′′ in Ω such that ||η − η′′|| ≥ \frac{N}{log N}, ||η′ − η′′|| ≥ \frac{N}{log N} and there are good paths, one in \{γ_{η,η′′}^{i}, i = 1, …, N\} and another in {γ_{η′,η′′}^{i}, i = 1, …, N}, such that the union of these two good paths is a self avoiding path, select this union as the path connecting η and η′ in Γ (notice that this is a good path since η′′ is good); otherwise, select γ_{η,η′}^{1}. Notice that all the paths constructed in this way have length smaller than N, so we have the bound

τ ≤ \frac{N^{2}}{Z_{N}} max_{b=⟨σ,σ′⟩} e^{β(H(σ)∨H(σ′))} ∑_{γ_{η,η′}∋b} e^{−β(H(η)+H(η′))}.  (4.6)

The next result controls the term e^{β(H(σ)∨H(σ′))}.

Proposition 4.1 With IP -probability 1, for all but a finite number of indices N, the set of paths Γ previously constructed is good.

Proof

We will argue that for an arbitrary pair (η, η′) in Ω, the probability not to find a good path connecting them as prescribed in the construction above is not bigger than e^{−c(e)N} for some constant c(e) that depends on c_{e} which can be chosen as big as we need. Since the number of such pairs does not exceed 4^{N}, choosing c(e) > log 4, the result follows from the first Borel-Cantelli Lemma. We assume that N is large enough to keep only the exponential factor in gaussian estimates.

For pairs of sites more than distance \frac{N}{log N} apart, using the previous lemma, there are at least \frac{N}{log N} disjoint paths of length at most N connecting them. The probability for a given site to be bad is no bigger than exp{−(1 + c_{e}) log N}. Thus the probability of a given path among the disjoint ones to be not good is at most N exp{−(1 + c_{e}) log N} = exp{−c_{e} log N}, since all the paths constructed have length smaller than N. We conclude that the probability that all the \frac{N}{log N} disjoint paths constructed in the previous lemma are not good is at most exp\{−c_{e}N\}.

For (η, η′) less than distance \frac{N}{log N} apart, let D(η, η′) be the coordinates where η and η′ disagree. Given η̃ that coincides with η on D(η, η′) and has \frac{N}{log N} discrepancies with η, let γ_{η̃,η̃′} be the path starting at the site η̃, constructed by flipping the coordinates in D(η, η′) in increasing order. The probability that the set of visited points by this path is not good is at most exp{−c_{e} log N}. Since, for any ϵ > 0, there are at least exp cN^{1−ϵ} many such η̃s and, as it is easy to check, all the paths γ_{η̃,η̃′} obtained by varying η̃ are disjoint, we get that the probability that all the disjoints paths γ_{η̃,η̃′} are not good is at most exp{−c_{e} log N exp{cN^{1−ϵ}}} for some positive constant c. Therefore, for N large enough almost surely, we can find at least one such good site η̃, say η” and the corresponding path, say γ_{η”,η”′}, with all its visited points good. By construction, η”′ coincides with η′ on D(η, η′) and is at distance \frac{N}{log N} apart from it. Therefore we are in the very same hypothesis as before and we can almost surely find good paths γ_{η”′,η′} and γ_{η,η”} for N large enough. Now glueing the three good paths γ_{η,η”}, γ_{η”,η”′} and γ_{η”′,η′}, we get a good path γ_{η,η′} and by construction this path is self avoiding.

All cases have now been covered and the result is proven. _{□}

We will now suppose that N is large enough so as to make (almost) sure, by the previous result, that we can take Γ good. Notice that, in this case, a bad site can appear only at the ends of any path of Γ. So, if b contains a bad site, say σ, and a path γ of Γ contains b, then σ is an end of γ and summing over all such paths is equivalent to summing over all sites of Ω but σ.

So, if b contains a bad site, the term inside the max sign in (4.6) can be bounded above by Z_{N}.

Let G be the collection of bonds of C_{N} that contain no bad site. By the last paragraph,

\frac{τ}{N^{2}} ≤ 1 ∨ Z_{N}^{−1} max_{b∈G} e^{β(H(σ)∨H(σ′))} ∑_{γ_{η,η′}∋b} e^{−β(H(η)+H(η′))}.  (4.7)

Using the fact that b ∈ G, we get

\frac{τ}{N^{2}} ≤ 1 ∨ [e^{β\sqrt{2(1+c_{e})N log N}}τ_{1}]  (4.8)

where

τ_{1} ≡ Z_{N}^{−1} max_{b} ∑_{γ_{η,η′}∋b} e^{−β(H(η)+H(η′))}.  (4.9)

4.2 Estimates for τ_{1}

We write

τ_{1} = τ_{1}^{1} + τ_{1}^{2},  (4.10)

where in τ_{1}^{1} the sum in (4.9) is over paths connecting sites at distance N/ log N or more apart and in τ_{1}^{2} the sum is over paths connecting sites at distance less than N/ log N apart.

We consider first τ_{1}^{1}. The sum can be estimated by

Z_{N}^{−1} ∑_{i=1}^{N} ∑_{γ_{η,η′}∋b}^{(i)}e^{−β(H(η)+H(η′))},  (4.11)

where the sum ∑^{(i)} is over all paths of Γ_{i}. Note that we have replaced here a random set of paths by non random ones. This follows from the fact that the subset of paths of Γ connecting sites which are more than distance O(N/ log N) apart is contained in ∪_{i=1}^{N}Γ_{i}. We have then the estimate

τ_{1}^{1} ≤ NZ_{N}^{−1} max_{i} max_{b} ∑_{γ_{η,η′}∋b}^{(i)}e^{−β(H(η)+H(η′))}.  (4.12)

The random variables

Z_{N}(i) ≡ max_{b} ∑_{γ_{η,η′}∋b}^{(i)}e^{−β(H(η)+H(η′))},

i = 1, …, N, have the same distribution. It will suffice to consider the first one. We will need some further notation.

Given a bond b = ⟨σ, σ′⟩, let ℓ = ℓ(b) be the coordinate where there is a discrepancy. Given a coordinate j and a site σ, define the collections of sites

Ω_{j}^{−}(σ) = {η ∈ Ω : η(i) = σ(i), i = j, …, N}  (4.13)
Ω_{j}^{+}(σ) = {η ∈ Ω : η(i) = σ(i), i = 1, …, j}.  (4.14)

Now

∑_{γ_{η,η′}∋b}^{(1)}e^{−β(H(η)+H(η′))} = ∑_{η∈Ω_{ℓ}^{−}(σ)} e^{−βH(η)} ∑_{η∈Ω_{ℓ}^{+}(σ′)} e^{−βH(η)},  (4.15)

since the paths in Γ_{1} through b connect sites in Ω_{ℓ}^{−}(σ) to sites in Ω_{ℓ}^{+}(σ′).

Thus

max_{b} ∑_{γ_{η,η′}∋b}^{(1)}e^{−β(H(η)+H(η′))}

= max_{j} max_{b=⟨σ,σ′⟩:ℓ(σ,σ′)=j} ∑_{η∈Ω_{j−1}} e^{−βH(η,σ_{j},...,σ_{N})} ∑_{η′∈Ω_{N−j}} e^{−βH(σ′_{1},...,σ′_{j},η′)}  (4.16)

where Ω_{i} = {1, −1}^{i}. Therefore calling

Z_{j−1}(ξ, ζ′) = ∑_{η∈Ω_{j−1}} e^{−βH(η,ξ,ζ′)}  (4.17)

and

Z_{N−j}(−ξ, ζ) = ∑_{η′∈Ω_{N−j}} e^{−βH(ζ,−ξ,η′)},  (4.18)

the right hand side of (4.16) equals

max_{j} max_{ξ=±1} max_{ζ′∈Ω_{N−j}} Z_{j−1}(ξ, ζ′) max_{ζ∈Ω_{j−1}} Z_{N−j}(−ξ, ζ).  (4.19)

4.2.1 Estimates for Z_{j−1}(ξ, ζ′) and Z_{N−j}(−ξ, ζ).

We now estimate Z_{j−1}(ξ, ζ′) and Z_{N−j}(−ξ, ζ) in the same way Olivieri and Picco estimated the REM partition function (see Section III in [4] through to equation (III.17)), rather using the exponential Markov inequality than the simple one in order to be able to control the max signs in (4.19) that involve an exponential number of terms. However, this section is self contained.

Let j and ζ′ ∈ Ω_{N−j} be fixed and take ξ = 1 (for definiteness). Let M be a positive integer to be chosen later and make a partition of the real line with the intervals

Δ_{0} = (−∞, β_{c} \frac{N}{M} ] ,
Δ_{k} = (β_{c} \frac{kN}{M} , β_{c} \frac{N(k + 1)}{M}] , if 1 ≤ k ≤ M,
Δ_{M+1} = (β_{c}(1 + 1/M)N, +∞) .

Now write

Z_{j−1}(ξ = 1, ζ′) = ∑_{σ∈Ω_{j−1}} ∑_{k=0}^{M+1} 1I_{Δ_{k}}(−H(σ, 1, ζ′))e^{−βH(σ,1,ζ′)}

≤ 2^{j−1}e^{β_{c}βN/M} + ∑_{k=1}^{M} N_{k}e^{β_{c}β(k+1)N/M} + N^{∗}e^{−βH(\underline{σ})},  (4.20)

where

N_{k} = N_{k}(ζ′, i = 1, ξ = +1) = ∑_{η∈Ω_{j−1}} 1I_{Δ_{k}}(−H(η, 1, ζ′))

for k = 0, …, M and

N^{∗} = ∑_{σ∈Ω} 1_{Δ_{M+1}}(−H(σ)).

Let us suppose now that j − 1 = αN and focus on the middle sum in (4.20). Let p_{k} denote IP (−H(σ) ∈ Δ_{k}). We then have

β_{c} \frac{\sqrt{N}}{M} 2^{− \frac{(k+1)^{2}}{M^{2}} N} < p_{k} < β_{c} \frac{\sqrt{N}}{M} 2^{− \frac{k^{2}}{M^{2}} N},  (4.21)

for all k = 1, …, M and N large enough.

Optimizing in the exponential Markov inequality, we get

IP (N_{k} > ρ_{k}E(N_{k})) ≤ e^{−λ_{k}2^{αN}} ,  (4.22)

where

ρ_{k} = 2^{( \frac{(k+1)^{2}+1}{M^{2}} −α)^{+}N+2}  (4.23)
λ_{k} = ρ_{k}p_{k} log \frac{ρ_{k}(1 − p_{k})}{1 − ρ_{k}p_{k}} − log [1 − p_{k} + \frac{ρ_{k}p_{k}(1 − p_{k})}{1 − ρ_{k}p_{k}}] ,
if ρ_{k}p_{k} < 1,
= ∞, otherwise.  (4.24)

In any case, we have λ_{k} ≥ cρ_{k}p_{k} for some positive constant c and thus,

IP (N_{k} > ρ_{k}E(N_{k})) ≤ exp{−cρ_{k}p_{k}2^{αN}}.  (4.25)

Also

ρ_{k}p_{k}2^{αN} ≥ 2^{N/M^{2}}.

Let the reader be reminded that N_{k} = N_{k}(ζ′, j, i = 1, ξ = 1) and that the previous estimates are done for a fixed configuration ζ′ ∈ Ω_{N−j} with j ∈ {1, …, N}, i ∈ {1, …, N} and ξ = ±1. Recalling (4.19), we have to make this estimates uniformly with respect to all those possible values. Since there are not more than 2N^{2}2^{N} random variables that come into account, we need to have a probability estimate in (4.25) that compensates this factor. This suggests that we choose M in such a way that 2^{N/M^{2}} ≥ c_{u}N for a positive constant c_{u} that will be chosen later. That is, we take

M = M(N) = \sqrt{\frac{N log 2}{log c_{u}N}}  (4.26)

and we get, for all ϵ > 0,

IP [max_{i} max_{j} max_{ζ′∈Ω_{N−j}} max_{1≤k≤M} N_{k}(ζ′, i, ξ) > ρ_{k}E(N_{k})]
≤ 2N^{2}M(N)2^{N}e^{−c_{u}N} ≤ e^{−ϵN}  (4.27)

choosing c_{u} > log 2 + 2ϵ.

We conclude that the middle sum in (4.20) is bounded above by constant times

\frac{\sqrt{N}}{M} ∑_{k=1}^{M} ρ_{k}2^{αN}2^{− \frac{k^{2}}{M^{2}} N}e^{β_{c}β(k+1)N/M}  (4.28)

= \frac{\sqrt{N}}{M} ∑_{k=1}^{\sqrt{αM^{2}−1}} e^{(α−k^{2}/M^{2}) log 2+β_{c}β(k+1)N/M} + \frac{\sqrt{N}}{M} ∑_{k=\sqrt{αM^{2}−1}}^{M} e^{β_{c}β(k+1)N/M}2^{N/M^{2}} (4.29)

≤ \sqrt{N} ( sup_{x∈[0,1]} e^{αG_{β/\sqrt{α}}(x)N}e^{β_{c}βN/M} + e^{β_{c}β(1+1/M)N}2^{N/M^{2}}) ,  (4.30)

where G_{β}(x) = β_{c}βx+ \frac{β_{c}^{2}}{2} (1−x^{2}), except for an event of probability not bigger than exp\{−ϵN\}. The sup term in (4.30) equals exp\{αF (β/\sqrt{α})N\}, where

F (x) = (x^{2} + β_{c}^{2})/2, if 0 ≤ x ≤ β_{c},  (4.31)
= β_{c}x, if x ≥ β_{c}  (4.32)

and αF (β/\sqrt{α})|_{α=0} ≡ 0.

So, uniformly in i, j, ξ, ζ′ we have

Z_{j−1}(ζ′, ξ) ≤ cMe^{αF (β/\sqrt{α})N}e^{β_{c}βN/M} + Me^{β_{c}β(1+1/M)N}2^{N/M^{2}} + N^{∗}e^{−βH(\underline{σ})}  (4.33)

with IP -probability not smaller than 1 − exp{−ϵN}, where we have absorbed the factor 2^{αN} in (4.20) by changing the constant c, since 2^{αN} ≤ e^{αF (β/\sqrt{α})N}, as it can be easily checked.

Notice that IP -almost surely, N^{∗} = 0 for all but a finite number of indices N, since

P (−H(σ) > (1 + 1/M)Nβ_{c}) ≤ 2^{−(1+1/M)^{2}N}.

After a similar reasoning with

Z_{N−j}(−ξ, ζ) = max_{ζ∈Ω_{j−1}} ∑_{η′∈Ω_{N−j}} e^{−βH(ζ,−1,η′)},

we conclude that IP -almost surely for all but a finite number of indices N

τ_{1}^{1} ≤ NZ_{N}^{−1} max_{0≤α≤1} ψ(α, N, M)ψ(1 − α, N, M),  (4.34)

where

ψ(α, N, M) = cMe^{αF (β/\sqrt{α})N}e^{β_{c}βN/M} + Me^{β_{c}β(1+1/M)N}2^{N/M^{2}}
≤ e^{c\sqrt{N log N}}e^{[αF (β/\sqrt{α})∨β_{c}β]N}

and c is a positive constant, not necessarily the same everytime it appears.

Collecting, we get that

\frac{1}{N} log τ_{1}^{1} ≤ max_{0≤α≤1} Ψ(α, β) − F (β) + cβ\sqrt{\frac{log N}{N}} + c′ \frac{log N}{N} .  (4.35)

where

Ψ(α, β) = [αF (\frac{β}{\sqrt{α}}) + (1 − α)F (\frac{β}{\sqrt{1 − α}})] ∨ [αF (\frac{β}{\sqrt{α}}) + β_{c}β] ∨ 2β_{c}β

and c′ is a positive constant.

Now one checks that max_{0≤α≤1} Ψ(α, β) − F (β) ≤ β_{c}β for all β.

Therefore, we get that IP -almost surely for all but a finite number of indices N

\frac{1}{N} log τ_{1}^{1} ≤ ββ_{c} + cβ\sqrt{\frac{log N}{N}} + c′ \frac{log N}{N}  (4.36)

for some constants c, c′ and all β.

4.2.2 Estimates for τ_{1}^{2}

We consider now the term τ_{1}^{2}. We estimate it in two different ways, one for β close to 0, another for β away from 0.

The first bound follows from the fact that the sum is over a set of paths connecting sites in a hypercube of dimension at most (N/ log N) around b, so we have

τ_{1}^{2} ≤ Z_{N}^{−1}e^{cN/ log N}e^{−2βH(\underline{σ})}  (4.37)

Unrestricting the paths to go through b, we get the other bound

τ_{1}^{2} ≤ Z_{N}^{−1}e^{−βH(\underline{σ})} max_{η∈Ω} ∑_{η′:||η′−η||< \frac{N}{log N}} e^{−βH(η′)}.  (4.38)

Notice that the sum in (4.38) is very similar to that in (4.17) and that it has less than 2^{αN} (independent) terms, with an arbitrary α > 0 (for N large enough). We can thus proceed to estimate the former in the same way as we did the latter to get the bound (4.33) from which the right hand side of (4.36) follows as an upper bound for the log of (4.38) divided by N when β > β_{0}, where β_{0} is a suitable positive fixed number close to 0 (the bound is in fact true for β > 0, but then N large enough will depend on β).

For β close to 0, we use (4.37) to get

\frac{1}{N} log τ_{1}^{2} ≤ 2β_{c}β − F (β) + c/ log N  (4.39)

which is negative for N large enough. This shows that (4.36) holds with τ_{1}^{1} replaced by τ_{1}^{2}.

We are now ready for the main result of this section. (4.36) (also applied to τ_{1}^{2}) substituted into (4.8) via (4.10) prove the following.

Proposition 4.2 For all β, there exist finite constant c and c′ such that, with IP -probability 1, for all but a finite number of indices N, we have

\frac{1}{N} log τ ≤ ββ_{c} + cβ\sqrt{\frac{log N}{N}} + c′ \frac{log N}{N} .  (4.40)

In particular,

lim sup_{N→∞} \frac{1}{N} log τ ≤ β_{c}β.  (4.41)

Remark 4.1 The argument leading to inequality (4.36) proves a weak form of the inequality

∑_{η∈Ω_{j−1}} e^{−βH(η,ξ,ζ′)} ∑_{η′∈Ω_{N−j}} e^{−βH(ζ,−ξ,η′)} ≤ e^{−βH(\underline{σ})}Z_{N}  (4.42)

for all 1 ≤ j ≤ N, ζ ∈ Ω_{j−1}, ξ = ±1 and ζ′ ∈ Ω_{N−j}. Namely, it is true almost surely after taking logs, dividing by N and passing to the limit as N → ∞. One might wonder whether a stronger, deterministic form of this inequality is true. It would simplify the long probabilistic argument of the last subsubsection and make extensions to similar models easier. But this is unfortunately not the case, as the following example shows. Let N be an odd number, j = (N + 1)/2, ξ = −1 and define

x(η, −1, −1, …, −1) = 1 for all η ∈ Ω_{j−1},
x(−1, …, −1, 1, η′) = 1 for all η′ ∈ Ω_{N−j},
x(σ) = 0 in all other cases.

Then it is clear that the left hand side in (4.42) (with the Boltzmann factors replaced by x(·)) equals 2^{N−1} while the right hand side equals 2^{(N+1)/2}.

5 Summing Up

Combining the bounds of Propositions 3.1 and 4.2, we have the following result.

Theorem 1 For all β, there exist finite constants c, c′ and c′′ such that, with IP -probability 1, for all but a finite number of indices N, we have

ββ_{c} − cβ\sqrt{\frac{log N}{N}} ≤ \frac{1}{N} log τ ≤ ββ_{c} + c′β\sqrt{\frac{log N}{N}} + c′′ \frac{log N}{N} .  (5.1)

In particular,

T (β) := lim_{N→∞} \frac{1}{N} log τ  (5.2)

exists with probability 1 and equals β_{c}β.

Remark 5.1 Although the REM as an equilibrium model exhibits a (third order) phase transition at β = β_{c}, this leaves no trace in the dynamical model (as regards T), neither at β_{c} nor elsewhere. We might then say that there is no dynamical phase transition for the REM under Metropolis dynamics. We did not work out the details, but believe this is so also for other (local) Glauber dynamics. In the next section, we consider a modification of Metropolis so that it is a global dynamics for which (5.2) has a third order phase transition at β_{c}.

Remark 5.2 An explanation for the result of Theorem 1 is as follows. Since the energies of the REM are independent, the minimum one is surrounded by order 1 energies that can have fluctuations of order \sqrt{N log N}. Therefore, the time to exit the ground state under a local dynamics is of the order of exp β_{c}βN and the fluctuations are of order exp \sqrt{N log N}. This should be the main contribution to τ to leading order. In the high temperature regime, the dominant contribution to the free energy comes from energies that are larger than the ground state, but the entropy comes into play to give a smaller free energy. However, with the local dynamics, the stochastic process is trapped into the ground states, that do not contribute to the statics, for a time which is bigger than all the exit times of the other states.

By using equations (2.6) and (1.7), it is not difficult to check the following result.

Theorem 2 There exists a positive constant c such that for all ϵ > 0, all β > 0 and all t′ > 0, if

t_{N}(t′) = e^{Nββ_{c}+c\sqrt{N log N}} [\frac{N}{2} (F (β) + ββ_{c}) + \frac{β}{2β_{c}} (log N + ϵ) + t′]  (5.3)

then, with IP -probability 1, for all but a finite number of indices N we have

sup_{σ}∥P_{t_{N} (t′)}(σ, ·) − μ_{N}(·)∥_{var} ≤ e^{−t′}.  (5.4)

Remark 5.3 For the proof of this theorem, we need only an upper bound for the square root term in (2.6), so a lower bound on μ(σ) is needed. Since we want a result which is uniform with respect to the initial conditions, we cannot exclude a priori to start with a configuration which corresponds to the spin configuration that makes H(σ) maximal. Even if the Gibbs measure of such configuration is very small. Also, we cannot expect to have any cancellation of the error terms that are of order log N. This is because a part of the errors terms are coming from the fluctuations of a Gibbs factor computed on a maxima and the other part is coming from the fluctuations of the partition function, the latter coming from the fluctuations of the minimum.

6 A Global Dynamics

In this chapter, we consider a global Metropolis dynamics, where the system can make all possible jumps, not only nearest neighbor ones as in the local dynamics. When scaled as for the local dynamics of the previous sections, τ is shown to exhibit a phase transition as a function of β (see Theorem 3 below).

Consider the following continuous-time Markov chain in Ω.

P (σ, σ′) = 2^{−N} exp{−β(H(σ′) − H(σ))^{+}}, if σ′ ≠ σ,
= 1 − ∑_{σ′′≠σ} P (σ, σ′′), if σ′ = σ,  (6.1)

This is an irreducible, reversible with respect to μ_{N} chain and thus we can apply the variational characterization of the gap (2.5). We use the same trial function for τ as in Section 3 to obtain

τ ≥ τ(ϕ\underline{σ}) = \frac{2^{N}e^{−βH(\underline{σ})}}{Z_{N}} .  (6.2)

The upper bound is much simpler to derive than the corresponding local one, either directly from the variational characterization or by using the Poincaré inequality (4.1). We choose the latter, using the set of paths

Γ = {(σ, σ′) : σ, σ′ ∈ Ω, σ ≠ σ′}

constituted of all bonds in Ω (notice that the global transition probabilities are nonzero over these) to get

\frac{2^{N}}{Z_{N}} max_{σ≠σ′} e^{β(H(σ)∨H(σ′))}e^{−β(H(σ)+H(σ′))} = \frac{2^{N}e^{−βH(\underline{σ})}}{Z_{N}} .  (6.3)

We conclude from (6.2) and (6.3) that

τ = \frac{2^{N}e^{−βH(\underline{σ})}}{Z_{N}} .  (6.4)

Therefore, since lim_{N→∞} F_{N}(β) = F (β) IP -almost surely, we get the following result.

Theorem 3 IP -almost surely,

T (β) = lim_{N→∞}(log τ)/N = β_{c}β + β_{c}^{2}/2 − F (β),  (6.5)

where F is given by (4.31) and (4.32) above.

Remark 6.1 Since F undergoes a third order phase transition in β = β_{c}, then so does T.

Remark 6.2 The identity (6.4) is valid for the same dynamics for any spin system. Applied to the Ising model, it shows that T inherits its phase transition (whenever that occurs).

To consider the error terms, we introduce the quantity

T (β) ≡ log [τe^{−NT (β)}] .  (6.6)

The first result is an almost sure one.

Theorem 4 If β ≥ β_{c}, then

T (β) ≤ 0 for all N  (6.7)

and, with IP -probability 1,

lim inf_{N→∞} \frac{T (β)}{log log N} ≥ −\frac{β}{β_{c}} .  (6.8)

If β < β_{c}, then, with IP -probability 1,

lim sup_{N→∞} \frac{T (β)}{log N} = − lim inf_{N→∞} \frac{T (β)}{log N} = \frac{β}{2β_{c}} .  (6.9)

Remark 6.3 The important fact is that the almost sure finite volume corrections to the free energy, that are of order log N/N in the low temperature regime, are coming precisely from the fluctuations of the ground states, and there is an exact cancellation of these fluctuations when τ is considered. This gives fluctuations that are of order at most log log N/N for T (β). In particular this implies that there is also a phase transitions in the errors terms.

One could be interested in the error terms in probability. In this case the results are simpler.

Theorem 5 If β ≥ β_{c}, then

lim_{N→∞} \frac{T (β)}{log N} = 0 in IP -probability.  (6.10)

If β < β_{c}, then

lim_{N→∞} \frac{T (β)}{log N} = −\frac{β}{2β_{c}} in IP -probability.  (6.11)

Proof of Theorem 4

We consider first the case where β < β_{c}. Using the explicit formula for F (β) see (4.31) and (4.32) we get

T (β) = −β(H(\underline{σ}) + Nβ_{c}) − log Z_{N}e^{−NF (β)}.  (6.12)

Using the proposition 5 in ([4]), that is (1.5), we get that with IP -probability 1, for all but a finite number of indices N the last term is of order at most Ne^{−λ(β)N}. For the first term, using (3.9) we get with IP -probability 1, for all but a finite number of indices N

T (β) ≥ −\frac{β}{2β_{c}} (1 + ϵ) log N.  (6.13)

On the other hand we have also, with IP -probability 1

lim inf_{N→∞} \frac{T (β)}{log N} = −\frac{β}{2β_{c}} .  (6.14)

This is a direct consequence of the proof of the formula (2.7) in [7] (see pages 520-521 there). Moreover we have with IP -probability 1, for all but a finite number of indices N

T (β) ≤ \frac{β}{2β_{c}} (1 + ϵ) log N,  (6.15)

which is a consequence of the following estimate that is easy to check.

IP (−H(\underline{σ}) ≤ β_{c}N(1 − \frac{log N}{2β_{c}^{2}N} − \frac{log log N^{1+δ} + log \sqrt{2π}}{β_{c}^{2}N})) ≤ \frac{c}{N^{1+δ}}  (6.16)

for some positive constant c.

Moreover it is not too difficult to see that we have, with IP -probability 1

lim sup_{N→∞} \frac{T (β)}{log N} = \frac{β}{2β_{c}} ,  (6.17)

from which we get (6.9).

For the proof of (6.7), we use again the explicit formula for F (β). If β ≥ β_{c} we have

T (β) = − log Z_{N}e^{βH(\underline{σ})}.  (6.18)

Since Z_{N}e^{βH(\underline{σ})} ≥ 1, we get T (β) ≤ 0. The proof of (6.8) is just a little more involved and will make use of results of [4] with some

modifications.

We define as in [4] (page 135), the real interval

I_{1} = [Nβ_{c} (1 − \frac{1}{2β_{c}^{2}} \frac{log N}{N} + \frac{(1 + ϵ)}{β_{c}^{2}} \frac{log log N}{N} ) , (1 + ϵ)Nβ_{c}] .  (6.19)

Then we have

∑_{σ} e^{−β(H(σ)−H(\underline{σ}))}1I_{I_{1}}(−H(σ)) ≤ ∑_{σ} 1I_{I_{1}}(−H(σ)),  (6.20)

since H(σ) − H(\underline{σ}) ≥ 0.

Now is it easy to check that

2^{N}IE(1I_{I_{1}}(−H(σ))) ≤ \frac{1}{β_{c}} (\frac{1}{log N} )^{1+ϵ} .  (6.21)

Using now the following nice, but not known as it deserves, inequality, which is a simple consequence of the Markov inequality,

IP (S_{n} ≥ r) ≤ e (np(n))^{r} ,  (6.22)

where S_{n} = ∑_{i=1}^{N} x_{i} and (x_{i})_{i=1,...,N} is a family of independent identicaly distributed random variables with values in 0, 1 and IP (x_{1} = 1) = p(n), we get

IP (∑_{σ} 1I_{I_{1}}(−H(σ)) ≥ \frac{log N}{log log N} ) ≤ \frac{1}{N^{1+ϵ}} .  (6.23)

We consider now the interval

I_{2} = (−∞, Nβ_{c}(1 − \frac{1}{2β_{c}^{2}} \frac{log N}{N} + \frac{(1 + ϵ)}{β_{c}^{2}} \frac{log log N}{N})].  (6.24)

Using Lemma 7 in [4], we have, with IP -probability 1, for all large enough N

∑_{σ} 1I_{I_{2}}(−H(σ))e^{−βH(σ)} ≤ \frac{(1 + ϵ)}{β_{c}} log log Ne^{Nββ_{c}(1−_{\frac{log N}{2β^{2}_{c}N}})}.  (6.25)

Therefore, collecting on the one hand (6.16) together with (6.25) and on the other hand (6.23) together with (6.20), using the first Borel-Cantelli Lemma, we get that, with IP -proba-bility 1, for all large enough N

Z_{N}e^{βH(\underline{σ})} ≤ \frac{log N}{log log N} + \frac{(1 + ϵ)}{β_{c}} log log Ne^{\frac{β}{βc} log log N^{1+δ}},  (6.26)

from which we get immediately

T (β) ≥ −\frac{β}{β_{c}} log log N − log log log N  (6.27)

and this concludes the proof of the Theorem 4. The proof of Theorem 5 is immediate.

We leave as an exercise to the reader to state and prove the corresponding of Theorem 2 for this dynamics.

A Microscopic Representation

We establish here the microscopic representation for the REM hamiltonian mentioned in the introduction. This representation already appears in Derrida’s papers without proof. We give an argument here for completeness.

Proposition A.1 Let H = {H(σ), σ ∈ Ω} be defined by Equation (1.2), where {J_{α}, α ⊂ Λ} is a family of i.i.d. standard gaussian random variables. Then H is a family of i.i.d. gaussian random variables with mean 0 and variance N.

Proof

The gaussianness, correct marginal mean and variance are clear. It suffices thus to establish independence. It is enough to show that the matrix

{σ_{α}; σ ∈ Ω, α ⊂ Λ}  (A.1)

is orthogonal, that is,

∑_{α⊂Λ} σ_{α}σ′_{α} = 0  (A.2)

for all distinct σ, σ′ ∈ Ω.

Given σ, σ′ ∈ Ω with σ ≠ σ′, let Δ denote the (nonempty) set where σ and σ′ disagree, that is

Δ = {i ∈ Λ : σ_{i} ≠ σ′_{i}}.  (A.3)

We have

∑_{α⊂Λ} σ_{α}σ′_{α} = ∑_{α⊂Λ}(−1)^{|α∩Δ|}.  (A.4)

The last sum can be rewritten as

∑_{k=0}^{M} ∑_{α⊂Λ:|α∩Δ|=k}(−1)^{k},  (A.5)

where M = |Δ|. It then equals

∑_{k=0}^{M} g_{Δ}(k)(−1)^{k},  (A.6)

where g_{Δ}(k) is the number of distinct subsets α of Λ intersecting Δ at exactly k points. There are k choices out of M in Δ, which yields \binom{M}{k} possibilities for α ∩ Δ, and total freedom in Λ\Δ, which yields 2^{N−M} possibilities for α\Δ. Thus

g_{Δ}(k) = \binom{M}{k} 2^{N−M}.  (A.7)

We finally have

∑_{α⊂Λ} σ_{α}σ′_{α} = 2^{N−M} ∑_{k=0}^{M} \binom{M}{k}(−1)^{k} = 2^{N−M}(1 − 1)^{M} = 0,  (A.8)

since M > 0. The result is proven. _{□}

B A Domination Lemma

It is enough for the purposes of supporting the argument in the proof of Proposition 3.1 to consider the following setup. Let X_{1}, …, X_{n+1} be a sequence of continuous i.i.d. random variables with distribution function F and let M_{n} denote their maximum (which is almost surely unique) and let M denote the corresponding index (so that M_{n} = X_{M}). Define Y_{i} = X_{i} if i < M and Y_{i} = X_{i+1} otherwise.

Lemma B.1

P (Y_{i} < y_{i}, i = 1, …, n) ≥ ∏_{i=1}^{n} P (X_{1} < y_{i}).  (B.1)

It follows immediately that the maximum of any subset of {Y_{1}, …, Y_{n}} is stochastically dominated by the maximum of the same number of X’s.

Proof

P (Y_{i} < y_{i}, i = 1, …, n)  (B.2)
= ∑_{j=1}^{n+1} P (Y_{i} < y_{i}, i = 1, …, n, M = j)  (B.3)

= ∑_{j=1}^{n+1} P (X_{i} < y_{i}, X_{i} < X_{j}, i < j, X_{i} < y_{i−1}, X_{i} < X_{j}, i > j)  (B.4)

= ∑_{j=1}^{n+1} ∫ P (X_{i} < y_{i}, X_{i} < x, i < j, X_{i} < y_{i−1}, X_{i} < x, i > j) dF (x)  (B.5)
= (n + 1) ∫ ∏_{i=1}^{n} P (X_{1} < y_{i} ∧ x) dF (x)  (B.6)
≥ ∏_{i=1}^{n} P (X_{1} < y_{i}) ∫ (n + 1)F^{n}(x) dF (x)  (B.7)
= ∏_{i=1}^{n} P (X_{1} < y_{i}),  (B.8)

where the inequality follows from

F (x ∧ y) ≥ F (x)F (y),  (B.9)

for all x, y. _{□}

Acknowledgements.

L. F. and M. I. thank M. Cassandro, A. Galves and A. Pellegrinotti for stimulating discussions. L. F. further thanks R. Férnandez, P. Ferrari, E. Jordão Neves, E. Kira and V. Sidoravicius for valuable comments, suggestions and discussions. His work was partially supported by Fapesp grants nos. 94/4303-5 and 95/8932-0 and is part of Fapesp Theme Grant no. 95/0790-1 and CNPq Pronex grant. He acknowledges support and hospitality when visiting the University of Rome ”La Sapienza” and the CPT, Luminy. Part of this work was written while he was visiting the Courant Institute (under CNPq grant no. 200125/96-6), where he found warm hospitality. M. I. was partially supported by CNPq grant no. 453865/93-3. He acknowledges hospitality in São Paulo. Y. K. was partially supported by FAPESP (Proc. 96/04505–2) and by CNPq (Proc. 300334/93–1 and ProTeM-CC-II Project ProComb).

References

[1] Derrida B., Random Energy Model: Limit of a Family of Disordered Models, Phys. Rev. Lett. 45, 79-82 (1980)

[2] Derrida B., Random Energy Model: An Exactly Solvable Model of Disordered Systems, Phys. Rev. B 24, 2613-2626 (1981)

[3] Eisele Th., On a Third Order Phase Transition, Comm. Math. Phys. 90, 125-159 (1983)

[4] Olivieri E., Picco P., On the Existence of Thermodynamics for the Random Energy Model, Comm. Math. Phys. 96, 125-144 (1984)

[5] Diaconis P., Stroock D., Geometric Bounds for Eigenvalues of Markov Chains, Ann. Appl. Probab. 1, 36-61 (1991)

[6] Cassandro M., Galves J.A. and Picco P., Dynamical phase transition in disordered systems: the study of a random walk model, Ann. Inst. H. Poincaré (Physique Théorique) 55, 689-706 (1991)

[7] Galves J.A., Martinez S. and Picco P., Fluctuations in Derrida’s Random Energy and Generalized Random Energy Models, J. Stat. Phys. 54 515-529 (1989)

[8] Cesi F., Maes, C. and Martinelli F., Relaxation in Disordered Magnets in the the Griffiths Regime, Comm. Math. Phys. 188 135-173 (1997)

[9] Cesi F., Maes, C. and Martinelli F., Relaxation to Equilibrium for Two Dimensional Disordered Ising Models in the Griffiths Phase, preprint 1997

[10] Mezard M., Parisi G. and Virasoro M., Spin Glass theory and beyond, World Scientific (1980)

[11] Parisi G., Slow dynamics of glassy systems, Varenna Lectures 1996 preprint condmat/9705312 on http://xxx.sissa.it/archive/cond-mat

[12] Sompolinsky H. and Zippelius A., Relaxational dynamics of the Edwards-Anderson model and the mean-field theory of spin-glasses, Phys. Rev. B 25 6860-6875 (1982)

[13] Zegarlinski B., Strong Decay to Equilibrium in one Dimensional Random Spin Systems, J. Stat. Phys. 77 717-732 (1994)

[14] Guionnet A., Averaged and Quenched Propagation of Chaos for Langevin Spin Glass Dynamics, preprint 1997

[15] Guionnet A. and Zegarlinski B., Decay to Equilibrium in Random Spin Systems on a Lattice, Comm. Math. Phys. 181 703-732 (1996)

[16] Guionnet A. and Zegarlinski B., Decay to Equilibrium in Random Spin Systems on a Lattice II, J. Stat. Phys. 86 899-xxx (1996)

[17] Ben Arous G. and Guionnet A., Large Deviations for Langevin Spin Glass Dynamics, Probab. Theory Relat. Fields 102, 455-509 (1995)

[18] Ben Arous G. and Guionnet A., Symmetric Langevin Spin Glass Dynamics, Ann. Probab. 25, 1367-1422 (1997)

[19] Gielis G. and Maes C., Percolation Techniques in Disordered Spin Flip Dynamics: Relaxation to the Unique Invariant Measure, Comm. Math. Phys. 177 83-xxx (1996)

[20] Sinclair A.J., Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1 351–370 (1992)

[21] Jerrum, M., Sinclair, A., Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and Comput. 82, 93–133 (1989)