论文标题
混合时间和非弯曲的马尔可夫链的扩展
Mixing time and expansion of non-negatively curved Markov chains
论文作者
论文摘要
我们为稀疏的马尔可夫链建立了非负曲率的三个显着后果。首先，它们的电导与状态数量降低。其次，他们的位移至少是扩散的，直到混合时间为止。第三，他们从未表现出截止现象。第一个结果为Ollivier，Milman和Naor的经典问题提供了几乎尖锐的定量答案。第二个使Lee和Peres的猜想定为具有非负曲率的图形。第三个提供了与均匀扩展的非弯曲链的最近确定的截止截止物的惊人对立面。
We establish three remarkable consequences of non-negative curvature for sparse Markov chains. First, their conductance decreases logarithmically with the number of states. Second, their displacement is at least diffusive until the mixing time. Third, they never exhibit the cutoff phenomenon. The first result provides a nearly sharp quantitative answer to a classical question of Ollivier, Milman and Naor. The second settles a conjecture of Lee and Peres for graphs with non-negative curvature. The third offers a striking counterpoint to the recently established cutoff for non-negatively curved chains with uniform expansion.
