《计算机科学》相关教学资源（参考文献）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 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) ￾ 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)

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) ￾ v￾V 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]

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): oaB,TaB∈{0,1}B |Pr((v)=0|08B)-Pr(a(v)=0 TaB)I<exp(-S(t)) strong spatial mixing (SSM): Pr((v)=0 00B,n)-Pr(G(v)=0 TOB,A)I<exp(-2(t)) G Uniqueness: WSM in reg.tree

Correlation Decay strong spatial mixing (SSM): B ￾B G v ￾￾￾B, ￾￾B ￾ {0, 1}￾B ￾ t weak spatial mixing (WSM): Uniqueness: WSM in reg. tree | 8Z(￾(v) = 0 | ￾￾B) ￾ 8Z(￾(v) = 0 | ￾￾B)| ￾ M`X(￾￾(t)) | 8Z(￾(v) = 0 | ￾￾B, ￾￾) ￾ 8Z(￾(v) = 0 | ￾￾B, ￾￾)| ￾ M`X(￾￾(t))

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: