Unified theory for finite Markov chains
Unified theory for finite Markov chains
复制标题
有限马尔可夫链的统一理论
DOI：
10.1016/j.aim.2019.03.004
复制
发表时间：
2017
影响因子：
1.7
通讯作者：
A. Schilling
中科院分区：
文献类型：
--
作者：
J. Rhodes;A. Schilling
我们提供了一个统一的框架来计算有限半群S上任何有限不可约马氏链的平稳分布或任何不可约随机游动的等价分布。我们的方法通过具有指定生成元的有限半群的Karnofsky-Rhodes展开式和McCammond展开式使用几何有限半群理论；这不涉及任何线性代数。原始的Tsetlin库是通过对P(N)应用展开而获得的，P(N)是由n个元素集合的所有子集组成的集合。我们的建立推广了Brown和Diaconis以前关于左正则带(或R-平凡带)的开创性工作，Ayyer，Steinberg，Thiéry和第二作者对R-平凡半群的推广，以及Chung和Graham最近的重要工作。S的右Cayley图关于生成元的Karnofsky-Rhodes展开式又产生右Cayley图。McCammond展开式提供了展开式S中元素的范式。利用我们以前在Berstel，Perrin，Rutenauer工作基础上对Silva的结果，我们构造了(无限)信号量码，我们可以在其上定义马尔可夫链。这些信号码可以利用几何半群理论进行集中。利用规范形和相应的Kleene表达式，给出了扩展的S和原始S的有限马氏链的平稳分布公式.分析规范形还给出了混合时间的估计.
We provide a unified framework to compute the stationary distribution of any finite irreducible Markov chain or equivalently of any irreducible random walk on a finite semigroup S. Our methods use geometric finite semigroup theory via the Karnofsky–Rhodes and the McCammond expansions of finite semigroups with specified generators; this does not involve any linear algebra. The original Tsetlin library is obtained by applying the expansions to P (n), the set of all subsets of an n element set. Our set-up generalizes previous groundbreaking work involving left-regular bands (or R-trivial bands) by Brown and Diaconis, extensions to R-trivial semigroups by Ayyer, Steinberg, Thiéry and the second author, and important recent work by Chung and Graham. The Karnofsky–Rhodes expansion of the right Cayley graph of S in terms of generators yields again a right Cayley graph. The McCammond expansion provides normal forms for elements in the expanded S. Using our previous results with Silva based on work by Berstel, Perrin, Reutenauer, we construct (infinite) semaphore codes on which we can define Markov chains. These semaphore codes can be lumped using geometric semigroup theory. Using normal forms and associated Kleene expressions, they yield formulas for the stationary distribution of the finite Markov chain of the expanded S and the original S. Analyzing the normal forms also provides an estimate on the mixing time.