Parallelize Single-Site Dynamics up to Dobrushin Criterion

Single-site dynamics are canonical Markov chain based algorithms for sampling from high-dimensional distributions, such as the Gibbs distributions of graphical models. We introduce a simple and generic parallel algorithm that faithfully simulates single-site dynamics. Under a much relaxed, asymptotic variant of the ℓ p -Dobrushin’s condition—where the Dobrushin’s influence matrix has a bounded ℓ p -induced operator norm for an arbitrary p ∈ [1, ∞]—our algorithm simulates N steps of single-site updates within a parallel depth of O ( N / n + log n ) on \(\tilde{O}(m) \) processors, where n is the number of sites and m is the size of the graphical model. For Boolean-valued random variables, if the ℓ p -Dobrushin’s condition holds—specifically, if the ℓ p -induced operator norm of the Dobrushin’s influence matrix is less than 1—the parallel depth can be further reduced to O (log N + log n ), achieving an exponential speedup. These results suggest that single-site dynamics with near-linear mixing times can be parallelized into \(\mathsf {RNC} \) sampling algorithms, independent of the maximum degree of the underlying graphical model, as long as the Dobrushin influence matrix maintains a bounded operator norm. We show the effectiveness of this approach with \(\mathsf {RNC} \) samplers for the hardcore and Ising models within their uniqueness regimes, as well as an \(\mathsf {RNC} \) SAT sampler for satisfying solutions of CNF formulas in a local lemma regime. Furthermore, by employing non-adaptive simulated annealing, these \(\mathsf {RNC} \) samplers can be transformed into \(\mathsf {RNC} \) algorithms for approximate counting.