Parallelising Glauber dynamics

For distributions over discrete product spaces prodi=1n Omegai', Glauber dynamics is a Markov chain that at each step, resamples a random coordinate conditioned on the other coordinates. We show that k-Glauber dynamics, which resamples a random subset of k coordinates, mixes k times faster in chi2-divergence, and assuming approximate tensorization of entropy, mixes k times faster in KL-divergence. We apply this to obtain parallel algorithms in two settings: (1) For the Ising model μJ,h(x)propto exp(frac1 2leftlangle x,Jx rightrangle + langle h,xrangle) with |J|<1-c (the regime where fast mixing is known), we show that we can implement each step of widetilde Theta(n/|J|F)-Glauber dynamics efficiently with a parallel algorithm, resulting in a parallel algorithm with running time widetilde O(|J|F) = widetilde O(√ n). (2) For the mixed p-spin model at high enough temperature, we show that with high probability we can implement each step of widetilde Theta(√ n)-Glauber dynamics efficiently and obtain running time widetilde O(√ n).