From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk
From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk
复制标题
DOI：
10.4230/lipics.approx/random.2021.32
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Kuikui Liu
中科院分区：
文献类型：
--
作者：
Kuikui Liu
摘要我们证明了“好”耦合的存在。离散乘积空间上任意局部马尔可夫链的汉明距离意味着Glauber动力学以黑箱形式快速混合。更具体地说，我们只要求耦合下连续迭代之间的预期距离是可求和的，而不是在最坏的情况下是一步收缩的。结合最近的局部到全局的争论[16]，当曲率条件[44]满足时，我们从有界度图上的自旋系统样本出发，建立了Glauber动力学的标准和修正的log-Sobolev常数的渐近最优下界。为了实现这一点，我们使用Stein的马氏链方法[10，46]来证明局部马氏链的“良好”耦合在[6]的意义下产生分布的谱无关性的强界。我们的主要应用是抽样有界度图上的适当列表着色。特别地，将[49，13]给出的翻转动力学的耦合与我们的技术相结合，我们证明了当颜色列表的大小至少为(11 6∆，其中ε≈10−5是小常数)时，任意有界度图上采样适当列表着色的Glauber动力学的最优O(Nlogn)混合。虽然O(N_2)混合已为人所知，但我们的方法还给出了Hamming Lipschitz函数在此区域内的Chernoff-型浓度界，这在以前是未知的。我们的方法与以前使用空间混合[6，14，15，30]为自旋系统建立光谱独立性的工作明显不同，这一点至关重要的是，在这种制度下仍然是开放的，以实现适当的列表着色。
Abstract We show that the existence of a “good” coupling w.r.t. Hamming distance for any local Markov chain on a discrete product space implies rapid mixing of the Glauber dynamics in a blackbox fashion. More specifically, we only require the expected distance between successive iterates under the coupling to be summable, as opposed to being one-step contractive in the worst case. Combined with recent local-to-global arguments [16], we establish asymptotically optimal lower bounds on the standard and modified log-Sobolev constants for the Glauber dynamics for sampling from spin systems on bounded-degree graphs when a curvature condition [44] is satisfied. To achieve this, we use Stein’s method for Markov chains [10, 46] to show that a “good” coupling for a local Markov chain yields strong bounds on the spectral independence of the distribution in the sense of [6]. Our primary application is to sampling proper list-colorings on bounded-degree graphs. In particular, combining the coupling for the flip dynamics given by [49, 13] with our techniques, we show optimal O(n log n) mixing for the Glauber dynamics for sampling proper list-colorings on any bounded-degree graph with maximum degree ∆ whenever the size of the color lists are at least ( 11 6 − ε ) ∆, where ε ≈ 10−5 is small constant. While O(n2) mixing was already known before, our approach additionally yields Chernoff-type concentration bounds for Hamming Lipschitz functions in this regime, which was not known before. Our approach is markedly different from prior works establishing spectral independence for spin systems using spatial mixing [6, 14, 15, 30], which crucially is still open in this regime for proper list-colorings.