Warm-up:When Luby meets Glauber starting from an arbitrary Xo E [g] at each step,for each vertex vV: GV,E) independently sample a random Luby number B.∈[0,1]； step if B,is locally maximum among its neighborhood Nv): resample X(v)according to the Glauber step marginal distribution induced by u at vertex v conditioning on X(Nv)); Luby step:Independently sample a random independent set. Glauber step:For independent set vertices,update correctly according to the current marginal distributions. Stationary distribution:the Gibbs distribution u
Warm-up: When Luby meets Glauber G(V,E): resample X(v) according to the marginal distribution induced by µ at vertex v conditioning on Xt(N(v)); at each step, for each vertex v∈V: starting from an arbitrary X0 ∈ [q]V independently sample a random number βv∈[0,1]; if βv is locally maximum among its neighborhood N(v): Luby step Glauber step • Luby step: Independently sample a random independent set. • Glauber step: For independent set vertices, update correctly according to the current marginal distributions. • Stationary distribution: the Gibbs distribution µ
Mixing of LubyGlauber influence matrix {Pv,u,Ev Dobrushin's condition: lplx=ma∑p,u≤1-e vEV u∈V Theorem (Dobrushin'70;Salas,Sokal'97): Dobrushin's Tmix =O(nlogn) condition for Glauber dynamics Dobrushin's Tmix=O(△logn) condition for the LubyGlauber chain
Mixing of LubyGlauber Dobrushin’s condition: k⇢k1 = max v2V X u2V ⇢v,u 1 ✏ influence matrix {⇢v,u }v,u2V u v Theorem (Dobrushin ’70; Salas, Sokal ’97): Dobrushin’s condition for Glauber dynamics ⌧mix = O (n log n) Dobrushin’s condition for the LubyGlauber chain ⌧mix = O ( log n)