《计算机科学》相关教学资源（参考文献）Decay of Correlation in Spin Systems

(An algorithmic perspective to the) Decay of Correlation in Spin Systems Yitong Yin Nanjing University

(An algorithmic perspective to the) Decay of Correlation in Spin Systems Yitong Yin Nanjing University

Decay of Correlation hardcore model: Pr[v∈I|o] H(I)xIII a+I)-ur。o →∝ ○-○-○- o:fixing leaves to be occupied/unoccupied by I Decay of correlation:Pr[velI o]does not depend on o when d if入≤入。=(d-1)a+西 counting total weights n of all I.S.in graphs with max-degree λc→no FPRAS unless NP=RP [Sly10][Galanis Stefankovie Vigoda 12][Sly Sun 12]

regular tree ` ! 1 v σ: fixing leaves to be occupied/unoccupied by I Pr[v 2 I | ￾] Decay of Correlation hardcore model: • λ λc 㱺 no FPRAS unless NP=RP Decay of correlation: Pr[v∈I | σ] does not depend on σ when l→∞ random independent set I iff counting total weights λ|I| of all I.S. in graphs with max-degree ≤ d+1 [Sly10] [Galanis Štefankovič Vigoda 12] [Sly Sun 12] [Weitz 06] (d+1)-

Spin System undirected graph G=(V,E) fixed integer g≥2 configuration o∈[glY weight:w(o)=A(ou,)b(o) {u,w}∈E u∈V A:[ql×[q→R≥o symmetric gxy matrix (symmetric binary constraint) b:[q→R>0 g-vector (unary constraint) partition function: zc=∑w(o) o∈[glV Gibbs distribution: c(o)= w(o) ZG

Spin System undirected graph G = (V, E) fixed integer q ≥ 2 ￾ 2 [q] V configuration w(￾) = Y {u,v}2E A(￾u, ￾v) Y v2V weight: b(￾v) A : [q] ⇥ [q] ! R￾0 b : [q] ! R￾0 symmetric q×q matrix q-vector (symmetric binary constraint) partition function: ZG = X ￾2[q]V w(￾) Gibbs distribution: µG(￾) = w(￾) ZG (unary constraint)

undirected graph G=(V,E) fixed integer g≥2 configuration o∈[g]Y weight:w(o)=A(ou,)b() {u,v}∈E u∈V 2-spin model:q=2,o{0,1} 4- edge activities 6= -9 external field hardcore model:B=0,y=1 ZG= ∑ λ川 I:independent sets in G ·Ising model:B=y multi-spin model:general g=2 ·Potts model: A= 81 ·q-coloring: B=0 1 b= 1

• 2-spin model: q =2, • hardcore model: β=0, γ=1 • Ising model: β = γ • multi-spin model: general q ≥ 2 • Potts model: • q-coloring: β=0 undirected graph G = (V, E) fixed integer q ≥ 2 ￾ 2 [q] V configuration w(￾) = Y {u,v}2E A(￾u, ￾v) Y v2V weight: b(￾v) ￾ 2 {0, 1}V A =  A00 A01 A10 A11￾ =  ￾ 1 1 ￾ ￾ b =  b0 b1 ￾ =  ￾ 1 ￾ edge activities external field 1 1 2 6 6 6 4 ￾ ￾ ... ￾ 3 7 7 7 A = 5 2 6 4 1 . . . 1 3 7 b = 5 ZG = X I: independent sets in G ￾|I|

Models ●spin systems: Ising model,Potts model,g-coloring ●hardcore model generalization hypergraph matchings ● nonomer-dimer一 ZG= ∑ AIMI (NOT a spin system) M:matchings in G Holant problem defined by the (weighted-)EQ,the At-Most-One constraint,and any binary constraints The recursion of marginal probabilities is the same as a recursion on the tree of self-avoiding walks. (hopefully) correlation decay tractability of on trees approximate counting

Models • spin systems: • Ising model, Potts model, q-coloring • hardcore model • monomer-dimer • Holant problem defined by the (weighted-)EQ, the At-Most-One constraint, and any binary constraints • The recursion of marginal probabilities is the same as a recursion on the tree of self-avoiding walks. (NOT a spin system) hypergraph matchings generalization correlation decay on trees tractability of approximate counting (hopefully) ZG = X M: matchings in G ￾|M|

Gibbs measure undirected graph G=(V,E) configuration o∈[g]V w(o) Gibbs distribution:)=HG()- by the chain rule:denoted V={v1,02,...,vn} w(o) w(o) u(σ)】 IIR=1PrX~uG[Xv:Ov:Vj<i:Xv3 =vj marginal probability:()=Pr[X=Xs=] X~HG where ve∈V,x∈[ql,boundary condition o∈[g]s on SCV approximately computing() FPTAS withinμg(c)±in time Poly(m for ZG

Gibbs Measure undirected graph G = (V, E) ￾ 2 [q] V configuration Gibbs distribution: by the chain rule: denoted V = {v1, v2,...,vn} where v∈V, x∈[q], boundary condition σ∈[q]S on S⊂V marginal probability: µ￾ v (x) = Pr X⇠µG [Xv = x | XS = ￾] FPTAS for ZG µ￾ v approximately computing (x) within µ￾ v (x) ± 1 n in time Poly(n) µ(￾) = µG(￾) = w(￾) ZG

Spatial Mixing (Decay of Correlation) marginal distribution at vertex v conditioning on weak spatial mixing(WSM）at rateδ()： o,T∈[g∂R：l呀-呀ITv≤δ(t) boundary conditions R 0 on infinite graphs: WSM uniqueness of infinite- volume Gibbs measure λ≤入c= dd a-a可> WSM of hardcore model on infinite(d+1)-regular tree

Spatial Mixing (Decay of Correlation) R G v t weak spatial mixing (WSM) at rate δ( ): kµ￾ v ￾ µ⌧ 8￾, ⌧ 2 [q] v kT V  ￾(t) @R : µ￾ v : marginal distribution at vertex v conditioning on σ boundary conditions on infinite graphs: WSM uniqueness of infinite￾volume Gibbs measure ￾ µ￾ v ￾  ￾c = dd (d￾1)(d+1) WSM of hardcore model on infinite (d+1)-regular tree ∂R

Spatial Mixing (Decay of Correlation) marginal distribution at vertex v conditioning on weak spatial mixing（WSM)）at rateδ()： o,T∈[goR: lg-Tv≤δ(t) strong spatial mixing(SSM)）at rateδ()： o,T∈[gR,p∈[g]s：lgUp-PlTV≤6(t) SSM marginal prob.(x) is well approximated by the local information

G Spatial Mixing (Decay of Correlation) R v t strong spatial mixing (SSM) at rate δ( ): weak spatial mixing (WSM) at rate δ( ): S kµ￾ v ￾ µ⌧ 8￾, ⌧ 2 [q] v kT V  ￾(t) @R : 8￾, ⌧ 2 [q] @R , 8⇢ 2 [q] S : µ￾ v : marginal distribution at vertex v conditioning on σ SSM µ⇢ v marginal prob. (x) is well approximated by the local information kµ￾[⇢ v ￾ µ⌧[⇢ v kT V  ￾(t) ∂R

Tree Recursion hardcore model: pr Prlv is occupied independent set in T T 入Π1(1-p) u()alII 1+入Π1(1-p) (Vi pi=Prlv;is occupied in T RT= PT occupancy ratio: 1-PT d w=中限 i=1

Tree Recursion µ(I) / ￾|I| hardcore model: independent set I in T = ￾ Qd i=1(1 ￾ pi) 1 + ￾ Qd i=1(1 ￾ pi) Ti pT = Pr[v is occupied ] v vi pi = Pr[vi is occupied ] in Ti T RT = pT 1 ￾ pT occupancy ratio: RT = ￾ Y d i=1 1 1 + Ri

Tree Recursion hardcore model: Prlv is occupied R=1-Prv is occupied independent set in G d (I)xλI 爬中 i三1 Prv is occupied] Pr[v2 is occupied o] Prvs is occupiedo] =1-Prvt is occupied R=1-Pri2 is occupied可 fs=1-Prv is occupied可 occupied ☑：unoccupied

R￾ 3 = Pr[v3 is occupied | ￾] 1 ￾ Pr[v3 is occupied | ￾] R￾ 2 = Pr[v2 is occupied | ￾] 1 ￾ Pr[v2 is occupied | ￾] R￾ 1 = Pr[v1 is occupied | ￾] 1 ￾ Pr[v1 is occupied | ￾] R￾ v = Pr[v is occupied | ￾] 1 ￾ Pr[v is occupied | ￾] R￾ v = ￾ Y d i=1 1 1 + R￾ i v v v Tree Recursion µ(I) / ￾|I| hardcore model: independent set I in G v v1 v2 v3 : occupied : unoccupied