Glauber Dynamics [Glauber'63] Markov chain {Xi}=0.1.2....over independent sets in G(V,E) transition Xi→Xi+l: pick a uniform random vertex v; if ueX,for all v's neighbors u: Xt+1= XeU{)with prob.中 Ixi\iv} with prob. else X++1=Xi; ergodic,irreducible Markoy chain time-reversible w.r.t.u convergence Thm Xi→uast→oo
Glauber Dynamics pick a uniform random vertex v; if u∉Xt for all v’s neighbors u: else Xt+1 = Xt; Xt+1 = ( Xt [ {v} with prob. 1+ Xt \ {v} with prob. 1 1+ Markov chain {Xt}t=0,1,2,… over independent sets in G(V,E) transition Xt → Xt+1 : ergodic, irreducible time-reversible w.r.t. μ Markov chain convergence Thm Xt → μ as t → ∞ [Glauber’63]
Glauber Dynamics [Glauber'63] Markov chain {Xi}=0.1.2....over independent sets in G(V,E) transition X→Xi+l: pick a uniform random vertex v; if ueX,for all v's neighbors u: Xt+1= XeU{)with prob.中 x\{o} with prob. else X++1=Xr; ergodic,irreducible Markov chain time-reversible w.r.t.u convergence Thm Xt>uast→oo mixing time:Tmix max mint drv(Xt,u)<0.1 Xo
Glauber Dynamics pick a uniform random vertex v; if u∉Xt for all v’s neighbors u: else Xt+1 = Xt; Xt+1 = ( Xt [ {v} with prob. 1+ Xt \ {v} with prob. 1 1+ Markov chain {Xt}t=0,1,2,… over independent sets in G(V,E) transition Xt → Xt+1 : ergodic, irreducible time-reversible w.r.t. μ Markov chain convergence Thm Xt → μ as t → ∞ mixing time: ⌧mix = max X0 min{t | dTV(Xt, µ) < 0.1} [Glauber’63]
sampling(with bounded error)from the hardcore model on graphs with max-degree A and fugacity )>0 uniqueness threshold:()=(A1)(1) e (4-2)A≈△-2
sampling (with bounded error) from the hardcore model on graphs with max-degree Δ and fugacity λ>0 c() = ( 1)(1) ( 2) ⇡ e 2 uniqueness threshold:
sampling(with bounded error)from the hardcore model on graphs with max-degree△and fugacityλ>O uniqueness threshold:d.(△)=（A-I)a-” e ≈ (△-2)A △-2 [Glauber'63]discovery of Glauber dynamic
• [Glauber’63] discovery of Glauber dynamic sampling (with bounded error) from the hardcore model on graphs with max-degree Δ and fugacity λ>0 c() = ( 1)(1) ( 2) ⇡ e 2 uniqueness threshold:
sampling(with bounded error)from the hardcore model on graphs with max-degree△and fugacityλ>O uniqueness threshold:()=(A-1)() e (△-2)A ≈△-2 [Glauber'63]discovery of Glauber dynamic [Luby-Vigoda'99][Dyer-Greenhill'00][Vigoda'01] Tmix=O(nlog n)for Glauber dynamics when A<2/(A-2)
• [Glauber’63] discovery of Glauber dynamic • [Luby-Vigoda’99][Dyer-Greenhill’00][Vigoda’01] τmix=O(nlog n) for Glauber dynamics when λ<2/(Δ-2) sampling (with bounded error) from the hardcore model on graphs with max-degree Δ and fugacity λ>0 c() = ( 1)(1) ( 2) ⇡ e 2 uniqueness threshold: