The LocalMetropolis Chain proposals: current: starting from an arbitrary XE [g],at each step: each vertex vEV independently proposes a random o,∈[lwith probabilityb(ou)/∑,(): a collective coin flipping each edge e=(u,v)passes its check independently made between With prob.Ae(X,)Ae(o:X.)Ae()/max(Ae(i,j))3; u and v i,jelal each vertex vEV accepts its proposal and update Xy to ov if all incident edges pass their checks; [Feng,Sun,Y.'171:the LocalMetropolis chain is time-reversible w.r.t.the MRF Gibbs distribution u.The LocalMetropolis Chain starting from an arbitrary X ∈ [q]V , at each step: each vertex v∈V independently proposes a random σv∈[q] with probability ; each edge e=(u,v) passes its check independently with prob. ; each vertex v∈V accepts its proposal and update Xv to σv if all incident edges pass their checks; a collective coin flipping made between u and v u v w current: Xu Xv Xw proposals: σu σv σw • [Feng, Sun, Y. ’17]: the LocalMetropolis chain is time-reversible w.r.t. the MRF Gibbs distribution µ. bv(￾v)/ P i2[q] bv(i) Ae(Xu, ￾v)Ae(￾u, Xv)Ae(￾u, ￾v)/ max i,j2[q] (Ae(i, j))3