# Fast relaxation of the random field Ising dynamics

Ahmed El Alaoui Department of Statistics and Data Science, Cornell University.
Ronen Eldan Microsoft Research and Weizmann Institute of Science. Reza
Gheissari Department of Mathematics, Northwestern University. Arianna Piana
Department of Mathematics, Weizmann Institute of Science.

###### Abstract

We study the convergence properties of Glauber dynamics for the random field
Ising model (RFIM) with ferromagnetic interactions on finite domains of
$\mathbb{Z}^{d}$, $d\geq 2$. Of particular interest is the _Griffiths phase_
where correlations decay exponentially fast in expectation over the quenched
disorder, but there exist arbitrarily large islands of weak fields where low-
temperature behavior is observed. Our results are twofold:

1\. Under _weak spatial mixing_ (boundary-to-bulk exponential decay of
correlations) in expectation, we show that the dynamics satisfy a _weak_
Poincaré inequality—equivalent to large-set expansion—implying algebraic
relaxation to equilibrium over timescales polynomial in the volume $N$ of the
domain, and polynomial time mixing from a warm start. From this we construct a
polynomial-time approximate sampling algorithm based on running Glauber
dynamics over an increasing sequence of approximations of the domain.

2\. Under _strong spatial mixing_ (exponential decay of correlations even near
boundary pinnings) in expectation, we prove a _full_ Poincaré inequality,
implying exponential relaxation to equilibrium and $N^{o(1)}$-mixing time.
Note by way of example, both weak and strong spatial mixing hold at any
temperature, provided the external fields are strong enough.

Our proofs combine a stochastic localization technique which has the effect of
increasing the variance of the field, with a field-dependent coarse graining
which controls the resulting sub-critical percolation process of sites with
weak fields.

##  1 Introduction

Given a finite graph $G=(V,E)$, the random field Ising model (RFIM) at
inverse-temperature $\beta>0$ on $G$ is the random probability measure on
$\\{-1,+1\\}^{V}$ given by

$\mu_{G}(\sigma)\propto\,\exp\big{\\{}-H(\sigma)\big{\\}},~{}~{}~{}\sigma\in\\{-1,+1\\}^{V}\,,$
(1.1)

where $H$ is the random Hamiltonian

$\displaystyle H(\sigma)=-\beta\sum_{(u,v)\in
E}\sigma_{u}\sigma_{v}-\sum_{u\in V}h_{u}\sigma_{u}\,,$ (1.2)

with $h=(h_{u})_{u\in V}$ i.i.d. random variables with a symmetric and tight
distribution. The vector $h$ is referred to as the external field, and is
viewed as a quenched source of disorder.

The RFIM has seen much attention in the statistical physics literature on
(subgraphs of) ${\mathbb{Z}}^{d}$ for $d\geq 2$. In $d=2$, Imry and Ma [36]
famously predicted in 1975 that the presence of an arbitrarily small random
field suppresses the low-temperature phase of the classical (zero-field $h=0$)
Ising model, so that at all values of $\beta$, the measure (1.1) exhibits
uniqueness and decay of correlations. After much debate within the physics
community, this prediction was confirmed by Aizenman and Wehr [3] who showed
that at all $\beta>0$ and for external fields with non-trivial distribution
and of arbitrarily small but non-zero variance, the expected influence on the
spin at the origin of boundary conditions at distance $r$ away must decay with
$r$. A recent flurry of activity on this problem gave quantitative rates on
this decay of influence with $r$ [14, 2, 1], and in the Gaussian case
$h_{u}\sim N(0,\sigma^{2})$ culminated in the breakthrough work [18] showing
that the influence decays exponentially at all temperatures and $\beta>0$ and
all field variances $\sigma^{2}>0$. In dimensions $d\geq 3$, the RFIM behaves
very differently. If the field is sufficiently large as a function of $\beta$,
influences decay exponentially fast in expectation over the field [27]. But
unlike in $d=2$, when $d\geq 3$ if the disorder is relatively small, there is
a phase transition as $\beta$ is varied. The lack of influence decay was shown
in [35] at $\beta=\infty$ and at $\beta$ sufficiently large in [10], and more
recently in the entire low temperature phase in [16].

In this paper, we are interested in the behavior of the _Glauber dynamics_ for
the RFIM on (subsets of) $\mathbb{Z}^{d}$ for general $d\geq 2$. The Glauber
dynamics is the continuous-time Markov process $(X_{t}(v))_{v\in V,t\geq 0}$,
reversible w.r.t. $\mu_{G}$, which assigns each vertex $v\in V$ a rate-1
Poisson clock, and when the clock at $v\in V$ rings at time $t$, it resamples
$X_{t}(v)$ according to the conditional distribution

$X_{t}(v)\,\sim\,\mu_{G}\Big{(}\sigma_{v}\in\cdot\,\,\Big{|}\,(\sigma_{w})_{w\neq
v}=(X_{t^{-}}(w))_{w\neq v}\Big{)}\,.$ (1.3)

This process was introduced in 1963 in [30] and has since seen immense
attention both as a physical model for the thermodynamic evolution of an Ising
system out of equilibrium, and as a Gibbs sampler MCMC algorithm for the
measure $\mu_{G}$. The central quantity to study for the Glauber dynamics is
its rate of convergence to $\mu_{G}$, typically measured either in $\ell^{2}$,
via spectral gap or Poincaré inequalities, or total-variation distance, via
mixing times.

For the classical Ising model (zero-field), the convergence rate to
equilibrium of the Glauber dynamics has been extensively studied over the last
thirty years, and is by now fairly well understood. Namely, for the Ising
Glauber dynamics on $\Lambda_{n}=[-n,n]^{d}\cap\mathbb{Z}^{d}$, weak and
strong spatial mixing properties (exponential decay of correlations away from
boundary conditions, and near frozen boundaries, respectively) have been shown
to imply order-1 inverse spectral gap, and exponentially fast relaxation to
equilibrium [45, 46]. These spatial mixing properties hold at all high
temperatures $\beta<\beta_{c}(d)$ in all $d\geq 2$, where $\beta_{c}(d)$ is
the critical inverse temperature of the zero-field Ising model on
${\mathbb{Z}}^{d}$. Implications from spatial mixing to temporal mixing have
since been a central tool in the analysis of mixing times of spin systems on
lattices: see e.g., [13, 21, 44, 29]. On the other hand, as soon as
$\beta>\beta_{c}(d)$, the mixing time becomes exponentially slow in $n^{d-1}$:
we refer to the lecture notes [47] for references on mixing times of Ising
Glauber dynamics on $\mathbb{Z}^{d}$.

In the presence of quenched disorder, as in the RFIM, such implications going
from exponential decay of correlations (now only in expectation) to fast
relaxation to equilibrium may no longer hold. This is because of what is known
as _Griffiths singularities_ [31], whereby if $\beta>\beta_{c}(d)$, there are
small but positive density regions in $\Lambda_{n}$ where the field is very
close to zero, and low-temperature behavior is observed, even though in
expectation over the field, correlations decay exponentially. In fact, it can
be shown that the Griffiths phase can slow down the dynamics so that even at
large field values, the spectral gap has to tend to zero at least super-
logarithmically in $n$ if $\beta>\beta_{c}(d)$ (see e.g., [12] in the context
of random interaction strengths rather than random fields, or our Section 6).
In particular, this precludes straightforward applicability of the recently
developed general purpose tools, such as spectral independence, to deduce fast
mixing under deterministic influence or covariance matrix bounds; e.g., [4, 5,
8, 24, 15]. This begs the question, most pertinent in the regime where
exponential decay of correlations holds for the RFIM in expectation, but not
for the corresponding zero-field model—e.g., $\beta>\beta_{c}(d)$ and large
variance field—of how fast the Glauber dynamics relaxes to equilibrium.

The RFIM dynamics are also interesting from the perspective of computational
complexity of approximate sampling and counting: the task of approximately
sampling from the zero-field Ising distribution was shown to be
algorithmically tractable in polynomial time on general graphs in [38]. On the
other hand, with arbitrary external fields, the sampling task is #BIS hard
[11], namely as hard as approximately counting the number of independent sets
on a bipartite graph, a task expected to be intractable in polynomial time.
From this perspective, the RFIM can be viewed as a proxy for the average-case
hardness of the sampling task. Recently, [34] showed on general graphs, that
if the variance of the fields is sufficiently large, there exists a
polynomial-time approximation algorithm for the RFIM; their algorithm is based
on the self-avoiding walk tree of Weitz [49]. They pose the question of
whether Markov chain approaches can provide a similar polynomial-time sampling
scheme.

In this paper, we prove Poincaré-type inequalities, and bound the rate of
convergence for the RFIM Glauber dynamics whenever it exhibits exponential
decay of correlations in expectation. The form of exponential decay falls into
two classes, weak spatial mixing and strong spatial mixing: the distinction is
that the latter requires the exponential decay of correlations in expectation
to hold even in the presence of frozen nearby spins. Our main result is that
under the weak spatial mixing assumption, the Glauber dynamics satisfies a
_weak Poincaré inequality_ , and converges at least algebraically fast to
equilibrium on polynomial in $n$ timescales: see Theorem 1.2. This also
translates to a polynomial-time sampling scheme built from running Glauber
dynamics chains on domains successively approximating $\Lambda_{n}$: see
Theorem 1.4. Under the stronger assumption of strong spatial mixing in
expectation, which for instance holds at any $\beta$ if the field variances
are sufficiently large as a function of $\beta$, we show a (full) Poincaré
inequality with inverse spectral gap that is $n^{o(1)}$, and consequently,
exponentially fast relaxation to equilibrium after such timescales: see
Theorem 1.6.

We note that as a consequence of the recently discovered correlation
inequality of [17], strong spatial mixing holds _uniformly_ in the external
field for $\beta<\beta_{c}(d)$, and hence one already obtains order-1 spectral
gap for the RFIM Glauber dynamics by standard implications; see [47]. Our
results are thus most pertinent in the Griffiths phase discussed above.

###  1.1 Main results

In what follows, our domain of most interest is
$\Lambda_{n}=[-n,n]^{d}\cap\mathbb{Z}^{d}$ endowed with nearest-neighbor
adjacency. To state our results and execute our arguments, we will also have
to consider the RFIM measure $\mu_{\Lambda}$ on general finite domains
$\Lambda\subset{\mathbb{Z}}^{d}$. (By abuse of notation we let $\Lambda$
denote the subgraph of ${\mathbb{Z}}^{d}$ whose vertex set is $\Lambda$.) We
will always let $N=|\Lambda|$ be the volume of the domain under consideration,
and we write ${\mathbb{P}}_{h}$ for the law of the random field $h$.

For a vertex $o\in{\mathbb{Z}}^{d}$ and an integer $r\geq 0$, we denote by
$B_{r}(o)$ the ball centered at $o$ with radius $r$ in the $\ell_{\infty}$
distance in ${\mathbb{Z}}^{d}$. For a subset $A\subseteq\Lambda$ we let
$\sigma_{A}=(\sigma_{u})_{u\in A}$. We use $\partial A$ to denote the exterior
vertex boundary of $A$ (with respect to $\Lambda$). Given a ‘boundary
condition’ $\tau\in\\{-1,+1\\}^{\partial A}$ we define

$\mu_{A}^{\tau}(\sigma_{A}):=\mu_{\Lambda}(\sigma_{A}\in\cdot\,|\,\sigma_{\partial
A}=\tau)\,,$ (1.4)

as the distribution of $\sigma_{A}$ induced by the RFIM measure
$\mu_{\Lambda}$ on $\\{-1,+1\\}^{A}$ conditional on $\sigma_{\partial
A}=\tau$. When $\tau$ is the all ‘$+$’ or the all ‘$-$’ configuration we
simply write $\mu_{A}^{+}$ and $\mu_{A}^{-}$ respectively.

##### Weak spatial mixing.

Our first assumption is of _weak spatial mixing_ (WSM) type where in
expectation, the influence of a boundary on the ‘root’ spin decays
exponentially in the distance from the boundary. This minimal level of
exponential decay should hold throughout the uniqueness region of the RFIM.

######  Definition 1.1.

We say that the RFIM on $\Lambda\subset{\mathbb{Z}}^{d}$ satisfies
$\text{\rm\small WSM}(C)$ for some constant $C>0$ if for all $o\in\Lambda$ and
all $r\geq 1$ we have

$\displaystyle{\mathbb{E}}_{h}\,\big{[}d_{\mbox{\rm\tiny
TV}}\big{(}\mu_{B_{r}(o)\cap\Lambda}^{+}(\sigma_{o}\in\,\cdot\,)\,,\,\mu_{B_{r}(o)\cap\Lambda}^{-}(\sigma_{o}\in\,\cdot\,)\big{)}\big{]}\leq
Ce^{-r/C}\,.$ (1.5)

where $d_{\mbox{\rm\tiny TV}}(\cdot,\cdot)$ is the total-variation distance,
and the expectation is over the field $h$. Importantly, all boundary pinnings
in WSM are at distance at least $r$ from $o$ (c.f. Definition 1.5 of SSM).

Denote by $(P_{t})_{t\geq 0}$ the Markov semigroup for the continuous-time
Glauber dynamics (1.3): i.e., for a given $h$ realization,
$P_{t}\varphi(\sigma)={\mathbb{E}}[\varphi(X_{t})|X_{0}=\sigma]$ for tests
function $\varphi:\\{-1,+1\\}^{V}\to\real$. For a probability measure $\mu$,
let $\mathrm{Var}_{\mu}(\varphi)=\mu(\varphi^{2})-\mu(\varphi)^{2}$ be the
variance of $\varphi$ under $\mu$, and let
$\mathrm{osc}(\varphi)=(\max\varphi-\min\varphi)^{2}$ be the (square of the)
oscillation of $\varphi$.

Under Definition 1.1, we show algebraic convergence to equilibrium for any
test function, after polynomial in $|\Lambda|$ time, and the existence of a
polynomial time sampling algorithm.

######  Theorem 1.2.

Suppose the RFIM on $\Lambda_{n}$ satisfies $\text{\rm\small WSM}(C)$ for some
$C>0$. Then there exists $K,\alpha,\kappa>0$ depending on $d,\beta,C$ such
that for all $\delta>0$ the following holds with
${\mathbb{P}}_{h}$-probability $1-\delta$: For all test functions
$\varphi:\\{-1,+1\\}^{\Lambda_{n}}\rightarrow{\mathbb{R}}$ and all $t>0$,

$\mathrm{Var}_{\mu_{\Lambda_{n}}}(P_{t}\varphi)\leq
Kn^{\kappa}\,\mathrm{osc}(\varphi)\big{/}(\delta t^{\alpha})\,,$ (1.6)

i.e., the continuous-time Glauber dynamics for the RFIM on $\Lambda_{n}$ has
algebraic convergence to equilibrium on $n^{\kappa/\alpha}$ timescales.

######  Remark 1.3.

Our techniques can also be used to extend Theorem 1.2 to the case of the torus
$T_{n}=(\mathbb{Z}/n\mathbb{Z})^{d}$. There, the vertex transitivity reduces
$\text{\rm\small WSM}(C)$ to the expected difference between the marginals on
the origin in boxes of radius $r$ with ‘$+$’ and ‘$-$’ boundary conditions.

The above algebraic convergence to equilibrium is a consequence of a _weak
Poincaré inequality_ [48] and accompanying large set expansion. These notions
have received attention since the classical work of Liggett [42] on critical
interacting particle systems, see e.g., [6, 7, 32]. The bound of (1.6) is
weaker than what would be implied by a spectral gap lower bound in two ways:
(1) the decay in time is inverse-polynomial (algebraic) instead of
exponential, and (2) the right-hand side of the inequality features the
oscillation of the test function rather than its variance w.r.t
$\mu_{\Lambda_{n}}$. A slightly stronger result which does not degenerate at
$t=0$ and recovers the trivial inequality
$\mathrm{Var}_{\mu_{\Lambda_{n}}}(P_{t}\varphi)\leq\mathrm{Var}_{\mu_{\Lambda_{n}}}(\varphi)$
can be found in Section 3.3, Eq. (3.16).

Next we let $\mathcal{Q}_{n}$ denote the collection of subsets of
$\Lambda_{n}$ of the form $B_{r}(o)\cup(\partial B_{r}(o)\cap A)$,
$A\subset{\mathbb{Z}}^{d}$, $r\leq n-1$. These are ‘cube-like’ domains where
the boundary may be irregular. The relevance of such domains will become clear
in the next paragraph.

######  Theorem 1.4.

Suppose that for some $C>0$, for all $\Lambda\in\mathcal{Q}_{n}$, the RFIM on
$\Lambda$ satisfies $\text{\rm\small WSM}(C)$. Then for any $\varepsilon>0$
and $\delta\in(0,1)$ there exists a randomized algorithm taking as input
$\beta,h$ and $\Lambda_{n}$ which runs in time $n^{c}$ for
$c=c(\varepsilon,\delta,\beta,C,d)>0$, and outputs a random configuration
$\sigma^{\mbox{\rm\tiny alg}}\in\\{-1,+1\\}^{\Lambda_{n}}$ with law
$\mu_{\Lambda_{n}}^{\mbox{\rm\tiny alg}}$ such that with
${\mathbb{P}}_{h}$-probability $1-\delta$,

$d_{\mbox{\rm\tiny
TV}}\big{(}\mu_{\Lambda_{n}},\mu_{\Lambda_{n}}^{\mbox{\rm\tiny
alg}}\big{)}\leq\varepsilon\,.$ (1.7)

Our sampling algorithm can attain any polynomially small total variation
distance to equilibrium in polynomial time. The algorithm proceeds iteratively
by running Glauber dynamics for polynomially many steps on the RFIM measure on
a domain $V_{i}$ with free boundary condition, where
$V_{1}=\\{o\\}\subset\cdots\subset V_{N}=\Lambda_{n}$ is an increasing
sequence of domains such that $V_{i+1}$ is obtained from $V_{i}$ by adding a
single vertex $v_{i+1}$ to its boundary. The chain at step $i+1$ on $V_{i+1}$
is initialized from the output of the chain at step $i$ on $V_{i}$
concatenated with the spin $\sigma_{v_{i+1}}$ sampled independently. We prove
that at each step $i$, this initialization is a _warm start_ with respect to
the RFIM measure on $V_{i}$, $\mu_{V_{i}}$, i.e., the initialization has
bounded Radon-Nikodym derivative w.r.t. $\mu_{V_{i}}$. We then use the tools
of Lovasz and Simonovits [43] to show that large set expansion implies the
chain mixes in polynomial time. The definition of the collection
$\mathcal{Q}_{n}$ is made exactly to accommodate such a construction: we will
have $V_{i}\in\mathcal{Q}_{n}$ for all $1\leq i\leq N$, so that WSM holds on
each $V_{i}$, and large-set expansion follows from Theorem 1.2.

##### Strong spatial mixing.

We now work under _strong spatial mixing_ (SSM) in expectation, whereby the
influence on the root spin decays exponentially in the distance from the
vertices _on which the two boundary conditions disagree_ , i.e., even in the
presence of arbitrarily close _agreeing_ pinnings. Assuming SSM in
expectation, we can show the stronger result that the continuous-time Glauber
dynamics on the RFIM on $\Lambda_{n}$ mixes in $N^{o(1)}$ time, or
equivalently mixing happens after $N^{1+o(1)}$ spin flips for the discrete
chain.

######  Definition 1.5.

For a constant $C>0$, we say that the RFIM on $\Lambda_{n}$ satisfies
$\text{\rm\small SSM}(C)$ if for every $r\geq 1$, every box
$B\in\\{w+B_{r}(o):w\in\\{-r+1,...,r-1\\}^{d}\\}$ (this is all possible cubes
of radius $r$ having the origin $o$ in their interior), and every
$z\in\partial B$,

$\displaystyle{\mathbb{E}}_{h}\Big{[}\max_{\xi\in\\{-1,+1\\}^{\partial
B\setminus\\{z\\}}}d_{\mbox{\rm\tiny
TV}}\big{(}\mu_{B}^{\xi^{+}}(\sigma_{o}\in\,\cdot\,)\,,\,\mu_{B}^{\xi^{-}}(\sigma_{o}\in\,\cdot\,)\big{)}\Big{]}\leq
Ce^{-d(o,z)/C}\,,$

where $\xi^{+},\xi^{-}\in\\{-1,+1\\}^{\partial B}$ are the boundary conditions
which agree with $\xi$ on $\partial B\setminus\\{z\\}$ and take the values $+$
and $-$ on $z$ respectively.

Let $\mathcal{E}_{\mu_{\Lambda}}$ be the Dirichlet form of Glauber dynamics:
for a test function $\varphi:\\{-1,+1\\}^{\Lambda}\rightarrow\real$,

$\mathcal{E}_{\mu_{\Lambda}}(\varphi,\varphi):=\frac{1}{2}\sum_{\sigma\sim\sigma^{\prime}}\frac{\mu_{\Lambda}(\sigma)\mu_{\Lambda}(\sigma^{\prime})}{\mu_{\Lambda}(\sigma)+\mu_{\Lambda}(\sigma^{\prime})}\left(\varphi(\sigma)-\varphi(\sigma^{\prime})\right)^{2}\,,$
(1.8)

and where the sum is over pairs
$\sigma,\sigma^{\prime}\in\\{-1,+1\\}^{\Lambda}$ which differ in only one
coordinate, and define the spectral gap of the chain as

$\text{\tt{gap}}_{\Lambda}=\inf_{\varphi}\frac{\mathcal{E}_{\mu_{\Lambda}}(\varphi,\varphi)}{\mathrm{Var}_{\mu_{\Lambda}}(\varphi)}\,,$
(1.9)

where the infimum is taken over test functions
$\varphi:\\{-1,+1\\}^{\Lambda}\to\real$ of non-zero variance.

Our main result under SSM is the following.

######  Theorem 1.6.

Suppose the RFIM on $\Lambda_{n}$ satisfies $\text{\rm\small SSM}(C)$ for some
$C>0$. Then there exists $\kappa=\kappa(d,\beta,C)>0$ such that for every
$L\geq\kappa\log n$,

$\text{\tt{gap}}_{\Lambda_{n}}\geq\exp\big{\\{}-L^{\frac{d-1}{d}+o(1)}\big{\\}}\,,$

with ${\mathbb{P}}_{h}$-probability at least $1-e^{-L}$. In particular, by
taking $L=\kappa\log n$, the mixing time of continuous-time Glauber dynamics
on $\Lambda_{n}$ is at most $n^{o(1)}$ with ${\mathbb{P}}_{h}$-probability
$1-n^{-\kappa}$.

It is not difficult to show that for every $\beta>0$, SSM (and hence WSM)
holds if the external field magnitudes $|h|$ are sufficiently anti-
concentrated: see Lemma 5.18. Conversely, one may wonder what should be the
optimal mixing time for the RFIM. General arguments in [33] give a ‘coupon
collecting’ lower bound of $\Omega(\log n)$. In Proposition 6.1, we show a
super-polylogarithmic lower bound on the mixing time for the RFIM for $\beta$
sufficiently large, provided the field variances are $O(1)$, confirming the
expected slowdown in the Griffiths phase. To be precise, in this Griffiths
regime the $L^{(d-1)/d}$ dependence in Theorem 1.6 should be optimal.

###  1.2 Overview of the proof

Our proof is broadly based on a combination of ideas and techniques used to
analyze dynamics of lattice models (mainly coarse graining and block dynamics)
with the more recently developed techniques for studying mixing times for
general spin systems (specifically, stochastic localization). Our sampling
algorithm is an adaptation of ideas from algorithmic convex geometry. We
describe these components in what follows.

####  1.2.1 An easy quasipolynomial bound

As a warm-up, and to introduce the difficulties inherent to obtaining
polynomial convergence in every dimension, let us provide a proof of
$e^{O((\log n)^{d-1})}$ mixing on $\Lambda_{n}$ under WSM, Def. 1.1. (This
already provides polynomial mixing time for $d=2$.) The crux of this bound is
to tile the domain with boxes of side-length $C_{0}\log n$ for some large
constant $C_{0}$, at which scale every box exhibits decay of correlation with
high probability, and then union bound over the probability of not coupling in
all of these boxes after their largest mixing time.

Let us assume $\text{\rm\small WSM}(C)$, $C>0$. Using Markov’s inequality and
a union bound over the vertices in $\Lambda_{n}$, there exists $C^{\prime}>0$
such that with probability $1-o_{n}(1)$, for all $r\geq C^{\prime}\log n$,

$\displaystyle\max_{v\in\Lambda_{n}}~{}d_{\mbox{\rm\tiny
TV}}\Big{(}\mu_{B_{r}(v)}^{+}(\sigma_{v}\in\cdot)\,,\,\mu_{B_{r}(v)}^{-}(\sigma_{v}\in\cdot)\Big{)}\leq
C^{\prime}e^{-r/C^{\prime}}\,.$ (1.10)

Let $r_{0}=C_{0}\log n$ and let $B_{v}=B_{r_{0}}(v)$ for each
$v\in\Lambda_{n}$. Fix a vertex $v$ and let $(Y_{t,v}^{+}),\,(Y_{t,v}^{-})$ be
two chains on the state space $\\{-1,+1\\}^{B_{v}}$ following Glauber dynamics
transitions, initialized from the all ‘$+$’ and all ‘$-$’ configurations
respectively, and ignoring all updates outside $B_{v}$. Then

$\displaystyle\max_{\sigma_{0},\sigma_{0}^{\prime}}d_{\mbox{\rm\tiny
TV}}\left({\mathbb{P}}(X_{t}^{\sigma_{0}}\in\cdot),{\mathbb{P}}(X_{t}^{\sigma_{0}^{\prime}}\in\cdot)\right)$
$\displaystyle\leq\sum_{v\in\Lambda_{n}}\mathbf{P}\left(Y_{t,v}^{+}(\sigma_{v})\neq
Y_{t,v}^{-}(\sigma_{v})\right)\,.$ (1.11)

The above inequality is obtained by a union bound over the vertices, and
monotonicity of the disagreement probability in the distance from the boundary
under the grand coupling $\mathbf{P}$. The latter is the coupling using the
same Poisson clock to update both chains, and when a vertex $w\in B_{v}$ needs
updating, $Y_{t,v}^{+}(w)$ and $Y_{t,v}^{-}(w)$ are sampled using the same
uniform random variable. (See the preliminaries in Section 2.)

By a triangle inequality, the probability on the right-hand side of (1.11) is
bounded by

$\displaystyle 2\max_{\iota\in\pm}~{}d_{\mbox{\rm\tiny
TV}}\left({\mathbb{P}}(Y_{t,v}^{\iota}\in\cdot)\,,\,\mu_{B_{v}}^{\iota}\right)+d_{\mbox{\rm\tiny
TV}}\big{(}\mu_{B_{v}}^{+}(\sigma_{v}\in\cdot)\,,\,\mu_{B_{v}}^{-}(\sigma_{v}\in\cdot)\big{)}\,.$
(1.12)

By submultiplicativity of the total variation distance, the first quantity is
at most $o(n^{-d})$ for

$t\geq T_{0}:=(C_{d}\log n)\max_{v}\big{\\{}t_{\mathrm{mix}}^{+}(B_{v})\vee
t_{\mathrm{mix}}^{-}(B_{v})\big{\\}}\,,$

where $t_{\mathrm{mix}}^{\iota}(B_{v})$ is the mixing time of
$(Y_{t,v}^{\iota})_{t\geq 0}$, $\iota=\pm$. With high probability, the second
quantity in (1.12) is also $o(n^{-d})$ for all $v$ by (1.10) if $C_{0}$ is a
sufficiently large constant. The proof is complete by noting that $T_{0}\leq
e^{O((\log n)^{d-1})}$ by the fact that the cut-width of $B_{v}$ is at most
$r_{0}^{d-1}=O((\log n)^{d-1})$ and that the mixing time is no more than
exponential in the cut-width. This can be shown using the canonical path
method of [37] (see e.g., [9, Proposition 1.1]).

The weakness of this approach, most apparent for $d\geq 3$, is that the boxes
in our tiling have volume $(\log n)^{d}$ as necessitated by (1.10) and the
union bound over all vertices of $\Lambda_{n}$. When the external fields are
strong enough, we may expect to do better by adapting the tiling to the
realization of the fields. The regions of slow-down of the chain are regions
of weak fields, which by percolation arguments are of volume $\log n$ instead
of $(\log n)^{d}$. To implement this, when the external fields are only
marginally strong enough for decay of correlations (e.g., the minimal
assumption of $\text{\rm\small WSM}(C)$ in expectation), we artificially
increase the external field strength using a _stochastic localization
process_. We explain both of these steps in the next three subsections.

####  1.2.2 Weak Poincaré under WSM and reduction to strong fields

We will show that under WSM, the RFIM on $\Lambda_{n}$ satisfies a _weak_
Poincaré inequality of the form

$\mathrm{Var}_{\mu_{\Lambda_{n}}}(\varphi)\leq
KN^{\kappa}\,\mathcal{E}_{\mu_{\Lambda_{n}}}(\varphi)^{1/p}\,\mathrm{osc}(\varphi)^{1/q}\,,$
(1.13)

for all test functions $\varphi$, with high probability over the randomness of
the external field $h$, for some $K,\kappa>0$ and $p,q\geq 1$ with $1/p+1/q=1$
which do not depend on $N$; see Theorem 3.1 for the precise statement. We will
deduce Theorem 1.2 as a consequence of this inequality.

We employ the stochastic localization (SL) technique of [23] to prove (1.13).
We consider the SL process $(\nu_{t})_{t\geq 0}$ with
$\nu_{0}=\mu_{\Lambda_{n}}$. In our context, this process is characterized as
follows: One may write

$\nu_{t}(\sigma)\propto\exp\big{\\{}-H(\sigma)-\langle
y_{t},\sigma\rangle\big{\\}}\ ,$

for a stochastic process $y_{t}$ of the form $y_{t}=B_{t}+v_{t}$ where $B_{t}$
is a standard Brownian motion and $v_{t}$ is a predictable process (i.e., a
drift). Moreover, the process $v_{t}$ is the unique process for which
$\nu_{t}(A)$ is a martingale for every subset $A$ of the configuration space.

In other words, the measure $\nu_{t}$ still has the form of a certain RFIM on
$\Lambda_{n}$, but the external fields follow a different distribution. We
will see that, roughly speaking, the strength of the external fields
_increases_ with time. For a sufficiently large but constant (in $N$) time $T$
we aim to show two key properties, to be sketched in further detail in the
subsections that follow:

  * •

The variance of any test function $\varphi$ under $\nu_{T}$ is ‘not much
smaller’ than its variance under $\nu_{0}$, with high probability. This
statement takes the form (see Theorem 3.1),

$\mathrm{Var}_{\nu_{0}}(\varphi)\leq
KN^{1/q}\,{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{T}}(\varphi)\,|\,h\big{]}^{1/p}\,\mathrm{osc}(\varphi)^{1/q}\,,$
(1.14)

for some $p,q$ such that $1/p+1/q=1$, with high
${\mathbb{P}}_{h}$-probability. (The expectation in the above display is with
respect to the SL process.) A stronger bound where $p=1$, $q=+\infty$ has been
referred to as an _approximate variance conservation bound_ and has been used
to show spectral gaps for Ising measures whose interaction matrix has a
spectral diameter bounded by 1 [24, 15]. In our case we are only able to prove
the weak version (1.14); this is due to the fact that the covariance matrix of
$\nu_{T}$ is not almost-surely bounded, but is of typical size $O(\log N)$
with an exponential upper tail; see Theorem 3.2.

  * •

The resulting random measure $\nu_{T}$ has a spectral gap with high
probability, in the usual sense; see Theorem 5.1. This crucially relies on the
fact that the coordinates of the new external field $h+y_{T}$ have independent
magnitudes (though not signs) and can be made sufficiently anti-concentrated
by taking $T$ to be a large constant. Thus the regions of weak fields form a
subcritical percolation process in $\Lambda_{n}$. We construct a (field-
dependent) block-dynamics for $\nu_{T}$ which exploits this property, and this
allows us to prove a spectral gap. See Section 5 for the construction.

Then the weak PI (1.13) for $\mu_{\Lambda_{n}}$ follows by combining Eq.
(1.14) with a spectral gap for $\nu_{T}$, together with the observation that
the Dirichlet form process $t\mapsto\mathcal{E}_{\nu_{t}}(\varphi,\varphi)$ is
a super-martingale (see [24, Lemma 9]). The statement and the full proof of
the weak PI can be found in Section 3, and the proof of Theorem 1.2 can be
found in Section 3.3.

####  1.2.3 Approximate variance conservation bound

Towards obtaining (1.14), we follow the usual paradigm of the SL technique
which suggests that the rate of variance decay along the SL process can be
bounded by the operator norm of the respective covariance matrices. In
particular, the decay rate of $\mathrm{Var}_{\nu_{t}}(\varphi)$ can be
controlled via the quantity $\|\mathrm{Cov}(\nu_{t})\|_{\textup{op}}$, which
is in turn bounded by $\mathrm{Tr}(\mathrm{Cov}(\nu_{t})^{p})^{1/p}$ with
$p\sim\log n$.

Controlling the covariance matrix of $\nu_{t}$ is the heart of the argument,
and uses several properties of the RFIM. Defining $(a_{i,j})_{i,j}$ as the
entries of $\mathrm{Cov}(\nu_{t})$, the natural first step is to write

$\mathrm{Tr}\big{(}\mathrm{Cov}(\nu_{t})^{p}\big{)}=\sum_{u_{1},...u_{p}\in\Lambda_{n}}a_{u_{1},u_{2}}\cdots
a_{u_{p-1},u_{p}}a_{u_{p},u_{1}}\,.$ (1.15)

Now we can control the influence of $u_{i+1}$ on $u_{i}$ by introducing a
boundary at distance $r\leq d_{\infty}(u_{i},u_{i+1})$ from $u_{i}$. By
monotonicity we obtain

$a_{u_{i},u_{i+1}}\leq d_{\mbox{\rm\tiny
TV}}\big{(}\nu_{t}(\sigma_{u_{i}}\in\,\cdot\,|\,\sigma_{\partial
B_{r}(u_{i})}=+)\,,\,\nu_{t}(\sigma_{u_{i}}\in\,\cdot\,|\,\sigma_{\partial
B_{r}(u_{i})}=-)\big{)}\,.$ (1.16)

The WSM condition (1.1) then gives an upper bound on the right-hand side in
the case $t=0$.

Obtaining a similar bound for general $t$ is more involved. It relies on two
main components:

  * •

A calculation that shows that the total-variation distance in (1.16) is in
some sense a super-martingale with respect to $t$. This calculation is
somewhat similar to that showing the Dirichlet form is a super-martingale
[24], and crucially uses the FKG correlation inequality.

  * •

A representation theorem obtained in [22] shows that the measure $\nu_{t}$ can
be written in a form that implies that the total variations at different
points are essentially independent under WSM. This allows to control the
expectation of the product in (1.15) under the randomness of the SL process.

Finally, a combinatorial counting argument is used in conjunction with the
above estimates to obtain a bound for
$\mathrm{Tr}(\mathrm{Cov}(\nu_{t})^{p})$.

####  1.2.4 Coarse-graining and disorder-dependent block dynamics

After use of the stochastic localization, we need to show high probability
bounds on the spectral gap of the Glauber dynamics for the RFIM with external
fields with are sufficiently anti-concentrated. We show that under such an
assumption, the inverse spectral gap is at most $N^{o(1)}$. This is actually
proved in conjunction with Theorem 1.6 as they both use identical strategies
based on combining a field-dependent _coarse-graining_ with a block dynamics
where the blocks are non-homogenous and determined by the realization of the
field.

Our aim is to localize the dynamics to blocks of diameter $C\log n$, inside of
which the large typical size of the field shields the center of the ball from
the influence of the boundary. This would reduce the mixing time on
$\Lambda_{n}$ to the maximum mixing time on a block. However, as indicated by
the short proof in Subsection 1.2.1, if these regions are chosen as cubes, the
worst-case mixing time will be super-polynomial in $n$ in $d\geq 3$.

Our proof leverages the fact that the regions where the external field is not
large are a sparse subset of $\Lambda_{n}$, i.e., they behave like a
subcritical percolation and their largest connected components have $O(\log
n)$ volume. We construct localizing blocks depending on the realization of
$h$, in such a way that their largest volume is $\tilde{O}(\log n)$, their
boundary is sufficiently shielded from their bulk by large fields, and the
blocks’ worst mixing time is sub-polynomial. The crux of this construction is
twofold:

  * •

We coarse-grain the lattice into good and bad blocks of radius $\log\log n$,
where bad blocks are those dominated by small field values (in a quantifiable
way). The coarse-graining enables a construction which isolates the “bad”
portions of $\Lambda_{n}$ while building up enough buffer around them that
different boundary conditions on a block do not influence its bulk. The
largest blocks in this construction will have volume $O(\log n\log\log n)$.

  * •

The amenability of and isoperimetry in $\mathbb{Z}^{d}$ ensure that the cut-
width of a domain with volume $|B|$ is at most $|B|^{(d-1)/d}$. A standard
bound of the mixing time by the exponential in the cut-width then gives a sub-
polynomial worst mixing time over the blocks.

We note that similar coarse-graining ideas were used to homogenize quenched
randomness in [12] for the random ferromagnet (random couplings rather than
fields).

### Acknowledgements

The research of R.G. was supported in part by NSF DMS-2246780. A.P. was
supported by an Israel Council of Higher Education Data Science Research
Fellowship.

##  2 Preliminaries

##### Markov chains

We first recall some basics of Markov chain mixing times used in our context.
The continuous time chain $(X_{t})$ defined in (1.3) is reversible,
irreducible and aperiodic with stationary measure $\mu_{G}$. We define its
$\varepsilon$-mixing time

$\tau_{\mathrm{mix}}^{\mathrm{cont}}(\varepsilon):=\inf\left\\{t\geq
0~{}:\max_{\sigma\in\\{-1,+1\\}^{V}}d_{\mbox{\rm\tiny
TV}}\big{(}{\mathbb{P}}(X_{t}\in\cdot\,|\,X_{0}=\sigma)\,,\,\mu_{G}\big{)}\leq\varepsilon\right\\}\,,$

where $d_{\mbox{\rm\tiny TV}}(\cdot,\cdot)$ is the total variation distance
between probability measures. By convention we set $\varepsilon=1/4$. We
sometimes abuse notation and write $d_{\mbox{\rm\tiny TV}}(X,Y)$ or
$d_{\mbox{\rm\tiny TV}}(X,\nu)$ for two random variables $X\sim\mu$ and
$Y\sim\nu$ instead of $d_{\mbox{\rm\tiny TV}}(\mu,\nu)$. The mixing time can
be estimated in terms of the inverse spectral gap as defined in (1.9), see
[40, Theorem 20.6] :

$\tau_{\mathrm{mix}}^{\mathrm{cont}}(\varepsilon)\leq\frac{1}{\text{\tt{gap}}_{G}}\log\left(\frac{1}{\varepsilon\mu_{\min}}\right)\,,$

where $\mu_{\min}=\min_{\sigma\in\\{-1,+1\\}^{V}}\mu_{G}(\sigma)$.

The discrete Glauber dynamics chain chooses a vertex $v\in V$ uniformly at
random at every step and resamples its value according to the same conditional
distribution (1.3). Letting $P$ denote its transition matrix, its
$\varepsilon$-mixing time $\tau_{\mathrm{mix}}(\varepsilon)$ is similarly
defined as the smallest integer $k\geq 0$ such that $d_{\mbox{\rm\tiny
TV}}(P^{k}(\sigma,\cdot),\mu)\leq\varepsilon$ for all starting points
$\sigma\in\\{-1,+1\\}^{V}$. The two mixing times are related by a factor of
$|V|$ up to constants (see, e.g. [40, Theorem 20.3]):

$(\varepsilon/2)\,|V|\,\tau_{\mathrm{mix}}^{\mathrm{cont}}(2\varepsilon)\leq\tau_{\mathrm{mix}}(\varepsilon)\leq
2|V|\,\tau_{\mathrm{mix}}^{\mathrm{cont}}(\varepsilon/4)\,.$

##### FKG and couplings

Positivity of the RFIM interactions ($\beta\geq 0$) implies useful correlation
inequalities such as the FKG inequality (see e.g., [26, 20]). In particular,
for any subset $A\subset V$ and any non-decreasing function
$\varphi:\\{-1,+1\\}^{A}\to\real$, the mean of $\varphi$ under
$\mu^{\tau}_{A}$ is monotone in the boundary condition:
$\mu^{\tau}_{A}(\varphi)\leq\mu^{\tau^{\prime}}_{A}(\varphi)$ if
$\tau\leq\tau^{\prime}$ (where this inequality is understood vertexwise). This
for instance implies that the covariance under $\mu_{G}$ between any two non-
decreasing functions (on the natural partial order over Ising configurations)
is non-negative.

Given two boundary conditions $\tau,\tau^{\prime}$, the measures
$\mu^{\tau}_{A},\,\mu^{\tau^{\prime}}_{A}$ can be coupled via the _monotone
coupling_ where we fix an ordering $v_{1},\cdots,v_{k}$ of the vertices in $A$
and draw unit uniform random variables $U_{1},\cdots,U_{k}$ independently. We
then construct the coupling $(\sigma^{\tau},\sigma^{\tau^{\prime}})$
sequentially where for each $i\geq 1$ we sample $\sigma_{v_{i}}^{\tau}$ and
$\sigma_{v_{i}}^{\tau^{\prime}}$ from their respective conditional
distributions (given $(\sigma_{v_{j}}^{\tau})_{j<i},\tau$ and
$(\sigma_{v_{j}}^{\tau^{\prime}})_{j<i},\tau^{\prime}$ respectively) using
$U_{i}$ as common randomness. It can be verified that this coupling is
monotone in the boundary condition: $\sigma^{\tau}\leq\sigma^{\tau^{\prime}}$
if $\tau\leq\tau^{\prime}$.

Finally, two chains of (continuous time) Glauber dynamics can be coupled via
_the grand coupling_ where the same Poisson clock is used to update both
chains, and whenever a vertex is to be updated (simultaneously in both
chains), the same uniform random variable is used. This coupling is monotone
in both initialization and boundary condition.

##### Stochastic localization

We now present some fundamental properties of _stochastic localization_ (SL),
first introduced in [23]. Let $\nu_{0}$ be an absolute continuous probability
measure on $\\{-1,+1\\}^{N}$ with density $\nu_{0}$ and with finite second
moment. (In our application of the method, $\nu_{0}=\mu_{\Lambda}$ the RFIM
measure on some domain $\Lambda$ of interest.) Let $(B_{t})_{t\geq 0}$ be a
standard Brownian motion on $\mathbb{R}^{N}$ with $B_{0}=0$. SL is the
stochastic process $(\nu_{t}(\sigma))_{t\geq 0}$, whose density

$\frac{\mathrm{d}\nu_{t}}{\mathrm{d}\nu_{0}}(\sigma)=F_{t}(\sigma)$

solves the stochastic differential equation

$\begin{cases}\mathrm{d}F_{t}(\sigma)&=F_{t}(\sigma)\langle\sigma-
a_{t},\mathrm{d}B_{t}\rangle\quad\forall\sigma\in\\{-1,+1\\}^{N}\,,\\\
F_{0}(\sigma)&=1\,,\end{cases}$ (2.1)

where $a_{t}$ is the barycenter of $\nu_{t}$:

$a_{t}=\int_{\\{-1,+1\\}^{N}}\sigma\,\,\nu_{t}(\mathrm{d}\sigma)\,.$ (2.2)

By [25, Proposition 9], the SL process defined in (2.1) is such that almost
surely, for all $t$, $\nu_{t}$ is a probability measure, and for all
$A\subseteq\\{-1,1\\}^{N}$, $t\mapsto\nu_{t}(A)$ is a martingale.

The SL process can be also seen as a stochastic tilt of $\nu_{0}$. For an
external field $y\in{}^{N}$, consider the tilted measure

$\mu_{y}(\sigma)\propto e^{\langle y,\sigma\rangle}\nu_{0}(\sigma)\,.$

The stochastically localized measure can be written as

$\nu_{t}(\sigma)=\mu_{y_{t}}(\sigma)\propto e^{\langle
y_{t},\sigma\rangle}\nu_{0}(\sigma)\,,$ (2.3)

where we let $y_{t}$ evolve according to the SDE

$\mathrm{d}y_{t}=a(y_{t})\mathrm{d}t+\mathrm{d}B_{t}\,,~{}~{}~{}~{}y_{0}=0\,,$
(2.4)

with $a(y_{t})=a_{t}$ as in (2.2). The measure-valued process
$(\nu_{t})_{t\geq 0}$ can be given a Bayesian interpretation in the following
sense:

######  Proposition 2.1.

([22, Theorem 2] and [39, Proposition 4.1]) Let $(\bar{B}_{t})_{t\geq 0}$ be a
standard Brownian motion and sample $\sigma^{\ast}\sim\nu_{0}$ independently
from $(\bar{B}_{t})_{t\geq 0}$. Then $(y_{t})_{t\geq 0}$ defined as in (2.4)
has the same distribution of $(\bar{y}_{t})_{t\geq 0}$ defined as

$\bar{y}_{t}=t\sigma^{*}+\bar{B}_{t}\,,~{}~{}~{}~{}t\geq 0\,,$ (2.5)

and $(\nu_{t})_{t\geq 0}$ is distributed as the process of conditional
measures $\big{(}\nu_{0}(\sigma^{*}\in\cdot\,|\,\bar{y}_{t})\big{)}_{t\geq
0}$.

From the above proposition and Eq. (2.3) it is clear that when
$\nu_{0}=\mu_{G}$, $\nu_{t}$ is another RFIM measure on $G$ with external
field $h+\bar{y}_{t}$.

##  3 A weak Poincaré inequality under WSM

Our main aim is to prove a weak Poincaré inequality for the RFIM on a domain
$\Lambda$ under WSM, to obtain Theorem 1.2 as a consequence. In this section,
we provide this proof modulo two important inputs, one being a bound on the
covariance matrix of $\nu_{t}$ under WSM, and the other being a proof of a
full Poincaré inequality if the fields are sufficiently anti-concentrated
(which will be the output of the localization scheme after a large but
constant time.) Those two steps will be the content of Sections 4–5
respectively.

###  3.1 Approximate variance conservation

We start with our weak version of an approximate variance conservation bound:

######  Theorem 3.1.

Suppose the RFIM on $\Lambda$ satisfies $\text{\rm\small WSM}(C)$ for some
$C>0$, then there exists $c_{0}=c_{0}(d,C)>0$ such that for all $\delta>0$,
the following holds with ${\mathbb{P}}_{h}$-probability at least $1-\delta$.
For all $T>0$ and all test functions
$\varphi:\\{-1,+1\\}^{\Lambda}\to{\mathbb{R}}$, we have

$\mathrm{Var}_{\nu_{0}}(\varphi)\leq\big{(}e^{-c_{0}}N/\delta\big{)}^{1/q}\,{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{T}}(\varphi)\,|\,h\big{]}^{1/p}\,\mathrm{osc}(\varphi)^{1/q}\,,$
(3.1)

with $N=|\Lambda|$, $p=e^{T/c_{0}}$ and $1/p+1/q=1$.

The proof of the above theorem crucially relies on a tail bound for the
operator norm of the covariance matrix of $\nu_{t}$ which we state here:

######  Theorem 3.2.

Suppose the RFIM on $\Lambda$ satisfies $\text{\rm\small WSM}(C)$ for some
$C>0$, then there exists $C_{0}=C_{0}(d,C)>0$ such that for any $p\geq 1$,

${\mathbb{E}}\left[\sup_{t\geq
0}\,{\mathbb{E}}\Big{[}\mathrm{Tr}(\mathrm{Cov}(\nu_{t})^{p})\,\big{|}\,h\Big{]}\right]\leq(C_{0}p)^{p}\,N\,,$
(3.2)

with $N=|\Lambda|$. In particular for all $R\geq 0$,

${\mathbb{E}}\left[\sup_{t\geq
0}\,{\mathbb{P}}\Big{(}\|\mathrm{Cov}(\nu_{t})\|_{\textup{op}}\geq
R\,\big{|}\,h\Big{)}\right]\leq Ne^{-c_{0}R}\,,$ (3.3)

with $c_{0}=(eC_{0})^{-1}$.

The proof of the above theorem is combinatorial in nature and is deferred to
Section 4.

###### Proof of Theorem 3.1.

We proceed by establishing a variational inequality for
${\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{t}}(\varphi)|h\big{]}$. First we note
that it follows from Theorem 3.2 and Markov’s inequality that

$\sup_{t\geq
0}\,{\mathbb{P}}\Big{(}\|\mathrm{Cov}(\nu_{t})\|_{\textup{op}}\geq
R\,|\,h\Big{)}\leq N\delta^{-1}e^{-c_{0}R}\,,$ (3.4)

with ${\mathbb{P}}_{h}$-probability $1-\delta$. We consider $h$ and $\delta>0$
fixed throughout and condition on the event given in Eq. (3.4). For ease of
notation it is implicitly understood that all expectations are conditional on
$h$, i.e., we only take expectation with respect to the SL process.

Define the martingale $M_{t}:=\nu_{t}(\varphi)$. Using the definition of the
SL process Eq. (2.1),

$\displaystyle\mathrm{d}M_{t}$
$\displaystyle=\mathrm{d}\int_{\\{-1,+1\\}^{\Lambda}}\varphi(x)\nu_{t}(\mathrm{d}x)=\int_{\\{-1,+1\\}^{\Lambda}}\varphi(x)\mathrm{d}F_{t}(x)\nu_{0}(\mathrm{d}x)$
$\displaystyle=\int_{\\{-1,+1\\}^{\Lambda}}\varphi(x)\langle
x-a_{t},\mathrm{d}B_{t}\rangle\nu_{0}(\mathrm{d}x)\,,$

and therefore we have

$\displaystyle\mathrm{d}[M]_{t}$
$\displaystyle=\left\|\int_{\\{-1,+1\\}^{\Lambda}}\varphi(x)(x-a_{t})\nu_{t}(\mathrm{d}x)\right\|^{2}\mathrm{d}t$
$\displaystyle=\sup_{\lvert\theta\lvert=1}\left(\int_{\\{-1,+1\\}^{\Lambda}}\varphi(x)\langle
x-a_{t},\theta\rangle\nu_{t}(\mathrm{d}x)\right)^{2}\mathrm{d}t$
$\displaystyle\overset{(\ast)}{\leq}\mathrm{Var}_{\nu_{t}}(\varphi)\sup_{\|\theta\|=1}\int_{\\{-1,+1\\}^{\Lambda}}\langle
x-a_{t},\theta\rangle^{2}\nu_{t}(\mathrm{d}x)\,\mathrm{d}t$
$\displaystyle=\mathrm{Var}_{\nu_{t}}(\varphi)\,\big{\|}\mathrm{Cov}(\nu_{t})\big{\|}_{\textup{op}}\,\mathrm{d}t\,,$
(3.5)

where in $(\ast)$ we apply the Cauchy–Schwarz inequality, and
$\mathrm{Cov}(\nu_{t})$ refers to the covariance matrix of $\nu_{t}$:

$\mathrm{Cov}(\nu_{t})=\int_{\\{-1,+1\\}^{\Lambda}}\sigma\sigma^{\top}\nu_{t}(\mathrm{d}\sigma)-a_{t}a_{t}^{\top}\,,~{}~{}~{}a_{t}=\int_{\\{-1,+1\\}^{\Lambda}}\sigma\,\nu_{t}(\mathrm{d}\sigma)\,.$

Let us write $A_{t}:=\mathrm{Cov}(\nu_{t})$. Next, we note that
$\nu_{t}(\varphi^{2})$ is a martingale. It follows from Itô’s formula that

$\displaystyle\mathrm{d}\mathrm{Var}_{\nu_{t}}(\varphi)$
$\displaystyle=\mathrm{d}\left(\nu_{t}(\varphi^{2})-M_{t}^{2}\right)=\mathrm{d}\nu_{t}(\varphi^{2})-2M_{t}\mathrm{d}M_{t}-\frac{1}{2}2\mathrm{d}[M]_{t}$
$\displaystyle=-\mathrm{d}[M]_{t}+\text{martingale}\,.$ (3.6)

It follows from Eq. (3.6) and Eq. (3.5) that

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\big{]}$
$\displaystyle\geq-{\mathbb{E}}\Big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\|A_{t}\|_{\textup{op}}\Big{]}$
$\displaystyle\geq-{\mathbb{E}}\Big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\|A_{t}\|_{\textup{op}}\mathbf{1}_{\|A_{t}\|_{\textup{op}}<R}\Big{]}-{\mathbb{E}}\Big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\|A_{t}\|_{\textup{op}}\mathbf{1}_{\|A_{t}\|_{\textup{op}}\geq
R}\Big{]}\,,$ (3.7)

for every $R>0$. We bound the two terms as

$\displaystyle{\mathbb{E}}\Big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\|A_{t}\|_{\textup{op}}\mathbf{1}_{\|A_{t}\|_{\textup{op}}<R}\Big{]}\leq
R\,{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\big{]}\,,$

and

$\displaystyle{\mathbb{E}}\Big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\|A_{t}\|_{\textup{op}}\mathbf{1}_{\|A_{t}\|_{\textup{op}}\geq
R}\Big{]}$
$\displaystyle\leq\mathrm{osc}(\varphi){\mathbb{E}}\big{[}\|A_{t}\|_{\textup{op}}\mathbf{1}_{\|A_{t}\|_{\textup{op}}\geq
R}\big{]}$
$\displaystyle=\mathrm{osc}(\varphi)\Big{(}R\,{\mathbb{P}}\big{(}\|A_{t}\|_{\textup{op}}\geq
R\big{)}+\int_{R}^{\infty}{\mathbb{P}}\big{(}\|A_{t}\|_{\textup{op}}\geq
r\big{)}\mathrm{d}r\Big{)}$
$\displaystyle\leq\mathrm{osc}(\varphi)N\delta^{-1}(R+c_{0}^{-1})e^{-c_{0}R}\,,$

where the last line follows from Eq. (3.4). We choose

$R=c_{0}^{-1}\log\left(\frac{N\mathrm{osc}(\varphi)}{\delta{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\big{]}}\right)\,.$

From Eq. (3.7) we obtain the differential inequality

$\frac{\mathrm{d}}{\mathrm{d}t}{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\big{]}\geq-
c_{0}^{-1}\left(2\log\left(\frac{N\mathrm{osc}(\varphi)}{\delta{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\big{]}}\right)+1\right){\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\big{]}\,.$
(3.8)

With

$u(t):={\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{t}}(\varphi)\big{]}\big{/}\mathrm{osc}(\varphi)\,,$

Eq. (3.8) becomes

$\frac{\mathrm{d}}{\mathrm{d}t}\log u(t)\geq 2c_{0}^{-1}\log
u(t)-c_{0}^{-1}\big{(}1+2\log(N/\delta)\big{)}\,.$

Considering the function $v(t)=e^{-2t/c_{0}}\log u(t)$ and integrating, we
obtain

$\displaystyle u(t)$ $\displaystyle\geq
u(0)^{e^{2t/c_{0}}}(N/\delta)^{1-e^{2t/c_{0}}}\exp\Big{(}-c_{0}\big{(}e^{2t/c_{0}}-1\big{)}/2\Big{)}\,.$

This implies the claimed bound. ∎

###  3.2 A weak Poincaré inequality

In this section we prove the weak Poincaré inequality for the RFIM on
$\Lambda$ under WSM.

######  Theorem 3.1.

Suppose $\text{\rm\small WSM}(C)$ holds for the RFIM on $\Lambda$ for some
constant $C>0$. Fix $\delta\in(0,1)$. With ${\mathbb{P}}_{h}$-probability at
least $1-\delta$, the following holds for all
$\varphi:\\{-1,+1\\}^{\Lambda}\to{\mathbb{R}}$:

$\mathrm{Var}_{\mu_{\Lambda}}(\varphi)\leq
K\delta^{-1/q}N^{\kappa}\,\mathcal{E}_{\mu_{\Lambda}}(\varphi,\varphi)^{1/p}\cdot\mathrm{osc}(\varphi)^{1/q}\,,$
(3.9)

where $p,q\geq 1$, $1/p+1/q=1$, and $K,\kappa>0$, all depending on
$C,\beta,d$.

Before starting the proof we quote the key result from Section 5 that a RFIM
with a strong external field obeys a spectral gap inequality with high
probability:

######  Theorem 3.2.

For every $d,\beta>0$ and $0<\varepsilon_{d}<1/d$, there exist
$\epsilon,K,\kappa$ such that if we consider the RFIM on $\Lambda$ with
external field $h$ such that $(|h_{x}|)_{x\in\Lambda}$ are i.i.d., with
${\mathbb{P}}(|h_{x}|\leq K)\leq\epsilon$, then for all $L\geq\kappa\log N$,

$\displaystyle\text{\tt{gap}}_{\Lambda}^{-1}\leq e^{L^{1-\varepsilon_{d}}}\,.$

with probability at least $1-e^{-L}$.

###### Proof of Theorem 3.1.

First as per Proposition 2.1, the external field of the RFIM measure $\nu_{T}$
is $y_{T}+h\stackrel{{\scriptstyle d}}{{=}}T\sigma^{*}+B_{T}+h$, where
$\sigma^{*}\sim\nu_{0}=\mu_{\Lambda}$, and $(B_{t})$ is an independent
standard Brownian motion. Since $\sigma^{*}$ is a binary vector and the
distribution of $h$ is symmetric, the vector of magnitudes $|y_{T}+h|$ (with
absolute value applied entrywise) is distributed as $|T+B_{T}+h|$ and hence
has independent coordinates. Next, let $\epsilon,K,\kappa$ as in Theorem 3.2.
Letting $Z\sim N(0,1)$, we have for any $H>0$,

${\mathbb{P}}\big{(}|T+\sqrt{T}Z+h_{x}|\leq
K\big{)}\leq{\mathbb{P}}\big{(}|T+\sqrt{T}Z|\leq
K+H\big{)}+{\mathbb{P}}\big{(}|h_{x}|\geq H\big{)}\,.$

We choose $H$ and $T$ large enough so that the above is smaller than
$\epsilon$. By Theorem 3.2, for all $L\geq\kappa\log N$ the following Poincaré
inequality holds with probability at least $1-e^{-L}$:

$\mathrm{Var}_{\nu_{T}}(\varphi)\leq
e^{L^{1-\varepsilon_{d}}}\mathcal{E}_{\nu_{T}}(\varphi,\varphi)\,,~{}~{}~{}~{}\mbox{for
all }\varphi:\\{-1,+1\\}^{\Lambda}\to{\mathbb{R}}\,.$ (3.10)

Now let $E_{L}$ denote the event “Eq. (3.10) holds” for some $L\geq\kappa\log
N$ to be chosen later. By Markov’s inequality,
${\mathbb{P}}(E_{L}^{c}\,|\,h)\leq e^{-L}/\delta$ with
${\mathbb{P}}_{h}$-probability at least $1-\delta$. Then with the same
probability it holds that for any $\varphi$ possibly depending on $h$ but not
on $y_{T}$,

$\displaystyle{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{T}}(\varphi)\,|\,h\big{]}$
$\displaystyle\leq
e^{L^{1-\varepsilon_{d}}}\,{\mathbb{E}}\big{[}\mathcal{E}_{\nu_{T}}(\varphi,\varphi)\mathbf{1}_{E_{L}}\,|\,h\big{]}+{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{T}}(\varphi)\mathbf{1}_{E_{L}^{c}}\,|\,h\big{]}$
$\displaystyle\leq
e^{L^{1-\varepsilon_{d}}}\,\mathcal{E}_{\nu_{0}}(\varphi,\varphi)+\delta^{-1}e^{-L}\mathrm{osc}(\varphi)\,.$
(3.11)

The last inequality follows from
$\mathrm{Var}_{\nu_{T}}(\varphi)\leq\mathrm{osc}(\varphi)$ and the fact that
$t\mapsto\mathcal{E}_{\nu_{t}}(\varphi,\varphi)$ is a super-martingale (see
[24, Lemma 9]). Next, let us assume that

$\mathcal{E}_{\nu_{0}}(\varphi,\varphi)\leq
N^{-\kappa}\mathrm{osc}(\varphi)\,,$ (3.12)

since otherwise,

$\mathrm{Var}_{\nu_{0}}(\varphi)\leq\mathrm{osc}(\varphi)\leq
N^{\kappa}\,\mathcal{E}_{\nu_{0}}(\varphi,\varphi)\,,$ (3.13)

and we are done. We then choose

$L=\log\left(\frac{\mathrm{osc}(\varphi)}{\delta\mathcal{E}_{\nu_{0}}(\varphi,\varphi)}\right)\geq\kappa\log
N\,.$

Since for any $\varepsilon>0$,

$e^{L^{1-\varepsilon_{d}}}\leq\left(\frac{\mathrm{osc}(\varphi)}{\delta\mathcal{E}_{\nu_{0}}(\varphi,\varphi)}\right)^{\varepsilon}\,,$

provided $N\geq N_{0}$ for some $N_{0}=N_{0}(d,\varepsilon)$, Eq. (3.11)
implies

$\displaystyle{\mathbb{E}}\big{[}\mathrm{Var}_{\nu_{T}}(\varphi)\,|\,h\big{]}$
$\displaystyle\leq\delta^{-\varepsilon}\mathcal{E}_{\nu_{0}}(\varphi,\varphi)^{1-\varepsilon}\Phi(\varphi)^{\varepsilon}+\mathcal{E}_{\nu_{0}}(\varphi,\varphi)$
$\displaystyle\leq\big{(}\delta^{-\varepsilon}+N^{-\kappa\varepsilon}\big{)}\,\mathcal{E}_{\nu_{0}}(\varphi,\varphi)^{1-\varepsilon}\mathrm{osc}(\varphi)^{\varepsilon}\,,$

where the last line follows from (3.12). Combining the above with the weak
approximate variance conservation bound of Theorem 3.1 we obtain with
${\mathbb{P}}_{h}$-probability at least $1-2\delta$, for all
$\varphi:\\{-1,+1\\}^{\Lambda}\to{\mathbb{R}}$,

$\mathrm{Var}_{\nu_{0}}(\varphi)\leq
K\big{(}\delta^{-\varepsilon}+N^{-\kappa\varepsilon}\big{)}^{1/p}(N/\delta)^{1/q}\,\mathcal{E}_{\nu_{0}}(\varphi,\varphi)^{(1-\varepsilon)/p}\cdot\mathrm{osc}(\varphi)^{\varepsilon/p+1/q}\,,$
(3.14)

where $p=e^{2T/c_{0}}$, $1/p+1/q=1$, and $K=e^{-c_{0}/(2q)}$. We ignore the
term $N^{-\kappa\varepsilon}$ and take $p^{\prime}=(1-\varepsilon)/p$,
$1/q^{\prime}=\varepsilon/p+1/q$. We obtain the desired conclusion by
combining Eq. (3.13) with Eq. (3.14) into one statement and adjusting the
constant $\kappa$. ∎

###  3.3 Algebraic decay and construction of the sampling algorithm

In this section we prove Theorems 1.2 and Theorem 1.4.

####  3.3.1 Algebraic decay and mixing from warm start

###### Proof of Theorem 1.2.

The algebraic decay is a direct consequence of the weak PI as shown in the
paper of Liggett [42]. We reproduce the argument here for completeness. From
Theorem 3.1 (applied to $\Lambda=\Lambda_{n}$) we have with
${\mathbb{P}}_{h}$-probability $1-\delta$,

$\mathrm{Var}_{\mu_{\Lambda}}(\varphi)\leq
A\,\mathcal{E}_{\mu_{\Lambda}}(\varphi,\varphi)^{1/p}\cdot\mathrm{osc}(\varphi)^{1/q}\,,$
(3.15)

for all $\varphi$, with $A=K\delta^{-1/q}N^{\kappa}$. Recalling that $P_{t}$
is the Markov semigroup of continuous-time Glauber dynamics, we have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\mathrm{Var}_{\mu_{\Lambda}}(P_{t}\varphi)$
$\displaystyle=-2\mathcal{E}_{\mu_{\Lambda}}(P_{t}\varphi,P_{t}\varphi)$
$\displaystyle\leq-2\frac{\mathrm{Var}_{\mu_{\Lambda}}(P_{t}\varphi)^{p}}{A^{p}\mathrm{osc}(P_{t}\varphi)^{p/q}}$
$\displaystyle\leq-2\frac{\mathrm{Var}_{\mu_{\Lambda}}(P_{t}\varphi)^{p}}{A^{p}\mathrm{osc}(\varphi)^{p/q}}\,,$

since $\mathrm{osc}(P_{t}\varphi)\leq\mathrm{osc}(\varphi)$. Equivalently,

$\frac{\mathrm{d}}{\mathrm{d}t}\mathrm{Var}_{\mu_{\Lambda}}(P_{t}\varphi)^{1-p}\geq\frac{2(p-1)}{A^{p}\mathrm{osc}(\varphi)^{p/q}}\,.$

By integrating we find for all $t>0$,

$\displaystyle\mathrm{Var}_{\mu_{\Lambda}}(P_{t}\varphi)$
$\displaystyle\leq\frac{\mathrm{Var}_{\mu_{\Lambda}}(\varphi)}{\Big{(}1+2(p-1)t\mathrm{Var}_{\mu_{\Lambda}}(\varphi)^{p-1}/A^{p}\mathrm{osc}(\varphi)^{p/q}\Big{)}^{1/(p-1)}}$
(3.16)
$\displaystyle\leq\frac{A^{q}\mathrm{osc}(\varphi)}{(2(p-1)t)^{1/(p-1)}}\,.$

Recalling $A=K\delta^{-1/q}N^{\kappa}$ this yields Eq. (1.6) of Theorem 1.2. ∎

##### Mixing from a warm start

Next, as a preliminary to the construction of the sampling algorithm we first
show that the weak PI (3.15) implies polynomial time mixing from a _warm
start_. Let us apply Eq. (3.15) to the indicator function
$\varphi=\mathbf{1}_{S}$, $S\subset\\{-1,+1\\}^{\Lambda}$:

$\mu_{\Lambda}(S)(1-\mu_{\Lambda}(S))\leq AQ(S,S^{c})^{1/p}\,,$ (3.17)

where $Q(S,S^{c})=\sum_{x\in S,y\in S^{c}}\mu_{\Lambda}(x)P(x,y)$, and $P$ is
the transition matrix of Glauber dynamics. Note that the inequality (3.17) is
a statement of large set expansion: it is a conductance bound which is most
effective when $\mu_{\Lambda}(S)$ is neither too small nor too close to 1.

For ease of notation in this subsection, let $(\sigma_{k})_{k\geq 0}$ be the
discrete-time Markov chain of Glauber dynamics, and let $\pi_{k}$ be the
distribution of $\sigma_{k}$ with $\pi_{\infty}=\mu_{\Lambda}$.

######  Lemma 3.3.

Suppose $\pi_{\infty}$ satisfies the weak conductance bound

$\pi_{\infty}(S)(1-\pi_{\infty}(S))\leq
AQ(S,S^{c})^{1/p}\,,~{}~{}~{}\forall~{}S\subseteq\\{-1,+1\\}^{\Lambda}\,,$
(3.18)

with $p\geq 1$, $A^{p}\geq 2/4^{p-1}$, and we further assume a warm start
condition for the chain:

$\max_{S\subseteq\\{-1,+1\\}^{\Lambda}}\frac{\pi_{0}(S)}{\pi_{\infty}(S)}\leq
M\,,$ (3.19)

for some $M>0$. Then

$d_{\mbox{\rm\tiny TV}}\big{(}\pi_{k},\pi_{\infty}\big{)}\leq
M\left(\frac{A^{2p}\log k}{k}\right)^{1/(2p-1)}\,,~{}~{}~{}k\geq 1\,.$ (3.20)

Before starting the proof let us remark that in our application of the above
Lemma, $A=K\delta^{-1/q}N^{\kappa}$ for which (3.17) holds from (3.15). We may
assume that the condition imposed on $A$ is satisfied provided $N$ is large
enough or $\delta$ is small enough.

###### Proof.

We follow an approach of Lovasz and Simonovits [43]. We consider the function

$h_{k}(x)=\sup_{g}\int_{\\{-1,+1\\}^{\Lambda}}g\mathrm{d}\pi_{k}-x\,,~{}~{}~{}x\in[0,1]\,,$

where the supremum is taken with respect to all measurable functions
$g:\\{-1,+1\\}^{\Lambda}\to[0,1]$ such that $\int g\mathrm{d}\pi_{\infty}=x$.
We observe that

$d_{\mbox{\rm\tiny TV}}\big{(}\pi_{k},\pi_{\infty}\big{)}=\max_{x}h_{k}(x)\,.$
(3.21)

A straightforward adaptation of Lemma 1.3 in [43] which uses the bound (3.18)
states the following recursion:

$h_{k}(x)\leq\frac{1}{2}\Big{[}h_{k-1}\big{(}x-2(A^{-1}x(1-x))^{p}\big{)}+h_{k-1}\big{(}x+2(A^{-1}x(1-x))^{p}\big{)}\Big{]}\,,~{}~{}~{}k\geq
1\,,$ (3.22)

valid for all $x$ such that the arguments in the above display are in $[0,1]$.
A sufficient condition for this to hold for all $x\in[0,1]$ is $A^{p}\geq
2/4^{p-1}$. By Eq. (3.19) we have $h_{0}(x)\leq Mx$. Since we also have
$h_{0}(x)\leq 1-x$ it follows that

$h_{0}(x)\leq\sqrt{Mx(1-x)}\,.$

Using this we have

$\displaystyle h_{0}\big{(}x-2(A^{-1}x(1-x))^{p}\big{)}^{2}$
$\displaystyle\leq
Mx(1-x)\big{(}1-2A^{-p}x^{p-1}(1-x)^{p}\big{)}\big{(}1+2A^{-p}x^{p}(1-x)^{p-1}\big{)}\,,$
$\displaystyle h_{0}\big{(}x+2(A^{-1}x(1-x))^{p}\big{)}^{2}$
$\displaystyle\leq
Mx(1-x)\big{(}1+2A^{-p}x^{p-1}(1-x)^{p}\big{)}\big{(}1-2A^{-p}x^{p}(1-x)^{p-1}\big{)}\,.$

With $a=2A^{-p}x^{p-1}(1-x)^{p}$ and $b=2A^{-p}x^{p}(1-x)^{p-1}$, the
recursion (3.22) implies the following bound on $h_{1}(x)$:

$\displaystyle h_{1}(x)$
$\displaystyle\leq\frac{1}{2}\sqrt{Mx(1-x)}\Big{(}\sqrt{(1-a)(1+b)}+\sqrt{(1+a)(1-b)}\Big{)}\,,$
$\displaystyle\leq\sqrt{Mx(1-x)}\sqrt{1-ab}\,,$
$\displaystyle=\sqrt{Mx(1-x)}\big{(}1-4A^{-2p}x^{2p-1}(1-x)^{2p-1}\big{)}^{1/2}\,,$

where the second line follows from Jensen’s inequality. Now assume that
$x(1-x)\geq r$ for some $r>0$. Then

$h_{1}(x)\leq\sqrt{Mx(1-x)}\big{(}1-4A^{-2p}r^{2p-1}\big{)}^{1/2}\,.$

By iterating this bound, if follows that

$\displaystyle h_{k}(x)$
$\displaystyle\leq\sqrt{Mx(1-x)}\big{(}1-4A^{-2p}r^{2p-1}\big{)}^{k/2}\,,$
$\displaystyle\leq\sqrt{M}e^{-2A^{-2p}r^{2p-1}k}\,,~{}~{}~{}k\geq 0\,.$

On the other hand we have the bound $h_{k}(x)\leq h_{0}(x)\leq Mx$ for all
$x$; indeed we have $h_{k+1}(x)=\sup_{g}\int Pg\mathrm{d}\pi_{k}-x\leq
h_{k}(x)$ since $Pg\in[0,1]$ and $\int Pg\mathrm{d}\pi_{\infty}=x$ since
$\pi_{\infty}$ is stationary for $P$. Now from Eq. (3.21) it follows that for
any $r\in(0,1)$,

$\displaystyle d_{\mbox{\rm\tiny TV}}\big{(}\pi_{k},\pi_{\infty}\big{)}$
$\displaystyle\leq\max\Big{\\{}\sqrt{M}e^{-2A^{-2p}r^{2p-1}k}\,,\,Mr\Big{\\}}$
$\displaystyle\leq\max\left\\{\frac{\sqrt{M}}{k}\,,\,M\left(\frac{A^{2p}\log
k}{2k}\right)^{1/(2p-1)}\right\\}\,,$

where the last line follows by taking $r^{2p-1}=(A^{2p}\log k)/(2k)$. ∎

####  3.3.2 A sampling algorithm under WSM

In this subsection we prove Theorem 1.4. We use the mixing result from a warm
start of the previous subsection to build a polynomial-time sampler from the
RFIM on $\Lambda_{n}$.

This sampler will proceed by building the sample up one vertex at a time. Fix
an enumeration $v_{1}=o,\cdots,v_{N}$ of the vertices of $\Lambda_{n}$ in such
a way that $\Lambda^{(i)}=\\{v_{j}\in\Lambda:j\leq i\\}\in\mathcal{Q}_{n}$
(recall that $\mathcal{Q}_{n}$ is the collection of ‘cube-like’ subsets
$B_{r}(o)\cup(\partial B_{r}(o)\cap A)$, with $r\leq n-1$ and
$A\subset{\mathbb{Z}}^{d}$.) This can be done by having the enumeration grow
layer by layer in a nucleation fashion, and such that $\Lambda^{(i)}$ is
always a union of at most $d$ cubes. The algorithm is as follows:

  1. 1.

Start with a perfect sample $X_{*}^{(1)}$ of the RFIM on a single origin
vertex $\Lambda^{(1)}=\\{v_{1}\\}$. ($X_{*}^{(1)}\in\\{-1,+1\\}$ is drawn with
probabilities proportional to $e^{\pm h_{v_{1}}}$.)

  2. 2.

For each $i\geq 2$, consider a Glauber dynamics chain $(X^{(i)}_{k})_{k\geq
0}$ on the RFIM measure $\mu_{\Lambda^{(i)}}$ on $\Lambda^{(i)}$ initialized
from
$X_{0}^{(i)}=[X_{*}^{(i-1)},\sigma_{v_{i}}]\in\\{-1,+1\\}^{\Lambda^{(i)}}$,
the concatenation of $X_{*}^{(i-1)}$ with a spin $\sigma_{v_{i}}\in\\{\pm
1\\}$ drawn independently with probabilities proportional to $e^{\pm
h_{v_{i}}}$.

  3. 3.

Run Glauber dynamics from this initialization for time $k_{*}=N^{C_{*}}$ to
obtain $X_{*}^{(i)}=X^{(i)}_{k_{*}}$.

The constant $C_{*}$ will be chosen subsequently, depending on the total
variation distance $\varepsilon$ and probability $\delta$ we are aiming for.

######  Proposition 3.4.

The sampling algorithm described by (1)–(3) above produces a sample that is
$\varepsilon$-close in total variation to $\mu_{\Lambda_{n}}$ with
${\mathbb{P}}_{h}$-probability $1-\delta$ and in time that is polynomial in
$N$. This can be achieved for any $\varepsilon,\delta\gtrsim
1/\textup{poly}(N)$.

###### Proof.

Fix $\Lambda_{n}$ as our target domain and $\varepsilon>0$ a target total-
variation distance. Our goal is to establish that as long as $C_{*}$ is a
large enough constant, the sampler described by (1)–(3) above yields

$\displaystyle d_{\mbox{\rm\tiny
TV}}\big{(}\pi^{(i)}_{k_{*}}\,,\,\mu_{\Lambda^{(i)}}\big{)}\leq\frac{i\varepsilon}{N}\,,~{}~{}~{}\mbox{for
all }1\leq i\leq N\,,$ (3.23)

where $\pi^{(i)}_{k}$ is the distribution of $X^{(i)}_{k}$ and
$k_{*}=N^{C_{*}}$ as described in the algorithm. Taking the final $i=N$ so
that $\Lambda^{(i)}=\Lambda_{n}$, we obtain $d_{\mbox{\rm\tiny
TV}}(\pi^{(N)}_{k_{*}},\mu_{\Lambda_{n}})\leq\varepsilon$. We prove this bound
inductively. For the base case, we are using a perfect sample from
$\mu_{\Lambda^{(1)}}$ so the bound trivially holds.

Let us assume the bound holds for $i-1$. Then $\pi_{0}^{(i)}$ is within total
variation distance $(i-1)\varepsilon/N$ from
$\mu_{\Lambda^{(i-1)}}\otimes\mu_{v_{i}}$, where $\mu_{v_{i}}(\sigma)\propto
e^{h_{v_{i}}\sigma}$. Coupling the Glauber dynamics realization $X^{(i)}_{k}$
initialized from $\pi_{0}^{(i)}$ with $Y^{(i)}_{k}$ initialized from
$\mu_{\Lambda^{(i-1)}}\otimes\mu_{v_{i}}$ by using the optimal total variation
coupling on the initializations $(X^{(i)}_{0},Y^{(i)}_{0})$, and then coupling
the dynamics with the identity coupling if $X^{(i)}_{0}=Y^{(i)}_{0}$, we
obtain

$\displaystyle d_{\mbox{\rm\tiny
TV}}\big{(}X^{(i)}_{k},\mu_{\Lambda^{(i)}}\big{)}\leq d_{\mbox{\rm\tiny
TV}}\big{(}X_{0}^{(i)},Y_{0}^{(i)}\big{)}+d_{\mbox{\rm\tiny
TV}}\big{(}Y_{k}^{(i)},\mu_{\Lambda^{(i)}}\big{)}\leq(i-1)\varepsilon/N+d_{\mbox{\rm\tiny
TV}}\big{(}Y_{k}^{(i)},\mu_{\Lambda^{(i)}}\big{)}\,.$ (3.24)

The distribution of $Y^{(i)}_{0}$, $\mu_{\Lambda^{(i-1)}}\otimes\mu_{v_{i}}$,
has Radon–Nikodym derivative to $\mu_{\Lambda^{(i)}}$ of at most
$M=e^{4d\beta}$ and thus satisfies the warm start condition (3.19) of Lemma
3.3 since the maximal change in energy from adding interactions between
$v_{i}$ and $\Lambda^{(i-1)}$ is $4d\beta$. Therefore Lemma 3.3 implies

$\displaystyle d_{\mbox{\rm\tiny
TV}}\big{(}Y^{(i)}_{k},\mu_{\Lambda^{(i)}}\big{)}\leq
M\Big{(}\frac{A_{i}^{2p}\log k}{k}\Big{)}^{1/(2p-1)}\,,$ (3.25)

with probability $1-\delta$, where
$A_{i}=K\delta^{-1/q}|\Lambda^{(i)}|^{\kappa}$ as per Theorem 3.1 applied to
$\Lambda^{(i)}$. By replacing $\delta$ by $\delta/N$ and applying a union
bound, the bound in Eq. (3.25) holds uniformly over $i$ with probability at
least $1-\delta$. By taking $k=N^{C_{*}}$ for $C_{*}$ sufficiently large, we
obtain $\max_{1\leq i\leq N}\,d_{\mbox{\rm\tiny
TV}}(Y^{(i)}_{k},\mu_{\Lambda^{(i)}})\leq\varepsilon/N$ under this event.
Combining with (3.24), we get the claimed bound of (3.23). ∎

##  4 Bound on the operator norm of the covariance matrix

This section is devoted to the proof of a tail bound on the operator norm of
the covariance matrix of $\nu_{t}$, Theorem 3.2. Fix
$\Lambda\subset{\mathbb{Z}}^{d}$ with volume $|\Lambda|=N$. Recall the
notation $A_{t}=\mathrm{Cov}(\nu_{t})$ where $(\nu_{t})_{t\geq 0}$ is the SL
process started at $\nu_{0}=\mu_{\Lambda}$; see Section 2.

We will rely on the observation that the correlation between the spins at $u$
and $v$ can be controlled by introducing a boundary separating the two
vertices. For a vertex $u\in\Lambda$ and an integer $\ell\geq 0$ we define

$\delta_{t}(u,\ell):=d_{\mbox{\rm\tiny
TV}}\Big{(}\nu_{t}\big{(}\sigma_{u}\in\cdot\,|\,\sigma_{\partial
B_{\ell}(u)}=+\big{)}\,,\,\nu_{t}\big{(}\sigma_{u}\in\cdot\,|\,\sigma_{\partial
B_{\ell}(u)}=-\big{)}\Big{)}\,,$ (4.1)

where we recall that $B_{\ell}(u)$ is the $\ell_{\infty}$-ball of radius
$\ell$ around $u$ in $\Lambda$. Let us define $\langle\,\cdot\,\rangle_{t}$ to
be the Gibbs average with respect to $\nu_{t}$ and

$\langle\sigma_{u};\sigma_{v}\rangle_{t}:=(\mathrm{Cov}(\nu_{t}))_{u,v}=\langle\sigma_{u}\sigma_{v}\rangle_{t}-\langle\sigma_{u}\rangle_{t}\langle\sigma_{v}\rangle_{t}\,,~{}~{}~{}u,v\in\Lambda\,.$

######  Lemma 4.1.

For all $u,v\in\Lambda$, $t\geq 0$ and integers $\ell\leq d_{\infty}(u,v)$ we
have

$0\leq\langle\sigma_{u};\sigma_{v}\rangle_{t}\leq\delta_{t}(u,\ell)\,.$

###### Proof.

The proof is standard and follows from monotonicity of the magnetization of
$\sigma_{u}$ with respect to the boundary condition (a consequence of the FKG
inequality) and the fact that $\partial B_{\ell}(u)$ separates $u$ from $v$ in
$\Lambda$. See e.g., [17, Corollary 1.3] for details. ∎

It follows from Lemma 4.1 that

$\mathrm{Tr}(A_{t}^{p})=\sum_{u_{1},\dots,u_{p}\in\Lambda}\prod_{i=1}^{p}\,\langle\sigma_{u_{i}};\sigma_{u_{i-1}}\rangle_{t}\leq\sum_{u_{1},\dots,u_{p}\in\Lambda_{n}}\prod_{i=1}^{p}\,\delta_{t}(u_{i},\ell_{i})\,,$
(4.2)

where $u_{0}=u_{1}$ and $\ell_{i}\leq d_{\infty}(u_{i},u_{i-1})$. Next we
control the expectation of the right-hand side in Eq. (4.2) uniformly in $t$
via the next proposition:

######  Proposition 4.2.

Fix $p\geq 1$, $t\geq 0$, a subset $A\subseteq[p]$ and a $p$-tuple of vertices
$u_{1},\cdots,u_{p}\in\Lambda$. For any sequence of integers $(\ell_{i})_{i\in
A}$ such that

$\displaystyle d_{\infty}(u_{i},u_{i-1})\geq\ell_{i}\,,~{}~{}~{}i\in
A\,,~{}~{}~{}\mbox{and}~{}~{}~{}~{}d_{\infty}(u_{i},u_{j})\geq
2(\ell_{i}+\ell_{j})\,,~{}~{}~{}i\neq j\in A\,,$ (4.3)

we have

${\mathbb{E}}\Big{[}\,\prod_{i\in
A}\delta_{t}(u_{i},\ell_{i})\,\Big{|}\,h\Big{]}\leq\prod_{i\in
A}\Big{(}\sum_{v\in
B_{\ell_{i}}(u_{i})}(1+\mathbf{1}_{v=u_{i}})\,\delta_{0}(v,\ell_{i})\Big{)}\,.$
(4.4)

It follows from Eq. (4.2) and Proposition 4.2 that

$\sup_{t\geq
0}\,{\mathbb{E}}\big{[}\mathrm{Tr}(A_{t}^{p})\,\big{|}\,h\big{]}\leq\Gamma(A,L)\,,$
(4.5)

where the quantity in the right-hand side is defined as follows: For a mapping
$A:(u_{1},\cdots,u_{p})\in\Lambda_{n}^{p}\mapsto
A(u_{1},\cdots,u_{p})\subseteq[p]$ from the set of $p$-tuples of vertices to
the subsets of $[p]$, and a mapping
$L:(u_{1},\cdots,u_{p})\in\Lambda_{n}^{p}\mapsto(\ell_{1},\cdots,\ell_{p})\in\mathbb{N}^{p}$,
$\ell_{i}=(L(u_{1},\cdots,u_{p}))_{i}$, $i\in[p]$, we let

$\Gamma(A,L):=\sum_{u_{1},\dots,u_{p}\in\Lambda}\,\prod_{i\in
A(u_{1},\cdots,u_{p})}\Big{(}\sum_{v\in
B_{\ell_{i}}(u_{i})}(1+\mathbf{1}_{v=u_{i}})\,\delta_{0}(v,\ell_{i})\Big{)}\,.$
(4.6)

######  Proposition 4.3.

Suppose the RFIM on $\Lambda$ satisfies $\text{\rm\small WSM}(C)$ for some
$C>0$. There exists two mappings $A$ and $L$ as defined above and satisfying
the conditions of Eq. (4.3), and a constant $C_{0}=C_{0}(d,C)$ such that

${\mathbb{E}}[\Gamma(A,L)]\leq C_{0}^{p}\,p!\,N\,.$ (4.7)

Theorem 3.2 follows immediately from Eq. (4.5) and Proposition 4.3. It remains
to prove Proposition 4.2 and Proposition 4.3. In the proof of Proposition 4.2
we crucially rely on a monotonicity property with respect to $t$ of the
expected total variations ${\mathbb{E}}[\delta_{t}(u,\ell)\,|\,h]$. More
precisely, the process $t\mapsto\delta_{t}(u,\ell)$ is a super-martingale. As
we will see, this is a consequence of the FKG inequality. We state and prove
the result in a slightly more general setting:

Let $G=(V,E)$ be a finite graph, and fix an arbitrary external field
$h=(h_{u})_{u\in V}$. We let

$\mu(\sigma)\propto\exp\Big{(}\sum_{(u,v)\in
E}J_{uv}\sigma_{u}\sigma_{v}+\sum_{u\in V}h_{u}\sigma_{u}\Big{)}\,,$

where $J_{uv}\geq 0$ for all $(u,v)\in E$. We make the dependence of the
external field explicit by writing $\langle\,\cdot\,\rangle_{h}$ as the Gibbs
average when the external field vector is $h$. Note that the Gibbs average
with respect to the corresponding stochastically localized measure is
$\langle\,\cdot\,\rangle_{h+y_{t}}$.

######  Lemma 4.4.

Consider an auxiliary field $g\in{\mathbb{R}}^{V}_{+}$ with nonnegative
entries, and consider averages of the form

$X^{\pm}_{t}:=\langle f(\sigma)\rangle_{y_{t}+h\pm g}\,,$ (4.8)

where $f:\\{-1,+1\\}^{V}\to{\mathbb{R}}$ is an increasing function. Then
$X^{+}$ is a super-martingale and $X^{-}$ is a sub-martingale.

In particular, letting $f(\sigma)=\sigma_{u}$ and $g_{u}=+\infty$ on the
boundary vertices and $g_{u}=0$ on the remaining vertices, we obtain

${\mathbb{E}}\big{[}\delta_{t}(u,\ell)\big{]}\leq\delta_{0}(u,\ell)\,.$ (4.9)

###### Proof.

We let

$\displaystyle\bar{w}_{t}(\sigma)$ $\displaystyle=\exp\Big{(}\sum_{(u,v)\in
E}J_{uv}\sigma_{u}\sigma_{v}+\sum_{u\in
V}(y_{t}+h+g)_{u}\,\sigma_{u}\Big{)}\,,$ $\displaystyle Z_{t}$
$\displaystyle=\sum_{\sigma\in\\{\pm
1\\}^{V}}\bar{w}_{t}(\sigma)\,,~{}~{}~{}\text{and}~{}~{}~{}w_{t}(\sigma)=\frac{1}{Z_{t}}\bar{w}_{t}(\sigma)\,.$

By Itô’s formula we have

$\mathrm{d}\bar{w}_{t}(\sigma)=\bar{w}_{t}(\sigma)\Big{(}\sigma^{\top}\mathrm{d}y_{t}+\frac{1}{2}\|\sigma\|^{2}\mathrm{d}t\Big{)}\,,$

and

$\displaystyle\mathrm{d}w_{t}(\sigma)$
$\displaystyle=\frac{\mathrm{d}\bar{w}_{t}(\sigma)}{Z_{t}}+\bar{w}_{t}(\sigma)\mathrm{d}Z_{t}^{-1}+\mathrm{d}[\bar{w}_{t},Z_{t}^{-1}]\,,$
$\displaystyle\mathrm{d}Z_{t}^{-1}$
$\displaystyle=-\frac{\mathrm{d}Z_{t}}{Z_{t}^{2}}+\frac{\mathrm{d}[Z_{t}]}{Z_{t}^{3}}\,,~{}~{}~{}\mbox{and}~{}~{}~{}\mathrm{d}[\bar{w}_{t},Z_{t}^{-1}]=-\frac{\mathrm{d}[\bar{w}_{t},Z_{t}]}{Z_{t}^{2}}\,.$

Therefore,

$\displaystyle\mathrm{d}w_{t}(\sigma)$
$\displaystyle=w_{t}(\sigma)\Big{(}\sigma^{\top}\mathrm{d}y_{t}+\frac{n}{2}\mathrm{d}t-\sum_{\tau}w_{t}(\tau)(\tau^{\top}\mathrm{d}y_{t}+\frac{n}{2}\mathrm{d}t)+\Big{\|}\sum_{\tau}w_{t}(\tau)\tau\Big{\|}_{2}^{2}\mathrm{d}t-\sum_{\tau}w_{t}(\tau)\tau^{\top}\sigma\mathrm{d}t\Big{)}$
$\displaystyle=w_{t}(\sigma)\Big{(}\sigma-\sum_{\tau}w_{t}(\tau)\tau\Big{)}^{\top}\Big{(}\mathrm{d}y_{t}-\sum_{\tau}w_{t}(\tau)\tau\mathrm{d}t\Big{)}$
$\displaystyle=w_{t}(\sigma)\Big{(}\sigma-\langle\sigma\rangle_{y_{t}+h+g}\Big{)}^{\top}\Big{(}\langle\sigma\rangle_{y_{t}+h}-\langle\sigma\rangle_{y_{t}+h+g}\Big{)}\mathrm{d}t+w_{t}(\sigma)\Big{(}\sigma-\sum_{\tau}w_{t}(\tau)\tau\Big{)}^{\top}\mathrm{d}B_{t}\,,$

where the last line plugged in (2.4) for $\mathrm{d}y_{t}$. So we obtain

$\mathrm{d}X^{+}_{t}=\Big{(}\langle
f(\sigma);\sigma\rangle_{y_{t}+h+g}\Big{)}^{\top}\Big{(}\langle\sigma\rangle_{y_{t}+h}-\langle\sigma\rangle_{y_{t}+h+g}\Big{)}\mathrm{d}t+b_{t}^{\top}\mathrm{d}B_{t}\,,$

where we recall that $\langle f;g\rangle=\langle fg\rangle-\langle
f\rangle\langle g\rangle$, and $b_{t}$ is some random vector in
${\mathbb{R}}^{V}$.

By the FKG inequality, since $g$ has nonnegative entries,
$\langle\sigma\rangle_{y_{t}+h}\leq\langle\sigma\rangle_{y_{t}+h+g}$ entrywise
and $\langle f(\sigma);\sigma\rangle_{y_{t}+h+g}\geq 0$ entrywise since $f$ is
increasing. We conclude that the drift term in the above equation is
nonpositive and therefore that $X^{+}_{t}$ is a super-martingale.

Replacing $g$ by $-g$ in the above does not affect the positivity of the
correlation $\langle f(\sigma);\sigma\rangle_{y_{t}+h-g}$, but the vector
$\langle\sigma\rangle_{y_{t}+h}-\langle\sigma\rangle_{y_{t}+h-g}$ is now
nonnegative. Therefore $X^{-}_{t}$ is a sub-martingale. ∎

Before turning to the proof of Proposition 4.2 we first state the following
simple lemma.

######  Lemma 4.5.

Consider two subsets of vertices $\Delta\subset\Delta^{\prime}\subseteq V$,

$\displaystyle d_{\mbox{\rm\tiny
TV}}\big{(}\mu(\sigma_{\Delta}\in\,\cdot\,|\,\sigma_{\partial\Delta^{\prime}}=+),$
$\displaystyle\mu(\sigma_{\Delta}\in\,\cdot\,|\,\sigma_{\partial\Delta^{\prime}}=-)\big{)}$
$\displaystyle\leq\sum_{v\in\Delta}d_{\mbox{\rm\tiny
TV}}\big{(}\mu(\sigma_{v}\in\,\cdot\,|\,\sigma_{\partial\Delta^{\prime}}=+),\mu(\sigma_{v}\in\,\cdot\,|\,\sigma_{\partial\Delta^{\prime}}=-)\big{)}\,.$
(4.10)

###### Proof.

The upper bound follows immediately from the monotone coupling of the two
measures on the left-hand side and a union bound over the vertices of
$\Delta$. ∎

###### Proof of Proposition 4.2.

Fix $p\geq 1$, $t\geq 0$, a subset $A\subseteq[p]$ and a $p$-tuple of vertices
$u_{1},\cdots,u_{p}\in\Lambda$. Fix a sequence of integers satisfying
condition Eq. (4.3). Without loss of generality we assume
$A=\\{u_{1},\cdots,u_{q}\\}$, $q\leq p$. We peel the terms in the product
$\prod_{i\in A}\delta_{t}(u_{i},\ell_{i})$ one by one. We observe that the
random variable $\delta_{t}(u_{i},\ell_{i})$ is a measurable function of
$\\{(y_{t}+h)_{v}:v\in B_{\ell_{i}}(u_{i})\\}$. Furthermore as per Proposition
2.1, $y_{t}$ has the distribution of $t\sigma^{*}+B_{t}$ where
$\sigma^{*}\sim\nu_{0}$ and $(B_{t})$ is an independent standard Brownian
motion. We define

$X_{i}={\mathbb{E}}\big{[}\delta_{t}(u_{i},\ell_{i})\,\big{|}\,\sigma^{*},h\big{]}\,.$

(The expectation is with respect to $B_{t}$.) This is a measurable function of
$\big{\\{}\sigma^{*}_{v},h_{v}:v\in B_{\ell_{i}}(u_{i})\big{\\}}$. Since the
balls $B_{\ell_{i}}(u_{i})$ do not intersect, we have

${\mathbb{E}}\Big{[}\,\prod_{i=1}^{q}\delta_{t}(u_{i},\ell_{i})\,\big{|}\,h\Big{]}={\mathbb{E}}\Big{[}\,\prod_{i=1}^{q}X_{i}\,\big{|}\,h\Big{]}=\nu_{0}\Big{(}\prod_{i=1}^{q}X_{i}\Big{)}\,.$

Moreover, since $d(u_{1},u_{i})\geq 2\ell_{1}+\ell_{i}$,
$B_{2\ell_{1}}(u_{1})$ and $B_{\ell_{i}}(u_{i})$ are disjoint for all $i$,
therefore

$\displaystyle\nu_{0}\Big{(}\prod_{i=1}^{q}X_{i}\Big{)}-\nu_{0}\big{(}X_{1}\big{)}\cdot\nu_{0}\Big{(}\prod_{i=2}^{q}X_{i}\Big{)}$
$\displaystyle~{}~{}~{}=\nu_{0}\Big{(}\Big{(}\nu_{0}\big{(}X_{1}|\sigma_{\partial
B_{2\ell_{1}}(u_{1})}^{*}\big{)}-\nu_{0}(X_{1})\Big{)}\cdot\nu_{0}\Big{(}\prod_{i=2}^{q}X_{i}\,|\,\sigma_{\partial
B_{2\ell_{1}}(u_{1})}^{*}\Big{)}\Big{)}$
$\displaystyle~{}~{}~{}\leq\sup_{\tau,\tau^{\prime}}\Big{(}\nu_{0}\big{(}X_{1}|\sigma_{\partial
B_{2\ell_{1}}(u_{1})}^{*}=\tau\big{)}-\nu_{0}\big{(}X_{1}|\sigma_{\partial
B_{2\ell_{1}}(u_{1})}^{*}=\tau^{\prime}\big{)}\Big{)}\cdot\nu_{0}\Big{(}\prod_{i=2}^{q}X_{i}\Big{)}\,.$
(4.11)

Since $0\leq X_{1}\leq 1$ and by monotonicity with respect to the boundary
condition, the above supremum is bounded above by

$\displaystyle d_{\mbox{\rm\tiny
TV}}\Big{(}\nu_{0}\big{(}\sigma_{B(u_{1},\ell_{1})}^{*}\in\cdot\,|\,\sigma_{\partial
B_{2\ell_{1}}(u_{1})}^{*}=+\big{)},\nu_{0}\big{(}\sigma_{B(u_{1},\ell_{1})}^{*}\in\cdot\,|\,\sigma_{\partial
B_{2\ell_{1}}(u_{1})}^{*}=-\big{)}\Big{)}$
$\displaystyle~{}~{}~{}\leq\sum_{v\in B(u_{1},\ell_{1})}d_{\mbox{\rm\tiny
TV}}\Big{(}\nu_{0}\big{(}\sigma_{v}^{*}\in\cdot\,|\,\sigma_{\partial
B_{2\ell_{1}}(u_{1})}^{*}=+\big{)},\nu_{0}\big{(}\sigma_{v}^{*}\in\cdot\,|\,\sigma_{\partial
B_{2\ell_{1}}(u_{1})}^{*}=-\big{)}\Big{)}$
$\displaystyle~{}~{}~{}\leq\sum_{v\in
B(u_{1},\ell_{1})}\delta_{0}(v,\ell_{1})\,.$ (4.12)

The second line follows from Lemma 4.5, and the last line from the observation
that $B_{\ell_{1}}(v)\subseteq B_{2\ell_{1}}(u_{1})$. It follows from Eq. (4)
and Eq. (4) that

$\nu_{0}\Big{(}\prod_{i=1}^{q}X_{i}\Big{)}\leq\prod_{i=1}^{q}\Big{(}\nu_{0}\big{(}X_{i}\big{)}+\sum_{v\in
B_{\ell_{i}}(u_{i})}\delta_{0}(v,\ell_{i})\Big{)}\,.$

We conclude the proof by noting that
$\nu_{0}(X_{i})={\mathbb{E}}\big{[}\delta_{t}(u_{i},\ell_{i})\,|\,h\big{]}\leq\delta_{0}(u_{i},\ell_{i})$
by Lemma 4.4. ∎

###### Proof of Proposition 4.3.

Assuming condition (4.3), the balls $B_{2\ell_{i}}(u_{i})$ are disjoint, and
therefore

$\displaystyle{\mathbb{E}}\big{[}\Gamma(A,L)\big{]}$
$\displaystyle=\sum_{u_{1},\dots,u_{p}\in\Lambda}\,\prod_{i\in
A(u_{1},\cdots,u_{p})}\Big{(}\sum_{v\in
B_{\ell_{i}}(u_{i})}(1+\mathbf{1}_{v=u_{i}})\,{\mathbb{E}}\big{[}\delta_{0}(v,\ell_{i})\big{]}\Big{)}$
$\displaystyle\leq\sum_{u_{1},\dots,u_{p}\in\Lambda}\,\prod_{i\in
A(u_{1},\cdots,u_{p})}\big{(}2C\,\ell_{i}^{d}\,e^{-\ell_{i}/C}\big{)}\,,$

where we used $\text{\rm\small WSM}(C)$ to obtain the last line. Next we build
the maps $A$ and $L$. For a sequence of points $u_{1},\dots,u_{p}\in\Lambda$
and a set $I\subseteq\\{1,\cdots,p\\}$ we define

$\ell_{i}(I):=\frac{1}{4}\min_{j\in\\{i-1\\}\cup
I\setminus\\{i\\}}d_{\infty}(u_{i},u_{j})\,,~{}~{}~{}~{}i\in[p]\,.$ (4.13)

Next we define for all $i\in[p]$,

$\displaystyle r_{i}=r_{i}(u_{1},...,u_{p})$
$\displaystyle:=\frac{1}{4}\min_{j<i}\,d_{\infty}(u_{i},u_{j})\,,$
$\displaystyle\mbox{and}~{}~{}J_{i}=J_{i}(u_{1},...,u_{p})$
$\displaystyle:=\text{argmin}_{j<i}\,\,d_{\infty}(u_{i},u_{j})\,.$

Now, define the set of indices that are relatively close

$Q_{k}=Q_{k}(u_{1},...,u_{p}):=\big{\\{}i\in[p]\,:~{}r_{i}\in[2^{k},2^{k+1}-1]\big{\\}}\,,~{}~{}~{}k\geq
0\,,$

and let

$k_{*}=k_{*}(u_{1},...u_{p}):=\mathrm{argmax}_{k}\,|Q_{k}|2^{k}\,.$

Finally, let

$A(u_{1},...,u_{p}):=Q_{k_{*}}\,,~{}~{}~{}\mbox{and}~{}~{}~{}\ell_{i}(u_{1},...,u_{p}):=\ell_{i}(A(u_{1},...,u_{p}))\,.$
(4.14)

With these definitions, conditions (4.3) are satisfied:
$d_{\infty}(u_{i},u_{i-1})\geq\ell_{i}$ and $d_{\infty}(u_{i},u_{j})\geq
2(\ell_{i}+\ell_{j})$ for all $i,j\in Q_{k_{*}}$, $i\neq j$. Next we claim
that

$\sum_{u_{1},\dots,u_{p}\in\Lambda_{n}}\prod_{i\in
A}2C\ell_{i}^{d}e^{-\ell_{i}/C}\leq C_{0}^{p}np!\,,$ (4.15)

where $C_{0}$ is only a function of $d$ and $C$, and we wrote $A$ and
$\ell_{i}$ for brevity. The key idea about the above definitions is that

$\ell_{i}\geq\frac{1}{2}r_{i}\,,~{}~{}\forall i\in Q_{k_{*}}\,.$ (4.16)

Indeed, suppose $\ell_{i}<\frac{1}{2}r_{i}$. Then there exists $j\in
Q_{k_{*}}$, $j>i$ such that $d_{\infty}(u_{i},u_{j})\leq\frac{1}{2}r_{i}$.
Since $j\in Q_{k_{*}}$, $r_{j}$ is on the order of $r_{i}$; in particular
$r_{j}\geq\frac{1}{2}r_{i}$. But $r_{j}\leq d_{\infty}(u_{i},u_{j})$, which
leads to a contradiction. Therefore

$\displaystyle\prod_{i\in Q_{k_{*}}}2C\ell_{i}^{d}e^{-\ell_{i}/C}\leq
c^{p}\prod_{i\in Q_{k_{*}}}e^{-\ell_{i}/2C}\leq c^{p}\,e^{-\sum_{i\in
Q_{k_{*}}}r_{i}/4C}\,,$ (4.17)

where $c=(2C)^{p}\max_{x>0}x^{d}e^{-x/2C}$, and we used (4.16) in the second
inequality. Now we claim that $\sum_{i\in Q_{k_{*}}}r_{i}\geq
c_{0}\sum_{i\in[p]}\sqrt{r_{i}}$ for some absolute constant $c_{0}>0$. Indeed,

$\displaystyle\sum_{i\in[p]}\sqrt{r_{i}}$ $\displaystyle=\sum_{k\geq
0}\sum_{i\in Q_{k}}\sqrt{r_{i}}\leq\sum_{k\geq 0}2^{-k/2}\sum_{i\in
Q_{k}}r_{i}$ $\displaystyle\leq\Big{(}\sum_{k\geq
0}2^{-k/2}\Big{)}\,\max_{k}\,\sum_{i\in Q_{k}}r_{i}\,,$

and

$\displaystyle\max_{k}\,\sum_{i\in Q_{k}}r_{i}$
$\displaystyle\leq\max_{k}2^{k+1}|Q_{k}|=2^{k_{*}+1}|Q_{k_{*}}|\leq
2\sum_{i\in Q_{k_{*}}}r_{i}\,.$

Plugging this to the display (4.17) yields

${\mathbb{E}}\big{[}\Gamma(A,L)\big{]}\leq
C_{0}^{p}\sum_{u_{1},\dots,u_{p}\in\Lambda}\,\prod_{i=1}^{p}e^{-c_{0}\sqrt{r_{i}}}\,,$
(4.18)

for some $C_{0},c_{0}>0$ depending on $d,C$. Now, there are $p!$ options for
the choice of $J_{i}$’s. Given the $J_{i}$’s and the different choices for
$r_{i}$, there are $|\Lambda|\prod_{i\in p}r_{i}^{d-1}$ different
configurations. (We determine the position of $u_{1}$ and then given $r_{i}$
and $J_{i}$, the point $u_{i}$ is on the boundary of $B_{r_{i}}(u_{J_{i}})$.
Notice that by construction $J_{i}<i$ which means that those offsets determine
the entire configuration.) All in all, the right-hand side of (4.18) is
bounded by

$C_{0}^{p}\,|\Lambda|\,p!\sum_{r_{1},...,r_{p}\in\mathbb{N}}\prod_{i\in[p]}r_{i}^{d-1}e^{-c\sqrt{r_{i}}}=C_{0}^{p}\Big{(}\sum_{r=0}^{\infty}r^{d-1}e^{-c\sqrt{r}}\Big{)}^{p}p!\,|\Lambda|\,,$

concluding the proof. ∎

##  5 Fast mixing with large variance fields or SSM

Our aim in this section is to show that in either of the following situations:

  1. a.

a RFIM with sufficiently anti-concentrated external field, whose absolute
values are independent (though the signs are not necessarily independent),

  2. b.

a RFIM satisfying $\text{\rm\small SSM}(C)$ in expectation (per Definition
1.5) with independent fields,

has $N^{o(1)}$ mixing time and inverse spectral gap. The first of these proves
Theorem 3.2, thereby concluding the missing step from the proof of Theorem
1.2, and the second proves Theorem 1.6.

These two proofs follow a very similar strategy based on coarse-graining the
lattice into blocks where the field is good, and a sub-critical set of blocks
where the field is bad, and we therefore present them together. In particular,
most of the steps in the proofs are identical, and in the instances they are
different, we present proofs for each situation.

The formal assumption for (a) above of a sufficiently anti-concentrated field
with independent absolute values is the following:

######  Assumption 5.1.

Let $K$ be such that

$\displaystyle\rho=\rho(\beta,d,K):=\frac{e^{2d\beta-K}}{e^{2d\beta-K}+e^{-2d\beta+K}}\,,$
(5.1)

is less than $1/40d$, say. Suppose that the RFIM with external field
$(h_{x})_{x\in\Lambda}$ is such that $(|h_{x}|)_{x}$ are i.i.d. (their signs
may be dependent), and such that

$\displaystyle\mathbb{P}_{h}(|h_{x}|\leq K)<\tfrac{1}{40d}\,.$

We will prove the following theorem that includes in it both Theorem 3.2 and
Theorem 1.6.

######  Theorem 5.1.

Suppose $\beta,d$ and $\mathbb{P}_{h}$ are such that one of Assumption 5.1 or
Assumption 1.5 holds. There exist $\kappa=\kappa(d,\beta,C)>0$ and
$C_{d,\beta}>0$ such that for every $L\geq\kappa\log n$, the RFIM Glauber
dynamics on $\Lambda\in\mathcal{Q}_{n}$ satisfies

$\displaystyle\mathbb{P}_{h}\Big{(}\text{\tt{gap}}_{\Lambda}^{-1}\geq
e^{C_{d,\beta}L^{\frac{d-1}{d}}(\log L)^{d-1}}\Big{)}\leq e^{-L}\,.$

Making the choice $L=\kappa\log n$, this gives that
$\text{\tt{gap}}_{\Lambda_{n}}^{-1}\leq n^{o(1)}$ except with probability
$n^{-\kappa}$.

For readability, we will prove this for $\Lambda=\Lambda_{n}$. It can easily
be checked that the addition of some boundary vertices can be handled in the
obvious manners.

###  5.1 The coarse graining

We begin with a coarse graining of the external field, to split it into good
regions where the field is fairly large in a coarse sense (depending on which
of Assumptions 5.1 or 1.5 are used) and exponential decay of correlations
strongly holds, and regions where the field is not large enough for the
exponential decay of correlations to hold.

To coarse-grain $\Lambda_{n}$, we take a large $R$ (which we will later take
to be $\approx\log L$) and consider $\Lambda_{n}^{(R)}=\Lambda_{n}\cap
R\mathbb{Z}^{d}$. For every vertex $v\in\Lambda_{n}^{(R)}$, let
$B_{v}=B_{R}(v)$ be the $\ell^{\infty}$-ball of radius $R$ (side-length $2R$)
in $\Lambda_{n}$ centered at $v$.

The coarse-grained percolation process is an $|h|$-measurable, or
$h$-measurable (depending on which assumption we are taking), percolation
process on $\Lambda_{n}^{(R)}$ consisting of assignments of
$\\{\mathsf{Good},\mathsf{Bad}\\}$ to $\Lambda_{n}^{(R)}$.

####  5.1.1 Good blocks of the coarse graining

Here, we define the properties of $|h|$ or $h$ that make a block
$v\in\Lambda_{n}^{(R)}$ be $\mathsf{Good}$. There will be two different
definitions for the two assumptions.

When under Assumption 5.1, the coarse-grained percolation process is defined
as follows.

######  Definition 5.2.

For any fixed realization of $|h|$ (and thus of $\omega^{h}$), let
$\omega_{x}^{h}=\mathbf{1}_{|h_{x}|\leq K}$ and let
$\eta=(\eta_{x})_{x\in\Lambda_{n}}$ be i.i.d. $\text{Ber}(\rho)$ from (5.1).
Finally, let $\omega^{\mathsf{i}}_{x}=\omega_{x}^{h}\vee\eta_{x}$ for each
$x\in\Lambda_{n}$.

A vertex $v\in\Lambda_{n}^{(R)}$ is called $\mathsf{Good}$ if for every $w\in
B_{v}$, for every $(\log R)^{2}\leq r\leq R/8$,

$\displaystyle\mathbb{P}(|\mathcal{C}_{w}(\omega^{\mathsf{i}})|\geq
r\mid\omega^{h})\leq e^{-r}\,.$

where we use $\mathcal{C}_{w}(\omega^{\mathsf{i}})$ for the connected
component of $w$ in $\omega^{\mathsf{i}}$. If $v\in\Lambda_{n}^{(R)}$ is not
$\mathsf{Good}$, it is $\mathsf{Bad}$.

When under Assumption 1.5, the coarse-grained percolation process is defined
as follows.

######  Definition 5.3.

For any fixed realization of $h$, a vertex $v\in\Lambda_{n}^{(R)}$ is called
$\mathsf{Good}$ if for every $w\in B_{v}$, for every $(\log R)^{2}\leq\ell\leq
2r\leq R/4$,

$\displaystyle\max_{B\in
B_{r}(w)+\\{-r+1,...,r-1\\}^{d}}\max_{\begin{subarray}{c}z\in\partial B\\\
d(w,z)=\ell\end{subarray}}\max_{\eta\in\\{\pm 1\\}^{\partial B\setminus
z}}d_{\mbox{\rm\tiny
TV}}\big{(}\mu_{B}^{\eta^{+}}(\sigma_{w}),\mu_{B}^{\eta^{-}}(\sigma_{w})\big{)}\leq
e^{-\ell/C_{*}}\,.$ (5.2)

The vertex $v$ is called $\mathsf{Bad}$ otherwise.

In both situations, the $\mathsf{Good}$ blocks are those in which the
influence of a boundary condition, on a distance at least $(\log R)^{2}$
interior to the block is indeed exponentially small.

####  5.1.2 Dominating bad blocks by a sub-critical percolation process

The following lemmas show that by taking $R$ large, under their respective
assumptions, the probability of a vertex in $\Lambda_{n}^{(R)}$ being
$\mathsf{Bad}$ can be made arbitrarily small.

######  Lemma 5.4.

Under Assumption 5.1 and the corresponding Definition 5.2, if $R$ is at least
a $d$-dependent constant, then for every $v\in\Lambda_{n}^{(R)}$,

$\displaystyle\mathbb{P}_{h}(v\text{ is $\mathsf{Bad}$})\leq R^{-5}\,.$

###### Proof.

We first observe that under Assumption 5.1, the process
$(\omega^{\mathsf{i}}_{x})_{x}$ of Definition 5.2 is stochastically below an
independent Bernoulli percolation with parameter $1/(20d)$.

By standard percolation reasoning (comparison to a branching process with
offspring distribution $\text{Bin}(2d,1/(20d))$) for every $w\in\Lambda_{n}$,
and every $r\geq 1$,

$\displaystyle\mathbb{P}_{h}\otimes\mathbb{P}_{\eta}(|\mathcal{C}_{w}(\omega^{\mathsf{i}})|\geq
r)\leq e^{-2r}\,,$

where $\mathbb{P}_{\eta}$ is the law of the $\text{Ber}(1/(20d)$ process
$(\eta_{x})_{x}$. By Markov’s inequality, for every $w\in\Lambda_{n}$,

$\displaystyle\mathbb{P}_{h}\big{(}\\{h:\mathbb{P}_{\eta}(|\mathcal{C}_{w}(\omega^{\mathsf{i}})|\geq
r\mid h)\geq e^{-r}\\}\big{)}\leq e^{-r}\,.$

As such, for each $v\in\Lambda_{n}^{(R)}$, by a union bound,

$\displaystyle\mathbb{P}_{h}\big{(}h:\forall w\in B_{v}\,,\,\forall(\log
R)^{2}\leq r\leq
R/8\,,\,\mathbb{P}_{\eta}(|\mathcal{C}_{w}(\omega^{\mathsf{i}})|\geq r\mid
h)\leq e^{-r}\big{)}\geq 1-(2R)^{d}\sum_{r=(\log R)^{2}}^{R/8}e^{-r}\,.$

In particular, we get that for $R$ larger than a fixed constant,
$\mathbb{P}_{h}(v\text{ is }\mathsf{Good})\geq 1-R^{-5}$. ∎

######  Lemma 5.5.

If $\text{\rm\small SSM}(C)$ holds per Definition 1.5, with the corresponding
Definition 5.3, there exists $C_{*}(d,C),R_{0}(d,C)$ such that for all $R\geq
R_{0}$, for every $v\in\Lambda_{n}^{(R)}$,

$\displaystyle\mathbb{P}_{h}(v\text{ is $\mathsf{Bad}$})\leq R^{-5}\,.$

###### Proof.

For each fixed $w\in B_{v}$, $(\log R)^{2}\leq\ell\leq r\leq R/8$, $B\in
B_{r}(w)+\\{-r+1,...,r-1\\}^{d}$ and $z\in\partial B$ in (5.2) at distance
$\ell$ from $w$, let $A_{w,B,z}$ be the complement of the event in (5.2) i.e.,

$\\{\max_{\xi\in\\{\pm 1\\}^{\partial B\setminus z}}d_{\mbox{\rm\tiny
TV}}(\mu_{B,\xi^{+}}(\sigma_{w}),\mu_{B,\xi^{-}}(\sigma_{w}))>e^{-\ell/C_{*}}\\}\,.$

Then, the assumption of $\text{\rm\small SSM}(C)$ implies by Markov’s
inequality that

$\displaystyle\mathbb{P}(A_{w,B,z})\leq
e^{-\frac{\ell}{C}+\frac{\ell}{C_{*}}}\,,$

so that if $C_{*}=2C$, then this is at most $e^{-\ell/C_{*}}$. Noting that

$\displaystyle\\{v\text{ is $\mathsf{Bad}$}\\}\subset\bigcup_{w\in
B_{v}}\bigcup_{\ell,r=(\log
R)^{2}}^{R/8}\bigcup_{B}\bigcup_{\begin{subarray}{c}z\in\partial B\\\
d(z,w)=\ell\end{subarray}}A_{w,B,z}\,,$

a union bound implies

$\displaystyle\mathbb{P}(v\text{ is $\mathsf{Bad}$})\leq
R^{d}\cdot(R/8)\cdot\sum_{\ell\geq(\log
R)^{2}}(R/8)^{d}\ell^{d-1}e^{-\ell/C_{*}}\,.$

Evidently, as long as $R$ is a sufficiently large constant depending on
$C_{*}$ and $d$, the right-hand side is at most $R^{-5}$ (in fact, super-
polynomially small) as claimed. ∎

For a realization of $h$, inducing a configuration $\omega^{h}$, let
$\mathsf{Good}(h)$ be the subset of $\Lambda_{n}^{(R)}$ that are
$\mathsf{Good}$, and let $\mathsf{Bad}(h)$ be the subset of
$\Lambda_{n}^{(R)}$ that are $\mathsf{Bad}$. Note that under Assumption 5.1,
$\mathsf{Good}(h)$ is an $|h|$-measurable process on $\Lambda_{n}^{(R)}$ and
under $\text{\rm\small SSM}(C)$, it is an $h$-measurable process on
$\Lambda_{n}^{(R)}$. The states of different $v,w\in\Lambda_{n}^{(R)}$ are not
quite independent, but the following lemma says that in either case, the
$\mathsf{Bad}$ sites of $\Lambda_{n}^{(R)}$ are stochastically below a sub-
critical independent percolation on $\Lambda_{n}^{(R)}$.

######  Lemma 5.6.

For every $c>0$, under Assumption 5.1, there exists $R_{0}(c,d)$ such that for
all $R>R_{0}(c)$, under $\mathbb{P}_{h}$ the set
$\mathsf{Bad}(h)\subset\Lambda_{n}^{(R)}$ is stochastically below an
independent Bernoulli-$c$ percolation on $\Lambda_{n}^{(R)}$.

Under Assumption 1.5, there exists $R_{0}(C,c,d)$ such that the same
conclusion holds.

###### Proof.

Under Assumption 5.1, for every $v\in\Lambda_{n}^{(R)}$, its status as
$\mathsf{Good}$ versus $\mathsf{Bad}$ is measurable with respect to
$(|h_{x}|)_{x:d_{\infty}(x,v)\leq 5R/4}$, whence the percolation generated by
the $\mathsf{Bad}$ sites on $\Lambda_{n}^{(R)}$ is $2$-dependent, i.e., it is
independent of the status of all sites at $\Lambda_{n}^{(R)}$-distance at
least $3$ (here we are endowing $\Lambda_{n}^{(R)}$ with adjacency if vertices
are at $\mathbb{Z}^{d}$-distance $R$). By [41], for every $c>0$, there exists
$c^{\prime}(c,\Delta)>0$ such that any $2$-dependent percolation on a graph of
maximum degree $\Delta$ of parameter $c^{\prime}$ is stochastically below and
independent $c$-percolation. Therefore, by Lemma 5.4, if $R$ is sufficiently
large, the probability of a vertex being $\mathsf{Bad}$ is at most
$c^{\prime}$, whence the set of $\mathsf{Bad}$ vertices are stochastically
below an independent $c$-percolation.

Under Assumption 1.5, using Lemma 5.5, the reasoning is identical except that
it is now $(h_{x})_{x:d_{\infty}(x,v)\leq 5R/4}$ measurable, but at the same
time $(h_{x})_{x}$ is an independent process rather than just $(|h_{x}|)_{x}$.
∎

To conclude the discussion of the coarse-graining, let us introduce a few
notions for the geometry of the $R$-coarse-grained lattice.

######  Definition 5.7.

We say two sites in $\Lambda_{n}^{(R)}$ are $R$-adjacent if they are at
$\ell^{2}$-distance $R$ from one another. We say they are $R$-$*$-adjacent if
they are at $\ell^{\infty}$-distance $R$ from one another. Using these notions
of $R$-adjacency, for a subset of $\Lambda_{n}^{(R)}$, we can define its
$R$-clusters (maximal connected components via $R$-adjacency), and analogously
$R$-$*$-clusters. The important thing about these notions of adjacency is that
$R$-adjacency is “dual to” $R$-$*$-adjacency, in the sense that if $A$ is not
$R$-$*$-connected to $B$, then there is an $R$-cluster separating $A$ from $B$
and vice versa.

Let $\mathcal{C}^{(R)}_{w,\mathsf{Bad}}(\omega^{h})\subset\Lambda_{n}^{(R)}$
denote the $R$-$*$-connected component of $\mathsf{Bad}(h)$ containing $w$.
Notice that its $R$-$*$-outer-boundary will form an $R$-connected subset of
$\mathsf{Good}(h)$ surrounding $w$. Since the degree of $\Lambda_{n}^{(R)}$
under $R$-$*$-adjacency is $3^{d}$, by Lemma 5.6 with the choice of
$c=1/4^{d}$, say, and standard percolation reasoning, we obtain the following.

######  Corollary 5.8.

Under Assumption 5.1, there exists $\kappa(d),R_{0}(d)$ such that if $R\geq
R_{0}(d)$ and $L\geq\kappa\log n$,

$\displaystyle\mathbb{P}_{h}\Big{(}\max_{w\in\Lambda_{n}^{(R)}}|\mathcal{C}^{(R)}_{w,\mathsf{Bad}}(\omega^{h})|\geq
L\Big{)}\leq e^{-L}\,.$

The same holds under Assumption 1.5 of $\text{\rm\small SSM}(C)$ with the
constants depending on $C$ also.

###  5.2 Blocks for the block dynamics

We now define our candidate blocks for the block dynamics using the coarse
graining of the previous section. The choice of the blocks will itself be
random, depend on the realization $h$ through the realization of
$\mathsf{Good}(h)$ and $\mathsf{Bad}(h)$. The crux of the construction is the
fact that for any choice of $h$ such that
$\max_{w}|\mathcal{C}^{(R)}_{w,\mathsf{Bad}}(\omega^{h})|\leq L$, the
resulting choice of blocks satisfies:

  1. 1.

The volume of every block is at most $L^{1+o(1)}$, and in turn the mixing time
of Glauber dynamics on the block is sub-exponential in $L$ by isoperimetry
properties in $\mathbb{Z}^{d}$.

  2. 2.

The expected Hamming distance of an update on any block with two boundary
conditions that differ only at one site is at most $O((\log R)^{2})$.

  3. 3.

For every site $v\in\Lambda_{n}$, the number of blocks for which $v$ is on
their boundary divided by the number for which $v$ is in their interior is at
most $O(1/R)$.

In the next subsection, these three properties will be used in conjunction to
obtain the claimed mixing time bound of Theorem 5.1.

######  Definition 5.9.

Fix a realization of $\mathsf{Good}(h)$. The blocks
$\mathcal{B}=(\mathcal{B}_{i})_{i}$ are constructed as follows.

  * •

_Type 1 blocks_ : For each vertex $w\in\Lambda_{n}$ at distance at most $3R/4$
from an element of $\mathsf{Good}(h)$, include the $\ell^{\infty}$-ball of
radius $R/8$ in $\Lambda_{n}$ centered at $w$ as a block in $\mathcal{B}$.

  * •

_Type 2 blocks_ : For each distinct component $\mathcal{C}$ in
$\\{\mathcal{C}_{w,\mathsf{Bad}}^{(R)}(\omega^{h})\\}_{w\in\Lambda_{n}^{(R)}}$,
let $B_{\mathcal{C}}$ consist of all vertices at $\ell^{\infty}$-distance at
most $R$ from $\mathcal{C}$ and $\ell^{\infty}$-distance at least $R/2$ from
$\mathsf{Good}(h)$. Include all translates
$(B_{\mathcal{C}}+a)_{a\in\\{-\frac{R}{8},...,\frac{R}{8}\\}^{d}}$
(intersected with $\Lambda_{n}$) as blocks in $\mathcal{B}$.

######  Observation 5.10.

By construction, each $B_{\mathcal{C}}$ is exactly a union of cubes of side-
length $R$, one centered at each vertex $v\in\mathcal{C}$. From this we deduce
that type 2 blocks originating from some $\mathcal{C}$ and type 2 blocks
originating from some other $\mathcal{C}^{\prime}$ must be at least distance
$3R/4$ apart.

We now focus on verifying that the desired properties (1)–(3) hold for this
family of blocks.

_Property (1)_. The volume of a block clearly is at most a factor of $R$
larger than the largest volume of the bad clusters
$\mathcal{C}\in(\mathcal{C}_{w,\mathsf{Bad}}^{(R)}(\omega^{h}))_{w\in\Lambda_{n}^{(R)}}$.
If we allowed a worst-case mixing time of exponential in the volume per block,
the fact that we need to choose $R$ to be diverging as $\Omega(\log L)$ means
the mixing time of the worst block would be super-exponential in $L$, which
translates to super-polynomial in $n$. We therefore wish to leverage the
classical fact (dating back to canonical path arguments of [37]) that the
mixing time of a spin system on a graph is bounded by exponential in the cut-
width of the graph, while isoperimetry in $\mathbb{Z}^{d}$ guarantees that the
cut-width of any domain is sub-linear in its volume.

We appeal to the following mixing time bound for Ising Glauber dynamics on
general subsets of $\mathbb{Z}^{d}$ using this isoperimetric property. This
was proved in [12, Theorem 4.12] in the absense of an external field, it is
easy to verify that all steps in the proof go through mutatis mutandis in the
presence of an arbitrary external field.

######  Lemma 5.11.

For every $d\geq 2$, $\beta>0$ there exists $C(d,\beta)>0$ such that the Ising
dynamics on a finite connected set $A\subset\mathbb{Z}^{d}$ at inverse
temperature $\beta$ and arbitrary fields $(h_{x})_{x\in A}$ has

$\displaystyle\min_{\phi}\text{\tt{gap}}_{A}^{\phi}\geq
C^{-1}\exp(-C|A|^{\frac{d-1}{d}})\,.$

where $\text{\tt{gap}}_{A}^{\phi}$ is the spectral gap of the Ising dynamics
on $A$ with boundary conditions $\phi$.

Thus, as long as the largest connected component of $\mathsf{Bad}$ blocks in
the coarse-graining has volume at most $L$, we deduce a bound on its inverse-
gap as sub-exponential in $L$. This is immediate from Lemma 5.11 together with
each block in $\mathcal{B}$ having volume at most $R^{d}L$.

######  Corollary 5.12.

If $h$ is such that
$\max_{w\in\Lambda_{n}^{(R)}}|\mathcal{C}_{w,\mathsf{Bad}}^{(R)}(\omega^{h})|\leq
L$, then if $\mathcal{B}=(\mathcal{B}_{i})_{i}$ are the blocks constructed out
of $\mathsf{Good}(h)$ in Definition 5.9, then

$\displaystyle\min_{i}\min_{\phi}\text{\tt{gap}}_{\mathcal{B}_{i}}^{\phi}\geq
C^{-1}\exp(-CR^{d-1}L^{\frac{d-1}{d}})\,.$

_Property (2)._ We now show using the definition of the coarse-graining and
the blocks, that they ensure a block update doesn’t increase the discrepancy
between two configurations too much.

######  Lemma 5.13.

Fix any realization of $h$, and any block $\mathcal{B}_{i}$ constructed out of
$\mathsf{Good}(h)$ per Definition 5.9. For any boundary condition $\xi$ let
$\xi^{y}$ be the boundary condition that agrees with $\xi$ everywhere except
at $y$, where it takes the opposite spin. For every
$y\in\partial\mathcal{B}_{i}$, and $(\xi,\xi^{y})$, there exists a coupling
$\mathbf{P}$ of $\sigma\sim\mu_{\mathcal{B}_{i}}^{\xi}$ and
$\sigma^{y}\sim\mu_{\mathcal{B}_{i}}^{\xi^{y}}$ such that

$\displaystyle\mathbf{E}[d_{H}(\sigma,\sigma^{y})]\leq(\log
R)^{2}+|\mathcal{B}_{i}|e^{-R/8}+O(1)\,,$

where $d_{H}$ denotes Hamming distance.

We have to prove Lemma 5.13 separately depending on the definition of
$\mathsf{Good}$ blocks we used (i.e., depending on which of Assumption 5.1 and
Assumption 1.5 we work under).

###### Proof.

If $\mathcal{B}_{i}$ is a type (1) block per Definition 5.9, then every vertex
on its boundary is at distance at most $7R/8$ from an element of
$\mathsf{Good}(h)$. If it is a type (2) block, every boundary vertex of
$B_{\mathcal{C}}$ is exactly distance $R/2$ from $\mathsf{Good}(h)$, so any of
its translates by $R/8$ must be within distance $5R/8$ from
$\mathsf{Good}(h)$. In either case, $y$ must have distance strictly less than
$7R/8$ from $\mathsf{Good}(h)$.

_Proof under $\mathsf{Good}$-blocks of Definition 5.2_. The above implies by
definition of $\mathsf{Good}$, that

$\displaystyle\mathbb{P}_{\eta}(|\mathcal{C}_{y}(\omega^{\mathsf{i}})|\geq
r\mid h)\leq e^{-r}\quad\text{ for all }(\log R)^{2}\leq r\leq R/8\,.$ (5.3)

We use the random-variables $\rho$ to construct a coupling of
$\sigma\sim\mu_{\mathcal{B}_{i}}^{\xi}$ and
$\sigma^{y}\sim\mu_{\mathcal{B}_{i}}^{\xi^{y}}$ as follows.

  1. 1.

Assign every vertex an i.i.d. Unif$[0,1]$ random variable $U_{x}$.

  2. 2.

One at a time starting from neighbors of $y$, use the uniforms to generate
$\sigma,\sigma^{y}$ in a coupled manner, where for each vertex $x$ having
$|h_{x}|\geq K$, if $U_{x}\leq 1-\rho$ (for $\rho$ from (5.1)) necessarily
both $\sigma_{x}$ and $\sigma_{x}^{\prime}$ take the value
$\operatorname{sgn}(h_{x})$.

  3. 3.

As soon as we have encountered a set of vertices separating $y$ from the rest
of $\mathcal{B}_{i}$ all of which take the value of
$\operatorname{sgn}(h_{x})$ in both $\sigma,\sigma^{y}$ use the identity
coupling on the remainder of the configuration (since it will have the same
induced boundary conditions on it in both $\sigma,\sigma^{y}$).

This is easily checked to be a valid coupling. Moreover, generating the
$\eta_{x}$ (used to construct $\omega^{\mathsf{i}}$) via
$\mathbf{1}_{U_{x}\geq 1-\rho}$, the boundary of
$\mathcal{C}_{y}(\omega^{\mathsf{i}})$ always serves as a set on which
$\sigma$ and $\sigma^{y}$ both take the value of $\operatorname{sgn}(h_{x})$,
so in particular, this coupling satisfies

$\displaystyle\sigma(\mathcal{B}_{i}\setminus\mathcal{C}_{y}(\omega^{\mathsf{i}}))=\sigma^{y}(\mathcal{B}_{i}\setminus\mathcal{C}_{y}(\omega^{\mathsf{i}}))\,.$

Therefore, we have

$\displaystyle\mathbf{E}[d_{H}(\sigma,\sigma^{\prime})]\leq(\log
R)^{2}+\sum_{r=(\log
R)^{2}}^{R/8}r\mathbb{P}_{\eta}(|\mathcal{C}_{w}(\omega^{\mathsf{i}})|\geq
r\mid
h)+|\mathcal{B}_{i}|\mathbb{P}_{\eta}(|\mathcal{C}_{w}(\omega^{\mathsf{i}})|\geq
R/8\mid h)\,.$

Plugging in the bound of (5.3) on the probabilities above, we evidently get
the desired bound up to change of the constant $C$.

_Proof under $\mathsf{Good}$-blocks of Definition 5.3_. As reasoned at the
beginning of the proof, by construction $y$ is at distance at most $7R/8$ from
$\mathsf{Good}(h)$. We now construct a monotone coupling $\mathbf{P}$ of
$\sigma\sim\mu_{\mathcal{B}_{i}}^{\xi}$ and
$\sigma^{y}\sim\mu_{\mathcal{B}_{i}}^{\xi^{y}}$ as follows.

  1. 1.

Assign every vertex an i.i.d. Unif$[0,1]$ random variable $U_{x}$

  2. 2.

Iteratively for $\ell\geq 1$, expose the spins
$(\sigma_{x},\sigma^{y}_{x})_{x\in\mathcal{B}_{i}:d_{1}(x,y)=\ell}$ coupled
via the monotone coupling using the common random variables $U_{x}$.

Notice that under this coupling, if $\sigma_{x}=\sigma^{y}_{x}$ for all
$x\in\mathcal{B}_{i}:d_{1}(x,y)=\ell$, then $\sigma$ and $\sigma^{y}$ agree on
all vertices at distance greater than $\ell$ from $y$. This is because on that
event, the induced boundary conditions on the un-revealed spins of
$\mathcal{B}_{i}$ will agree completely. In particular, in that case,
$d_{H}(\sigma,\sigma^{y})$ would be at most $\ell^{d}$. Furthermore, we always
have the deterministic bound $d_{H}(\sigma,\sigma^{y})\leq|\mathcal{B}_{i}|$.
Therefore, we can bound

$\displaystyle\mathbf{E}[d_{H}(\sigma,\sigma^{y})]$ $\displaystyle\leq(\log
R)^{2d}+\sum_{\ell=(\log
R)^{2}}^{R/8}\mathbf{P}(d_{H}(\sigma,\sigma^{y})\geq\ell^{d})+|\mathcal{B}_{i}|\mathbf{P}(d_{H}(\sigma,\sigma^{y})\geq(R/8)^{d})\,.$
(5.4)

By the above reasoning, the tail probabilities for $(\log R)^{2}\leq\ell\leq
R/8$ are bounded as

$\displaystyle\mathbf{P}(d_{H}(\sigma,\sigma^{y})\geq\ell^{d})\leq\ell^{d-1}\max_{x\in\mathcal{B}_{i}:d_{1}(x,y)=\ell}\mathbf{P}(\sigma_{x}\neq\sigma^{y}_{x})\,.$
(5.5)

Since the coupling $\mathbf{P}$ is monotone, the disagreement probability on
the right is exactly

$\displaystyle\mathbf{P}(\sigma_{x}\neq\sigma^{y}_{x})=d_{\mbox{\rm\tiny
TV}}(\mu_{\mathcal{B}_{i}}^{\xi}(\sigma_{x}\in\cdot),\mu_{\mathcal{B}_{i}}^{\xi^{y}}(\sigma_{x}^{y}\in\cdot))\,.$
(5.6)

For that tv-distance, inscribe a ball $B$ of $\ell^{\infty}$-radius $\ell$,
say, in $\mathcal{B}_{i}$, such that all points in $\partial B$ at graph
distance less than $\ell$ from $x$ belong to $\partial\mathcal{B}_{i}$. This
ensures that the boundary conditions induced by
$\mu_{\mathcal{B}_{i}}^{\xi},\mu_{\mathcal{B}_{i}}^{\xi^{y}}$ on the vertices
in $\partial B$ at distance less than $\ell$ from $x$ are identical. (This
inscription is always possible since by Observation 5.10, all
$\mathcal{B}_{i}$ can be partitioned into disjoint cubes of side-length $R/2$,
and $\ell\leq R/8$.) The vertices in $\partial B$ at distance at least $\ell$
from $x$ may all differ; call two such boundary conditions
$\zeta,\zeta^{\prime}$ on $\partial B$. By flipping one spin at a time to
interpolate between $\zeta,\zeta^{\prime}$, by (5.2) (which applies since $x$
is at distance at most $R/8$ from $y$ and thus at distance at most $R$ from a
good vertex $v\in\mathsf{Good}(h)$),

$\displaystyle d_{\mbox{\rm\tiny
TV}}(\mu_{\mathcal{B}_{i}}^{\xi}(\sigma_{x}),\mu_{\mathcal{B}_{i}}^{\xi^{y}}(\sigma_{x}))\leq\sum_{z\in\partial
B:d(z,x)\geq\ell}\max_{\zeta\in\\{\pm 1\\}^{\partial B\setminus
z}}d_{\mbox{\rm\tiny
TV}}(\mu_{B}^{\zeta^{+}}(\sigma_{x}),\mu_{B}^{\zeta^{-}}(\sigma_{x}))\leq\ell^{d-1}e^{-\ell/C_{*}}\,.$

Altogether, plugging this into (5.6), then (5.5), then (5.4), we get the bound

$\displaystyle\mathbf{E}[d_{H}(\sigma,\sigma^{\prime})]\leq(\log
R)^{2d}+|\mathcal{B}_{i}|e^{-R/16C_{*}}+O(1)\,,$

as desired. ∎

_Property (3)._ The last property we check is that no vertex is placed on the
boundary of too many blocks compared to the number to which it is interior.

######  Lemma 5.14.

For any realization of $h$, and $\mathcal{B}=(\mathcal{B}_{i})$ constructed
per Definition 5.9, we have

$\displaystyle\max_{w\in\Lambda_{n}}\frac{|\\{i:w\in\partial\mathcal{B}_{i}\\}|}{|\\{i:w\in\mathcal{B}_{i}\\}|}\leq\frac{32d2^{d}}{R}\,.$

###### Proof.

Fix any vertex $w\in\Lambda_{n}$ We consider different cases depending on the
distance of $w$ to $\mathsf{Good}(h)$ and $\mathsf{Bad}(h)$.

If $w$ is at distance at most $5R/8$ from an element of $\mathsf{Good}(h)$,
then the $\ell^{\infty}$-balls of radius $R/8$ centered at every vertex
distance less than $R/8$ are included in $\mathcal{B}$, and they all have $w$
in their interior, so that

$|\\{i:w\in\mathcal{B}_{i}\\}|\geq(R/4)^{d}\,.$

The number of type-1 blocks having $w$ on their boundary is at most
$(2d)(R/4)^{d-1}$ for those centered at vertices exactly at distance $R/8$
from $w$. By Observation 5.10, all type-2 blocks having $w$ on their boundary
must be originating from the same $\mathcal{C}$. Moreover, at most
$2d(R/4)^{d-1}$ of the translates of $B_{\mathcal{C}}$ can have $w$ on their
boundary since $B_{\mathcal{C}}$’s boundary is a subset of the boundaries of
its constituent $R\times\cdots\times R$ cubes from the second part of
Observation 5.10. Combining the above,

$\displaystyle\frac{|\\{i:w\in\partial\mathcal{B}_{i}\\}|}{|\\{i:w\in\mathcal{B}_{i}\\}|}\leq\frac{32d}{R}\quad\text{
if $d_{\infty}(w,\mathsf{Good}(h))\leq 5R/8$}$

If $w$ is at distance at least $5R/8$ from $\mathsf{Good}(h)$, clearly it must
also have distance at most $3R/8$ from an element of $\mathsf{Bad}(h)$. If
$\mathcal{C}$ is the cluster of bad sites of the coarse graining it is closest
to, then $w$ must be interior to all $(R/4)^{d}$ translates of
$B_{\mathcal{C}}$. On the other hand, it can be on the boundary only of type-1
blocks centered at vertices exactly distance $R/8$ away, there being at most
$(2d)(R/4)^{d-1}$ many of these, that leaves

$\displaystyle\frac{|\\{i:w\in\partial\mathcal{B}_{i}\\}|}{|\\{i:w\in\mathcal{B}_{i}\\}|}\leq\frac{16d}{R}\quad\text{
if $d_{\infty}(w,\mathsf{Good}(h))\geq 5R/8$}\,.$

Together, these bounds give the claim for vertices $w$ at distance at least
$R$ from the boundary of $\Lambda_{n}$ when viewed as a subset of
$\mathbb{Z}^{d}$.

If $w$ at distance at most $R$ from the boundary of $\Lambda_{n}$, there may
be as few as a $1/2^{d}$ fraction of the number of blocks containing $w$ in
their interiors as for $w$ far from the boundary (e.g., if $w$ is a corner of
$\Lambda_{n}$). The number of blocks containing $w$ on their boundary is upper
bounded by the same number as when $w$ is far from the boundary. Thus,
multiplying the earlier bound of $32d/R$ by $2^{d}$, we get the worst-possible
ratio one could arrive at. ∎

###  5.3 From block dynamics to a mixing time bound

We now use the blocks from the previous section to deduce the claimed bound on
the mixing time of the RFIM on $\Lambda_{n}$ with large variance. Given the
properties (1)–(3) proved in the previous subsection, stitching them together
is a fairly standard application of the block dynamics tool in Markov chain
mixing times.

######  Definition 5.15.

If blocks $(\mathcal{B}_{i})$ cover $V$, the _block dynamics_ with blocks
$\mathcal{B}$ is the continuous-time Markov chain that assigns each block a
rate-1 Poisson clock, and when the clock corresponding to block
$\mathcal{B}_{i}$ rings, it fully resamples the configuration on
$\mathcal{B}_{i}$ conditional on the configuration on
$V\setminus\mathcal{B}_{i}$.

######  Proposition 5.16 ([47, Proposition 3.4]).

Consider a continuous-time single-site Markov chain for the Ising model on
$G=(V,E)$, which is reversible w.r.t. the Gibbs distribution $\mu_{G}$. Let
$\text{\tt{gap}}_{G}$ and $\text{\tt{gap}}_{\mathcal{B}}$ respectively be the
spectral gap of the single-site dynamics on $G$, and the spectral gap of the
block dynamics corresponding to blocks
$\mathcal{B}_{1},...,\mathcal{B}_{k}\subset V$ such that
$\bigcup_{i}\mathcal{B}_{i}=V$. Then letting $\chi=\sup_{v\in
V}\\#\\{i:v\in\mathcal{B}_{i}\\}$, we obtain

$\displaystyle\text{\tt{gap}}_{G}^{\xi}\geq\chi^{-1}\text{\tt{gap}}_{\mathcal{B}}^{\xi}\inf_{i}\inf_{\phi}\text{\tt{gap}}_{\mathcal{B}_{i}}^{\phi}\,.$

where the infimum over $\phi$ is over boundary conditions on
$\mathcal{B}_{i}$, i.e., assignments to $\Lambda_{n}\setminus\mathcal{B}_{i}$.

The proof of Theorem 5.1 essentially breaks into the following two lemmas
controlling the inverse gap of the block dynamics and the individual blocks
(the quantity $\chi$ is easily bounded).

######  Lemma 5.17.

Fix $\mathsf{Good}(h)$ and let $\mathcal{B}_{i}$ be constructed per Definition
5.9. Then, if we have that $R\geq C_{0}\log(\max_{i}|\mathcal{B}_{i}|)$ for a
large enough constant $C_{0}$, there is a constant $C^{\prime}$ such that

$\displaystyle\text{\tt{gap}}_{\mathcal{B}}^{-1}\leq C^{\prime}\,.$

###### Proof.

The proof goes by path coupling. Let us consider the discrete time version of
the block dynamics where a block is chosen uniformly at random at each
discrete time step. The inverse gap of the discrete and continuous time chains
are within a factor of the number of blocks of one another, which is evidently
on the order of $|\Lambda_{n}|R^{d}$.

Consider the Hamming distance on configurations. Recalling the path coupling
from [40, Theorem 14.6], for each pair of adjacent configurations
$\sigma,\sigma^{y}$ that differ at vertex $y$, we wish to construct a coupling
$\mathbf{P}$ of their respective 1-step transitions $X_{1}\sim
P_{\mathcal{B}}\sigma$ and $Y_{1}\sim P_{\mathcal{B}}\sigma^{y}$ such that

$\displaystyle\mathbf{E}[d_{H}(X_{1},Y_{1})]\leq\theta<1\,.$

If this holds for a $\theta<1$ for all pairs $(\sigma,\sigma^{y})$ then

$\displaystyle\mathbf{E}[d_{H}(X_{t},Y_{t})]\leq\theta^{t}|\Lambda_{n}|\qquad\text{and}\qquad\text{\tt{gap}}_{\mathcal{B}}^{-1}\leq(1-\theta)^{-1}\,.$

We prove this with $\theta=1-\Theta(\frac{1}{|\Lambda_{n}|})$ for the
discrete-time block dynamics, which implies the claimed bound for the
continuous-time block dynamics.

Fix any $y\in\Lambda_{n}$, and let $\sigma^{+},\sigma^{-}$ be two arbitrary
configurations that agree on all sites except at $y$ where they take values
$+,-$ respectively. Let $\mathcal{B}_{i}$ be the next block whose clock rings
(this is uniformly chosen amongst the blocks, and we use the same choice for
the coupling of $X_{1},Y_{1}$). On the event that
$y\notin\mathcal{B}_{i}\cup\partial\mathcal{B}_{i}$, the expected Hamming
distance between $X_{1},Y_{1}$ is still $1$. On the event that
$y\in\mathcal{B}_{i}$, the identity coupling is used, the boundary conditions
induced by $\sigma^{+},\sigma^{-}$ on $\mathcal{B}_{i}$ are identical, and the
expected Hamming distance is $0$. Finally, on the event that
$y\in\partial\mathcal{B}_{i}$, the coupling of Lemma 5.13 is used, whence the
expected Hamming distance is at most $2(\log R)^{2}$ as long as $R$ is at
least $C_{0}\log|\mathcal{B}_{i}|$. Putting these together, we see that

$\displaystyle\mathbf{E}[d_{H}(X_{1},Y_{1})]\leq
1-\frac{1}{|\mathcal{B}|}\Big{(}|\\{i:y\in\mathcal{B}_{i}\\}|-2|\\{i:y\in\partial\mathcal{B}_{i}\\}|(\log
R)^{2}\Big{)}\,.$

Noting that $|\mathcal{B}|\leq|\Lambda_{n}|R^{d}$ and
$|\\{i:y\in\mathcal{B}_{i}\\}|\geq(R/4)^{d}$, and then using Lemma 5.14, this
gives

$\displaystyle\mathbf{E}[d_{H}(X_{1},Y_{1})]$ $\displaystyle\leq
1-\frac{1}{4^{d}|\Lambda_{n}|}\Big{(}1-\frac{|\\{i:y\in\partial\mathcal{B}_{i}\\}|}{|\\{i:y\in\mathcal{B}_{i}\\}|}2(\log
R)^{2}\Big{)}$ $\displaystyle\leq
1-\frac{1}{4^{d}|\Lambda_{n}|}\Big{(}1-\frac{64d2^{d}(\log
R)^{2}}{R}\Big{)}\,.$

At this point, we find that as long as $R$ is sufficiently large as a function
of $d$, we have contraction with $\theta=1-\Theta(\frac{1}{|\Lambda_{n}|})$
concluding the proof. ∎

###### Proof of Theorem 5.1.

Fix a realization of $\mathsf{Good}(h)$ and let
$\mathcal{B}=(\mathcal{B}_{i})_{i}$ be the corresponding set of blocks defined
per Definition 5.9. Suppose that $h$ is such that
$\max_{w\in\Lambda_{n}^{(R)}}|\mathcal{C}_{w,\mathsf{Bad}}^{(R)}(\omega^{h})|\leq
L$, (the complement of this event having $\mathbb{P}_{h}$-probability $e^{-L}$
by Corollary 5.8). By construction, this implies that
$\max_{i}|\mathcal{B}_{i}|\leq R^{d}L$. We now make the concrete choice

$\displaystyle R=C_{1}\log L\,,$

for a sufficiently large constant $C_{1}$. The quantity $\chi$, i.e., the
maximum number of blocks confining a single vertex is easily seen to be at
most $2(R/4)^{d}\leq O((\log L)^{d})$.

Since $\max_{i}|\mathcal{B}_{i}|\leq LR^{d}$ for large $n$, if $C_{1}$ is
sufficiently large then $R\geq C_{0}\log(\max_{i}|\mathcal{B}_{i}|)$ so we can
apply Lemma 5.17 whence $\text{\tt{gap}}_{\mathcal{B}}^{-1}\leq C^{\prime}$
for some $C^{\prime}$.

At the same time, by Lemma 5.12, we get that

$\displaystyle(\min_{i}\min_{\phi}\text{\tt{gap}}_{\mathcal{B}_{i}}^{\phi})^{-1}\leq
C\exp(CR^{d}L^{\frac{d-1}{d}})\,.$

Combining these three bounds into Proposition 5.16, we deduce that

$\displaystyle\text{\tt{gap}}_{\Lambda_{n}}^{-1}\leq\exp\big{(}CL^{\frac{d-1}{d}}(\log
L)^{d-1}\big{)}\,,$

concluding the proof of the theorem. ∎

###  5.4 SSM holds if the field is sufficiently anti-concentrated

In this short subsection, we prove that if $|h|$ is i.i.d. and the variance of
$|h|$ is sufficiently large, then $\text{\rm\small SSM}(C)$ holds. Note: this
isn’t enough to just reduce the proof with Assumption 5.1 to the proof with
Assumption 1.5 because the proof with the SSM assumption requires independence
of $(h_{x})_{x}$, which the proof with Assumption 5.1 does not require, and
the reduction from WSM after stochastic localization does not have.

######  Lemma 5.18.

Suppose that Assumption 5.1 holds. Then there is $C$ such that the RFIM has
$\text{\rm\small SSM}(C)$.

###### Proof.

Fix a domain $B$ containing the origin $o$, and fix a $z\in\partial B$. We
consider the process $(\eta_{x})$ which is $1$ if $|h_{x}|\leq K$. As before,
$K$ is chosen such that $\rho(K)$ from (5.1) is at most $1/10d$, say. In that
case, wherever $\eta_{x}=0$, the probability that $\sigma_{x}$ agrees with
$\text{sign}(h_{x})$ is at least $1-1/10d$, uniformly over the neighboring
spins to $x$.

We construct a coupling of samples $\sigma^{+}\sim\mu_{B}^{\xi^{+}}$ and
$\sigma^{-}\sim\mu_{B}^{\xi^{-}}$ disagreeing at $z\in\partial B$, at the
origin $\sigma_{0}$ as follows. Starting from neighbors of $z$, use the
monotone coupling (with the same uniform random variables at each vertex) to
iteratively reveal the spins of $\sigma^{+}$ and $\sigma^{-}$, exposing the
maximal component of $z$ on which the two disagree. By the above reasoning,
the probability that they disagree at a site $x$, even conditionally on the
fields and spins at all other sites, is at most $1/5d$. Therefore, the
disagreement region is confined by an independent $\text{Ber}(1/5d)$
percolation, and beyond the component of $z$ in this percolation, the two
configurations are coupled via the identity coupling. Since the degree of
$\mathbb{Z}^{d}$ is $2d$, the $\text{Ber}(1/5d)$ percolation is subcritical,
and $\max_{\eta\in\\{\pm 1\\}^{\partial B\setminus\\{z\\}}}d_{\mbox{\rm\tiny
TV}}(\mu_{B}^{\xi^{+}}(\sigma^{+}_{0}),\mu_{B}^{\xi^{-}}(\sigma^{-}_{0}))$ is
bounded by the indicator that this sub-critical percolation connects $z$ to
$0$ in $B$. This event has probability at most $e^{-d(0,z)/C}$ for some
$C(d)$, so that also bounds the expectation of its indicator, yielding the
claim. ∎

##  6 Construction of a super-polylogarithmic lower bound

Given the fact that our mixing time upper bound, even at very large variance
is $n^{o(1)}$, one may wonder what the true mixing time should be. Standard
arguments (see [33]) give a coupon collecting lower bound of $O(\log n)$,
which also applies in the absence of an external field. In what follows we
show that when the temperature is below the zero-field critical point, the
mixing time of the RFIM is at least super-polylogarithmically slower.

To be precise, we construct an $\exp((\log n)^{c})$ lower bound for the mixing
time of the RFIM with an $O(1)$ variance, when the temperature $\beta$ is
large. We will phrase this for Gaussian external fields though a distribution
with density at zero, for instance, would suffice.

######  Proposition 6.1.

For $\beta$ sufficiently large as a function of $d$, and i.i.d. Gaussian
external fields $(h_{x})_{x}$, the mixing time of the continuous-time Glauber
dynamics for the RFIM on $\Lambda_{n}$ with $\mathrm{Var}(h_{x})=O(1)$ is at
least $\exp((\log n)^{(d-1)/4d})$.

The lower bound in fact applies whenever there exists a (sequence of) boundary
conditions $\zeta_{L}$ under which the mixing time of the zero-field Ising
model on boxes of side-length $L$ with boundary conditions $\zeta_{L}$ is
$\exp(\Omega(L^{d-1}))$. Such a boundary condition should exist for all
$\beta<\beta_{c}(d)$ in all $d\geq 3$, and we give concrete examples below.

######  Example 6.2.

In $d=2$ and any $\beta>\beta_{c}$, if $\zeta_{L}$ is $+$ on the top and
bottom of $\Lambda_{L}$ and $-$ on the left and right, it induces
$\exp(L^{d-1})$ slow mixing (see e.g., [28, Theorem 1 together with Remark
1.2]). In $d\geq 3$ and $\beta>\beta_{0}$ sufficiently large, if $\zeta_{L}$
is all $-$, except a strip of $+$ of width $\epsilon n$, say
$\\{x\in\partial\Lambda_{L}:x_{d}\in[\frac{n}{2},\frac{n}{2}+\epsilon n]\\}$,
it induces slow mixing. The slowdown in this latter case follows from the
rigidity of the $+/-$ Dobrushin interface [19].

###### Proof of Proposition 6.1.

Let $m=(\log n)^{1/4d}$. The domain $\Lambda_{n}$ can evidently be tiled by
$\lfloor(\frac{n}{m+1})^{d}\rfloor$ many cubes of side-length $m$, at distance
at least $2$ from one another, denoted $(B_{i})_{i}$. We will use the event
that one of these has a bad realization of the external field to embed the
assumed slow mixing with boundary conditions $\zeta_{L}$ into $B_{i}$ for some
$i$. For each $i$, let $E_{i}$ be the following event:

  1. 1.

Every vertex on the boundary $\partial B_{i}$ has external field
$(h_{v})_{v\in\partial B_{i}}$ with absolute value at least $m^{d}$, and signs
given by $\zeta_{m}$; and

  2. 2.

Every vertex in $B_{i}$ has external field at most $1/m^{d}$ in absolute
value.

There exists a constant $c$ depending on $\text{Var}(h_{v})$, such that this
pair of events has probability $(e^{-cm^{2d}})^{m^{d-1}}$ for item (1), and
$(c/m^{d})^{m^{d}}$ for item (2). Since these events are independent,
$\mathbb{P}(E_{i})\geq e^{-m^{3d}}\geq n^{-o(1)}$, whence the independence of
$(E_{i})_{i}$ implies that

$\displaystyle\mathbb{P}\Big{(}\bigcup_{i=1}^{(\frac{n}{m+1})^{d}}E_{i}\Big{)}\geq
1-o(1)\,.$

We claim that on the event $\bigcup_{i}E_{i}$ the mixing time is slow. Take
any such external field realization, and let $B_{\star}=B_{i}$ for an $i$ such
that $E_{i}$ holds. Let $X_{t,\star}$ be the projection of the Glauber
dynamics onto $B_{\star}\cup\partial B_{\star}$, initialized from $\zeta_{m}$
on $\partial B_{\star}$, and initialized interior to $B_{\star}$ from the
initialization attaining the zero-field slow mixing with boundary condition
$\zeta_{m}$ (and arbitrarily elsewhere).

In each update on $\partial B_{i}$, uniformly over the exterior configuration,
the probability that a site on $\partial B_{i}$ flips its spin to disagree
with $\zeta_{m}$ is at most $e^{-m^{d}+2\beta d}$; by a union bound, this
implies that for $e^{\Omega(m^{d})}$ times, with high probability
$X_{t,\star}(\partial B_{i})\equiv\zeta_{m}$. On that event, the dynamics
interior to $B_{i}$ is exactly a Glauber dynamics chain interior to $B_{i}$
with frozen boundary conditions $\zeta_{m}$. Since its zero-field version has
a mixing time that is $\exp(m^{d-1})$, by a standard comparison of Dirichlet
forms and the fact that the measure on $B_{\star}$ with zero field and with
the fields on the event item (2) of $E_{i}$ are within an exponential factor
of $e^{O(1)}$ of one another, we find that the mixing time of
$X_{t,\star}(B_{\star})$ as a Markov chain only on the interior of $B_{\star}$
is at least $\exp(\Omega(m^{d-1}))$.

Therefore, there exists an event measurable with respect to the interior spins
of $B_{\star}$ which gets at least $1/4$ more mass under the stationary
measure on $B_{\star}$ than it does under $X_{t,\star}(B_{\star})$ while
$t\leq e^{m^{d-1}}$. That implies the mixing time of the full Glauber dynamics
Markov chain has at least total variation distance $1/4-o(1)$ from its
stationary distribution while $t\leq e^{m^{d-1}}$, which gives the claimed
lower bound after plugging in for $m$. ∎

## References

  * [1] Michael Aizenman, Matan Harel and Ron Peled  “Exponential Decay of Correlations in the 2D Random Field Ising Model”  In _Journal of Statistical Physics_ 180.1, 2020, pp. 304–331  DOI: 10.1007/s10955-019-02401-5
  * [2] Michael Aizenman and Ron Peled  “A Power-Law Upper Bound on the Correlations in the 2D Random Field Ising Model”  In _Communications in Mathematical Physics_ 372.3, 2019, pp. 865–892  DOI: 10.1007/s00220-019-03450-3
  * [3] Michael Aizenman and Jan Wehr  “Rounding effects of quenched randomness on first-order phase transitions”  In _Communications in Mathematical Physics_ 130.3, 1990, pp. 489–528  DOI: 10.1007/BF02096933
  * [4] Nima Anari, Kuikui Liu and Shayan Oveis Gharan  “Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model”  In _SIAM Journal on Computing_ 0.0, 0, pp. FOCS20–1–FOCS20–37  DOI: 10.1137/20M1367696
  * [5] Nima Anari et al.  “Entropic Independence: Optimal Mixing of down-up Random Walks”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2022  Rome, Italy: Association for Computing Machinery, 2022, pp. 1418–1430  DOI: 10.1145/3519935.3520048
  * [6] Christophe Andrieu, Anthony Lee, Sam Power and Andi Q. Wang  “Comparison of Markov chains via weak Poincaré inequalities with application to pseudo-marginal MCMC”  In _The Annals of Statistics_ 50.6 Institute of Mathematical Statistics, 2022, pp. 3592 –3618  DOI: 10.1214/22-AOS2241
  * [7] Christophe Andrieu, Anthony Lee, Sam Power and Andi Q Wang  “Poincaré inequalities for Markov chains: a meeting with Cheeger, Lyapunov and Metropolis”  In _arXiv preprint arXiv:2208.05239_ , 2022
  * [8] Roland Bauerschmidt and Thierry Bodineau  “A very simple proof of the LSI for high temperature spin systems”  In _Journal of Functional Analysis_ 276.8, 2019, pp. 2582–2588  DOI: https://doi.org/10.1016/j.jfa.2019.01.007
  * [9] Noam Berger, Claire Kenyon, Elchanan Mossel and Yuval Peres  “Glauber dynamics on trees and hyperbolic graphs”  In _Probability Theory and Related Fields_ 131.3, 2005, pp. 311–340  DOI: 10.1007/s00440-004-0369-4
  * [10] J. Bricmont and A. Kupiainen  “Phase transition in the 3d random field Ising model”  In _Communications in Mathematical Physics_ 116.4, 1988, pp. 539–572  DOI: 10.1007/BF01224901
  * [11] Jin-Yi Cai et al.  “#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region”  In _Journal of Computer and System Sciences_ 82.5, 2016, pp. 690–711  DOI: https://doi.org/10.1016/j.jcss.2015.11.009
  * [12] F. Cesi, C. Maes and F. Martinelli  “Relaxation of Disordered Magnets in the Griffiths’ Regime”  In _Communications in Mathematical Physics_ 188.1, 1997, pp. 135–173  DOI: 10.1007/s002200050160
  * [13] Filippo Cesi  “Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields”  In _Probability Theory and Related Fields_ 120.4, 2001, pp. 569–584  DOI: 10.1007/PL00008792
  * [14] Sourav Chatterjee  “On the Decay of Correlations in the Random Field Ising Model”  In _Communications in Mathematical Physics_ 362.1, 2018, pp. 253–267  DOI: 10.1007/s00220-018-3085-0
  * [15] Yuansi Chen and Ronen Eldan  “Localization schemes: A framework for proving mixing bounds for Markov chains”  In _arXiv preprint arXiv:2203.04163_ , 2022
  * [16] Jian Ding, Yu Liu and Aoteng Xia  “Long range order for three-dimensional random field Ising model throughout the entire low temperature regime”  In _arXiv preprint arXiv:2209.13998_ , 2022
  * [17] Jian Ding, Jian Song and Rongfeng Sun  “A new correlation inequality for Ising models with external fields”  In _Probability Theory and Related Fields_ Springer, 2022, pp. 1–16
  * [18] Jian Ding and Jiaming Xia  “Exponential decay of correlations in the two-dimensional random field Ising model”  In _Inventiones mathematicae_ 224.3, 2021, pp. 999–1045  DOI: 10.1007/s00222-020-01024-y
  * [19] R. L. Dobrushin  “The Gibbs state that describes the coexistence of phases for a three-dimensional Ising model”  In _Teor. Verojatnost. i Primenen._ 17, 1972, pp. 619–639
  * [20] Hugo Duminil-Copin  “Lectures on the Ising and Potts models on the hypercubic lattice”  In _PIMS-CRM Summer School in Probability_ , 2017, pp. 35–161  Springer
  * [21] Martin Dyer, Alistair Sinclair, Eric Vigoda and Dror Weitz  “Mixing in time and space for lattice spin systems: A combinatorial view”  In _Random Structures & Algorithms_ 24.4, 2004, pp. 461–479  DOI: https://doi.org/10.1002/rsa.20004
  * [22] Ahmed El Alaoui and Andrea Montanari  “An Information-Theoretic View of Stochastic Localization”  In _IEEE Transactions on Information Theory_ 68.11, 2022, pp. 7423–7426
  * [23] Ronen Eldan  “Thin shell implies spectral gap up to polylog via a stochastic localization scheme”  In _Geometric and Functional Analysis_ 23.2 Springer, 2013, pp. 532–569
  * [24] Ronen Eldan, Frederic Koehler and Ofer Zeitouni  “A spectral condition for spectral gap: fast mixing in high-temperature Ising models”  In _Probability Theory and Related Fields_ 182, 2022, pp. 1035–1051
  * [25] Ronen Eldan and Omer Shamir  “Log concavity and concentration of Lipschitz functions on the Boolean hypercube”  In _Journal of Functional Analysis_ 282.8, 2022
  * [26] Sacha Friedli and Yvan Velenik  “Statistical mechanics of lattice systems: a concrete mathematical introduction”  Cambridge University Press, 2017
  * [27] Jürg Fröhlich and John Z. Imbrie  “Improved perturbation expansion for disordered systems: beating Griffiths singularities”  In _Communications in Mathematical Physics_ 96.2 Springer, 1984, pp. 145 –180
  * [28] Reza Gheissari and Eyal Lubetzky  “The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions”  In _Electron. J. Probab._ 23 The Institute of Mathematical Statisticsthe Bernoulli Society, 2018, pp. 30 pp.  DOI: 10.1214/18-EJP180
  * [29] Reza Gheissari and Alistair Sinclair  “Spatial mixing and the random-cluster dynamics on lattices”  In _Random Structures & Algorithms_ n/a.n/a DOI: https://doi.org/10.1002/rsa.21191
  * [30] Roy J. Glauber  “Time‐Dependent Statistics of the Ising Model”  In _Journal of Mathematical Physics_ 4.2, 1963, pp. 294–307  DOI: 10.1063/1.1703954
  * [31] Robert B. Griffiths  “Nonanalytic Behavior Above the Critical Point in a Random Ising Ferromagnet”  In _Phys. Rev. Lett._ 23 American Physical Society, 1969, pp. 17–19  DOI: 10.1103/PhysRevLett.23.17
  * [32] Martin Grothaus and Feng-Yu Wang  “Weak Poincaré inequalities for convergence rate of degenerate diffusion processes”  In _The Annals of Probability_ 47.5 Institute of Mathematical Statistics, 2019, pp. 2930 –2952  DOI: 10.1214/18-AOP1328
  * [33] Thomas P. Hayes and Alistair Sinclair  “A general lower bound for mixing of single-site dynamics on graphs”  In _The Annals of Applied Probability_ 17.3 Institute of Mathematical Statistics, 2007, pp. 931 –952  DOI: 10.1214/105051607000000104
  * [34] Tyler Helmuth et al.  “Approximation Algorithms for the Random Field Ising Model”  In _SIAM Journal on Discrete Mathematics_ 37.3, 2023, pp. 1610–1629  DOI: 10.1137/21M1467389
  * [35] John Z. Imbrie  “The ground state of the three-dimensional random-field Ising model”  In _Communications in Mathematical Physics_ 98.2 Springer, 1985, pp. 145 –176