Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)
Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)
复制标题
DOI：
--
复制
发表时间：
2016-03
期刊：
影响因子：
--
通讯作者：
V. Guruswami
中科院分区：
文献类型：
--
作者：
V. Guruswami
综述了现有的马尔可夫链混合时间约束技术。混合时间与称为电导的几何参数有关，电导是边缘膨胀的度量。电导的边界通常通过一种称为“规范路径”的技术来获得，其思想是找到一组路径，每个源-目标对之间都有一条路径，这样就不会有严重的拥塞。然而，规范路径方法不能总是显示快速混合链的快速混合。如果我们允许一对状态之间的流沿着多条路径传播，那么这个缺点就消失了。我们证明了对于一大类马尔可夫链，正则路径确实捕获了快速混合。允许多条路径路由流在证明中仍然有很大帮助，正如Morris和Sinclair （FOCS'99）对采样0/1背包解的马尔可夫链的快速混合的结果所说明的那样。另一种证明快速混合的方法是“耦合”。路径耦合是由Bubley & Dyer （FOCS'97）发现的一种变体，它通常极大地降低了设计良好耦合的复杂性。我们给出了路径耦合在快速混合证明中的几个应用。这些方法总是比使用电导得到的混合时间边界要好得多，而且基于耦合的证明通常更简单。这引发了这样一个问题：在链快速混合的情况下，是否可以使耦合工作。Kumar和Ramesh （FOCS'99）对这个问题给出了否定的回答，他们表明，没有任何耦合策略可以证明Jerrum-Sinclair链的快速混合可以实现采样完美和接近完美的匹配。
We survey existing techniques to bound the mixing time of Markov chains. The mixing time is related to a geometric parameter called conductance which is a measure of edge-expansion. Bounds on conductance are typically obtained by a technique called "canonical paths" where the idea is to find a set of paths, one between every source-destination pair, such that no edge is heavily congested. However, the canonical paths approach cannot always show rapid mixing of a rapidly mixing chain. This drawback disappears if we allow the flow between a pair of states to be spread along multiple paths. We prove that for a large class of Markov chains canonical paths does capture rapid mixing. Allowing multiple paths to route the flow still does help a great deal in proofs, as illustrated by a result of Morris & Sinclair (FOCS'99) on the rapid mixing of a Markov chain for sampling 0/1 knapsack solutions. A different approach to prove rapid mixing is "Coupling". Path Coupling is a variant discovered by Bubley & Dyer (FOCS'97) that often tremendously reduces the complexity of designing good Couplings. We present several applications of Path Coupling in proofs of rapid mixing. These invariably lead to much better bounds on mixing time than known using conductance, and moreover Coupling based proofs are typically simpler. This motivates the question of whether Coupling can be made to work whenever the chain is rapidly mixing. This question was answered in the negative by Kumar & Ramesh (FOCS'99), who showed that no Coupling strategy can prove the rapid mixing of the Jerrum-Sinclair chain for sampling perfect and near-perfect matchings.