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= X:Uf with prob. with prob. else X++1=Xi;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 : [Glauber’63]