Correlation Decay up to Uniqueness in Spin Systems Yitong Yin Nanjing University Joint work with Liang Li (Peking University) Pinyan Lu (Microsoft research Asia)
Correlation Decay up to Uniqueness in Spin Systems Joint work with Liang Li (Peking University) Pinyan Lu (Microsoft research Asia) Yitong Yin Nanjing University
Two-State Spin System graph G=(V,目 2 states {0,1) configuration o:V→{0，l} A [-月 b=(b0,b1)=(入，1) w(o）=ΠAa,o(o)IIb() (u,v)∈E v∈V edge activity: external field: λ○ 01
Two-State Spin System A = A0,0 A0,1 A1,0 A1,1 = 1 1 2 states {0,1} configuration : V {0, 1} graph G=(V,E) edge activity: 1 external field: 1 b = (b0, b1)=(, 1) w() = (u,v)E A(u),(v) vV b(v)
Two-State Spin System graph G=(V,E 2 states {0,1) configuration V->{0,1} 4-[=日 b=(b0,b1)=(入，1) w(o)=ΠAgu.a(wΠba) (u,v)∈E u∈V Gibbs measure: Pr(a)= w(o) Z(G) partition function: ZG )=入w(o）》 o∈{0,1}V
Two-State Spin System A = A0,0 A0,1 A1,0 A1,1 = 1 1 2 states {0,1} configuration : V {0, 1} graph G=(V,E) w() = (u,v)E A(u),(v) vV b(v) Gibbs measure: = {0,1}V partition function: Z(G) w() 8Z() = w() Z(G) b = (b0, b1)=(, 1)
w(o)=Ao(u),(v)IIba() (u,w)∈E ∈V partition function: Z(G)=∑w(a) o∈{0,1}v Gibbs measure: Pr(a)= w(o) ZG) marginal probability: Pr(σ(v)=0|OA) 1/n additive error for FPTAS for Z(G) marginal in poly(n)-time
w() = (u,v)E A(u),(v) vV b(v) marginal probability: 1/n additive error for marginal in poly(n)-time FPTAS for Z(G) Gibbs measure: 8Z() = w() Z(G) = {0,1}V partition function: Z(G) w() 8Z((v) = 0 | )
ferromagnetic: Byy >1 FPRAS:[Jerrum-Sinclair'93][Goldberg-Jerrum-Paterson'03] anti-ferromagnetic: By<1 hardcore model:B=0,y =1 [Weitz'06] Ising model:B=y [Sinclair-Srivastava-Thurley'12] (B,y,A)lies in the interior of FPTAS for graphs uniqueness region of A-regular tree of max-degree△ 2.5 -By=1 uiqueness threshold threshold achieved by heatbath random walk [Goldberg-Jerrum-Paterson'03] 15 [Li-Lu-Y.'12]: 0.5 0<B.y<1 FPTAS for arbitrary graphs 0 0.5 1.5 2.5
ferromagnetic: [Jerrum-Sinclair’93] > 1 FPRAS: [Goldberg-Jerrum-Paterson’03] anti-ferromagnetic: < 1 hardcore model: Ising model: = 0, = 1 = ∃ FPTAS for graphs of max-degree Δ (β, γ, λ) lies in the interior of uniqueness region of Δ-regular tree [Sinclair-Srivastava-Thurley’12] [Weitz’06] 0 0.5 1 1.5 2 2.5 3 0 0.5 1 1.5 2 2.5 3 0< , <1 = 1 uniqueness threshold threshold achieved by heatbath random walk [Li-Lu-Y. ’12]: FPTAS for arbitrary graphs [Goldberg-Jerrum-Paterson’03]