Proposition 4.1(coupling lemma).For any coupling (X,Y)ofu and v,it holds that Pr[X≠Y]≥drv(4,v). Furthermore,there is an optimal coupling that achieves equality. Local neighborhood.Let G=(V,E)be a graph.For any vertex v EV,let IG(v)fu EV I fu,v}E E}denote the neighborhood of v,andr(v)=IG(v)Ufu}the inclusive neighborhood of v.We simply write I=r(v)=IG(v)and r=r+(v)=r(v)for short when G is clear in the context.We use △=△G兰maxvev Tl to denote the maximum degree of graph G. A notion of local neighborhood for MRF is frequently used.Let I =(V,E,be an MRF instance.For vV,we denote by[]the restriction of I on the inclusive neighborhood ofv,i.e.Iu=(Tt,Ev,Q,Φu),where Ev={u,v}∈E}andΦu=(pa)aeTtUEv Gibbs sampling.The Gibbs sampling (a.k.a.heat-bath,Glauber dynamics),is a classic Markov chain for sampling from Gibbs distributions.Let I=(V,E,be an MRF instance and u =ur its Gibbs distribution.The chain of Gibbs sampling(Algorithm 1)is on the space OV,and has the stationary distribution ur [LP17,Chapter 3]. Algorithm 1:Gibbs sampling Initialization:an initial state Xo E (not necessarily feasible) 1 for t =1,2,...,T do 2 pick Ur EV uniformly at random; 3 draw a random value c O from the marginal distribution Hu (X-1T)); Xr(or)←-c and X(w←-Xi-1(u)for all u∈V\{uri Marginal distributions.Here ((T))=Ho.r(.T))denotes the marginal distribution at vV conditioning on (T)O,which is computed as: (4) pu(c)Πuer Puv(ou,c) VeQ:H()Tet ( Due to the assumption(1),this marginal distribution is always well defined,and its computation uses only the information of Coupling for mixing time.Consider a chain(X)on space with stationary distribution r for MRF instance I.The mixing rate is defined as:for e>0, rmix(Ie)max min (tdrv) where dry(Xt,ur)denotes the total variation distance between ur and the distribution of X.. A coupling of a Markov chain is a joint process(Xt,Y:)tzo such that(X)tzo and(Y:)tzo marginally follow the same transition rule as the original chain.Consider the following type of couplings. Definition 4.2(one-step optimal coupling for Gibbs sampling).A coupling(Xt,Y)tzo of Gibbs sampling on an MRF instance I =(V,E,Q,)is a one-step optimal coupling if it is constructed as follows:For t=1,2,..., (1)pick the same random vr E V,and let (Xi(u),Yi(u))(X:-1(u),Y-1(u))for all uv; (②）sample（X,(().Y(er》from an optimal coupling D8oi.,C,）of the marginal distributions Ho(Io)and uv,(IT)where o =X1-1(Tv)and T =Y-(Tv). The coupling Dop()is an optimal coupling of)and)that attains the maximum Prx=y]for all couplings (y)ofa)andy).The coupling Dop)is determined by the local information I and o,rE Odeg(). With such a coupling,we can establish the following relation between the Dobrushin-Shlosman condition and the rapid mixing of the Gibbs sampling [DS85a,DS85b,DS87,BD97,Hay06,DGJ08]. 7Proposition 4.1 (coupling lemma). For any coupling (X,Y) of µ and ν, it holds that Pr[X , Y] ≥ dTV (µ, ν) . Furthermore, there is an optimal coupling that achieves equality. Local neighborhood. Let G = (V, E) be a graph. For any vertex v ∈ V , let ΓG (v) ≜ {u ∈ V | {u,v} ∈ E} denote the neighborhood of v, and Γ + G (v) ≜ ΓG (v)∪ {v} the inclusive neighborhood of v. We simply write Γv = Γ(v) = ΓG (v) and Γ + v = Γ + (v) = Γ + G (v) for short when G is clear in the context. We use ∆ = ∆G ≜ maxv ∈V |Γv | to denote the maximum degree of graph G. A notion of local neighborhood for MRF is frequently used. Let I = (V, E,Q, Φ) be an MRF instance. For v ∈ V , we denote by Iv ≜ I[Γ + v ] the restriction of I on the inclusive neighborhood Γ + v of v, i.e. Iv = (Γ + v , Ev,Q, Φv ), where Ev = {{u,v} ∈ E} and Φv = (φa)a ∈Γ + v ∪Ev . Gibbs sampling. The Gibbs sampling (a.k.a. heat-bath, Glauber dynamics), is a classic Markov chain for sampling from Gibbs distributions. Let I = (V, E,Q, Φ) be an MRF instance and µ = µI its Gibbs distribution. The chain of Gibbs sampling (Algorithm 1) is on the space Ω ≜ Q V , and has the stationary distribution µI [LP17, Chapter 3]. Algorithm 1: Gibbs sampling Initialization: an initial state X0 ∈ Ω (not necessarily feasible); 1 for t = 1, 2, . . . ,T do 2 pick vt ∈ V uniformly at random; 3 draw a random value c ∈ Q from the marginal distribution µvt (· | Xt−1(Γvt )); 4 Xt (vt ) ← c and Xt (u) ← Xt−1(u) for all u ∈ V \ {vt }; Marginal distributions. Here µv (· | σ(Γv )) = µv,I(· | σ(Γv )) denotes the marginal distribution at v ∈ V conditioning on σ(Γv ) ∈ Q Γv , which is computed as: ∀c ∈ Q : µv (c | σ(Γv )) = φv (c) Î u ∈Γv φuv (σu,c) Í c 0∈Q φv (c 0 ) Î u ∈Γv φuv (σu,c 0 ) (4) . Due to the assumption (1), this marginal distribution is always well defined, and its computation uses only the information of Iv . Coupling for mixing time. Consider a chain (Xt ) ∞ t=0 on space Ω with stationary distribution µI for MRF instance I. The mixing rate is defined as: for ϵ > 0, τmix(I, ϵ) ≜ max X0 min {t | dTV (Xt , µI)} , where dTV (Xt , µI) denotes the total variation distance between µI and the distribution of Xt . A coupling of a Markov chain is a joint process (Xt ,Yt )t ≥0 such that (Xt )t ≥0 and (Yt )t ≥0 marginally follow the same transition rule as the original chain. Consider the following type of couplings. Definition 4.2 (one-step optimal coupling for Gibbs sampling). A coupling (Xt ,Yt )t ≥0 of Gibbs sampling on an MRF instance I = (V, E,Q, Φ) is a one-step optimal coupling if it is constructed as follows: For t = 1, 2, . . ., (1) pick the same random vt ∈ V , and let (Xt (u),Yt (u)) ← (Xt−1(u),Yt−1(u)) for all u , vt ; (2) sample (Xt (vt ),Yt (vt )) from an optimal coupling D σ ,τ opt,Ivt (·, ·) of the marginal distributions µvt (· | σ) and µvt (· | τ ) where σ = Xt−1(Γvt ) and τ = Yt−1(Γvt ). The coupling D σ ,τ opt,Ivt (·, ·) is an optimal coupling of µvt (· | σ) and µvt (· | τ ) that attains the maximum Pr[x = y] for all couplings (x,y) of x ∼ µvt (· | σ) and y ∼ µvt (· | τ ). The coupling D σ ,τ opt,Ivt (·, ·) is determined by the local information Iv and σ, τ ∈ Q deg(v) . With such a coupling, we can establish the following relation between the Dobrushin-Shlosman condition and the rapid mixing of the Gibbs sampling [DS85a, DS85b, DS87, BD97, Hay06, DGJ08]. 7