论文标题
正则修改的对数 - 索堡不平等和马尔可夫链的比较
Regularized modified log-Sobolev inequalities, and comparison of Markov chains
论文作者
论文摘要
在这项工作中，我们为有限状态空间上两个可逆的马尔可夫链的修改log-Sobolev不等式（MLSI）常数开发了一个比较程序。 MLSI Dirichlet形式的有效比较是马尔可夫链理论中众所周知的障碍。我们通过引入一个{\ it正则化} mlSI常数来解决这个问题，在某些假设下，该常数的数量级与通常的MLSI常数相同，但可以进行比较，因此在某些情况下可以估算得多。作为此一般比较过程的应用，我们在简单的两部分常规图上，用固定度$ d $ $ n $的简单两分的常规图提供了开关链的MLSI常数。我们的估计意味着开关链的总变化混合时间为订单$ o_d（n \ log n）$。结果取决于$ d $的最佳倍数，并解决了一个长期的开放问题。我们希望本文实施的MLSI比较技术将找到进一步的应用程序。
In this work, we develop a comparison procedure for the Modified log-Sobolev Inequality (MLSI) constants of two reversible Markov chains on a finite state space. Efficient comparison of the MLSI Dirichlet forms is a well known obstacle in the theory of Markov chains. We approach this problem by introducing a {\it regularized} MLSI constant which, under some assumptions, has the same order of magnitude as the usual MLSI constant yet is amenable for comparison and thus considerably simpler to estimate in certain cases. As an application of this general comparison procedure, we provide a sharp estimate of the MLSI constant of the switch chain on the the set of simple bipartite regular graphs of size $n$ with a fixed degree $d$. Our estimate implies that the total variation mixing time of the switch chain is of order $O_d(n\log n)$. The result is optimal up to a multiple depending on $d$ and resolves a long-standing open problem. We expect that the MLSI comparison technique implemented in this paper will find further applications.
