Introduction to the Correlation Decay Method Yitong Yin Nanjing University Introduction to Partition Functions Workshop,July 20,2018 Computational Aspects of Partition Functions,CIB@EPFL
Introduction to the Correlation Decay Method Yitong Yin Nanjing University Introduction to Partition Functions Workshop, July 20, 2018 Computational Aspects of Partition Functions, CIB@EPFL
July 20:Introduction to the correlation decay method (Yitong) July 23:Correlation decay for distributed counting (Yitong) July 25:Beyond bounded degree graphs (Piyush) July 26:Correlation decay,zeros of polynomials,and the Lovasz local lemma (Piyush)
• July 20: Introduction to the correlation decay method (Yitong) • July 23: Correlation decay for distributed counting (Yitong) • July 25: Beyond bounded degree graphs (Piyush) • July 26: Correlation decay, zeros of polynomials, and the Lovász local lemma (Piyush)
Counting Independent Set hardcore model:undirected graph G(V,E)fugacity>0 IV()T is an independent set in c otherwise partition function:Z=ZG(A)=>w(I) ICV e uniqueness threshold:Ac(A)= (△-1)A-1 (△-2)A △-2 Computing Zc()in graphs with constant max-degree λc(△)→no FPRAS unless NP=RP [Galanis Stefankovie Vigoda 12][Sly Sun 12]
Counting Independent Set hardcore model: • λ λc(Δ) 㱺 no FPRAS unless NP=RP ∀ I ⊆ V: uniqueness threshold: Computing ZG(λ) in graphs with constant max-degree ≤ ∆ [Galanis Štefankovič Vigoda 12] [Sly Sun 12] [Weitz 06] undirected graph G(V,E) fugacity λ > 0 partition function: Z = ZG() = X I✓V w(I) w(I) = ( |I| I is an independent set in G 0 otherwise c() = ( 1)1 ( 2) ⟸ strong spatial mixing ⇡ e 2
Spin System undirected graph G=(V,E) finite integer g≥2 configuration o∈[gl' weight:w(o)=A(ou,)b(o) {u,w}∈E u∈V A:[ql×[q→R≥o symmetric gxg matrix (symmetric binary constraint) b:[q→R>0 g-vector (unary constraint) partition function: Zc=∑w(a) o∈[gV Gibbs distribution: c(o)= w(o) ZG
Spin System undirected graph G = (V, E) finite integer q ≥ 2 2 [q] V configuration w() = Y {u,v}2E A(u, v) Y v2V weight: b(v) A : [q] ⇥ [q] ! R0 b : [q] ! R0 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) finite integer q≥2 configuration o∈[glY weight:w()=A(ou,)b(o) {u,v}∈E v∈V ·2-spin system:q=2,o∈{0,1}V symmetric A= a00 a10 6= ●hardcore model: 4-81- ●Ising model ●multi-spin system:general g≥2 ●Potts model: 1 A= ●q-coloring:B:=0 1 b= 1.:1
• 2-spin system: q =2, • hardcore model: • Ising model: • multi-spin system: general q ≥ 2 • Potts model: • q-coloring: β=0 undirected graph G = (V, E) 2 [q] V configuration w() = Y {u,v}2E A(u, v) Y v2V weight: b(v) 2 {0, 1}V 1 1 2 6 6 6 4 ... 3 7 7 7 A = 5 2 6 4 1 . . . 1 3 7 b = 5 A = a00 a01 a10 a11 b = b0 b1 A = 0 1 1 1 b = 1 A = 1 1 symmetric finite integer q ≥ 2 b = 1
Marginal Probability undirected graph G=(V,E) finite integer g≥2 Gibbs distribution uG over all configurations in [g] V possible boundary condition o E [g]A specified on an arbitrary subset ACD marginal distribution at vertexy: VxE [q]:u()=Pr [X=XA=0] XoHG a）=4o)）=Π-1(a) ZG i=1
Marginal Probability Gibbs distribution µG over all configurations in [q]V undirected graph G = (V, E) finite integer q ≥ 2 specified on an arbitrary subset Λ⊂V ∀ possible boundary condition σ ∈ [q]Λ marginal distribution at vertex µ v ∈ V : v 8x 2 [q] : µ v (x) = Pr X⇠µG [Xv = x | X⇤ = ] w() ZG = µ() = Y n i=1 µ1,...,i1 vi (i)
Marginal Probability undirected graph G=(V,E) finite integer q≥2 Gibbs distribution uG over all configurations in [g] V possible boundary condition o E [g]A specified on an arbitrary subset ACD marginal distribution g at vertex vEV: x∈[q]：%(x)=Pr[Xu=x|XA=o] XouG approximately approximately computingu computing ZG approx.inference approx.counting
Marginal Probability Gibbs distribution µG over all configurations in [q]V undirected graph G = (V, E) finite integer q ≥ 2 specified on an arbitrary subset Λ⊂V ∀ possible boundary condition σ ∈ [q]Λ marginal distribution at vertex µ v ∈ V : v 8x 2 [q] : µ v (x) = Pr X⇠µG [Xv = x | X⇤ = ] approximately computing µ v approximately computing ZG approx. inference approx. counting
Spatial Mixing (Decay of Correlation) marginal distribution at vertex v conditioning on weak spatial mixing（WsM)）at rateδ()： o,T∈[gl：‖lg-IlTv≤6(dista(v,A) boundary conditions 0 dist(v,A) on infinite graphs: WSM 1<> uniqueness of infinite- volume Gibbs measure 入≤λ(A)<> WSM of hardcore model on infinite A-regular tree
Spatial Mixing (Decay of Correlation) G v dist(v,Λ) weak spatial mixing (WSM) at rate δ( ): µ v : marginal distribution at vertex v conditioning on σ boundary conditions on infinite graphs: WSM uniqueness of infinitevolume Gibbs measure µ v WSM of hardcore model on infinite Δ-regular tree Λ 8, ⌧ 2 [q] ⇤ : kµ v µ⌧ v kT V (distG(v,⇤)) c()
Spatial Mixing (Decay of Correlation) marginal distribution at vertex v conditioning on weak spatial mixing（WsM)at rateδ()： ∀o,T∈[gA:lμg-lTv≤(distc(w,△) strong spatial mixing(SSM)at rateδ()： Vo,T∈[g]that differ on△：lμg-utTv≤(distc(v,△) SSM dist(v,△) marginal probabilities are well approximated by the local information
Spatial Mixing (Decay of Correlation) strong spatial mixing (SSM) at rate δ( ): weak spatial mixing (WSM) at rate δ( ): µ v : marginal distribution at vertex v conditioning on σ SSM marginal probabilities are well approximated by the local information G v dist(v,Δ) Δ Λ\Δ weak spatial mixing (WSM) at rate δ( ): 8, ⌧ 2 [q] ⇤ : kµ v µ⌧ v kT V (distG(v,⇤)) kµ v µ⌧ 8, ⌧ 2 [q] v kT V (distG(v, )) ⇤ that differ on Δ:
Tree Recurrence hardcore model:i independent set I in T u( pr≌，Pr[is unoccupied by I] IouT T Wd T T Ta pz,≌，Pr[is unoccupied byI] IouTi
pT , Pr I⇠µT [v is unoccupied by I ] Ti v ui T hardcore model: independent set I in T µT (I) / |I| Tree Recurrence pTi , Pr I⇠µTi [ui is unoccupied by I ] u1 ud T1 Td