.

# Randomized Systematic Scan dynamics on the Mean-field Ising Model

Sanghak Jeon  Mathematics Department, Princeton University, Princeton, NJ
08544-1000, USA

###### Abstract.

We study the mixing time of systematic scan Glauber dynamics Ising model on
the complete graph. On the complete graph $K_{n}$, at each time, $k\leq n$
vertices are chosen uniformly random and are updated one by one according to
the uniformly randomly chosen permutations over the $k$ vertices. We show that
if $k=o(n^{1/3})$, the high temperature regime $\beta<1$ exhibits cutoff
phenomena. For critical temperature regime $\beta=1$, We prove that the mixing
time is of order $n^{3/2}k^{-1}$. For $\beta>1$, we prove the mixing time is
of order $nk^{-1}\log n$ under the restricted dynamics.

E-mail addresses<EMAIL_ADDRESS>
2023 Mathematics Subject Classification. Primary: 60J10; Secondary: 60C05,
60G42.

Keywords and phrases. Markov chain, mixing time, Ising model, systematic scan,
cutoff phenomenon.

##  1\. Introduction

The Ising model has risen in Statistical Physics to explain the
ferromagnetism, and its mixing time has been extensively studied, yet there
are only few cutoff results([DLY09], [DLP09], [LLP10], [LS12], [LS14]). In
this paper we propose the Ising model under systematic scan, suggest the
mixing time order for all regimes, and prove the existence of the total
variation cutoff phenomenon for a high temperature regime.

One of the common ways to evolve the Ising model is the Glauber dynamics:
choosing a vertex $v$ uniformly randomly from a given graph and update its
spin according to the spins of the vertices connected to $v$. From a different
point of view, rather than choosing a vertex uniformly randomly, we can
consider a model with which is updated in a deterministic way. This is so-
called systematic scan, and a folklore belief on several problems is that
models with a random update dynamics and systematic scan share a similar have
similar metastability. To be more precise, for the Ising model on a finite
graph $G=(V,\mathcal{E})$, fix $k\leq|V|$ and uniformly randomly choose $k$
vertices among $V$, uniformly randomly choose a permutation over those $k$
vertices and update one by one along the permutation.

The question that comes along with a given Markov chain is how fast it
converges to its stationary distribution. Total variation distance on Markov
chain measures the difference between the worst probability distribution and
the stationary measure:

$d(t):=\max_{x\in X}\left\|P^{t}_{x}-\pi\right\|_{TV}=\frac{1}{2}\max_{x\in
X}\sum_{y\in X}|P^{t}(x,y)-\pi(y)|,$

and the mixing time associated with the distance

$t_{\textrm{mix}}(\epsilon):=\min\\{t:d(t)\leq\epsilon\\}$

quantifies the convergence rate. Often $t_{\textrm{mix}}(1/4)$ is written as
$t_{\textrm{mix}}$. In addition, with a sequence of graphs $G_{n}$ we can
investigate their asymptotic behavior around the mixing time. For a sequence
of Markov chains $\\{X_{n}\\}$ with the distance $d_{n}(t)$, we say the chain
exhibits cutoff at $\\{t_{n}\\}$ with window size $\\{w_{n}\\}$ if
$w_{n}=o(t_{n})$ and

$\begin{split}\lim_{\gamma\to\infty}\liminf_{n\to\infty}d_{n}(t_{n}-\gamma
w_{n})&=1,\\\ \lim_{\gamma\to\infty}\limsup_{n\to\infty}d_{n}(t_{n}+\gamma
w_{n})&=0.\end{split}$

There is an equivalent statement for cutoff phenomena, but it does not provide
any information about the window size. See [LP10] chapter 18 for more details
on cutoff phenomena.

To this end we can pose a problem on systematic scan Ising model: Do Ising
models with Glauber dynamics and with systematic scan dynamics have the same
order of the mixing time, and cutoff phenomena? One of the main theorems of
this paper is that the complete graph Ising model equipped with systematic
scan dynamics has a total variation cutoff in the high temperature regime,
$\beta<1$.

######  Theorem 1.1.

Suppose $\beta<1$. If $k=o(n^{1/3})$, then the model exhibits cutoff at
$t_{n}=[2k(1-\beta)]^{-1}n\log n$ with window size $w_{n}=n/k$.

For the complete graph Ising model, $\beta=1$ is known for not exhibiting a
cutoff. Hence we only propose both the upper and lower bound of the mixing
time under systematic scan:

######  Theorem 1.2.

Suppose $\beta=1$. If $k=o(n^{1/4})$, then there exists constants
$c_{1},c_{2}>0$ such that $c_{1}n^{3/2}k^{-1}\leq t_{\textrm{mix}}(1/4)\leq
c_{2}n^{3/2}k^{-1}$.

For the last regime, $\beta>1$, the mixing time is known to be exponential in
$n$. [LLP10] suggested a restricted version of Glauber dynamics and they
showed the mixing time is $O(n\log n)$. The restricted dynamics can be also
applied to systematic scan case, and we prove the mixing time order is
$nk^{-1}\log n$ in this model.

######  Theorem 1.3.

Suppose $\beta>1$. If $k=o(n^{1/2})$, then there exists constants
$c_{1},c_{2}>0$ such that $c_{1}nk^{-1}\log n\leq t_{\textrm{mix}}(1/4)\leq
c_{2}nk^{-1}\log n$, where $t_{\textrm{mix}}(1/4)$ is the mixing time under
the restricted dynamics.

There are two remarks on this dynamics compared to the block dynamics:
Randomized systematic scan dynamics updates $k$ vertices one by one while
block dynamics updates $k$ vertices at once. Unlike the block dynamics,
randomized systematic scan dynamics generates a small amount of error during
$k$ numbers of single-site updates. This error accumulation makes
magnetization analysis more difficult. Secondly, if $k$ is large, computer
modeling on randomized scan dynamics is more efficient than block dynamics, as
one update with randomized scan Glauber dynamics can be divided into $k$
single-site updates, which requires much less memory storage.

[DGJ08] showed the mixing time of the Curie-Weiss model in high temperature
regime is of order $n\log n$ under systematic scan. We conjecture the highest
order term for the mixing time for $k=n$ case is $[2(1-\beta)]^{-1}\log n$,
which is consistent to Theorem 1.1. We expect there must be a cutoff under
both systematic scan and the randomized systematic scan. All three
abovementioned Theorems 1.1, 1.2, and 1.3 are proven by showing both upper
bound and lower bound inequalities. All the upper bound are mostly derived
from coupling argument, however as $k$ numbers of vertices are updated at each
time, several calculations are required to finalize the proofs. The lower
bound arguments are heavily relying on the estimates on magnetizations.
Section 3, 4, and 5 contains Theorem 1.1, 1.2, and 1.3 and their proofs
respectively. Section 6 briefly discuss the case $k=n$, which is the model
without coupon collecting properties. One of the proofs of the lemma which is
crucial for Theorem 1.3 is moved to the Appendix, Section 7.

###  1.1. Background and previous researches

The mixing time and cutoff results for the Ising model on the complete graph,
also known as Curie-Weiss model, were established on [LLP10], [DLY09] and
[DLP09], showing that there is a cutoff only in the high temperature regime.
For the lattice, Lubetzky and Sly [LS12] showed that there is a cutoff on
$(\mathbb{Z}/n\mathbb{Z})^{d}$ with strong spatial mixing, which always holds
when $d=2$. There is a result on the Ising model on a regular tree also, yet
people are working on 3 or higher dimensional lattice. [DP11] suggested a
lower bound argument for the mixing time of the Ising model over an arbitrary
graph, and [Nes19] suggested another lower bound argument, in terms of the
separation distance mixing time.

Systematic scan naturally emerged from Markov chains, particularly from the
card shuffling problems. Since systematic scan excludes coupon-collecting
properties from the dynamics, one might expect systematic scan to accelerate
the mixing. However, there are only few results on systematic scan dynamics,
and several results showed that the random updates chain and systematic scan
chain have the same mixing time order. For example, [MPS04] and [SZ07] are
systematic scan version of [DS81], which showed the mixing time of two schemes
are in the same order. There are some techniques for systematic scan [SZ07],
[PW13], [DR04]; however systematic scan dynamics still poses challenges to be
analyzed. [bcsv17] is one of few results on the Ising model and systematic
scan simultaneously. [bcsv17] studied the mixing time of the Ising model over
$d-$dimensional lattice, under the systematic scan.

Particularly for the Ising model over the complete graph, It has been well
known that the model’s mixing time is of order $n\log n$ under the Glauber
dynamics. Furthermore [DGJ08] proved that the order of the mixing time under
systematic scan Glauber dynamics is the same as the original one, by utilizing
the Dobrushin-Shlosman condition. Nonetheless the existence of cutoff remained
uncovered since the lack of symmetry prevents the coupling argument and vertex
rematching - the fundamental idea of [LLP10].

##  2\. Preliminaries

In this section we present some definitions and several properties, which are
used for the remainder of the paper. The Ising model on a given finite graph
$G=(V,\mathcal{E})$ with a parameter $\beta>0$ is a probability distribution
over the state space $\Omega:=\\{+1,-1\\}^{V}$ with the probability of
$\sigma\in\Omega$ given by the Gibbs measure

$\pi(\sigma)=\frac{1}{Z(\beta)}\exp\left(\beta\sum_{(vw)\in\mathcal{E}}J(v,w)\sigma(v)\sigma(w)\right),$

where $Z(\beta)$ is a normalizing constant. We assume there are no external
fields. $\beta$ is often interpreted as an inverse-temperature, is chosen to
be non-negative for ferromagnetism.

One of the common ways to evolve the Ising model is the Glauber dynamics,
which is the following: from configuration $\sigma$, a vertex $v\in V$ is
uniformly chosen, and a new configuration is selected from the set
$\\{\eta\in\Omega:\eta(w)=\sigma(w),w\neq v\\}$. The new configuration and
$\sigma$ agree on all vertices except at $v$, and at $v$ the new spin is $\pm
1$ with probability

$p(\sigma;v)=\frac{e^{\pm\beta S^{\nu}(\sigma)}}{e^{\beta
S^{\nu}(\sigma)}+e^{-\beta S^{\nu}(\sigma)}},$ (1)

where $S^{\nu}(\sigma):=(1/n)\sum_{w:(wv)\in\mathcal{E}}\sigma(w)$. Therefore,
the new spin at $v$ only depends on the current spins of the neighboring
vertices of $v$. Pick an element from $\Omega$ and evolve with the Glauber
dynamics generates a discrete-time Markov chain.

From now on, the Ising model under the randomized systematic scan dynamics
will be denoted by $\\{X_{t}\\}^{\infty}_{t=0}$. We use $\mathbb{P}_{\sigma}$
and $\mathbb{E}_{\sigma}$ to denote the probability measure and associated
expectations given $X_{0}=\sigma$. We define a coupling of the dynamics as a
process $(X_{t},\widetilde{X}_{t})_{t\geq 0}$, where each $\\{X_{t}\\}$ and
$\\{\widetilde{X}_{t}\\}$ are versions of the dynamics. Similarly we write
$\mathbb{P}_{\sigma,\widetilde{\sigma}}$ and
$\mathbb{E}_{\sigma,\widetilde{\sigma}}$ for the probability measure and
associated expectation respectively, starting from $\sigma$ and
$\widetilde{\sigma}$.

For a configuration $\sigma\in\\{-1,1\\}^{V}$, denote $\sigma(v)$ as a spin on
the vertex $v$. As we mainly focus on complete graphs, sometimes we denote
$\sigma(i)$ for $i\in\\{1,...,n\\}$ as a spin on the $i$-th vertex. Define
magnetization of $\sigma$ as the average of all spins of $\sigma$:

$S(\sigma):=\frac{1}{n}\sum_{v\in V}{\sigma(v)}.$

We are going to denote the magnetization of $X_{t}$ as $S_{t}:=S(X_{t})$, for
simplicity’s sake. Due to the symmetry of $K_{n}$, defining those functions
are helpful to abbreviate equations:

$\begin{split}p_{+}(x)&:=\frac{1+\tanh{\beta x}}{2}\\\
p_{-}(x)&:=\frac{1-\tanh{\beta x}}{2}=1-p_{+}(x)\end{split}$ (2)

Then the probability $p(\sigma;v)$ from Equation (1) equals
$p_{\pm}\left(S(\sigma)-\sigma(v)/n\right)$.

We uniformly randomly choose $k\leq n$ vertices among $n$ vertices and pick a
permutation uniformly randomly on these selected vertices. We update $k$
vertices in that order and repeat the entire process. This randomized
systematic scan updates $k$ vertices at each time $t$, we may try to split it
into $k$ numbers of single-site updates; to elaborate, we can consider $(k+1)$
states $Y_{0}=X_{0},Y_{1},...,Y_{k-1},Y_{k}=X_{1}$ such that $Y_{i+1}$ is
derived from the single-site update from $Y_{i}$. As $i$ number of vertices of
$Y_{i}$ cannot be updated, $\\{Y_{i}\\}$ is not a Markov chain. However, since
$S(Y_{i+1})-S(Y_{i})\in\\{\pm 2/n,0\\}$, we can apply several birth-and-death
chains results. Although those results need modifications as $S(Y_{i})$ is not
a Markov chain, considering $\\{Y_{i}\\}$ still useful for coupling arguments
and hitting time estimates. We denote these $\\{Y_{i}\\}$ as intermediate
states. Sometimes we consider the extended version of intermediate states
$\\{Y_{i}\\}_{0\leq i\leq kT}$ such that $Y_{ki}=X_{i}$ for all $i\leq T$. For
each intermediate state $Y_{i}$, $i$(mod $k$) vertices cannot be selected for
the update. Call these vertices as not available vertices and denote as
$\mathcal{N}_{i}$.

Define the grand coupling $\\{X_{\sigma,t}\\}_{\sigma\in\Omega,t\geq 0}$ from
all states of $\Omega$ as the following: for each $\sigma\in\Omega$, the
coordinate process $(X_{\sigma,t})_{t\geq 0}$ is the Glauber dynamics that
starts from $\sigma$. For each time $t\geq 0$, let $\\{Y_{\sigma,i}\\}_{0\leq
i\leq k}$ be all intermediates such that $Y_{\sigma,0}=X_{\sigma,t}$. Randomly
choose the ordered set of vertices $\\{v_{1},...,v_{k}\\}$ to update.
$Y_{\sigma,i}$ denotes the configuration started from $X_{\sigma,t}$ with
updates on $\\{v_{1},...,v_{i}\\}$. Define $U_{1},U_{2},...,U_{k}$ as copies
of random variables which are uniform on $[0,1]$ and let $U_{i}$ determine the
spin $Y_{\sigma,i}(v_{i})$ for all $\sigma\in\Omega$ by

$Y_{\sigma,i}(v_{i})=\begin{cases}+1&\textrm{if}\quad 0\leq U\leq
p_{+}(S(Y_{\sigma,i-1})-n^{-1}Y_{\sigma,i-1}(v_{i}))\\\ -1&\textrm{if}\quad
p_{+}(S(Y_{\sigma,i-1})-n^{-1}Y_{\sigma,i-1}(v_{i}))<U\leq 1,\end{cases}$

and $Y_{\sigma,i}(v)=Y_{\sigma,i-1}(v)$ for all $v\neq v_{i}$. Finally accept
$X_{\sigma,t+1}=Y_{\sigma,k}$. The construction ensures that
$X_{\sigma,t+1}(w)=X_{\sigma,t}(w)$ for all vertices but
$\\{v_{1},...,v_{k}\\}$. For any two given configurations $\sigma$ and
$\widetilde{\sigma}$, define monotone coupling
$(X_{\sigma,t},X_{\widetilde{\sigma},t})$ as the projection of the grand
coupling with starting configurations $\sigma$ and $\widetilde{\sigma}$.

For two spin configurations $\sigma$ and $\widetilde{\sigma}$, define their
Hamming distance as the number of disagreeing vertices:

$\textrm{dist}(\sigma,\widetilde{\sigma}):=\frac{1}{2}\sum^{n}_{j=1}|\sigma(j)-\widetilde{\sigma}(j)|.$

Then Hamming distance contracts under monotone coupling in high temperature
regime.

######  Proposition 2.1.

Under the randomized systematic scan dynamics, the monotone coupling
$(X_{t},\widetilde{X}_{t})$ with
$(X_{0},\widetilde{X}_{0})=(\sigma,\widetilde{\sigma})$ satisfies

$\mathbb{E}_{\sigma,\widetilde{\sigma}}\big{[}\textrm{dist}(X_{t},\widetilde{X}_{t})\big{]}\leq\frac{1}{\beta}\Big{[}1+(\beta-1)\Big{(}1+\frac{\beta}{n}\Big{)}^{k}\Big{]}^{t}\textrm{dist}(\sigma,\widetilde{\sigma}).$
(3)

######  Remark.

Proposition 2.1 remains true for any $k\leq n$. If $\beta<1$,

$\rho:=\frac{1}{\beta}\Big{[}1+(\beta-1)\Big{(}1+\frac{\beta}{n}\Big{)}^{k}\Big{]}\leq
1-\frac{k(1-\beta)}{n}<1$

holds, thus Hamming distance tends to decrease in the high temperature regime.

###### Proof.

We consider the special case when dist$(\sigma,\widetilde{\sigma})=1$ and
$t=1$. Let $I$ be a vertex that has two different spins:
$1=\sigma(I)\neq\widetilde{\sigma}(I)=-1$. With probability $\frac{n-k}{n}$
the vertex $I$ is not selected to be updated; let $\mathcal{P}$ be the ordered
$k$ vertices set to be updated. From $X_{0}$ to $X_{1}$, if
$I\notin\mathcal{P}$, in terms of intermediate states $\\{Y_{i}\\}_{0\leq
i\leq k}$ and $\\{\widetilde{Y}_{i}\\}_{0\leq i\leq k}$,

$\begin{split}&\mathbb{E}_{\sigma,\widetilde{\sigma}}\big{[}\textrm{dist}(Y_{i+1},\widetilde{Y}_{i+1})|\textrm{dist}(Y_{i},\widetilde{Y}_{i})\big{]}\\\
&\qquad=\textrm{dist}(Y_{i},\widetilde{Y}_{i})+\big{|}p_{+}(S(Y_{i})-n^{-1}Y_{i}(v))-p_{+}(S(\widetilde{Y}_{i})-n^{-1}\widetilde{Y}_{i}(v))\big{|}\\\
&\qquad\leq\textrm{dist}(Y_{i},\widetilde{Y}_{i})+\tanh\Big{(}\beta\frac{|S(Y_{i})-S(\widetilde{Y}_{i})|}{2}\Big{)}\\\
&\qquad\leq\Big{(}1+\frac{\beta}{n}\Big{)}\textrm{dist}(Y_{i},\widetilde{Y}_{i}),\end{split}$
(4)

for some $v\neq I$. Otherwise, suppose $I$ is chosen to be $j$-th updated
vertex. Equation (4) holds for every indices $i\neq j-1$, but for $j-1$,

$\begin{split}&\mathbb{E}_{\sigma,\widetilde{\sigma}}\big{[}\textrm{dist}(Y_{j},\widetilde{Y}_{j})|\textrm{dist}(Y_{j-1},\widetilde{Y}_{j-1})\big{]}\\\
&\qquad=\textrm{dist}(Y_{j-1},\widetilde{Y}_{j-1})-\left(1-\big{|}p_{+}(S(Y_{j-1})-n^{-1}Y_{j-1}(v))-p_{+}(S(\widetilde{Y}_{j-1})-n^{-1}\widetilde{Y}_{j-1}(v))\big{|}\right)\\\
&\qquad\leq\textrm{dist}(Y_{j-1},\widetilde{Y}_{j-1})+\tanh\Big{(}\beta\frac{S(Y_{j-1})-S(\widetilde{Y}_{j-1})-2/n}{2}\Big{)}-1\\\
&\qquad\leq\Big{(}1+\frac{\beta}{n}\Big{)}\big{(}\textrm{dist}(Y_{j-1},\widetilde{Y}_{j-1})-1\big{)},\end{split}$

due to the fact that $S(Y_{i})\geq S(\widetilde{Y}_{i})+2/n$ for any $i\leq
j-1$. Other than $i=j-1$ we can apply Equation (4) hence we have

$\mathbb{E}_{\sigma,\widetilde{\sigma}}[\textrm{dist}(X_{1},\widetilde{X}_{1})|\textrm{dist}(X_{0},\widetilde{X}_{0})]\leq\left(1+\frac{\beta}{n}\right)^{k}-\left(1+\frac{\beta}{n}\right)^{j}$
(5)

for $I\in\mathcal{P}$. Combining Equation (4) and Equation (5),

$\begin{split}&\mathbb{E}_{\sigma,\widetilde{\sigma}}\big{[}\textrm{dist}(X_{1},\widetilde{X}_{1})|\textrm{dist}(X_{0},\widetilde{X}_{0})\big{]}\\\
&\qquad\leq\frac{1}{n}\sum_{i=0}^{k-1}\Big{[}\Big{(}1+\frac{\beta}{n}\Big{)}^{k}-\Big{(}1+\frac{\beta}{n}\Big{)}^{i+1}\Big{]}+\frac{n-k}{n}\Big{(}1+\frac{\beta}{n}\Big{)}^{k}\\\
&\qquad=\frac{1}{\beta}\Big{\\{}1+\frac{\beta}{n}\Big{[}1-\Big{(}1+\frac{\beta}{n}\Big{)}^{k}\Big{]}+(\beta-1)\Big{(}1+\frac{\beta}{n}\Big{)}^{k}\Big{\\}}\\\
&\qquad\leq\frac{1}{\beta}\Big{[}1+(\beta-1)\Big{(}1+\frac{\beta}{n}\Big{)}^{k}\Big{]}.\end{split}$
(6)

To finish the proof, for general $\sigma,\widetilde{\sigma}$, we can choose
dist$(\sigma,\widetilde{\sigma})+1$ numbers of states so that they form a
sequence from $\sigma$ to $\widetilde{\sigma}$ that the Hamming distances
between any consecutive states are 1. Equation (6) and trigonometric
inequality finishes this case, and recursive application gives Equation (3). ∎

For simplicity of notation, we write $S_{t}:=S(X_{t})$ from now on. As
$|S_{t}-\widetilde{S}_{t}|\leq(2/n)\textrm{dist}(X_{t},\widetilde{X}_{t})$ at
any time $t$, we can transform Proposition 2.1 to an equation in terms of
magnetization.

######  Proposition 2.2.

Suppose $\beta<1$. For any two configurations $\sigma$ and
$\widetilde{\sigma}$, under the monotone coupling,

$\mathbb{E}_{\sigma,\widetilde{\sigma}}\left[|S_{t}-\widetilde{S}_{t}|\right]\leq\frac{2}{n}\rho^{t}\textrm{dist}(\sigma,\widetilde{\sigma})\leq
2\rho^{t},$ (7)

where $\rho=1-k(1-\beta)/n<1$.

The constant $\rho$ comes from Proposition 2.1. Furthermore, for any two
configurations $\sigma$ and $\widetilde{\sigma}$, with the same constant
$\rho<1$ we can prove

$|\mathbb{E}_{\sigma}[S_{1}]-\mathbb{E}_{\widetilde{\sigma}}[S_{1}]|\leq\rho|S_{0}-\widetilde{S}_{0}|$
(8)

in an analogous way.

Often magnetization becomes supermartingale, so the lemma below is utilized
throughout the paper. This lemma is suggested from [LP10] chapter 18 with its
proof so we omit the proof here.

######  Lemma 2.1.

Let $(W_{t})_{t\geq 0}$ be a non-negative supermartingale and $\tau$ be a
stopping time such that

  1. (1)

$W_{0}=k$

  2. (2)

$W_{t+1}-W_{t}\leq B$

  3. (3)

$\textrm{Var}(W_{t+1}|\mathcal{F}_{t})>\sigma^{2}>0\textrm{ on the event
}\tau>t$.

If $u>4B^{2}/(3\sigma^{2})$, then

$\mathbb{P}_{k}(\tau>u)\leq\frac{4k}{\sigma\sqrt{u}}.$

Lemma 2.1 requires a lower bound on a variance. Each step of the original
Glauber dynamics generates a variance of magnetization of order $1/n^{2}$.
Since the randomized systematic scan consists of $k$ numbers of single-site
update, we can guess the variance should be of order $k/n^{2}$.

######  Lemma 2.2.

Suppose $k=o(n)$. For any randomized scan dynamics chain $X_{t}$ with
arbitrary starting state $\sigma$, $\textrm{Var}_{\sigma}[S_{1}]$ is of order
$k/n^{2}$.

###### Proof.

Define $v_{i}:=\max\textrm{Var}_{\sigma}[S(Y_{i})]$ for $t=0,1,...,(k-1)$,
where $Y_{i}$ is an intermediate state and the maximum is taken over all
$\sigma\in\Omega$ and all possible vertex update permutations. We have
$v_{1}=\Omega(n^{-2})$. Let
$\mathcal{R}=S(Y_{i+1})-S(Y_{i})\in\\{-2/n,0,2/n\\}$. In regards to the
variation identity,

$\begin{split}v_{i+1}&=\max_{\sigma\in\Omega}\textrm{Var}_{\sigma}[S(Y_{i+1})]\\\
&=\max_{\sigma\in\Omega}\Big{\\{}\mathbb{E}\big{[}\textrm{Var}_{\sigma}[S(Y_{i+1})|\mathcal{R}]\big{]}+\textrm{Var}\big{[}\mathbb{E}_{\sigma}[S(Y_{i+1})|\mathcal{R}]\big{]}\Big{\\}}\end{split}$

The first term inside the parenthesis satisfies

$\mathbb{E}\big{[}\textrm{Var}_{\sigma}[S(Y_{i+1})|\mathcal{R}]\big{]}=\mathbb{E}\big{[}\textrm{Var}_{\sigma}[S(Y_{i})]\big{]}\leq
v_{i}$

because the variance is invariant under constant translation. Also the second
term is bounded below by $O(n^{-2})$; There are only three cases to consider
for the variance calculation. For any $k$, $0\leq i\leq k-1$, and $\sigma$,
there is $\epsilon=\epsilon(\beta)>0$ which satisfies

$\mathbb{P}_{\sigma}[S(Y_{i+1})=S(Y_{i})+2/n]+\mathbb{P}_{\sigma}[S(Y_{i+1})=S(Y_{i})-2/n]\in[\epsilon,1-\epsilon].$

Therefore there exists $c_{1}>0$ which satisfies

$v_{i+1}\leq v_{i}+\frac{c_{1}}{n^{2}}$ (9)

with $v_{1}=\Omega(1/n^{2})$. For the lower bound, analogously define
$w_{i}:=\min\textrm{Var}_{\sigma}[S(Y_{i})]$ then

$w_{t+1}\geq w_{t}+\frac{c_{2}}{n^{2}}$ (10)

for some $c_{2}=c_{2}(\beta)>0$. Equation (9) and Equation (10) finishes the
proof. ∎

We can derive a general variance bound by combining Equation (8) with Lemma
2.2. This can be done with the lemma below.

######  Lemma 2.3.

Suppose $(Z_{t})$ be a (general) Markov chain which takes values from
$\mathbb{R}$. Define $\mathbb{P}_{z}$ and $\mathbb{E}_{z}$ to be probability
and expectation started from $z$. Suppose there exists some $0<\rho<1$ such
that for any initial states $(z,z^{\prime})$,

$\Big{|}\mathbb{E}_{z}[Z_{t}]-\mathbb{E}_{z^{\prime}}[Z_{t}]\Big{|}\leq\rho^{t}|z-z^{\prime}|.$
(11)

Then $v_{t}:=\sup_{z_{0}}\textrm{Var}_{z_{0}}(Z_{t})$ satisfies

$v_{t}\leq v_{1}\min\big{\\{}t,(1-\rho^{2})^{-1}\big{\\}}.$

[LLP10] mentioned Lemma 2.3 and its proof so we omit here. Combining Lemma 2.2
and Lemma 2.3, we have Var${}_{\sigma}[S_{t}]=O(1/n)$ at any time $t\geq 0$ if
$\beta<1$. The last tool for cutoff in high temperature regime is the
information of the number of each spins on an arbitrary vertices subset.

######  Lemma 2.4.

Suppose $\beta<1$.
(i) For all $\sigma\in\Omega$ and $v\in V$,

$|\mathbb{E}_{\sigma}[S_{t}]|\leq
2e^{-kt(1-\beta)/n}\qquad\textrm{and}\qquad|\mathbb{E}_{\sigma}[X_{t}(v)]|\leq
2e^{-kt(1-\beta)/n}.$

(ii) For any subset $A\subset V$, define

$M_{t}(A):=\frac{1}{2}\sum_{v\in V}X_{t}(v).$

Then we have $|\mathbb{E}_{\sigma}[M_{t}(A)]|\leq|A|e^{-kt(1-\beta)/n}$.
Furthermore, if $t\geq[2(1-\beta)k]^{-1}n\log n$, then
$\textrm{Var}_{\sigma}[M_{t}(A)]\leq Cn$ for some constant $C>0$.
(iii) For any subset $A$ of vertices and all $\sigma\in\Omega$,

$\mathbb{E}_{\sigma}\big{[}|M_{t}(A)|\big{]}\leq
ne^{-kt(1-\beta)/n}+O(\sqrt{n}).$

###### Proof.

(i) Denote $\mathbbm{1}$ to be the configuration of all pluses. Consider the
monotone coupling $(X_{t},\widetilde{X}_{t})$ where $X_{0}=\mathbbm{1}$ and
$\widetilde{X}_{0}$ following the stationary distribution $\mu$. Since the
distribution on $\widetilde{X}_{t}$ remains the same and symmetric,
$\mathbb{E}_{\mu}[\widetilde{S}_{t}]=0$ holds. From Proposition 2.2,

$\mathbb{E}_{\mathbbm{1}}[S_{t}]\leq\mathbb{E}_{\mathbbm{1},\mu}\big{[}|S_{t}-\widetilde{S}_{t}|\big{]}+\mathbb{E}_{\mu}[\widetilde{S}_{t}]\leq
2\Big{(}1-\frac{k(1-\beta)}{n}\Big{)}^{t}\leq 2e^{-kt(1-\beta)/n}.$

Similarly we consider $-\mathbbm{1}$, the configuration with all minuses, then
$-2e^{-kt(1-\beta)/n}\leq\mathbb{E}_{-\mathbbm{1}}[S_{t}]$. The monotonicity
ensures
$\mathbb{E}_{-\mathbbm{1}}[S_{t}]\leq\mathbb{E}_{\sigma}[S_{t}]\leq\mathbb{E}_{\mathbbm{1}}[S_{t}]$.
For $\mathbb{E}_{\sigma}[X_{t}(v)]$, the symmetry of $K_{n}$ gives

$\mathbb{E}_{\mathbbm{1}}[S_{t}]=\mathbb{E}_{\mathbbm{1}}[X_{t}(v)]$

for any $v\in V$. Appealing to the monotonicity gives the second inequality.

(ii) The expectation argument comes from (i). Consider the monotone coupling
between $\mathbbm{1}$, $-\mathbbm{1}$, and $\sigma$ again. Denote
$M_{\sigma,t}(A)$ as $M_{t}(A)$ starts from $\sigma$ then

$M_{-\mathbbm{1},t}(A)\leq M_{\sigma,t}(A)\leq M_{\mathbbm{1},t}(A).$

As a consequence of Lemma 2.3, we have $\textrm{Var}_{\sigma}[S_{t}]=O(1/n)$.
Hence
$\mathbb{E}_{\mathbbm{1}}[M_{t}([n])^{2}]=n^{2}/4[\textrm{Var}_{\mathbbm{1}}[S_{t}]+(\mathbb{E}_{\mathbbm{1}}S_{t})^{2}=O(n)$
when $t\geq[2(1-\beta)]^{-1}n\log n$. Due to the symmetry of complete graphs,

$\mathbb{E}\Big{[}M_{\mathbbm{1},t}([n])^{2}\Big{]}=n+{n\choose
2}\mathbb{E}[X_{\mathbbm{1},t}(1)X_{\mathbbm{1},t}(2)].$

Therefore $|\mathbb{E}[X_{\mathbbm{1},t}(1)X_{\mathbbm{1},t}(2)]|=O(1/n)$.
Consider the same expansion, then

$\mathbb{E}M_{\mathbbm{1},t}(A)^{2}=|A|+{|A|\choose
2}\mathbb{E}[X_{\mathbbm{1},t}(1)X_{\mathbbm{1},t}(2)]\leq n+{n\choose
2}O(1/n)=O(n).$

Similar argument comes out for $\mathbb{E}M_{-\mathbbm{1},t}(A)$. From the
monotonicity,

$M_{\sigma,t}(A)^{2}\leq M_{-\mathbbm{1},t}(A)^{2}+M_{\mathbbm{1},t}(A)^{2}.$
(12)

Now taking expectation on both sides of Equation (12) we have
$\mathbb{E}[M_{\sigma,t}(A)^{2}]=O(n)$. The first expectation argument implies
$|\mathbb{E}M_{\sigma,t}(A)|=O(\sqrt{n})$ when $t\geq[2(1-\beta)k]^{-1}$, so
we can get the variance estimate for large time $t$.

(iii) Again, consider monotone coupling between $X_{t}$ and
$\widetilde{X}_{t}$, where $X_{0}=\sigma$ and $\widetilde{X}_{0}$ which
follows the stationary distribution $\mu$. Then

$\mathbb{E}[|M_{t}(A)|]\leq\mathbb{E}[|M_{t}(A)-\widetilde{M}_{t}(A)|]+\mathbb{E}[|\widetilde{M}_{t}(A)|].$

Applying Cauchy-Schwartz inequality considering
$|\widetilde{M}_{t}(A)-M_{t}(A)|\leq\textrm{dist}(X_{t},\widetilde{X}_{t})$
yields

$\mathbb{E}[|M_{t}(A)|]\leq\mathbb{E}[\textrm{dist}(X_{t},\widetilde{X}_{t})]+\sqrt{\mathbb{E}[\widetilde{M}_{t}(A)^{2}]}.$

Applying Theorem 2.1 subsequently gives

$\mathbb{E}[|M_{t}(A)|]\leq
n\rho^{t}+\sqrt{\mathbb{E}[\widetilde{M}_{t}(A)^{2}]}.$

Since the variables $\\{\widetilde{X}_{t}(i)\\}^{n}_{i=1}$ are positively
correlated under $\mu$,

$\mathbb{E}[\widetilde{M}_{t}(A)^{2}]\leq\frac{n^{2}}{4}\mathbb{E}[\widetilde{S}^{2}_{t}]=\frac{n^{2}}{4}\textrm{Var}[\widetilde{S}_{t}]=O(n),$

therefore we can get

$\mathbb{E}[|M_{t}(A)|]\leq ne^{-(1-\beta)kt/n}+O(\sqrt{n}).$

∎

Lemma 2.5 claims that for arbitrary two chains, if their magnetizations agree,
then there is a coupling that they can agree in $O(n\log n/k)$ time with high
probability. It becomes useful for $\beta\geq 1$ case.

######  Lemma 2.5.

For any $\sigma,\widetilde{\sigma}\in\Omega$ such that
$S(\sigma)=S(\widetilde{\sigma})$, there exists a coupling for
$(X_{t},\widetilde{X}_{t})$ with starting points
$(\sigma,\widetilde{\sigma})$,

$\lim_{n\to\infty}\mathbb{P}_{\sigma,\widetilde{\sigma}}\left[\min_{t}\\{t:X_{t}=\widetilde{X}_{t}\\}>\frac{\gamma
n\log n}{k}\right]=0,$

for some constant $\gamma=\gamma(\beta)>0$.

###### Proof.

For each time $t$ before updating $k$ vertices, rematch vertices of $X_{t}$
and $\widetilde{X}_{t}$ such that if $X_{t}(v)=\widetilde{X}_{t}(v)$, then
match $v$ from $X_{t}$ with $v$ from $\widetilde{X}_{t}$. If
$X_{t}(v)\neq\widetilde{X}_{t}(v)$, from $S_{t}=\widetilde{S}_{t}$ we have

$D_{t}:=|\\{v:(X_{t}(v),\widetilde{X}_{t}(v))=(1,-1)\\}|=|\\{w:(X_{t}(w),\widetilde{X}_{t}(w))=(-1,1)\\}|,$

therefore we can rematch vertices one to one from
$\\{v:(X_{t}(v),\widetilde{X}_{t}(v))=(1,-1)\\}$ to
$\\{w:(X_{t}(w),\widetilde{X}_{t}(w))=(-1,1)\\}$. We consider monotone
coupling on these chains, with the rematched vertices. Their magnetizations
remain agreed under the coupling, and the number of vertices whose spins are
not matched, $2D_{t}$, decreases. More precisely, $D_{t}$ is supermartingale,
and there exists $c=c(\beta)>0$ such that

$\mathbb{E}_{\sigma,\widetilde{\sigma}}[D_{t+1}|D_{t}]\leq\Big{(}1-\frac{ck}{n}\Big{)}D_{t}.$

Therefore, combining with the Markov inequality, we get

$\mathbb{P}_{\sigma,\widetilde{\sigma}}\left[\min_{t}\\{t:X_{t}=\widetilde{X}_{t}\\}>\frac{\gamma
n\log n}{k}\right]\leq\mathbb{P}_{\sigma,\widetilde{\sigma}}[D_{\gamma n\log
n/k}\geq 1]\leq n\exp(-c\gamma\log n).$

Choosing proper $\gamma=\gamma(\beta)$ makes the rightmost term go to $0$ as
$n\to\infty$. ∎

It is well known that the magnetization under the original Glauber dynamics
tends to go to zero, so the absolute value of it becomes supermartingale.
Similarly we need a bound to measure how much the magnetization changes by
randomized systematic scan dynamics.

######  Lemma 2.6.

(Magnetization estimate) For any given chain $X_{t}$ starting from $\sigma$,

$\Big{|}\mathbb{E}_{\sigma}[S_{1}]-\big{(}1-\frac{k}{n}\big{)}S(\sigma)-\frac{k}{n}\tanh\beta
S(\sigma)\Big{|}\leq\frac{2k}{n}\tanh\beta\frac{2k}{n}=O\Big{(}\frac{k^{2}}{n^{2}}\Big{)}.$
(13)

###### Proof.

Consider the intermediate states $Y_{0}=\sigma,...,Y_{k}=X_{1}$. For any
vertex selected to be updated, the probability that the new spin becomes $1$
is

$p_{+}\Big{(}S(Y_{i})\pm\frac{1}{n}\Big{)}=\frac{1+\tanh\beta(S(Y_{i})\pm
1/n)}{2},$

thus the expectation of the updated spin of the vertex is

$p_{+}\Big{(}S(Y_{i})\pm\frac{1}{n}\Big{)}-p_{-}\Big{(}S(Y_{i})\pm\frac{1}{n}\Big{)}=\tanh\beta\Big{(}S(Y_{i})\pm\frac{1}{n}\Big{)}$

and we know $|S(Y_{i})-S_{0}|\leq\frac{2i}{n}$.

Since $k$ vertices are chosen uniformly randomly among $n$ vertices at $t=0$,
the expected sum of spins of vertices which are not chosen to be updated is
$(n-k)S_{0}$. Therefore

$\begin{split}&(n-k)S_{0}+k\tanh\beta\Big{(}S_{0}-\frac{1}{n}-\frac{2(k-1)}{n}\Big{)}\\\
&\qquad\qquad\qquad\leq
n\mathbb{E}_{\sigma}[S_{1}]\leq(n-k)S_{0}+k\tanh\beta\Big{(}S_{0}+\frac{1}{n}+\frac{2(k-1)}{n}\Big{)},\end{split}$

which becomes Equation (13) by appealing $|\tanh x-\tanh y|\leq
2\tanh\left|(x-y)/2\right|$. ∎

Sometimes we need to investigate the magnetization not only for $(X_{t})$ but
for all its intermediates $(Y_{i})$. Since $|S(Y_{i+1})-S(Y_{i})|\leq 2/n$, we
can get an estimate for the time $\tau_{\textrm{mag}}:=\min\\{i\geq
0:S(Y_{i})=S(\widetilde{Y}_{i})\\}$. However, due to unavailable vertices, we
are not sure whether we can manipulate the coupling so that those two chains’
magnetization remain equal. The following lemma partially gives an answer for
such a case.

######  Lemma 2.7.

Assume $k=o(\sqrt{n})$. Suppose we have two chains $X_{t}$ and
$\widetilde{X}_{t}$(not necessarily independent) such that
$S_{0}>\widetilde{S}_{0}$. Define their intermediate states $\\{Y_{i}\\}$ and
$\\{\widetilde{Y}_{i}\\}$ such that
$(Y_{kt},\widetilde{Y}_{kt})=(X_{t},\widetilde{X}_{t})$ for all $t\geq 0$.
Consider $\tau_{\textrm{almost}}:=\min\\{i\geq
0:|S(Y_{i})-S(\widetilde{Y_{i}})|\leq 2/n\\}$ and
$\tau_{\textrm{exact}}:=\min\\{i\geq 0:S(Y_{i})=S(\widetilde{Y_{i}})\\}$ under
any given coupling. Then,

  1. (1)

There exists a coupling for intermediates from $\tau_{\textrm{exact}}$ to
$T:=\lceil\tau_{\textrm{exact}}/k\rceil$ which ensures
$S_{T}=\widetilde{S}_{T}$ with high probability.

  2. (2)

There exists a coupling for intermediates from $\tau_{\textrm{almost}}$ to
$T^{\prime}:=\lceil\tau_{\textrm{almost}}/k\rceil$ which ensures that
$|S_{T^{\prime}}-\widetilde{S}_{T^{\prime}}|\leq 4k/n$ with high probability,
for large enough $n$.

######  Remark.

Both $\tau_{\textrm{almost}}$ and $\tau_{\textrm{exact}}$ are defined on
intermediates. Lemma 2.7 implies that if the two magnetizations on
intermediates are matched, magnetizations on the original chains can be
matched soon with high probability. For the case (ii), Lemma 2.2 and Markov
inequality ensures the magnetization matching after $O(n/k)$ times.

###### Proof.

(i) Let $l:=\tau_{\textrm{exact}}\textrm{ (mod k)}$. At time
$i=\tau_{\textrm{exact}}$, rematch vertices according to their current spins
without considering its update history. For the remaining $(k-l)$ updates,
apply monotone coupling for $(Y_{i},\widetilde{Y}_{i})$: randomly choose one
of the available vertices from $Y_{i}$ and check the corresponding vertices of
$\widetilde{Y}_{i}$. If that vertex from $\widetilde{Y}_{i}$ is an unavailable
vertex, stop monotone coupling and run two Markov chains independently. If
not, update two corresponding vertices under rematched monotone coupling.

This coupling preserves the magnetization matching unless it choose
unavailable vertices during $(k-l)$ updates. In the worst case, the
probability that the monotone coupling does not stop at $i=j$ is
$(n-2j)/(n-j)=1-j/(n-j)$. After it survives, the probability that the coupling
does not stop at $i=(j+1)$ is $(n-2j-1)/(n-j-1)=1-j/(n-j-1)$. To summarize,
the probability that the coupling does not stop until $i=k$ is greater than or
equal to

$\Big{(}1-\frac{l}{n-l}\Big{)}\Big{(}1-\frac{l}{n-l-1}\Big{)}...\Big{(}1-\frac{l}{n-k}\Big{)}.$

This is greater than

$\Big{(}1-\frac{k}{n-k}\Big{)}^{k}\sim\exp\left(-\frac{k^{2}}{n-k}\right)\to
1.$ (14)

Since $k=o(\sqrt{n})$, there is a coupling that ensures
$\mathbb{P}[S_{T}=\widetilde{S}_{T}]\to 1$ as $n\to\infty$.
(ii) In case of $\tau_{\textrm{almost}}=\tau_{\textrm{exact}}$, there is
nothing to prove. Without loss of generality, suppose
$S(Y_{\tau_{\textrm{almost}}})-S(\widetilde{Y}_{\tau_{\textrm{almost}}})=2/n$.
Rematch vertices so that $Y_{\tau_{\textrm{almost}}}$ and
$\widetilde{Y}_{\tau_{\textrm{almost}}}$ are monotone. Apply monotone coupling
from $\tau_{\textrm{almost}}$ to $kT^{\prime}$ in the same way as (i): stop
the coupling and update independently when an unavailable vertex is chosen to
be updated. Monotone coupling succeeds to time $kT^{\prime}$ with probability
$1-O(k^{2}/n)$. Only one vertex is mismatched at time $\tau_{\textrm{almost}}$
so an analogous argument from Proposition 2.1 ensures that

$|S_{T^{\prime}}-\widetilde{S}_{T^{\prime}}|\leq\frac{2}{n}\left(1+\frac{\beta}{n}\right)^{k-l}\leq\frac{4}{n}.$

for large enough $n$. ∎

##  3\. Main results: high temperature regime

In this section, we prove Theorem 1.1. Assume $\beta<1$ throughout this
section.

###  3.1. Mixing time upper bound for $\beta<1$

Here we set the exact upper bound statement for the mixing time first.

######  Theorem 3.1.

Suppose $k=o(\sqrt[3]{n})$. Then

$\lim_{\gamma\to\infty}\limsup_{n\to\infty}d_{n}\Big{(}\frac{n\log
n}{2k(1-\beta)}+\frac{\gamma n}{k}\Big{)}=0.$ (15)

The proof of Theorem 3.1 consists of two parts: for any given two
configuration chains we couple their magnetizations in the first
part(magnetization matching phase), then set up another coupling so that their
spins exactly match with high probability(two-coordinate chain phase). Each
parts consists of two small steps, since two chains often cross each other
during $k$ updates. For any two chains $X_{t}$ and $\widetilde{X}_{t}$,

  1. (1)

Update $X_{t}$ and $\widetilde{X}_{t}$ under the grand coupling. In
$\frac{n\log n}{2k(1-\beta)}$ time,
$|S(X_{t})-S(\tilde{X}_{t})|\leq\frac{4k}{n}$ holds with high probability.

  2. (2)

Rematch vertices of $X_{t}$ and $\widetilde{X}_{t}$ and run two chains
independently. After additional $\gamma_{1}n/k$ time,
$S(X_{t})=S(\tilde{X}_{t})$ holds with high probability.

  3. (3)

Setup a coupling so that $S(X_{t})=S(\widetilde{X}_{t})$ remains true. Define
two-coordinate chain from $X_{t}$ and $\widetilde{X}_{t}$ (call them
$U^{X}_{t}$ and $U^{\tilde{X}}_{t}$). After additional $\gamma_{2}n/k$ time,
$|U^{X}_{t}-U^{\tilde{X}}_{t}|\leq k$ holds with high probability.

  4. (4)

Setup another coupling for $U^{X}_{t}$ and $U^{\widetilde{X}}_{t}$. After
additional $n/k$ time, $U^{X}_{t}=U^{\widetilde{X}}_{t}$ holds with high
probability, and this becomes equivalent to $X_{t}=\widetilde{X}_{t}$.

In particular, (1), (2), and (3) requires the restriction $k=o(\sqrt{n})$.
$k=o(\sqrt[3]{n})$ is necessary only for (4).

######  Theorem 3.2.

(magnetization matching phase)
Suppose $k=o(\sqrt{n})$. For any two configurations $\sigma$ and
$\widetilde{\sigma}$, there exists a coupling $(X_{t},\widetilde{X}_{t})$
starting with $X_{0}=\sigma$ and $\widetilde{X}_{0}=\widetilde{\sigma}$, which
satisfies $S_{t^{*}}=\widetilde{S}_{t^{*}}$ with probability
$1-O(\gamma^{-1/2})$, where $t^{*}=[2k(1-\beta)]^{-1}n\log n+\gamma n/k$.

###### Proof.

For convenience, define $t(\gamma):=[2k(1-\beta)]^{-1}n\log n+\gamma n/k$. For
any given configuration $\sigma$ and $\widetilde{\sigma}$ consider the
monotone coupling $(X_{t},\widetilde{X}_{t})$ with $X_{0}=\sigma$ and
$\widetilde{X}_{0}=\widetilde{\sigma}$. From Proposition 2.2,

$\mathbb{E}_{\sigma,\widetilde{\sigma}}\left[|S_{t(0)}-\widetilde{S}_{t(0)}|\right]\leq
c_{1}n^{-1/2}$ (16)

holds for some $c_{1}>0$. Without loss of generality assume
$S_{t(0)}\geq\widetilde{S}_{t(0)}$ and define a stopping time

$\tau_{\textrm{pre}}:=\min\\{t\geq t(0):|S_{t}-\widetilde{S}_{t}|\leq 4k/n\\}$

If $\tau_{\textrm{pre}}\leq t(\gamma)$, from time $\tau_{\textrm{pre}}$
rematch vertices according to their spins and update together under the
monotone coupling. Otherwise run two chains $(X_{t})$ and
$(\widetilde{X}_{t})$ under the monotone coupling until $t(\gamma)$ and run
independently for $t(\gamma)<t\leq\tau_{\textrm{pre}}$. Since
$S_{t}\geq\widetilde{S}_{t}$ for $t\leq\tau_{\textrm{pre}}$, the process
$(S_{t}-\widetilde{S}_{t})_{t(\gamma)\leq t<\tau_{\textrm{pre}}}$ has a non-
positive drift and is non-negative. $t<\tau_{\textrm{pre}}$ ensures
$S_{t+1}-\widetilde{S}_{t+1}>0$ so Lemma 2.1 and Lemma 2.2 can be applied,
provided that $k=o(\sqrt{n})$,

$\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau_{\textrm{pre}}>t(\gamma)|X_{t(0)},\widetilde{X}_{t(0)}]\leq\frac{c|S_{t(0)}-\widetilde{S}_{t(0)}|}{\frac{\sqrt{k}}{n}\sqrt{\frac{\gamma
n}{k}}}=\frac{c\sqrt{n}|S_{t(0)}-\widetilde{S}_{t(0)}|}{\sqrt{\gamma}}.$

Taking expectation over $X_{t(0)}$ and $\widetilde{X}_{t(0)}$ with Equation
(16) gives

$\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau_{\textrm{pre}}>t(\gamma_{1})]\leq
O(\gamma^{-1/2}_{1}).$ (17)

After we reach to $\tau_{\textrm{pre}}$, the number of plus signs of
$X_{\tau_{\textrm{pre}}}$ and $\widetilde{X}_{\tau_{\textrm{pre}}}$ are
different by at most $2k$, by the definition of $\tau_{\textrm{pre}}$. Define
another stopping time

$\tau_{\textrm{almost}}:=\min\\{i\geq
k\tau_{\textrm{pre}}:|S(Y_{i})-S(\widetilde{Y}_{i})|\leq 2/n\\}.$

From Lemma 2.7, there is a coupling from $\tau_{\textrm{almost}}$ to
$k\lceil\tau_{\textrm{almost}}/k\rceil$ with high probability that ensure the
magnetization difference is at most $4/n$. Without loss of generality suppose
$S(Y_{k\tau_{\textrm{pre}}})>S(\widetilde{Y}_{k\tau_{\textrm{pre}}})$.
Consider a sequence
$\\{S_{t}-\widetilde{S}_{t}+4k/n\\}_{t\geq\tau_{\textrm{pre}}}$ by running
$X_{t}$ and $\widetilde{X}_{t}$ independently, then we can apply Lemma 2.1 for
$\tau:=\min\\{t\geq k\tau_{\textrm{pre}}:S_{t}-\widetilde{S}_{t}+4k/n\geq
4k/n\\}$:

$\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau>\tau_{\textrm{pre}}+\gamma_{2}n/k]\leq\frac{4\frac{8k}{n}}{\frac{\sqrt{k}}{n}\sqrt{\gamma_{2}n}}=\frac{32\sqrt{k}}{\sqrt{\gamma_{2}n}}=O(\gamma_{2}^{-1/2}).$

However $k\tau\geq\tau_{\textrm{almost}}$, hence

$\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau_{\textrm{almost}}>k\tau_{\textrm{pre}}+\gamma_{2}n]\leq
O(\gamma_{2}^{-1/2}).$ (18)

From $\tau_{\textrm{almost}}$ we couple intermediates as we discussed in Lemma
2.7. Then we can have at time $t=T:=k\lceil\tau_{\textrm{almost}}/k\rceil$ the
magnetization difference is less then or equal to $4/n$ with high probability.
If it is $0$ then the magnetization matching phase is done. If not, we can
rematch vertices from time $t=T$ so that $X_{T}(v)-\widetilde{X}_{T}(v)$ are
either all non-negative or all non-positive. Then Proposition 2.2 and Markov
inequality ensures

$\begin{split}\mathbb{P}_{\sigma,\widetilde{\sigma}}[S_{t+T}=\widetilde{S}_{t+T}|\mathcal{F}_{T}]&\leq
n\mathbb{E}_{\sigma,\widetilde{\sigma}}\left[|S_{t+T}-\widetilde{S}_{t+T}|\big{|}|S_{T}-\widetilde{S}_{T}|\right]\\\
&\leq n\left(1-\frac{k(1-\beta)}{n}\right)^{t}|S_{T}-\widetilde{S}_{T}|\leq
4e^{-\frac{kt(1-\beta)}{n}}\end{split}$ (19)

Hence $t=\gamma_{3}n/k$ is enough to assure $S_{t+T}=\widetilde{S}_{t+T}$ with
high probability. To sum up, define $\tau_{\textrm{mag}}:=\min\\{t\geq
0:S_{t}=\widetilde{S}_{t}\\}$ then combining Equation (17), (18), and (19)
gives

$\begin{split}&\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau_{\textrm{mag}}<t(3\gamma)]\\\
&\qquad\geq\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau_{\textrm{pre}}<t(\gamma)]\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau_{\textrm{almost}}<k\tau_{\textrm{pre}}+\gamma
n]\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau_{\textrm{mag}}<\lceil\tau_{\textrm{almost}}/k\rceil+\gamma
n/k]\\\ &\qquad=1-O(\gamma^{-1/2})\to 1.\end{split}$ (20)

as $\gamma\to\infty$. ∎

After we reach $\tau_{\textrm{mag}}$, we transform two chains
$(X_{t},\widetilde{X}_{t})$ into another Markov chain
$(U_{t},\widetilde{U}_{t})$ and try to setup a coupling on $U_{t}$. Following
lemmas are necessary to move on to the two-coordinate chains
$(U_{t},\widetilde{U}_{t})$. We omit the proof of Lemma 3.1; See [LLP10] page
239 for the proof.

######  Lemma 3.1.

Suppose $k=o(n)$. For any subset $\Omega_{0}\subset\Omega=\\{-1,1\\}^{n}$ with
stationary distribution $\mu$,

$\max_{\sigma\in\Omega}\|\mathbb{P}_{\sigma}(X_{t_{0}+t}\in\cdot)-\mu\|_{TV}\leq\max_{\sigma_{0}\in\Omega_{0}}\|\mathbb{P}_{\sigma_{0}}(X_{t}\in\cdot)-\mu\|_{TV}+\max_{\sigma\in\Omega}\mathbb{P}_{\sigma}(X_{t_{0}}\notin\Omega_{0}).$

Consider the set $\Omega_{0}=\\{\sigma\in\Omega:|S(\sigma)|\leq 1/2\\}$. From
Lemma 2.4, there is a constant $\theta_{0}>0$ such that
$|\mathbb{E}_{\sigma}[S_{\theta_{0}n/k}]|\leq 1/4$. Since $k=o(n)$,

$\begin{split}\mathbb{P}_{\sigma}(X_{\theta_{0}n/k}\notin\Omega_{0})&=\mathbb{P}_{\sigma}(|S_{\theta_{0}n/k}|>1/2)\\\
&\leq\mathbb{P}_{\sigma}(|S_{\theta_{0}n/k}-\mathbb{E}_{\sigma}[S_{\theta_{0}n/k}]|>1/4)\leq
16\textrm{Var}_{\sigma}(S_{\theta_{0}n/k})=O(n^{-1}).\end{split}$

The last equation comes from the consequence of Lemma 2.3. Both the number of
positive spins and that of negative spins from any $\sigma_{0}\in\Omega_{0}$
are in between $n/4$ and $3n/4$. More formally, define

$u_{0}:=|\\{v\in V:\sigma_{0}(v)=1\\}|,\qquad v_{0}:=|\\{v\in
V:\sigma_{0}(v)=-1\\}|$

as numbers of each spins, and

$\Lambda_{0}:=\\{(u,v)\in\mathbb{Z}^{2}:n/4\leq u,v\leq 3n/4,u+v=n\\}.$

Then $\sigma_{0}\in\Omega_{0}$ if and only if $(u_{0},v_{0})\in\Lambda_{0}$.
With this definition we move on two-coordinate chain $(u,v)$ from the original
chain $(X_{t})$.

######  Definition 3.1.

(two-coordinate chain) Fix a configuration $\sigma_{0}\in\Omega_{0}$. For
$\sigma\in\Omega$, define

$\begin{split}U_{\sigma_{0}}(\sigma)&:=|\\{v\in
V:\sigma(v)=\sigma_{0}(v)=1\\}|\\\ V_{\sigma_{0}}(\sigma)&:=|\\{v\in
V:\sigma(v)=\sigma_{0}(v)=-1\\}|.\end{split}$

From now on, we shall write simply $U(\sigma)$ for $U_{\sigma_{0}}(\sigma)$
and $V(\sigma)$ for $V_{\sigma_{0}}(\sigma)$.
For any randomized systematic scan dynamics chain $\\{X_{t}\\}$, we can define
a process $(U_{t},V_{t})_{t\geq 0}$ by

$U_{t}=U(X_{t})\qquad\textrm{and}\qquad V_{t}=V(X_{t}).$

This is a Markov chain on $\\{0,...,u_{0}\\}\times\\{0,...,v_{0}\\}$. Denote
the stationary measure for this chain as $\pi_{2}$, and note that this chain
also determines the magnetization of the original chain $\\{X_{t}\\}$:

$S_{t}=\frac{2(U_{t}-V_{t})}{n}-\frac{u_{0}-v_{0}}{n}.$

The first thing to check is how the original Markov chain and two-coordinate
chain are related to each other. The total variation distances of the original
chain and that of the two-coordinate chain turn out to be equal. This is also
from [LLP10], page 241. We omit the proof.

######  Lemma 3.2.

Suppose $(X_{t})$ is the Glauber dynamics that starts from $\sigma_{0}$ and
$(U_{t},V_{t})$ is the corresponding two-coordinate chain that starts from
$(u_{0},v_{0})$. Then

$\|\mathbb{P}_{\sigma_{0}}(X_{t}\in\cdot)-\mu\|_{TV}=\|\mathbb{P}_{(u_{0},v_{0})}((U_{t},V_{t})\in\cdot)-\pi\|_{TV},$

where $\mu$ and $\pi$ are the stationary distributions of two chains,
respectively.

Thanks to Lemma 3.2, it suffices to bound from above the total variation
distance of the two-coordinate chain. Let’s determine $\sigma_{0}$ later and
consider the two coordinate chain first. The difference of $U$ becomes non-
negative supermartingale for a short period of time.

######  Lemma 3.3.

Suppose two configuration $\sigma$ and $\widetilde{\sigma}$ satisfy
$S(\sigma)=S(\widetilde{\sigma})$ and $U(\widetilde{\sigma})-U(\sigma)>0$.
Define

$\Xi_{1}:=\Big{\\{}\sigma^{*}\in\Omega:\min\\{U(\sigma^{*}),u_{0}-U(\sigma^{*}),V(\sigma^{*}),v_{0}-V(\sigma^{*})\\}\geq\frac{n}{16}\Big{\\}}$

and

$R(\sigma_{1},\sigma_{2}):=U(\sigma_{1})-U(\sigma_{2}),\qquad\qquad\tau_{k}=\min_{t\geq
0}\\{t:R(\widetilde{X}_{t},X_{t})\leq k\\}.$

There exists a Markovian coupling $(X_{t},\widetilde{X}_{t})_{0\leq
t\leq\tau_{k}}$ of the randomized systematic scan dynamics with initial state
$X_{0}=\sigma$ and $\widetilde{X}_{t}=\tilde{\sigma}$, such that

  1. (1)

$S_{t}=\widetilde{S}_{t}$ at any time $t$.

  2. (2)

For all $t\leq\tau_{k}$, intermediate states $\\{Y_{i}\\}_{0\leq i\leq
k\tau_{k}}$ and $\\{\widetilde{Y}_{i}\\}_{0\leq i\leq k\tau_{k}}$ such that
$Y_{ik}=X_{i}$ and $\widetilde{Y}_{ik}=\widetilde{X}_{i}$ for all $i\geq 0$
satisfies

$\mathbb{E}_{\sigma,\tilde{\sigma}}\left[R(\widetilde{Y}_{i+1},Y_{i+1})-R(\widetilde{Y}_{i},Y_{i})\Big{|}Y_{i},\widetilde{Y}_{i}\right]\leq
0,$

for any $i$.

  3. (3)

There exists a constant $c>0$ independent from $k$ and $n$ so that on the
event $\\{X_{t}\in\Xi,\widetilde{X}_{t}\in\Xi\\}$,

$\mathbb{P}_{\sigma,\tilde{\sigma}}\left[R(\widetilde{Y}_{i+1},Y_{i+1})-R(\widetilde{Y}_{i},Y_{i})\neq
0\Big{|}Y_{i},\widetilde{Y}_{i}\right]\geq c.$

######  Remark.

The lemma ensures the chain $R(\widetilde{Y}_{i},Y_{i})$ to be supermartingale
until it becomes less than $k$. Note that the statement works on all
intermediate states, not only for $R(\widetilde{X}_{t},X_{t})$.

###### Proof.

We couple $(X_{t},\widetilde{X}_{t})$ by coupling
$(Y_{i},\widetilde{Y}_{i})_{0\leq i\leq k\tau_{k}}$ for every $i$. From
$(Y_{i},\widetilde{Y}_{i})$ to $(Y_{i+1},\widetilde{Y}_{i+1})$, choose a
vertex $I_{i}$ randomly from $V\setminus\mathcal{N}_{i}$ and assign the next
spin $\mathcal{S}$ according to the probability from equation (2);

$\mathbb{P}(\mathcal{S}=1)=p_{+}(S(Y_{i})-Y_{i}(I_{i})/n).$

In other words, $Y_{i+1}$ becomes

$Y_{i+1}(v)=\begin{cases}Y_{i}(v)&v\neq I_{i},\\\
\mathcal{S}&v=I_{i}.\end{cases}$

For $\widetilde{Y}_{i+1}$, we select $\widetilde{I}_{i}$ randomly from
$\\{v:\widetilde{Y}_{i}(v)=Y_{i}(v)\\}\setminus\widetilde{\mathcal{N}}_{i}$
and set

$\widetilde{Y}_{i+1}(v)=\begin{cases}\widetilde{Y}_{i}(v)&v\neq\widetilde{I}_{i},\\\
\mathcal{S}&v=\widetilde{I}_{i}.\end{cases}$

Figure 1. All vertices except $\mathcal{N}_{i}$(which are not allowed to be
updated at the moment) are divided into four categories. Some vertices from
$B_{i}\cap\widetilde{A}_{i}$ and $C_{i}\cap\widetilde{D}_{i}$ can be also
included in $\mathcal{N}_{i}$.

The first condition of Lemma 3.3 is done since this coupling ensures
$S(Y_{i})=S(\widetilde{Y}_{i})$ for any $i$. Next, consider

$\begin{split}A_{i}&=|\\{v:\sigma_{0}(v)=1,Y_{i}(v)=1\\}\setminus\mathcal{N}_{i}|\\\
B_{i}&=|\\{v:\sigma_{0}(v)=1,Y_{i}(v)=-1\\}\setminus\mathcal{N}_{i}|\\\
C_{i}&=|\\{v:\sigma_{0}(v)=-1,Y_{i}(v)=1\\}\setminus\mathcal{N}_{i}|\\\
D_{i}&=|\\{v:\sigma_{0}(v)=-1,Y_{i}(v)=-1\\}\setminus\mathcal{N}_{i}|,\end{split}$

and $\widetilde{A}_{i}$, $\widetilde{B}_{i}$, $\widetilde{C}_{i}$,
$\widetilde{D}_{i}$ analogous way. From $S(Y_{i})=S(\widetilde{Y}_{i})$ we
have $A_{i}+C_{i}=\widetilde{A}_{i}+\widetilde{C}_{i}$ and
$B_{i}+D_{i}=\widetilde{B}_{i}+\widetilde{D}_{i}$.

Denote $R_{i}:=R(\widetilde{Y}_{i},Y_{i})$, and $i^{\prime}=i\textrm{(mod k)}$
for convenience. Then

$\begin{split}\mathbb{P}_{X_{0},\widetilde{X}_{0}}[R_{i+1}-R_{i}=-1|Y_{i},\widetilde{Y}_{i}]&=\frac{C_{i}}{n-i^{\prime}}\frac{\widetilde{A}_{i}}{\widetilde{A}_{i}+\widetilde{C}_{i}}p_{-}\Big{(}S(Y_{i})-\frac{1}{n}\Big{)}+\frac{B_{i}}{n-i^{\prime}}\frac{\widetilde{D}_{i}}{\widetilde{B}_{i}+\widetilde{D}_{i}}p_{+}\Big{(}S(Y_{i})+\frac{1}{n}\Big{)}\\\
\mathbb{P}_{X_{0},\widetilde{X}_{0}}[R_{i+1}-R_{i}=1|Y_{i},\widetilde{Y}_{i}]&=\frac{A_{i}}{n-i^{\prime}}\frac{\widetilde{C}_{i}}{\widetilde{A}_{i}+\widetilde{C}_{i}}p_{-}\Big{(}S(Y_{i})-\frac{1}{n}\Big{)}+\frac{D_{i}}{n-i^{\prime}}\frac{\widetilde{B}_{i}}{\widetilde{B}_{i}+\widetilde{D}_{i}}p_{+}\Big{(}S(Y_{i})+\frac{1}{n}\Big{)}.\end{split}$

Since $R_{i+1}-R_{i}\in\\{-1,0,1\\}$,

$\mathbb{E}_{X_{0},\widetilde{X}_{0}}[R_{i+1}-R_{i}|Y_{i},\widetilde{Y}_{i}]=\frac{\widetilde{C}_{i}-C_{i}}{n-i}p_{-}\Big{(}S(Y_{i})-\frac{1}{n}\Big{)}+\frac{\widetilde{B}_{i}-B_{i}}{n-i}p_{+}\Big{(}S(Y_{i})+\frac{1}{n}\Big{)}.$

For any $t\leq\tau_{k}-1$,

$k\leq R_{kt}=-(\widetilde{C}_{kt}-C_{kt})=-(\widetilde{B}_{kt}-B_{kt}),$

hence $\widetilde{C}_{i}-C_{i}$ and $\widetilde{B}_{i}-B_{i}$ are both less
then or equal to $0$ if $i\leq k\tau_{k}$ because both of them can only change
by $1$ as $i$ changes. The last condition of Lemma 3.3 follows from that
$p_{\pm}([-1,1])\subset[\epsilon,1-\epsilon]$ for some $\epsilon>0$. ∎

Lemma 3.3 satisfies all the conditions of Lemma 2.1, thus we can calculate how
much time we need for $\tau_{k}$. Without loss of generality let
$U_{\tau_{k}}<\widetilde{U}_{\tau_{k}}$. At each time $t\geq\tau_{k}$, rematch
the vertices of $A_{tk}$ to $\widetilde{A}_{tk}$ as many as possible, and do
the same procedure for $D_{tk}$ to $\widetilde{D}_{tk}$. Match
$\widetilde{B}_{tk}$ to $B_{tk}$, and $\widetilde{C}_{tk}$ to $C_{tk}$ as
well. Match the remaining vertices of $C_{tk}$ to those of
$\widetilde{A}_{tk}$, and those of $B_{tk}$ to $\widetilde{D}_{tk}$. All
vertices from $X_{t}$ and $\widetilde{X}_{t}$ are matched one to one; Now
update $k$ vertices arbitrarily from $X_{t}$ and corresponding vertices from
$\widetilde{X}_{t}$ under the Monotone coupling. Repeat the rematching process
according to their current spins and updates, unless
$U_{t}=\widetilde{U}_{t}$. This coupling has two remarks. First of all,
magnetizations remain coupled during the process, and secondly $R_{t}$ is non-
negative and non-increasing sequence.

######  Lemma 3.4.

Suppose $k=o(n^{1/3})$. Define
$\tau_{\textrm{match}}=\min\\{t\geq\tau_{k}:U_{t}=\widetilde{U}_{t}\\}$. Then
we have

$\mathbb{P}_{X_{\tau_{k}},\widetilde{X}_{\tau_{k}}}\Big{\\{}\tau_{\textrm{match}}>\tau_{k}+\frac{\gamma
n}{k}\Big{\\}}=O(k^{3/2}n^{-1/2}).$ (21)

###### Proof.

Suppose we apply the original (single site) Glauber dynamics to $X_{\tau_{k}}$
and $\widetilde{X}_{\tau_{k}}$ and let them $X^{\prime}_{t}$ and
$\widetilde{X}^{\prime}_{t}$. Then
$\\{R(X^{\prime}_{i},\widetilde{X}^{\prime}_{i})\\}_{i\geq k\tau_{k}}$ becomes
supermartingale. Lemma 2.1 ensures that the stopping time
$\tau^{\prime}_{R}:=\\{i\geq
k\tau_{k}:R(X^{\prime}_{i},\widetilde{X}^{\prime}_{i})=0\\}$ satisfies
$\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau^{\prime}_{R}>k\tau_{k}+A|R_{k\tau_{k}}]\lesssim\frac{k}{\sqrt{A}}$
for any large enough $A$. Now compare this result with systematic scan
dynamics case. Define $\tau_{R}:=\\{i\geq
k\tau_{k}:R_{i}=R(X_{i},\widetilde{X}_{i})=0\\}$. In the similar fashion as
Lemma 2.7, grouping by $k$ numbers of single site updates from $i=\tau_{k}$ to
$i=\tau_{k}+A$ generates $A/k$ times of systematic scan update and the
probability that none of the group update same vertex more than once equals
greater than $(e^{-k^{2}/n})^{A/k}=e^{-Ak/n}$. Hence

$\begin{split}\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau_{R}\leq
k\tau_{k}+A|R_{k\tau_{k}}]&\geq\mathbb{P}[\tau^{\prime}_{R}=\tau_{R}]\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau^{\prime}_{R}\leq
k\tau_{k}+A|R_{k\tau_{k}}]\\\ &\geq
e^{-Ak/n}\left(1-O\left(\frac{k}{\sqrt{A}}\right)\right).\end{split}$

Pick $A=\sqrt{nk}$, then the rightmost term becomes $1-O(k^{3/2}n^{-1/2})$,
which goes to $1$. For the original dynamics, after $i=\tau^{\prime}_{R}$,
$R(X^{\prime}_{i},\widetilde{X}^{\prime}_{i})$ remains zero. Hence modifying
the argument for the smallest multiple of $k$ greater than $\tau^{\prime}_{R}$
would give the same result on $\tau_{\textrm{match}}$. The proof is finished
by
$\mathbb{P}[\tau_{\textrm{match}}\geq\tau_{k}+\sqrt{n/k}]\geq\mathbb{P}[\tau_{\textrm{match}}>\tau_{k}+n/k]\geq\mathbb{P}[\tau_{\textrm{match}}>\tau_{k}+\gamma
n/k]$. ∎

We must introduce one more lemma to finish the two-coordinate chain phase. If
two arbitrary chain starting from $(\sigma,\widetilde{\sigma})$ reach to
$\tau_{\textrm{mag}}$, we have not only
$S_{\tau_{\textrm{mag}}}=\widetilde{S}_{\tau_{\textrm{mag}}}$ but also we have
a bound for $|U_{\tau_{\textrm{mag}}}-\widetilde{U}_{\tau_{\textrm{mag}}}|$.

######  Lemma 3.5.

For arbitrary $\sigma,\widetilde{\sigma}\in\Omega$, consider chains
$(X_{t},\widetilde{X}_{t})$ with $X_{0}=\sigma$ and
$\widetilde{X}_{0}=\widetilde{\sigma}$, and suppose the magnetization matching
phase is finished according to Theorem 3.2; i.e.
$S_{\tau_{\textrm{mag}}}=\widetilde{S}_{\tau_{\textrm{mag}}}$. At that moment,

$\mathbb{E}_{\sigma,\widetilde{\sigma}}\Big{[}|U_{\tau_{\textrm{mag}}}-\widetilde{U}_{\tau_{\textrm{mag}}}|\Big{]}=O(\sqrt{n})$

holds for $\sigma_{0}=\sigma$.

###### Proof.

Let $u_{0}$ be the number of $(+1)$ spins from $\sigma_{0}$.

$u_{0}=\frac{n(1+S(\sigma_{0}))}{2}.$

Then we can observe that

$U_{t}=M_{t}(A_{0})+\frac{u_{0}}{2}\qquad\textrm{ and
}\qquad\widetilde{U}_{t}=\widetilde{M}_{t}(A_{0})+\frac{u_{0}}{2},$

where $A_{0}=\\{v:\sigma(v)=1\\}$ ($M_{t}$ is defined at Lemma 2.4). The
difference of the two satisfies

$|U_{t}-\widetilde{U}_{t}|=|M_{t}(A_{0})-\widetilde{M}_{t}(A_{0})|\leq|M_{t}(A_{0})|+|\widetilde{M}_{t}(A_{0})|.$

Take expectation for $\sigma$ and $\widetilde{\sigma}$. By Lemma 2.4, we get
the result. ∎

######  Theorem 3.3.

(two-coordinate chain phase)
Suppose $k=o(\sqrt[3]{n})$. Consider $(X_{t},\widetilde{X_{t}})$ which starts
from $(\sigma,\widetilde{\sigma})$. Evolve the chain as given in Theorem 3.2
and suppose $\tau_{\textrm{mag}}\leq t_{1}+\gamma n/k$ for some $\gamma$. Then
their two-coordinate chains $U_{t}$ and $\widetilde{U}_{t}$ match after
additional $2\gamma n/k$ time with high probability.

###### Proof.

Recall the definition

$\Xi_{1}:=\Big{\\{}\sigma:\min\\{U(\sigma),u_{0}-U(\sigma),V(\sigma),v_{0}-V(\sigma)\\}\geq\frac{n}{16}\Big{\\}}$

and let $H(t):=\\{(X_{t},\widetilde{X}_{t})\in\Xi_{1}\times\Xi_{1}\\}$. The
coupling that we suggested makes $(X_{t},\widetilde{X}_{t})$ remain in $H(t)$
with high probability. Define

$D:=\bigcup_{t\in[t(\gamma),t(3\gamma)]}\\{|M_{t}(A_{0})|\geq
n/32\\}\qquad\textrm{and}\qquad\delta:=\sum_{t\in[t(\gamma),t(3\gamma)]}\mathbbm{1}_{M_{t}(A_{0})>n/64}.$

Since $|M_{t+1}(A_{0})-M_{t}(A_{0})|\leq k$, if $|M_{t_{0}}(A_{0})|>n/32$ then
$|M_{t}(A_{0})|>n/64$ for all $t$ in any interval of length $\frac{n}{64k}$
containing $t_{0}$. Therefore $D\subset\\{\delta>n/64k\\}$ and

$\mathbb{P}_{\sigma,\widetilde{\sigma}}(D)\leq\mathbb{P}_{\sigma,\widetilde{\sigma}}(\delta>n/64k)\leq\frac{ck\mathbb{E}_{\sigma,\widetilde{\sigma}}[\delta]}{n}.$

Since $X_{t}$ and $\widetilde{X}_{t}$ has finished the magnetization phase,
from Lemma 2.4, provided that $t\geq t(\gamma)$, we have

$\mathbb{P}_{\sigma,\widetilde{\sigma}}(|M_{t}(A_{0})|>n/64)\leq\frac{64\mathbb{E}_{\sigma,\widetilde{\sigma}}[M_{t}(A_{0})]}{n}=O(n^{-1}),$

thus $\mathbb{E}_{\sigma,\widetilde{\sigma}}[\delta]=O(\gamma)$. Therefore,
$\mathbb{P}_{\sigma,\widetilde{\sigma}}(D)=O(\gamma k/n)$. Similar procedure
for $\widetilde{M}_{t}(A_{0})$ also gives
$\mathbb{P}_{\sigma,\widetilde{\sigma}}(\widetilde{D})=O(\gamma k/n)$. Suppose
$U_{t}\leq n/16$. Then $u_{0}-U_{t}\geq 3n/16$ as we are assuming $u_{0}\geq
n/4$. This implies

$|M_{t}(A_{0})|=|U_{t}-(u_{0}-U_{t})|\geq(u_{0}-U_{t})-U_{t}\geq\frac{n}{8}.$

Similarly we can get the same result from $(u_{0}-U_{t})\leq n/16$. This
argument is also applicable for $V_{t}$ and $v_{0}-V_{t}$. Therefore,

$H(t)^{c}\subset\\{|M_{t}(A_{0})|\geq
n/16\\}\cup\\{|\widetilde{M}_{t}(A_{0})|\geq n/16\\}$

and finally,

$\mathbb{P}_{\sigma,\widetilde{\sigma}}\Big{(}\bigcup_{t\in[t(\gamma),t(3\gamma)]}H(t)^{c}\Big{)}\leq\mathbb{P}_{\sigma,\widetilde{\sigma}}(D)+\mathbb{P}_{\sigma,\widetilde{\sigma}}(\widetilde{D})=O(\gamma
k/n).$

Now consider the event

$H=\bigcap_{t\in[t(\gamma),t(3\gamma)]}H(t).$

Combining Lemma 2.1 and 3.3 gives

$\mathbb{P}_{\sigma,\widetilde{\sigma}}\big{[}\tau_{k}>t(2\gamma)|X_{t(\gamma)},\widetilde{X}_{t(\gamma)}\big{]}\leq\frac{c|R_{t(\gamma)}|}{\sqrt{n\gamma}},$

taking expectation over $X_{t(\gamma)}$ and $\widetilde{X}_{t(\gamma)}$ with
Lemma 3.5,

$\mathbb{P}_{\sigma,\widetilde{\sigma}}\big{[}\tau_{k}>t(2\gamma)\big{]}\leq
O(\gamma^{-1/2}).$

When the event $\tau_{k}\leq t_{3}+\gamma n/k$ happens, applying the last
coupling with Theorem 3.4 yields

$\mathbb{P}_{\sigma,\widetilde{\sigma}}\big{[}\tau_{\textrm{match}}>\tau_{k}+\gamma
n/k\big{]}\leq O(\gamma^{-1}).$

To sum up,

$\mathbb{P}_{\sigma,\widetilde{\sigma}}\big{[}\tau_{\textrm{match}}>t(3\gamma))\leq
O(\gamma^{-1/2}\big{]}.$

∎

###### Proof.

(of the theorem 3.1)
From Lemma 3.1 and Lemma 3.2, we have

$\begin{split}d(\theta_{0}n/k+t)&\leq\max_{\sigma_{0}\in\Omega_{0}}\big{\|}\mathbb{P}_{\sigma_{0}}(X_{t}\in\cdot)-\mu\big{\|}_{TV}+O(n^{-1})\\\
&=\max_{(u,v)\in\Lambda_{0}}\big{\|}\mathbb{P}_{(u,v)}((U_{t},V_{t})\in\cdot)-\pi\big{\|}_{TV}+O(n^{-1}).\end{split}$

Start from two chains $(X_{t},\widetilde{X}_{t})$. Define an event
$G:=\\{\tau_{\textrm{mag}}<t(\gamma)\\}$, then thanks to the theorem 3.2,

$\mathbb{P}_{\sigma,\widetilde{\sigma}}(G^{c})=O(\gamma^{-1/2}).$ (22)

From Theorem 3.3, we also have

$\mathbb{P}_{\sigma,\widetilde{\sigma}}(H^{c}|G)=O(\gamma k/n)$ (23)

and

$\mathbb{P}_{\sigma,\widetilde{\sigma}}(\tau_{\textrm{match}}>t(3\gamma)|H,G)\leq
O(\gamma^{-1/2}).$ (24)

Finally, when the event $G$, $H$, $\\{\tau_{\textrm{match}}<t(3\gamma)\\}$
happen, Equation (22), (23), and (24) give

$d(t_{4})\leq\mathbb{P}_{\sigma,\widetilde{\sigma}}[\tau_{\textrm{match}}>t_{4}]+O(n^{-1})\leq
O(\gamma^{-1/2})+O(\gamma k/n)+O(n^{-1})\to 0.$

This is possible because we take limit $n\to\infty$ first and then
$\gamma\to\infty$. ∎

###  3.2. Mixing time Lower bound for $\beta<1$

######  Theorem 3.4.

Suppose $k=o(\sqrt{n})$. Then

$\lim_{\gamma\to\infty}\liminf_{n\to\infty}d_{n}\Big{(}\frac{n\log
n}{2k(1-\beta)}-\frac{\gamma n}{k}\Big{)}=1.$

###### Proof.

It is enough to display a suitable lower bound on the distance between $S_{t}$
and the stationary distribution, as $(S_{t})$ is a projection of $(X_{t})$. To
be more precise, we consider an intermediate sequence $\\{Y_{i}\\}$ of
$\\{X_{t}\\}$ and then suggest a lower bound for $S(Y_{i})$.
Let $i^{\prime}:=i\textrm{(mod k)}$ and $k^{+},k^{-}$ be the number of
unavailable vertices at each time $i$. We have $k^{+}+k^{-}=i^{\prime}$ and
$k^{+},k^{-}\geq 0$. The drift of $S(Y_{i})$ becomes

$\mathbb{E}_{s_{0}}[S(Y_{i+1})-S(Y_{i})|S(Y_{i})=s,k^{\pm}]=\frac{1}{n}\left\\{\frac{n(1-s)-2k^{-}}{n-i^{\prime}}p_{+}\left(s+\frac{1}{n}\right)-\frac{n(1+s)-2k^{+}}{n-i^{\prime}}p_{-}\left(s-\frac{1}{n}\right)\right\\}.$

If $s\geq 0$, then the equation is equal to

$\mathbb{E}_{s_{0}}[S(Y_{i+1})-S(Y_{i})|S(Y_{i})=s]\geq\frac{1}{2n(n-i^{\prime})}\left\\{-2ns-4k+2n\tanh{\beta
s}-O(1)\right\\}.$

Since

$\frac{1}{n(n-i^{\prime})}=\frac{1}{n^{2}}+O\left(\frac{k}{n^{3}}\right),$

combining with the Taylor expansion of $\tanh$, we have

$\mathbb{E}_{s_{0}}[S(Y_{i+1})-S(Y_{i})|S(Y_{i})=s]\geq-\frac{(1-\beta)s}{n}-\frac{s^{3}}{2n}-O\left(\frac{k}{n^{2}}\right).$

From the symmetry of magnetization or direct calculation, we can check that
the equation is true for $s\leq 0$ as well. Hence, when $|S(Y_{i})|\geq 2/n$,

$\mathbb{E}_{s_{0}}\left[|S(Y_{i+1})|\big{|}S(Y_{i})\right]\geq\left(1-\frac{1-\beta}{n}\right)|S(Y_{i})|-\frac{|S(Y_{i})|^{3}}{2n}-O\left(\frac{k}{n^{2}}\right).$

This is clearly true when $S(Y_{i})=0$ or $|S(Y_{i})|=1/n$ as well. Define
$\eta:=1-\frac{1-\beta}{n}$ and $Z_{i}=|S(Y_{i})|\eta^{-i}$. For large enough
$n$ the inequality becomes

$\mathbb{E}_{Z_{0}}[Z_{i+1}]\geq
Z_{i}-\frac{\eta^{-i}[|S(Y_{i})|^{3}+O(k/n)]}{n}.$

As $|S(Y_{i})|\leq 1$,

$\mathbb{E}_{Z_{0}}[Z_{i}-Z_{i+1}]\leq\frac{\eta^{-i}[|S(Y_{i})|^{2}+O(k/n)]}{n}.$
(25)

Now, we want to estimate $\mathbb{E}_{s_{0}}[|S(Y_{i})|^{2}]$. First of all,

$\left(\mathbb{E}_{s_{0}}[S(Y_{i})]\right)^{2}=\left|\mathbb{E}_{s_{0}}[S(Y_{i-i^{\prime}})]+\mathbb{E}_{s_{0}}[S(Y_{i})-S(Y_{i-i^{\prime}})]\right|^{2}$
(26)

The absolute value of the first term of Equation (26) is bounded by
$2|s_{0}|(1-k(1-\beta)/n)^{(i-i^{\prime})/k}\leq 2|s_{0}|\eta^{i-i^{\prime}}$.
The second term of Equation (26) satisfies

$|\mathbb{E}_{s_{0}}[S(Y_{i})-S(Y_{i-i^{\prime}})]|=|\mathbb{E}_{s_{0}}[\mathbb{E}_{s_{0}}[S(Y_{i})-S(Y_{i-i^{\prime}})|Y_{i-i^{\prime}}]]|\leq\mathbb{E}_{s_{0}}\left[\frac{c_{1}k}{n}|S(Y_{i-i^{\prime}})|+\frac{c_{2}k^{2}}{n^{2}}\right],$

which is bounded by $c_{3}|s_{0}|k\eta^{i-i^{\prime}}/n+O(k^{2}/n^{2})$. For
the variance,
$\textrm{Var}[S(Y_{i})]=\textrm{Var}[S(Y_{i-i^{\prime}})]+\textrm{Var}[S(Y_{i})|S(Y_{i-i^{\prime}})]\leq
O(1/n)+O(k/n^{2})=O(1/n)$. Hence

$\begin{split}\mathbb{E}_{s_{0}}[|S(Y_{i})|^{2}]&=\left(\mathbb{E}_{s_{0}}[S(Y_{i})]\right)^{2}+\textrm{Var}_{s_{0}}[S(Y_{i})]\leq\left[c_{4}|s_{0}|\eta^{i-i^{\prime}}+O\left(\frac{k^{2}}{n^{2}}\right)\right]^{2}+O\left(\frac{1}{n}\right)\\\
&\leq
c_{5}|s_{0}|^{2}\eta^{2(i-k)}+\frac{c_{6}k^{2}|s_{0}|\eta^{i-k}}{n^{2}}+O\left(\frac{k^{4}}{n^{4}}+\frac{1}{n}\right).\end{split}$

Taking expectation on Equation (25) becomes

$\mathbb{E}_{Z_{0}}[Z_{i}-Z_{i+1}]\leq\frac{c_{5}|s_{0}|^{2}\eta^{i-2k}}{n}+\frac{c_{6}k^{2}|s_{0}|\eta^{-k}}{n^{3}}+\eta^{-i}O\left(\frac{k}{n^{2}}\right).$
(27)

Let $i^{*}=n\log n/2(1-\beta)-\gamma n/(1-\beta)$ and sum up Equation (27) for
all $i=0,1,...,i^{*}$.

$s_{0}-\mathbb{E}_{s_{0}}[Z_{i^{*}}]\leq\frac{c_{5}|s_{0}|^{2}\eta^{-2k}}{n(1-\eta)}+\frac{c_{7}k^{2}|s_{0}|\eta^{-k}\log
n}{n^{2}}+O\left(\frac{k}{\sqrt{n}}\right).$

Because $\eta^{-i^{*}}\leq n^{1/2}$, $\eta^{-k}\to 1$ as $n\to\infty$, two
terms vanish as $n\to\infty$. For large $n$, if we choose
$s_{0}<\frac{1-\beta}{3c_{5}}$ then the right side of the equation is less
than $s_{0}/2$. If so,

$\mathbb{E}_{s_{0}}[|S(Y_{i^{*}})]\geq\frac{s_{0}\eta^{i^{*}}}{2}\geq\frac{s_{0}e^{\gamma}}{2\sqrt{n}}=:A$

As we discussed before, since $\textrm{Var}_{s_{0}}[S(Y_{i^{*}})]=O(n^{-1})$,

$\mathbb{P}_{s_{0}}(|S(Y_{i^{*}})|<A/2)\leq\mathbb{P}_{s_{0}}(|S(Y_{i^{*}})-\mathbb{E}_{s_{0}}S(Y_{i^{*}})|>A/2)\leq\frac{4\textrm{Var}_{s_{0}}[S(Y_{t^{*}})]}{A^{2}}\leq
O(e^{-2\gamma}s^{-2}_{0}).$

On the other point of view, $\mathbb{E}_{\pi}[S]=0$ and
$\textrm{Var}_{\pi}[S]=O(n^{-1})$. Therefore

$\mathbb{P}_{\pi}(|S|>A/2)\leq\frac{4\textrm{Var}_{\pi}[S]}{A^{2}}=O(e^{-2\gamma}s^{-2}_{0}).$

Finally, let $\mathcal{A}:=[-A/2,A/2]$. Then

$\|\mathbb{P}_{s_{0}}(S_{i^{*}/k}\in\cdot)-\pi\|_{\textrm{TV}}\geq\pi(\mathcal{A})-\mathbb{P}_{s_{0}}(|S_{i^{*}/k}|\leq
A/2)\geq 1-O(e^{-2\gamma}s^{2}_{0}).$

Taking $\gamma\to\infty$ ensures the total variation distance goes to $1$.

∎

######  Remark.

Theorem 3.4 is only available when $k=o(\sqrt{n})$. Without this condition we
can derive another lower bound under $k=o(n)$. This work can be done with
generalized Wilson’s lemma, which is from [NN18].

$\lim_{\gamma\to\infty}\liminf_{n\to\infty}d_{n}\Big{(}\frac{n\log
n}{2k(1-\beta)}-\frac{n\log k}{2k(1-\beta)}-\frac{\gamma n}{k}\Big{)}=1.$

However, $\log k=o(\log n)$ condition is required for cutoff when Equation
Remark is combined with the upper bound result.

##  4\. Main results: critical temperature regime

In this section we show that the mixing time under the randomized systematic
scan dynamics is of order $n^{3/2}/k$ when $\beta=1$. Assume $\beta=1$
throughout this section.

###  4.1. Mixing time Upper bound for $\beta=1$

######  Theorem 4.1.

Suppose $\beta=1$. If $k=o(\sqrt[4]{n})$ then $t_{mix}=O(n^{3/2}/k)$.

###### Proof.

The proof consists of two steps. With some positive probability, for any given
two chains, their magnetization values eventually agree in time of order
$n^{3/2}/k$. After two magnetizations coalesce, two chains can be matched by
using the same matching method used in the case of $\beta<1$. Markov
inequality and Lemma 2.5 ensures the exact match can be done in $O(n\log n/k)$
time for the second step. It is enough to show that the magnetizations of two
arbitrary chains can be matched in time of order $n^{3/2}/k$. Recall Theorem
2.6; for any chain $X_{t}$ we have

$\Big{|}\mathbb{E}_{\sigma}[S_{1}]-\left(1-\frac{k}{n}\right)S_{0}-\frac{k}{n}\tanh\beta
S_{0}\Big{|}\leq\frac{2k}{n}\tanh\beta\frac{2k}{n}\leq\frac{4k^{2}}{n^{2}}.$

Define $\tau_{0}=\min\\{t\geq 0:|S_{t}|\leq 2\sqrt[3]{k/n}\\}$. For any
$t<\tau_{0}$, as $|S_{t+1}-S_{t}|\leq 2k/n<2\sqrt[3]{k/n}$, the sign of both
$S_{t}$ and $S_{t+1}$ are the same. In this case, we can apply the absolute
value on the magnetization:

$\mathbb{E}_{\sigma}\big{[}|S_{t+1}|\big{|}S_{t}\big{]}\leq\big{(}1-\frac{k}{n}\big{)}|S_{0}|+\frac{k}{n}\tanh|S_{0}|+\frac{4k^{2}}{n^{2}}.$

Let
$\xi_{t}=\mathbb{E}\big{[}|S_{t}|\big{|}\mathbbm{1}\\{\tau_{0}>t\\}\big{]}$.
Then the above becomes

$\xi_{t+1}\leq\Big{(}1-\frac{k}{n}\Big{)}\xi_{t}+\frac{k}{n}\tanh\xi_{t}+\frac{4k^{2}}{n^{2}}.$

Thus if $\xi_{t}>\epsilon$, there exist $c_{\epsilon}>0$ which satisfies

$\xi_{t+1}-\xi_{t}\leq-\frac{kc_{\epsilon}}{n},$

provided $k=o(n)$. Therefore in $t_{*}=O(n/k)$ time we can get $\xi_{t}\leq
1/4$, for all $t\geq t_{*}$.
Taylor series of $\tanh$ gives

$\xi_{t+1}\leq\xi_{t}-\frac{k\xi^{3}_{t}}{4n}+\frac{4k^{2}}{n^{2}}$

for $t\geq t_{*}$. Therefore for some large enough $n$, $\xi_{t}$ is a
decreasing sequence. It is enough to consider the cases in which $n$ is large
enough. Consider a decreasing sequence $b_{i}=(1/4)2^{-i}$ and define
$u_{i}:=\min\\{t>t_{*}:\xi_{t}\leq b_{i}\\}$. We can check that
$b_{i+1}<\xi_{t}\leq b_{i}$ when $u_{i}\leq t<u_{i+1}$. Now, for any
$t\in(u_{i},u_{i+1}]$,

$\xi_{t+1}\leq\xi_{t}-\frac{kb^{3}_{i}}{32n}+O\Big{(}\frac{k^{2}}{n^{2}}\Big{)}$

holds, and summing up for all $t\in(u_{i},u_{i+1}]$ gives

$u_{i+1}-u_{i}\leq\frac{16n}{kb^{2}_{i}}[1+O(b^{-3}_{i}n^{-1}k)].$

Now, let $i_{0}=\min\\{i:b_{i}\leq n^{-1/4}\\}$. For any $i<i_{0}$, we have
$O(b^{-3}_{i}n^{-1}k)=o(1)$ with the assumption $k=o(\sqrt[4]{n})$. Therefore,
for large $n$ and $0\leq i<i_{0}$,

$u_{i+1}-u_{i}\leq\frac{32n}{kb^{2}_{i}}.$ (28)

Summing up Equation (28) for all $i=0,...,i_{0}$ becomes

$u_{i_{0}}-u_{0}\leq\sum^{i_{0}-1}_{i=0}\frac{32n}{kb^{2}_{i}}\leq\frac{cn}{kb^{2}_{i_{0}-1}}=O(n^{3/2}k^{-1}).$

Since $u_{0}=t_{*}=O(n/k)$, finally we derive

$u_{i_{0}}\leq
O\Big{(}\frac{n^{3/2}}{k}\Big{)}+O\Big{(}\frac{n}{k}\Big{)}=O\Big{(}\frac{n^{3/2}}{k}\Big{)}.$

The $O(n/k)$ term comes from that $u_{0}=t_{*}=O(n/k)$. Now let
$r_{n}=c_{1}n^{3/2}k^{-1}$, then

$\mathbb{E}_{\sigma}\big{[}|S_{r_{n}}|\mathbbm{1}\\{\tau_{0}>r_{n}\\}\big{]}=O(n^{-1/4}).$
(29)

Appealing to Lemma 2.1 on $|S_{t}|$ gives

$\mathbb{P}_{\sigma}\Big{(}\tau_{0}>r_{n}+\frac{\gamma
n^{3/2}}{k}\Big{|}X_{r_{n}}\Big{)}\leq\frac{C|S_{r_{n}}|}{\sqrt{\frac{k}{n^{2}}}\sqrt{\frac{\gamma
n^{3/2}}{k}}}=\frac{C|S_{r_{n}}|}{\sqrt{\gamma}n^{1/4}}$ (30)

Therefore, multiply $\mathbbm{1}\\{\tau_{0}>r_{n}\\}$ on Equation (30) and
taking expectation with gives

$\mathbb{P}_{\sigma}\Big{(}\tau_{0}>r_{n}+\frac{\gamma
n^{3/2}}{k}\Big{)}=O(\gamma^{-1/2}).$

Since $r_{n}=O(n^{3/2}k^{-1})$, we can reach $\tau_{0}$ in $O(n^{3/2}k^{-1})$
time with high probability.

Now consider two chains $\\{X_{t}\\}$ and $\\{\widetilde{X}_{t}\\}$. Without
loss of generality assume $\tau_{0}$ of $\\{X_{t}\\}$ is greater than that of
$\\{\widetilde{X}_{t}\\}$. Define $\tau_{\textrm{cross}}$ with respect to
their intermediates as in Lemma 2.7. We know that

$\mathbb{P}_{\sigma,\widetilde{\sigma}}\left(\tau_{0}>\frac{\gamma_{1}n^{3/2}}{k}\right)\leq
O(\gamma_{1}^{-1/2}).$

In case of $\tau_{\textrm{cross}}<k\tau_{0}$ then by Lemma 2.7 we can couple
the magnetizations with a positive probability. This proves
$\mathbb{P}[\tau_{\textrm{mag}}\leq\tau_{0}]$ is uniformly bounded above from
$0$. On the other hand, if $\tau_{\textrm{cross}}>\tau_{0}$, that means both
$S_{\tau_{0}}$ and $\widetilde{S}_{\tau_{0}}$ are in
$[-2\sqrt[3]{k/n},2\sqrt[3]{k/n}]$ with high probability. Define

$Z_{t}:=S_{t}-\widetilde{S}_{t}+\frac{4k}{n}$

and run two chains $X_{t}$ and $\widetilde{X}_{t}$ independently from
$\tau_{0}$. Set a stopping time
$\tau_{1}=\min\\{t\geq\tau_{0}:Z_{t}\leq\frac{4k}{n}\\}$. From the assumption
$\tau_{\textrm{cross}}>\tau_{0}$ and $\tau_{\textrm{cross}}$ for $X_{t}$ is
greater, we have $Z_{\tau_{0}}>\frac{4k}{n}$. Apply Lemma 2.1 on $Z_{t}$ gives

$\mathbb{P}_{\sigma,\widetilde{\sigma}}\left[\tau_{1}>\frac{n^{3/2}\gamma}{k}+\tau_{0}\big{|}Z_{\tau_{0}}\right]\lesssim\frac{Z_{\tau_{0}}}{\sqrt{\frac{k}{n^{2}}}\sqrt{\frac{n^{3/2}\gamma}{k}}}\lesssim\frac{k^{1/3}}{n^{1/12}\gamma^{1/2}}\lesssim\gamma^{-1/2}.$

However, $k\tau_{1}\leq k\tau_{\textrm{cross}}$ by definition, so we can
capture the time $\tau_{\textrm{cross}}$ and follow the coupling from Lemma
2.7. In sum up, $\mathbb{P}[\tau_{\textrm{mag}}>\frac{\gamma
n^{3/2}}{k}]<c<1$. This is enough to show $t_{\textrm{mix}}=O(n^{3/2}/k)$. ∎

###  4.2. Mixing time Lower bound for $\beta=1$

######  Theorem 4.2.

There exists a constant $c>0$ such that $t_{mix}\geq cn^{3/2}/k$.

###### Proof.

Since the magnetization chain $S_{t}$ depends on the original chain, it is
enough to prove for the lower bound of the mixing time of $S_{t}$. If we
denote $S$ to be a magnetization in equilibrium, then the sequence $n^{1/4}S$
converges to a non-trivial limit law as $n\to\infty$, according to [SG73] and
[Ellis66](See Theorem V.9.5). Therefore, pick $A>0$ such that

$\mu\Big{(}|S|\leq An^{-1/4}\Big{)}\geq 3/4,$

and also let $s_{0}:=2An^{-1/4}$. Now define $\widetilde{S_{t}}$ as a chain
with the same transition probability as $S_{t}$, except $s=s_{0}$.

Define $Z_{t}=\widetilde{S}_{0}-\widetilde{S}_{t\wedge\tau}$, where
$\tau:=\min\\{t\geq 0:\widetilde{S}_{t}\leq An^{-1/4}\\}$. When
$An^{-1/4}<\widetilde{S}_{t}=s^{\prime}<s_{0}$, the conditional distribution
of $\widetilde{S}_{t+1}$ is the same to that of $S_{t+1}$ in case of
$S_{t}=s^{\prime}$. Therefore,

$\mathbb{E}_{s_{0}}\Big{[}\widetilde{S}_{t+1}|\widetilde{S}_{t}=s\Big{]}=\mathbb{E}_{s_{0}}\Big{[}S_{t+1}|S_{t}=s\Big{]}\geq
s-\frac{c_{0}ks^{3}}{n}$

holds for some constant $c_{0}$. From this, in terms of $Z_{t}$,

$\mathbb{E}[Z_{t+1}|\mathcal{F}_{t}]\leq Z_{t}+\frac{c_{0}k}{n}S^{3}_{t}.$

Now, consider the second moment of $Z_{t+1}$;

$\mathbb{E}_{s_{0}}\Big{[}Z^{2}_{t+1}|\mathcal{F}_{t}\Big{]}=\textrm{Var}(Z_{t+1}|\mathcal{F}_{t})+\Big{(}\mathbb{E}_{s_{0}}[Z_{t+1}|\mathcal{F}_{t}]\Big{)}^{2}.$
(31)

Lemma 2.2 ensures

$\textrm{Var}(Z_{t+1}|\mathcal{F}_{t})\leq O\Big{(}\frac{k}{n^{2}}\Big{)}.$

The last term of Equation (31), for $t<\tau$, there is another constant
$c_{1}=c_{1}(A)$ such that

$\mathbb{E}^{2}_{s_{0}}[Z_{t+1}|\mathcal{F}_{t}]\leq
Z^{2}_{t}+2\frac{c_{0}k}{n}Z_{t}\widetilde{S}^{3}_{t}+\frac{c^{2}_{0}k^{2}\widetilde{S}^{6}_{t}}{n^{2}}\leq
Z^{2}_{t}+\frac{c_{1}k}{n^{2}}.$

In conclusion, we can get

$\mathbb{E}_{s_{0}}\Big{[}Z^{2}_{t+1}-Z^{2}_{t}|\mathcal{F}_{t}\Big{]}\leq\frac{c_{A}k}{n^{2}}.$

This means $\mathbb{E}_{s_{0}}[Z^{2}_{t}]\leq\frac{c_{A}kt}{n^{2}}$, which
leads to

$c_{A}n^{-2}t\leq\mathbb{E}_{s_{0}}[Z^{2}_{t}]\leq\mathbb{E}_{s_{0}}[Z^{2}_{t}\mathbbm{1}_{\\{\tau\leq
t\\}}]\leq\frac{A^{2}}{\sqrt{n}}\mathbb{P}_{s_{0}}(\tau\leq t)$

Take $t=(A^{2}/4c_{A})n^{3/2}/k$. Then

$\mathbb{P}_{s_{0}}\Big{(}S_{t}\leq An^{-1/4}\Big{)}\leq\frac{1}{4},$

which proves $d(cn^{3/2}/k)\geq 1/2$. ∎

##  5\. Main results: low temperature regime

We assume $\beta>1$ throughout this section. It is well known that the mixing
time on low temperature regime is exponential, as shown by the Cheeger
constant in [GWL66]. To this end [LLP10] suggested the restricted Glauber
dynamics holds only for $\Omega^{+}:=\\{\sigma\in\Omega:S(\sigma)\geq 0\\}$.
This can be also generalized for the randomized scan dynamics. The restricted
randomized scan dynamics for low temperature is the following update scheme:
for any given $\sigma\in\Omega^{+}$, generate a candidate $\sigma^{\prime}$ by
$k$ site of updates from $\sigma$ with the usual randomized systematic scan
dynamics. If $S(\sigma^{\prime})\geq 0$ we accept $\sigma^{\prime}$ for the
next state; if $S(\sigma^{\prime})<0$ then we accept $-\sigma^{\prime}$, the
state whose spins are all reversed from $\sigma^{\prime}$, for the next state.
Analyzing corresponding magnetization chain takes an important role, so we
denote $S^{+}_{t}:=S(X_{t})$ with the plus sign to emphasize we are working
under the restricted Glauber dynamics.

###  5.1. Mixing time Upper bound for $\beta>1$

######  Theorem 5.1.

Under the restricted Glauber dynamics, $t_{\textrm{mix}}\leq\frac{c_{1}n\log
n}{k}$ for some constant $c_{1}=c_{1}(\beta)>0$.

######  Lemma 5.1.

Suppose $k=o(\sqrt{n})$. Define $s^{*}$ to be the unique positive solution of
$\tanh(\beta s)=s$, and for constant $\alpha$ let

$\tau^{*}=\tau^{*}(\alpha):=\inf\Big{\\{}t\geq 0:S^{+}_{t}\leq
s^{*}+\frac{\alpha}{\sqrt{n}}\Big{\\}}.$

Then, for some suitable $c=c(\alpha,\beta)>0$,

$\lim_{n\to\infty}\mathbb{P}_{\sigma}(\tau^{*}>cn\log n/k)=0.$

###### Proof.

Start from Theorem 2.6. In case of $S^{+}_{t}>2k/n$,

$\mathbb{E}_{\sigma}[S^{+}_{t+1}-S^{+}_{t}|S^{+}_{t}=s]\leq\frac{k}{n}(\tanh(\beta
S^{+})-S^{+})+\frac{4k^{2}}{n^{2}}.$

Define $\gamma^{*}:=\beta\cosh^{-2}(\beta s^{*})$. By the mean value theorem,
for $y>0$,

$\tanh(\beta(s^{*}+y))-\tanh(\beta
s^{*})=\frac{\beta}{\cosh^{2}(s^{*}+\tilde{y})}y\leq\gamma y.$

Therefore for $y\geq 0$, $\tanh(\beta(s^{*}+y))\leq s^{*}+\gamma^{*}y$. In
conclusion, provided that $S^{+}_{t}>(2k/n\vee s^{*})$,

$\mathbb{E}_{\sigma}[S^{+}_{t+1}-S^{+}_{t}|S^{+}_{t}=s]\leq-\frac{k(1-\gamma^{*})}{n}(s-s^{*})+\frac{4k^{2}}{n^{2}}.$

Define

$Y_{t}:=\Big{[}1-\frac{k(1-\gamma^{*})}{n}\Big{]}^{-t}\Big{(}S^{+}_{t}-s^{*}-\frac{4k}{n(1-\gamma^{*})}\Big{)}.$

Take large $n$ so that $(2k/n\vee s^{*})=s^{*}$, then $Y_{t}$ becomes non-
negative supermartingale for $t<\tau^{*}$ since $s^{*}$ only depends on
$\beta$. From the optional stopping lemma,

$1\geq\mathbb{E}_{\sigma}[Y_{\tau^{*}\wedge
t}]\geq\Big{[}1-\frac{k(1-\gamma^{*})}{n}\Big{]}^{-t}\Big{(}\frac{\alpha}{\sqrt{n}}-\frac{4k}{n(1-\gamma^{*})}\Big{)}\mathbb{P}_{\sigma}(\tau^{*}>t).$

Hence

$\mathbb{P}_{\sigma}(\tau^{*}>t)\leq\Big{(}\frac{\alpha}{\sqrt{n}}-\frac{4k}{n(1-\gamma^{*})}\Big{)}^{-1}\Big{[}1-\frac{k(1-\gamma^{*})}{n}\Big{]}^{t}.$

Plugging in $t=cn\log n/k$ finishes the proof, as $k/n=o(1/\sqrt{n})$. ∎

######  Lemma 5.2.

Define $s^{*}$ in the same way as Lemma 5.1. For any $\alpha>0$, define

$\tau_{*}=\tau_{*}(\alpha):=\min\Big{\\{}t\geq 0:S^{+}_{t}\geq
s^{*}+\frac{\alpha}{\sqrt{n}}\Big{\\}}.$

If $k=o(\sqrt{n})$, then $\mathbb{E}_{0}[\tau_{*}]=O(n\log n/k)$.

The proof of Lemma 5.2 is suggested on the appendix. With Lemma 5.1 and Lemma
5.2, the upper bound can be proven.

###### Proof.

(Theorem 5.1) First of all, for any arbitrary configurations $\sigma$ and
$\widetilde{\sigma}$ in $\Omega^{+}$ which satisfies
$S(\sigma)=S(\widetilde{\sigma})$, we can show that two chains start from
these two configurations can be exactly matched with high probability in
$O(n\log n/k)$ times. This can be done by applying Lemma 2.5 in a slightly
different way. From this fact, it is enough to show that there exists $C>0$
that for any two states $\sigma$ and $\widetilde{\sigma}$,

$\lim_{C\to\infty}\limsup_{n\to\infty}\mathbb{P}_{\sigma,\widetilde{\sigma}}(\tau_{\textrm{mag}}>Cn\log
n/k)<1,$ (32)

where $\tau_{\textrm{mag}}$ is the first time $t$ with
$S^{+}_{t}=\widetilde{S}^{+}_{t}$.
Although the monotone coupling for $X_{t}$ we have discussed does not make
sense under the restricted dynamics, there is still a coupling for two
magnetization chains $(S^{+}_{t},\widetilde{S}^{+}_{t})$ which preserves
monotonicity between magnetizations; i.e.
$(S^{+}_{t}-\widetilde{S}^{+}_{t})(S^{+}_{t+1}-\widetilde{S}^{+}_{t+1})\geq
0$. Due to this monotonicity, it is enough to consider two starting points $0$
and $1$(odd $n$ case can be also done in an analogous way). Consider two
chains, denoted as $S^{+}_{T}$ and $S^{+}_{B}$, whose starting positions are
$1$ and $0$ respectively. Let $\mu^{+}$ be the stationary distribution of the
restricted magnetization chain and $S^{+}_{\mu}$ be a stationary copy of the
restricted magnetization, i.e. whose initial distribution is $\mu^{+}$. Run
three chains $S^{+}_{T},S^{+}_{B}$, and $S^{+}_{\mu}$ independently at the
beginning. For some constants $0<c_{1}\leq c_{2}$, define stopping times as

$\begin{split}\tau_{1}&:=\min\Big{\\{}t\geq 0:S^{+}_{T,t}\leq
s^{*}+c_{1}n^{-1/2}\Big{\\}},\\\ \tau_{2}&:=\min\Big{\\{}t\geq
0:S^{+}_{B,t}\geq s^{*}+c_{2}n^{-1/2}\Big{\\}}.\end{split}$

Assume $\tau_{1}<\tau_{2}$. If $S^{+}_{\mu,\tau_{1}}\geq s^{*}+c_{1}n^{-1/2}$,
for $t\geq\tau_{1}$ we couple $S^{+}_{\mu}$ chain and $S^{+}_{T}$ chain, while
$S^{+}_{B}$ runs independently. On the event
$S^{+}_{\mu,\tau_{1}}<s^{*}+c_{1}n^{-1/2}$, continue running all three chains
independently. After reaching the time $\tau_{2}$, if
$S^{+}_{\mu,\tau_{2}}\leq s^{*}+c_{2}n^{-1/2}$ couple all three chains
monotonically. If $S^{+}_{\mu,\tau_{2}}>s^{*}+c_{2}n^{-1/2}$, continue running
all three chains independently. The other case, $\tau_{1}\geq\tau_{2}$ can be
set similarly.
For another constant $c_{3}>0$, define events $H_{1},H_{2}$ as

$\begin{split}H_{1}&:=\\{\tau_{1}\leq c_{3}n\log
n/k\\}\cap\Big{\\{}S_{\mu,\tau_{1}}\geq s^{*}+c_{1}n^{-1/2}\Big{\\}},\\\
H_{2}&:=\\{\tau_{2}\leq c_{3}n\log n/k\\}\cap\Big{\\{}S_{\mu,\tau_{2}}\leq
s^{*}+c_{2}n^{-1/2}\Big{\\}}.\end{split}$

Then we have

$\begin{split}\mathbb{P}_{\sigma,\widetilde{\sigma}}(H_{1}^{c})&\leq\mathbb{P}_{\sigma,\widetilde{\sigma}}(\tau_{1}>c_{3}n\log
n/k)+\mu^{+}(0,s^{*}+c_{1}n^{-1/2})\\\
\mathbb{P}_{\sigma,\widetilde{\sigma}}(H_{2}^{c})&\leq\mathbb{P}_{\sigma,\widetilde{\sigma}}(\tau_{2}>c_{3}n\log
n/k)+\mu^{+}(s^{*}+c_{2}n^{-1/2},1).\end{split}$

Observe that on the event $H_{1}\cap H_{2}$ the chains $S_{T}$ and $S_{B}$
cross over each other by $c_{3}n\log n/k$, therefore

$\begin{split}\mathbb{P}_{\sigma,\widetilde{\sigma}}&\geq
1-\mathbb{P}_{\sigma,\widetilde{\sigma}}(\tau_{1}>c_{3}n\log
n/k)-\mathbb{P}_{\sigma,\widetilde{\sigma}}(\tau_{2}>c_{3}n\log n/k)\\\
&\qquad\qquad-\mu^{+}((s^{*}+c_{1}n^{-1/2},s^{*}+c_{2}n^{-1/2})^{c}).\end{split}$

$\mu^{+}$ satisfies a central limit theorem([ENR80]), therefore the last term
$\mu^{+}((s^{*}+c_{1}n^{-1/2},s^{*}+c_{2}n^{-1/2})^{c})$ is uniformly bounded
away from $1$. Further, from the previous two Lemmas 5.1 and 5.2, we have

$\lim_{n\to\infty}\mathbb{P}_{\sigma,\widetilde{\sigma}}(\tau_{1}>c_{3}n\log
n/k)=\lim_{n\to\infty}\mathbb{P}_{\sigma,\widetilde{\sigma}}(\tau_{2}>c_{3}n\log
n/k)=0.$

Therefore $\mathbb{P}_{\sigma,\widetilde{\sigma}}(H_{1}\cap H_{2})$ is bounded
away from $0$, and this means $S^{+}_{T}$ and $S^{+}_{B}$ cross by the time
$c_{3}n\log n/k$. As a final step, define

$\tau_{\textrm{loc}}=\min\\{t\geq
1:(S^{+T}_{T,t-1}-S^{+T}_{B,t-1})(S^{+T}_{T,t}-S^{+T}_{B,t})\leq 0\\}$

then $\mathbb{P}_{\sigma,\widetilde{\sigma}}(\tau_{\textrm{loc}}<c_{3}\log
n)>\epsilon$ uniformly on $n$. From $k^{2}=o(n)$ condition, there is a
coupling between $S^{+T}_{T}$ and $S^{+T}_{B}$ such that

$\mathbb{P}_{\sigma,\widetilde{\sigma}}\Big{(}\tau_{\textrm{mag}}=\left\lceil\frac{\tau_{\textrm{loc}}}{k}\right\rceil\Big{)}>\epsilon>0,$

where $\epsilon$ is independent to $n$. ∎

###  5.2. Mixing time Lower bound for $\beta>1$

######  Theorem 5.2.

Under the restricted Glauber dynamics, $t_{\textrm{mix}}\geq(1/4)n\log n/k$.

###### Proof.

The proof can be done in the similar fashion as [LLP10]. Again, define $s^{*}$
to be the unique positive solution of the equation $\tanh(\beta s)=s$. Let
$\\{X_{t}\\}$ start from $\mathbbm{1}$, and let $\\{\widetilde{X}_{t}\\}$
follows the stationary distribution $\mu^{+}$. Apply the monotone coupling to
, and write $\mathbb{P}_{\mathbbm{1},\mu^{+}}$ and
$\mathbb{E}_{\mathbbm{1},\mu^{+}}$ be the probability measure and expectation
under this coupling. Define $\mathcal{B}(\sigma)$ be a set of vertices with a
minus spin, and $B(\sigma):=|\mathcal{B}(\sigma)|$. From the stationary
magnetization result of [ENR80], for some suitable $0<c_{1}<1$,

$\mathbb{P}_{\mathbbm{1},\mu^{+}}(B(\widetilde{X}_{0})\leq
c_{1}n)=\mu^{+}(\\{\sigma:B(\sigma)\leq c_{1}n\\})=o(1).$

Let $N_{t}$ be the number of the sites in $\mathcal{B}(\widetilde{X}_{0})$
that have not been updated until time $t$. Then,

$\mathbb{E}_{\mathbbm{1},\mu^{+}}[N_{t}|B(\widetilde{X}_{0})]=B(\widetilde{X}_{0})\left(1-\frac{k}{n}\right)^{t}.$

Plugging in $t^{*}:=(1/4)n\log n/k$ gives

$\mathbb{E}_{\mathbbm{1},\mu^{+}}[N_{t^{*}}|B(\widetilde{X}_{0})]\geq
c_{2}B(\widetilde{X}_{0})n^{-1/4}.$

If we consider $N_{t}$ as a sum of indicators showing the update status on
each vertices, for any $v,w\in\mathcal{B}(\widetilde{X}_{0})$,

$\mathbb{E}_{\mathbbm{1},\mu^{+}}[I_{v}I_{w}]=(1-\frac{2k}{n})^{t}\leq(1-\frac{k}{n})^{2t}=\mathbb{E}_{\mathbbm{1},\mu^{+}}[I_{v}]\mathbb{E}_{\mathbbm{1},\mu^{+}}[I_{w}],$

so indicators are negatively correlated. This ensures
$\textrm{Var}_{\mathbbm{1},\mu^{+}}(N_{t})\leq n$ at all time. Combining with
Chebyshev’s inequality, on the event
$E_{1}:=\\{B(\widetilde{X}_{0})>c_{1}n\\}$, with some $c_{3}>0$,

$\mathbb{P}_{\mathbbm{1},\mu^{+}}[N_{t^{*}}\leq
c_{3}n^{3/4}|B(\widetilde{X}_{0})]=o(1).$

Therefore,

$\mathbb{P}_{\mathbbm{1},\mu^{+}}[N_{t^{*}}\leq
c_{3}n^{3/4}]\leq\mathbb{P}_{\mathbbm{1},\mu^{+}}(E_{1}^{c})+\mathbb{P}_{\mathbbm{1},\mu^{+}}(E_{1}\cap\\{N_{t^{*}}\leq
c_{3}n^{3/4}\\})=o(1).$

Now, suppose $N_{t^{*}}\leq c_{3}n^{3/4}$. In this case we have
$S_{t^{*}}\geq\widetilde{S}_{t^{*}}+c_{4}n^{-1/4}$ for some $c_{4}>0$. Pick a
small constant $c_{5}\in(0,c_{4})$ and define $E_{2}:=S_{t^{*}}\leq
s^{*}+c_{5}n^{-1/4}$. In this case,

$\begin{split}\mathbb{P}_{\mathbbm{1},\mu^{+}}(E_{2})&\leq\mathbb{P}_{\mathbbm{1},\mu^{+}}(N_{t^{*}}>c_{3}n^{3/4})+\mathbb{P}_{\mathbbm{1},\mu^{+}}(E_{2}\cap\\{N_{t^{*}}\leq
c_{3}n^{3/4}\\})\\\ &\leq
o(1)+\mathbb{P}_{\mathbbm{1},\mu^{+}}(\widetilde{S}_{t^{*}}\leq
s^{*}+(c_{5}-c_{4})n^{-1/4})\\\ &=o(1),\end{split}$

by appealing to the central limit theorem at the last equation. Furthermore
the theorem gives

$\mu^{+}\Big{(}\\{\sigma:S(\sigma)>s^{*}+c_{5}n^{-1/4}\\}\Big{)}=o(1).$

Finally,

$d(t^{*})\geq\mathbb{P}_{\mathbbm{1},\mu^{+}}(\\{\sigma:S(\sigma)>s^{*}+c_{5}n^{-1/4}\\})-\mu^{+}(\\{\sigma:S(\sigma)>s^{*}+c_{5}n^{-1/4}\\})=1-o(1).$

Therefore we have $t_{\textrm{mix}}(n)\geq(1/4)n\log n/k$. ∎

## Acknowledgement

We are sincerely grateful to Evita Nestoridi for introducing the topic and
helpful discussions.

##  6\. Appendix: proof of Lemma 5.2

In this section we suggest a detailed calculation for Lemma 5.2. Throughout
this section we assume $\beta>1$, $k=o(n)$, and let $s^{*}$ be the unique
positive solution of $\tanh(\beta s)=s$. This relationship can be modified to

$\beta=\frac{1}{2s^{*}}\log\Big{(}\frac{1+s^{*}}{1-s^{*}}\Big{)},$

and Taylor expansion on the right side at $s=0$ gives $\beta>1+(s^{*})^{2}/3$.

######  Proposition 6.1.

Define

$I(x):=-2\beta x^{2}+\frac{\lambda
k}{n}x+\Big{(}\frac{1}{2}+x\Big{)}\log\Big{(}\frac{1}{2}+x\Big{)}+\Big{(}\frac{1}{2}-x\Big{)}\log\Big{(}\frac{1}{2}-x\Big{)}+\log
2.$

Then there exists $s_{0},s_{1}$ such that
$I^{\prime}(s_{0})=I^{\prime}(s_{1})=0$, $0<s_{0}=O(k/n)$, and
$s^{*}/2>s_{1}=s^{*}/2-O(k/n)$.

###### Proof.

Since

$\begin{split}I^{\prime}(x)&=-4\beta
x+\log\big{(}\frac{1}{2}+x\big{)}-\log\big{(}\frac{1}{2}-x\big{)}+\frac{\lambda
k}{n}\\\ I^{\prime\prime}(x)&=-4\beta+\frac{4}{1-4x^{2}},\end{split}$

we have $I^{\prime}(s^{*}/2)=I^{\prime}(0)=\lambda k/n>0$. Furthermore
$I(0)=0$, $I(s^{*}/2)<0$ for large enough $n$ as $k/n\to 0$ and $s^{*}$ is a
fixed value. From this condition we can deduce at least two points in
$(0,s^{*}/2)$ have a horizontal tangential line. Pick the smallest and the
largest among them from $(0,s^{*}/2)$ and call them $s_{1}$ and $s_{2}$
respectively.
Taylor expansion of $I$ at $x=0$ becomes

$I(x)\sim\frac{\lambda
k}{n}x-2(\beta-1)x^{2}=-2(\beta-1)\Big{(}x-\frac{\lambda
k}{4(\beta-1)n}\Big{)}^{2}+O\Big{(}\frac{k^{2}}{n^{2}}\Big{)}.$

and $I$ at $x=s^{*}/2$ becomes

$\begin{split}I(x)&\sim I(s^{*}/2)+\frac{\lambda
k}{n}\Big{(}x-\frac{s^{*}}{2}\Big{)}+\frac{I^{\prime\prime}(s^{*}/2)}{2}\Big{(}x-\frac{s^{*}}{2}\Big{)}^{2}\\\
&=I(s^{*}/2)+\frac{I^{\prime\prime}(s^{*}/2)}{2}\Big{(}x-\frac{s^{*}}{2}+\frac{\lambda
k}{nI^{\prime\prime}(s^{*}/2)}\Big{)}^{2}-O\Big{(}\frac{k^{2}}{n^{2}}\Big{)}.\end{split}$

Substitute $I^{\prime\prime}(s^{*}/2)$ in terms of $s^{*}$ and $\beta$ then we
have

$s_{1}\sim\frac{\lambda k}{4(\beta-1)n},\qquad\textrm{and}\qquad
s_{2}\sim\frac{s^{*}}{2}-\frac{\lambda k}{nI^{\prime\prime}(s^{*}/2)}.$

∎

######  Lemma 6.1.

Suppose a function $f:\mathbb{R}\to\mathbb{R}\in\mathcal{C}^{3}$ and a real
number $s_{0}$ satisfies

  1. (1)

$f^{\prime\prime\prime}(t)\geq 0$ for all $t\geq s_{0}$.

  2. (2)

$f^{\prime}(t)\leq 0$ for all $t\geq s_{0}$.

  3. (3)

$f^{\prime}(s_{0})=0$.

Then for any $s\leq x\leq y$, $f(y)-f(x)\leq\frac{f^{\prime}(y)}{2}(y-x)$
holds.

###### Proof.

Without loss of generality, set $s=0$.

$\begin{split}f(x)-f(y)+\frac{(y-x)f^{\prime}(y)}{2}&=-\int_{x}^{y}f^{\prime}(t)dt+\int_{x}^{y}\frac{f^{\prime}(y)}{2}dt\\\
&=\int_{x}^{y}t\Big{(}\frac{f^{\prime}(t)}{t}-\frac{f^{\prime}(y)}{y}\Big{)}dt+f^{\prime}(y)\frac{x^{2}-xy}{2y}.\end{split}$
(33)

Rightmost term of (33) is non-negative. Furthermore,
$tf^{\prime\prime}(t)-f^{\prime}(t)=\int_{0}^{t}f^{\prime\prime}(t)ds-\int_{0}^{t}f^{\prime\prime}(s)ds=\int_{0}^{t}(f^{\prime\prime}(t)-f^{\prime\prime}(s))ds\geq
0$ ensures that

$\frac{d}{dt}\Big{(}\frac{f^{\prime}(t)}{t}\Big{)}=\frac{tf^{\prime\prime}(t)-f^{\prime}(t)}{t^{2}}\geq
0,$

which finishes the proof. ∎

######  Remark.

The function $I(x)$ defined in Lemma 6.1 satisfies the all the conditions of
Lemma 6.1 with $s=s_{1}$.

###### Proof.

(Lemma 5.2)
Suppose $n$ is even, and consider a new sequence $M_{i}:=nS^{+}(Y_{i})/2$.
This is not a Markov chain, but $M_{i}$ forms an integral sequence in
$[0,n/2]$ whose difference between any consecutive terms are in
$\\{-1,0,1\\}$. Define $\tau_{c}:=\min\\{t\geq 0:M_{i}=c\\}$ and

$\begin{split}B_{c}&:=\sup\mathbb{E}_{c}[\tau_{c+1}]\\\
p_{c}&:=\sup\mathbb{P}_{c}[M_{i+1}-M_{i}=1|\mathcal{F}_{i}]\\\
q_{c}&:=\sup\mathbb{P}_{c}[M_{i+1}-M_{i}=-1|\mathcal{F}_{i}]\\\
r_{c}&:=\sup\mathbb{P}_{c}[M_{i+1}-M_{i}=0|\mathcal{F}_{i}].\end{split}$

All these four terms depend on $i^{\prime}:=i(\textrm{mod }k)$ and the
previous $i-i^{\prime}$ update history. Therefore, we take supremum over all
possible $i^{\prime}$s and $\mathcal{N}_{i}$. We can setup an estimate for
$B_{c}$. We know that $B_{0}=O(1)$, so for $1\leq c\leq
ns^{*}+\alpha\sqrt{n}$, for any time $i$

$\begin{split}\mathbb{E}_{c}[\tau_{c+1}|\mathcal{F}_{i}]&\leq
p_{c}+q_{c}(B_{c-1}+B_{c}+1)+r_{c}(B_{c}+1)\\\
&\qquad\longrightarrow(1-q_{c}-r_{c})B_{c}\leq(p_{c}+q_{c}+r_{c})+q_{c}B_{c-1}\end{split}$
(34)

Regardless of $i(\textrm{mod }k)$, we know that

$\begin{split}p_{c}&=\Big{[}\frac{1-s}{2}+O\Big{(}\frac{k}{n}\Big{)}\Big{]}p_{+}\Big{(}s+\frac{1}{n}\Big{)}=\Big{[}\frac{n-2c}{2n}+O\Big{(}\frac{k}{n}\Big{)}\Big{]}p_{+}\Big{(}\frac{1}{n}(2c+1)\Big{)}\\\
q_{c}&=\Big{[}\frac{1+s}{2}+O\Big{(}\frac{k}{n}\Big{)}\Big{]}p_{-}\Big{(}s-\frac{1}{n}\Big{)}=\Big{[}\frac{n+2c}{2n}+O\Big{(}\frac{k}{n}\Big{)}\Big{]}p_{-}\Big{(}\frac{1}{n}(2c-1)\Big{)},\end{split}$

hence Equation (34) becomes

$\begin{split}B_{c}&\leq
A+\Big{[}\frac{n+2c}{n-2c}+O\Big{(}\frac{k}{n}\Big{)}\Big{)}\Big{]}\frac{p_{-}\Big{(}\frac{1}{n}(2c-1)\Big{)}}{p_{+}\Big{(}\frac{1}{n}(2c+1)\Big{)}}B_{c-1}\\\
&\leq
A+\Big{[}\frac{n+2c}{n-2c}+O\Big{(}\frac{k}{n}\Big{)}\Big{)}\Big{]}\Big{(}1+O\Big{(}\frac{1}{n}\Big{)}\Big{)}e^{-\frac{2\beta}{n}(2c+1)}B_{c-1}\\\
&\leq A+\Big{[}\frac{n+2c}{n-2c}+\frac{\lambda
k}{n}\Big{]}e^{-\frac{2\beta}{n}(2c+1)}B_{c-1}\end{split}$ (35)

for some positive constant $A$ and $\lambda$. We know $B_{1}=O(1)$, so
repeating Equation (35) gives

$\begin{split}B_{c}\lesssim\sum_{j=1}^{c}e^{-\frac{2\beta}{n}(c^{2}-j^{2})}\frac{n+2c}{n-2c}...\frac{n+2j}{n-2j}e^{(c-j)\frac{\lambda
k}{n}}.\end{split}$ (36)

For any $1\leq j\leq c\leq ns^{*}+\alpha\sqrt{n}$,

$\begin{split}\frac{n+2c}{n-2c}...\frac{n+2j}{n-2j}&=\frac{(n/2+c)!/(n/2+j-1)!}{(n/2-j)!/(n/2-c-1)!}=\frac{(n/2+c)!(n/2-c-1)!}{(n/2-j)!(n/2+j-1)!}\\\
&\simeq\frac{(n/2+c)!(n/2-c)!}{(n/2-j)!(n/2+j)!}\simeq\frac{(n/2+c)^{n/2+c}(n/2-c)^{n/2-c}}{(n/2-j)^{n/2-j}(n/2+j)^{n/2+j}}\\\
&=\exp\Big{(}nf(c/n)-nf(j/n)\Big{)},\end{split}$

where
$f(x)=\left(\frac{1}{2}+x\right)\log\left(\frac{1}{2}+x\right)+\left(\frac{1}{2}-x\right)\log\left(\frac{1}{2}-x\right)+\log
2$. Hence (36) becomes

$\begin{split}B_{c}&\lesssim\sum_{j=1}^{c}\exp\Big{\\{}-\frac{2\beta}{n}(c^{2}-j^{2})+n\big{[}f\big{(}\frac{c}{n}\big{)}-f\big{(}\frac{j}{n}\big{)}\big{]}+(c-j)\frac{\lambda
k}{n}\Big{\\}}\\\
&=\sum_{j=1}^{c}\exp\Big{\\{}nI\big{(}\frac{c}{n}\big{)}-nI\big{(}\frac{j}{n}\big{)}\Big{\\}},\end{split}$

where $I$ is from Proposition 6.1. Eventually we need to bound $\sum B_{c}$,
which is

$\begin{split}\sum_{i=1}^{(ns^{*}+\alpha\sqrt{n})/2}B_{i}&\leq\sum_{i=1}^{(ns^{*}+\alpha\sqrt{n})/2}\sum_{j=1}^{i}\exp\Big{\\{}nI\big{(}\frac{i}{n}\big{)}-nI\big{(}\frac{j}{n}\big{)}\Big{\\}}\\\
&\simeq
n^{2}\int_{0}^{\frac{s^{*}}{2}+\frac{\alpha}{2\sqrt{n}}}\int_{0}^{y}\exp[nI(y)-nI(x)]dxdy.\end{split}$

The problem changed to calculate the integral over triangular area $\\{0\leq
y\leq s^{*}/2+\alpha/2\sqrt{n},0\leq x\leq y\\}$. We split the domain into by
8 pieces(Figure 2).

Figure 2. A graphical domain division by 8 pieces.

Piece 1: $\\{0\leq y\leq s_{1},0\leq x\leq y\\}$
For any $x\leq y$, we have

$|I(y)-I(x)|\leq(y-x)\sup_{x<s<y}I^{\prime}(s)\leq(y-x)\sup_{0<s<s_{1}}I^{\prime}(s)=(y-x)O\Big{(}\frac{k}{n}\Big{)}=O\Big{(}\frac{k^{2}}{n^{2}}\Big{)},$

therefore the integration over this domain becomes
$n^{2}s_{1}^{2}\exp\left(O\left(\frac{k^{2}}{n}\right)\right)=O(k^{2})$.

Piece 2: $\\{s_{1}\leq y\leq s_{2},0\leq x\leq s_{1}\\}$

$\begin{split}&n^{2}\int_{0}^{s_{1}}\exp[-nI(x)]dx\int_{s_{1}}^{s_{2}}\exp[nI(y)]dy\\\
&\qquad\qquad\leq n^{2}s_{1}\exp[-nI(0)]\int_{s_{1}}^{s_{2}}\exp[nI(y)]dy\\\
&\qquad\qquad\leq
n^{2}s_{1}\exp[nI(s_{1})-nI(0)]\int_{s_{1}}^{s_{2}}\exp[nI(y)-nI(s_{1})]dy\\\
&\qquad\qquad=O(kn)\int_{s_{1}}^{s_{2}}\exp[nI(y)-nI(s_{1})]dy.\end{split}$

Around $y=s_{1}$ we have $nI(y)-nI(s_{1})\simeq-2n(\beta-1)(y-s_{1})^{2}$. If
$y$ is far from $s_{1}$, since $I$ is a decreasing function on
$(s_{1},s_{2})$, $nI(y)-nI(s_{1})$ rapidly becomes small. Splitting the domain
of integration into $(s_{1},s_{1}+\log n/n)$ and $(s_{1}+\log n/n,s_{2})$
gives

$O(kn)\int_{s_{1}}^{s_{2}}\exp[nI(y)-nI(s_{1})]dy=O(kn)O\left(\frac{\log
n}{\sqrt{n}}\right)=O(k\sqrt{n}\log n).$

Piece 3: $\\{s_{1}\leq y\leq s_{2},s_{1}\leq x\leq y\\}$
This domain should be divided into 6 pieces again. This continues at the end
of the proof.

Piece 4: $\\{s_{2}\leq y\leq s^{*}/2,0\leq x\leq s_{1}\\}$
Since $I$ is increasing on both $(0,s_{1})$ and $(s_{2},s^{*}/2)$,

$n^{2}\int_{0}^{s_{1}}\exp[-nI(x)]dx\int_{s_{2}}^{s^{*}/2}\exp[nI(y)]dy\leq
n^{2}s_{1}\exp[-nI(0)]\Big{(}\frac{s^{*}}{2}-s_{2}\Big{)}\exp[nI(s^{*}/2)]=O(k^{2}).$

Piece 5: $\\{s_{2}\leq y\leq s^{*}/2,s_{1}\leq x\leq s_{2}\\}$
Similar to Piece 2.

$\begin{split}&n^{2}\int_{s_{1}}^{s_{2}}\exp[-nI(x)]dx\int_{s_{2}}^{s^{*}/2}\exp[nI(y)]dy\\\
&\qquad\qquad\leq
n^{2}\int_{s_{1}}^{s_{2}}\exp[-nI(x)]dx\left(\frac{s^{*}}{2}-s_{2}\right)\exp[nI(s^{*}/2)]\\\
&\qquad\qquad=n^{2}\int_{s_{1}}^{s_{2}}\exp[nI(s_{2})-nI(x)]dx\left(\frac{s^{*}}{2}-s_{2}\right)\exp\left[nI(s^{*}/2)-nI(s_{2})\right]\\\
&\qquad\qquad\lesssim
n^{2}\int_{s_{1}}^{s_{2}}\exp[nI(s_{2})-nI(x)]dx\left(\frac{s^{*}}{2}-s_{2}\right)\\\
&\qquad\qquad=n^{2}O(\frac{\log
n}{\sqrt{n}})O\Big{(}\frac{k}{n}\Big{)}=O(k\sqrt{n}\log n).\end{split}$

Piece 6: $\\{s_{2}\leq y\leq s^{*}/2,s_{2}\leq x\leq s^{*}/2\\}$
Similar to Piece 1.

$n^{2}\iint\exp[nI(y)-nI(x)]dydx\lesssim
n^{2}\Big{(}\frac{s^{*}}{2}-s_{2}\Big{)}^{2}=O(k^{2}).$

Piece 7: $\\{s^{*}/2\leq y\leq s^{*}/2+\alpha/2\sqrt{n},0\leq x\leq
s^{*}/2\\}$
Similar to Piece 4, 5, 6. The integral is

$n^{2}\int_{s^{*}/2}^{s^{*}/2+\alpha/2\sqrt{n}}\exp[nI(y)]dy\int_{0}^{s^{*}/2}\exp[-nI(x)]dx.$

We have $I(\frac{s^{*}}{2})<0$. Taylor expansion at $\frac{s^{*}}{2}$ for
large enough $n$ ensures
$I\left(\frac{s^{*}}{2}+\frac{\alpha}{2\sqrt{n}}\right)<0$. Therefore

$n^{2}\int_{s^{*}/2}^{s^{*}/2+\alpha/2\sqrt{n}}\exp[nI(y)]dy\lesssim n^{3/2}.$

Now, split the range of $x$ by
$[0,s_{1}]\cup[s_{1},s_{2}]\cup[s_{2},s^{*}/2]$. Then each integral with
respect to $x$ gives $O(k/n),O(\log n/\sqrt{n})$ and $O(k/n)$. In conclusion,

$n^{2}\iint\exp[nI(y)-nI(x)]dydx=O(k\sqrt{n}+n\log n)=O(n\log n).$

Piece 8: $\\{s^{*}/2\leq y\leq s^{*}/2+\alpha/2\sqrt{n},s^{*}/2\leq x\leq
s^{*}/2+\alpha/2\sqrt{n}\\}$
Similar to Piece 1.

$n^{2}\iint\exp[nI(y)-nI(x)]dydx\lesssim
n^{2}\Big{(}\frac{\alpha}{2\sqrt{n}}\Big{)}^{2}=O(n).$

We divide Piece 3: $\\{s_{1}\leq y\leq s_{2},s_{1}\leq x\leq y\\}$ again into
6 pieces with a parameter $0<\epsilon=o(1)$. $\epsilon$ will be chosen after
the calculation(Figure 3).

Figure 3. A graphical domain division for Piece 3 from Figure 2, by 6 pieces.

Piece 3-1 : $\\{s_{1}\leq y\leq s_{1}+\epsilon,s_{1}\leq x\leq y\\}$
For small enough $\epsilon>0$, $s_{1}\leq x\leq y\leq s_{1}+\epsilon$ implies
$I(x)\geq I(y)$. Therefore,

$n^{2}\int_{s_{1}}^{s_{1}+\epsilon}\int_{s_{1}}^{y}\exp[nI(y)-nI(x)]dxdy\lesssim
n^{2}\epsilon^{2}.$

Piece 3-2 : $\\{s_{1}+\epsilon\leq y\leq s_{2}-\epsilon,s_{1}\leq x\leq
s_{1}+\epsilon\\}$

$n^{2}\int_{s_{1}+\epsilon}^{s_{2}-\epsilon}\int_{s_{1}}^{s_{1}+\epsilon}\exp[nI(y)-nI(x)]dxdy\leq
n^{2}\epsilon\int_{s_{1}+\epsilon}^{s_{2}-\epsilon}\exp[nI(y)-nI(s_{1}+\epsilon)]dy$

Near $y=s_{1}+\epsilon$, the approximation
$nI(y)-nI(s_{1}+\epsilon)\simeq-2n(\beta-1)\\{(y-s_{1})^{2}-\epsilon^{2}\\}$
holds. $I(y)$ is uniformly bounded above by $I(s_{1}+\epsilon)$ when $y$ is
far from $s_{1}+\epsilon$. Hence the above is bounded by $O(n^{2}\epsilon)$,
provided that $n\epsilon\to\infty$.

Piece 3-3 : $\\{s_{1}+\epsilon\leq y\leq s_{2}-\epsilon,s_{1}+\epsilon\leq
x\leq y\\}$
Proposition 6.1 can be applied to the function $I$ in this domain.

$\begin{split}&n^{2}\int_{s_{1}+\epsilon}^{s_{2}-\epsilon}\int_{s_{1}+\epsilon}^{y}\exp[nI(y)-nI(x)]dxdy\\\
&\qquad\qquad\leq
n^{2}\int_{s_{1}+\epsilon}^{s_{2}-\epsilon}\int_{s_{1}+\epsilon}^{y}\exp[nI^{\prime}(y)(y-x)/2]dxdy\\\
&\qquad\qquad=n^{2}\int_{s_{1}+\epsilon}^{s_{2}-\epsilon}-\frac{2}{nI^{\prime}(y)}\Big{\\{}1-\exp\Big{[}nI^{\prime}(y)\big{(}\frac{y}{2}-\frac{s_{1}+\epsilon}{2}\big{)}\Big{]}\Big{\\}}dy\\\
&\qquad\qquad\leq
n^{2}\int_{s_{1}+\epsilon}^{s_{2}-\epsilon}-\frac{2}{nI^{\prime}(y)}dy\end{split}$

Near $y=s_{1}+\epsilon$ we have $I^{\prime}(y)\simeq 4(\beta-1)(y-s_{1})$,
while near $y=s_{2}-\epsilon$ we have $I^{\prime}(y)\simeq O(1)(s_{2}-y)$. For
$y$ in between $s_{1}+\epsilon$ and $s_{2}-\epsilon$, $|I^{\prime}(y)|$ is
bounded below by a positive constant. Therefore,

$n^{2}\int_{s_{1}+\epsilon}^{s_{2}-\epsilon}-\frac{2}{nI^{\prime}(y)}dy\lesssim
nO(\log(1/\epsilon))+O(n)=O(-n\log\epsilon)+O(n).$

Piece 3-4 : $\\{s_{2}-\epsilon\leq y\leq s_{2},s_{1}\leq x\leq
s_{1}+\epsilon\\}$
Similar to Piece 3-1. In this domain we have $I(x)\geq I(y)$ for $x\leq y$.
Therefore

$n^{2}\iint\exp[nI(y)-nI(x)]dydx\lesssim n^{2}\epsilon^{2}.$

Piece 3-5 : $\\{s_{2}-\epsilon\leq y\leq s_{2},s_{1}+\epsilon\leq x\leq
s_{2}-\epsilon\\}$
Similar to Piece 3-2.

$n^{2}\int_{s_{2}-\epsilon}^{s_{2}}\int_{s_{1}+\epsilon}^{s_{2}-\epsilon}\exp[nI(y)-nI(x)]dxdy=n^{2}\epsilon\int_{s_{1}+\epsilon}^{s_{2}-\epsilon}\exp[nI(s_{2}-\epsilon)-nI(x)]dx.$

Near $x=s_{2}-\epsilon$, the approximation $nI(s_{2}-\epsilon)-nI(x)\simeq
O(n)\epsilon(x-s_{2}+\epsilon)$ holds. Hence the above is bounded by
$O(n^{2}\epsilon)$ in an analogous way.

Piece 3-6 : $\\{s_{2}-\epsilon\leq y\leq s_{2},s_{2}-\epsilon\leq x\leq y\\}$
Similar to Piece 3-1, $I(x)\geq I(y)$ for $x\leq y$ implies

$n^{2}\iint\exp[nI(y)-nI(x)]dydx\lesssim n^{2}\epsilon^{2}.$

Now set $\epsilon=O(\log n/n)$. Under $k=o(\sqrt{n})$ assumption, all the
integrals over the domains are $O(n\log n)$, which ensures that

$\mathbb{E}_{0}\Big{[}\min\big{\\{}i\geq 0:S^{+}(Y_{i})\geq
s^{*}+\frac{\alpha}{\sqrt{n}}\big{\\}}\Big{]}=O(n\log n).$

As this is true for any $\alpha>0$, after you reach the stopping time

$\tau_{**}:=\Big{\\{}i\geq 0:S^{+}(Y_{i})\geq
s^{*}+\frac{\alpha}{\sqrt{n}}\Big{\\}},$

Consider the time $\lceil\tau_{**}/k\rceil$. We have

$S^{+}(X_{\lceil\tau_{**}/k\rceil})=S^{+}(Y_{k\lceil\tau_{**}/k\rceil})\geq
s^{*}+\frac{\alpha}{\sqrt{n}}-\frac{2k}{n}$

From the condition $k=o(\sqrt{n})$, adjusting $\alpha$ gives

$\lceil\frac{\tau_{**}}{k}\rceil\sim\tau_{*}:=\min\big{\\{}t\geq
0:S^{T}_{t}\geq s^{*}+\frac{\alpha}{\sqrt{n}}\big{\\}}.$

Therefore, $\mathbb{E}_{0}[\tau_{*}]=O(n\log n/k)$. ∎

## References

  * [LLP10] Levin, D. A., Luczak M. J., and Peres, Y.  Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability.  Prob. Theory and Related Fields, 146:223–265, 2010.
  * [DLY09] Ding, J., Lubetzky, E., and Peres, Y.  The mixing time evolution of Glauber dynamics for the mean-field Ising model.  Comm. in Math. Phys., 289(2):725–764, 2009
  * [DLP09] Ding, J., Lubetzky, E., and Peres, Y.  Censored Glauber Dynamics for the Mean Field Ising Model.  J of Stat. Phys., 137:407–458, 2009
  * [LS12] Lubetzky, E., and Sly, A.  Cutoff for the Ising model on the lattice.  Inv. Math., 191:719–755, 2013
  * [LS14] Lubetzky, E., and Sly, A.  Universality of cutoff for the Ising model.  Ann. of Prob., 45(6A):3664–3696, 2017
  * [DP11] Ding, J., and Peres, Y.  Mixing time for the Ising model: A uniform lower bound for all graphs.  Ann. de l’IHP Prob. et stat., 47(4):1020–1028, 2011
  * [LP10] Levin, D. A., Peres, Y., and Elizabeth L. W.  Markov Chains and Mixing Times(2nd Ed.).  American Mathematical Society, RI, 2017.
  * [SG73] Simon, B., and Griffiths, R.B.  The $(\varphi^{4})_{2}$ field theory as a classical Ising model.  Comm. in Math. Phys., 33:145–164, 1973
  * [Ellis66] Ellis R.S.  Entropy, large deviations, and statistical mechanics. Taylor & Francis, 1431(821), 2006
  * [ENR80] Ellis R.S., Newman, C.M., and Rosen, J.S.  Limit theorems for sums of dependent random variables occuring in statistical mechanics. II. Conditioning, multiple phases, and metastability.  Z. Wahrsch. für Verw. Gebiete, 51(2):153–169, 1980
  * [DS81] Diaconis, P., and Shahshahani, M.  Generating a random permutation with random transpositions.  Z. Wahrsch. für Verw. Gebiete, 57(2):159–179, 1981
  * [MPS04] Mossel, E., Peres, Y., and Sinclair, A.  Shuffling by semi-random transpositions.  Proceedings 45th Annual IEEE Symposium on FOCS, 572–581, 2004
  * [SZ07] Saloff-Coste, L., and Zuniga, J.  Convergence of some time inhomogeneous Markov chains via spectral techniques.  Stoc. Proc. their appl., 117(8):961–979, 2007
  * [DR04] Diaconis, P., and Ram, A.  Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques.  Michigan Math. J, 48(1):157–190, 2000
  * [bcsv17] Blanca, A., Caputo, P., Sinclair, A., and Vigoda, E.  Spatial Mixing and Non-local Markov chains.  Random Structures & Algorithms, 55(3):584–614, 2019
  * [NN18] Nam, D., and Nestoridi, E.  Cutoff for the cyclic adjacent transposition shuffle.  Ann. of App. Prob, 29(6):3861–3892, 2019
  * [Nes19] Nestoridi, E.  Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement.  Prob. Theory and Related Fields, 174(3-4):929–943, 2019
  * [PW13] Peres, Y., and Winkler, P.  Can extra updates delay mixing?.  Comm. in Math. Phys., 323:1007–1016, 2013
  * [Lac16] Lacoin, H.  Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion.  Ann. of Prob., 44(2):1426–1487, 2016
  * [DF80] Diaconis, P., Freedman, D.  Finite exchangeable sequences.  Ann. of Prob., 8(4):745–764, 1980
  * [GWL66] Griffiths, R.B., Weng, C.-Y., and Langer, J.S.  Relaxation times for metastable states in the mean-field model of a ferromagnet.  Phys. Rev., 149(1):301, 1966
  * [DGJ08] Dyer, M., Goldberg, L., and Jerrum, M.  Dobrushin conditions and systematic scan.  Comb. Prob. and computing, 17(6):761–779, 2008