论文标题
有限马尔可夫链的混合时间上的上限
Upper bounds on mixing time of finite Markov chains
论文作者
论文摘要
我们提供了一个通用框架，用于计算有限马尔可夫链的混合时间的上限时，其最小的理想是零。我们的分析基于Brown和Diaconis的结果以及我们先前关于有限马尔可夫链的固定分布的工作。可以从Markov链上有限的半群的右Cayley图的Karnofsky--Rhodes和McCammond扩展计算固定分布。使用循环图，该图是由带有连接循环的直线组成的平面图，对于概率中的固定分布有理性表达式。从这些中，我们获得了混合时间的界限。此外，我们还提供了一个新的马尔可夫连锁店，该链在带有$ n $顶点的Poset的线性扩展上，其灵感来自但与Ayyer，Klee和最后一位作者的促销马尔可夫链不同。这个马尔可夫链的混合时间为$ O（n \ log n）$。
We provide a general framework for computing upper bounds on mixing times of finite Markov chains when its minimal ideal is left zero. Our analysis is based on combining results by Brown and Diaconis with our previous work on stationary distributions of finite Markov chains. Stationary distributions can be computed from the Karnofsky--Rhodes and McCammond expansion of the right Cayley graph of the finite semigroup underlying the Markov chain. Using loop graphs, which are planar graphs consisting of a straight line with attached loops, there are rational expressions for the stationary distribution in the probabilities. From these we obtain bounds on the mixing time. In addition, we provide a new Markov chain on linear extension of a poset with $n$ vertices, inspired by but different from the promotion Markov chain of Ayyer, Klee and the last author. The mixing time of this Markov chain is $O(n \log n)$.
