Glauber Dynamics starting from an arbitrary Xo E [g] G(V,E) transition for XX+1: pick a uniform random vertex v; resample X(v)according to the marginal distribution induced by u at vertex v conditioning on X(N(v)); marginal distribution: bu(c)ΠueN回A(u,(Xu,) Prxet()) MRF:o∈g', u(a) ΠAe(o,o)Πb(o) e=(u,v)EE uV stationary distribution:u mixing time::Tmix=max min{t|drv(Xt,)）≤2e} XoGlauber Dynamics G(V,E): pick a uniform random vertex v; resample X(v) according to the marginal distribution induced by µ at vertex v conditioning on Xt(N(v)); starting from an arbitrary X0 ∈ [q]V transition for Xt → Xt+1 : marginal distribution: Pr[Xv = x | XN(v)] = bv(x) Q u2N(v) A(u,v)(Xu, x) P y2[q] bv(y) Q u2N(v) A(u,v)(Xu, y) Ae bv v µ(￾) / Y e=(u,v)2E Ae(￾u, ￾v) Y v2V bv(￾v) MRF: 8￾ 2 [q] V , stationary distribution: µ mixing time: ⌧mix = max X0 min ￾ t | dTV(Xt, µ)  1 2e