The single-site dynamics are a canonical class of Markov chains for sampling from high-dimensional probability distributions, e.g. the ones represented by graphical models. We give a simple and generic parallel algorithm that can faithfully simulate single-site dynamics. When the chain asymptotically satisfies the $\ell_p$-Dobrushin's condition, specifically, when the Dobrushin's influence matrix has constantly bounded $\ell_p$-induced operator norm for an arbitrary $p\in[1,\infty]$, the parallel simulation of $N$ steps of single-site updates succeeds within $O\left({N}/{n}+\log n\right)$ depth of parallel computing using $\tilde{O}(m)$ processors, where $n$ is the number of sites and $m$ is the size of graphical model. Since the Dobrushin's condition is almost always satisfied asymptotically by mixing chains, this parallel simulation algorithm essentially transforms single-site dynamics with optimal $O(n\log n)$ mixing time to RNC algorithms for sampling. In particular we obtain RNC samplers, for the Ising models on general graphs in the uniqueness regime, and for satisfying solutions of CNF formulas in a local lemma regime. With non-adaptive simulated annealing, these RNC samplers can be transformed routinely to RNC algorithms for approximate counting. A key step in our parallel simulation algorithm, is a so-called "universal coupling" procedure, which tries to simultaneously couple all distributions over the same sample space. We construct such a universal coupling, that for every pair of distributions the coupled probability is at least their Jaccard similarity. We also prove this is optimal in the worst case. The universal coupling and its applications are of independent interests.

翻译：单站点动态是用于从高维概率分布中取样的Markov链条的卡通级, 例如由图形模型代表的模型。 我们给出一个简单和通用的平行算法, 可以忠实模拟单站点动态。 当链条自动满足 $\ ell_ p$_ p$- Dobrushin 的条件时, 具体来说, 当Dobrushin 的影响力矩阵不断将 $\ ell_ p_ p$ 诱导操作器规范捆绑在任意 $p\ in [1,\ infty] 中进行取样, 单站点更新的单点步骤($n) 的平行模拟。 双点更新在 $\ left ({N} / {n\ log nright) 中成功成功。 当链链路段运行时, 最差的Dorbrubrubralal 运算法 中, 最慢的RNC 和最低的RNC 运算法 模型中, 最难点的Rmalal 运算 。