M-T dynamic sampler heat-bath dynamic sampler R[vertices affected by update); R[vertices affected by update); while R≠odo while R≠odo for every vR,resampleb,independently; pick a random u R; every internal e ={u,v)CR accepts w.p.A(X); 1 with probability o- do every boundary e =[u,v)with u ER,vR accepts w.p. u(X.IXNG） Ae(Xe X) resample X,~4(·|Xwoi A(Xold,X.) delete u from R; R← else e rejects add all neighbors of u to R; chain:(X,R)→(X',R) Conditional Gibbs property: Given anyRandthealways tollows defined in [Feng,Vishnoi,Y.'19],also implicitly in [Guo,Jerrum'18] 。 satisfied invariantly by the M-T and heat-bath dynamic samplers >Las Vegas perfect samplers (interruptible) retrospectively,holds for Partial Rejection Sampling [Guo,Jerrum,Liu'17] and Randomness Recycler [Fill,Huber '00]; while do pick a random ; with probability do resample ; delete from ; else add all neighbors of to ; R ← {vertices affected by update} R ≠ ∅ u ∈ R ∝ 1 μu(Xu ∣ XN(u)) Xu ∼ μu( ⋅ ∣ XN(u) ) u R u R M-T dynamic sampler heat-bath dynamic sampler Given any R and X , the always follows . R XR μ XR R Conditional Gibbs property: • defined in [Feng, Vishnoi, Y. ’19], also implicitly in [Guo, Jerrum ’18] • satisfied invariantly by the M-T and heat-bath dynamic samplers Las Vegas perfect samplers (interruptible) • retrospectively, holds for Partial Rejection Sampling [Guo, Jerrum, Liu ’17] and Randomness Recycler [Fill, Huber ’00] ⟹ chain: (X, R) ⟶ (X′ , R′) ; while do for every , resample independently; every internal accepts w.p. ; every boundary with accepts w.p. ; R ← {vertices affected by update} R ≠ ∅ v ∈ R Xv ∼ bv e = {u, v} ⊆ R Ae(Xu, Xv) e = {u, v} u ∈ R, v ∉ R ∝ Ae(Xu, Xv) Ae(X��� u , Xv) ; R ← ⋃ e rejects e