MCMC Sampling Markov chain for sampling=(X1,X2,...,X) Gibbs sampling(Glauber dynamics,heat-bath) pick a random i; [Glauber,'63] resample Xi~u(·W(); [Geman,Geman,'84] Metropolis-Hastings algorithm pick a random i; propose a random c; [Metropolis et al,'53] X=cwp.∝4(X)/u: [Hastings,'84] Analysis:coupling methods [Aldous,'83][Jerrum,'95][Bubley,Dyer '97] may give O(n log n)upper bound for mixing timeMCMC Sampling • Gibbs sampling (Glauber dynamics, heat-bath) • Metropolis-Hastings algorithm Markov chain for sampling X = (X1, X2,…, Xn) ∼ μ pick a random i; resample Xi ~ µv( · |N(v)); pick a random i; propose a random c; Xi = c w.p. ∝ µ(X’)/µ(X); [Glauber, ’63] [Geman, Geman, ’84] [Metropolis et al, ’53] [Hastings, ’84] • Analysis: coupling methods [Aldous, ’83] [Jerrum, ’95] [Bubley, Dyer ’97] may give O(n log n) upper bound for mixing time