论文标题
改进了高阶随机步行和应用的分析
Improved Analysis of Higher Order Random Walks and Applications
论文作者
论文摘要
这项工作的动机是将高阶随机步行技术扩展到简单复合物上，以分析马尔可夫链的混合时间，以解决组合问题。我们的主要结果是，就其链接的第二个特征值而言，上向上步行的第二特征值上的第二特征值上方的上限。我们在分析了马尔可夫链的混合时间中显示了一些应用程序，包括对图的独立集和两个分区矩形的共同独立集进行采样。
The motivation of this work is to extend the techniques of higher order random walks on simplicial complexes to analyze mixing times of Markov chains for combinatorial problems. Our main result is a sharp upper bound on the second eigenvalue of the down-up walk on a pure simplicial complex, in terms of the second eigenvalues of its links. We show some applications of this result in analyzing mixing times of Markov chains, including sampling independent sets of a graph and sampling common independent sets of two partition matroids.
