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

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) ￾ v￾V 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) ￾ v￾V 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 FPTAS for Z(G)

w(￾) = ￾ (u,v)￾E A￾(u),￾(v) ￾ v￾V 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

anti-ferromagnetic: By<1 bounded△or△=∞ (B,y,A)lies in the interiors of uniqueness regions of d-regular trees for all ds A. 3 FPTAS for graphs of max-degree A [Sly-Sun'12] [Galanis-Stefankovic-Vigoda'12]: (B,y,A)lies in the interiors of non-uniqueness regions of a-regular trees for some d≤△. NR assuming FPRAS for graphs of max-degree A

anti-ferromagnetic: ￾￾ < 1 ∃ FPTAS for graphs of max-degree Δ (β, γ, λ) lies in the interiors of uniqueness regions of d-regular trees for all d ≤ Δ. ∄ FPRAS for graphs of max-degree Δ (β, γ, λ) lies in the interiors of non-uniqueness regions of d-regular trees for some d ≤ Δ. assuming NP ≠RP [Sly-Sun’12] [Galanis-Stefankovic-Vigoda’12]: bounded Δ or Δ=∞

Uniqueness Condition marginal ±exp(-) (d+1)-regular tree at root d =A(》 t reg. tree 元d=fa(cd) lf(元d)川<1 arbitrary boundary config

Uniqueness Condition (d+1)-regular tree reg. tree t arbitrary boundary config marginal at root ± exp(-t) fd(x) = ￾ ￾￾x + 1 x + ￾ ￾d x ˆ d = fd(ˆxd) |f￾ d(ˆxd)| < 1

anti-ferromagnetic:B 1 bounded△or△=o Ju(x)= (》 d1 assuming NP≠RP 肀FPRAS for graphs of max--degree△

anti-ferromagnetic: ￾￾ 1 fd(x) = ￾ ￾￾x + 1 x + ￾ ￾d

Correlation Decay weak spatial mixing (WSM): VoaB,TaB∈{0,1}8B Prlo(v)=0100]P(v)=0TOB] strong spatial mixing (SSM): Pilo(v)=0100,]Pro(v)=0TOB,On] G error exp (-t) exponential correlation decay uniqueness:WSM in reg.tree

Correlation Decay strong spatial mixing (SSM): B ￾B G v ￾￾￾B, ￾￾B ￾ {0, 1}￾B ￾ 8Z ￾ [￾(v) = 0 | ￾￾B] ￾ 8Z ￾ [￾(v) = 0 | ￾￾B] 8Z ￾ [￾(v) = 0 | ￾￾B, ￾￾] ￾ 8Z ￾ [￾(v) = 0 | ￾￾B, ￾￾] t error < exp (-t) exponential correlation decay weak spatial mixing (WSM): uniqueness: WSM in reg. tree

Self-Avoiding Walk Tree due to Weitz(2006) G-(V,E T=TSAW(G,U) 3 6 preserve the marginal dist.at v on b bounded degree graphs: SSM> FPTAS

1 Self-Avoiding Walk Tree due to Weitz (2006) 1 2 3 4 5 6 2 4 4 1 4 4 6 5 5 6 4 3 3 5 6 5 6 4 1 G=(V,E) v T = T;)?(G, v) 6 6 6 6 6 ￾￾ preserve the marginal dist. at v SSM FPTAS on bounded degree graphs: