Correlation Decay up to Uniqueness in Spin Systems Yitong Yin Nanjing University Joint work with Liang Li (Peking Univ) Pinyan Lu (Microsoft research Asia)
Correlation Decay up to Uniqueness in Spin Systems Yitong Yin Nanjing University Joint work with Liang Li (Peking Univ) Pinyan Lu (Microsoft research Asia)
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)
A 8=B】方=o,a)=a山 w(o）=IA(,o(w)b(w) (u,w)∈E w∈V partition function: Z(G)=>w(o) σ∈{0,1}V marginal probability:Pr[(v)=0(v1),...,() Pr(r)=ΠPro(k)=T(k)|o()=T(i),1≤i< k=1 w(T) Z 1/poly(n)additive error for marginal in poly-time > FPTAS for Z(G)
w() = (u,v)E A(u),(v) vV b(v) = {0,1}V Z(G) w() A = A0,0 A0,1 A1,0 A1,1 = 1 1 partition function: marginal probability: b = (b0, b1)=(, 1) 8Z [(v) = 0 | (v1),..., (vk)] 8Z( ) = n k=1 8Z [(vk) = (vk) | (vi) = (vi), 1 i<k] = w( ) Z 1/poly(n) additive error for marginal in poly-time FPTAS for Z(G)
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 [Goldberg-Jerrum-Paterson'03] y=1 uiqueness threshold --threshold achieved by heatbath mndom walk FPRAS for arbitrary graphs 15 [Li-Lu-Y.'12]:no external field 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 [Goldberg-Jerrum-Paterson’03] FPRAS for arbitrary graphs [Li-Lu-Y. ’12]: no external field FPTAS for arbitrary graphs