Markov chains, -trivial monoids and representation theory
Markov chains, -trivial monoids and representation theory
复制标题
马尔可夫链，-平凡幺半群和表示论
DOI：
--
复制
发表时间：
2014
影响因子：
0.8
通讯作者：
Nicolas M. Thiéry
中科院分区：
文献类型：
--
作者：
Arvind Ayyer;A. Schilling;B. Steinberg;Nicolas M. Thiéry
我们发展了一个马氏链的一般理论，它可实现为$mathscr R$-平凡么半群上的随机游动。给出了转移矩阵的本征值的显式和简明的公式，给出了转移矩阵的特征值沿格求逆的重数的显式公式，转移矩阵可对角化的条件和混合时间的界的一些技巧.此外，我们还讨论了几个例子，如Toom-Tsetlin模型，有限Coxeter群的交换行走，以及作者以前研究过的例子，如非交换沙堆模型和偏序集上的推广马尔可夫链.其中许多例子可以看作是自由树么半群的商上的随机游动，这是我们发展的一类新的么半群的组合.
We develop a general theory of Markov chains realizable as random walks on $mathscr R$-trivial monoids. It provides explicit and simple formulas for the eigenvalues of the transition matrix, for multiplicities of the eigenvalues via M"obius inversion along a lattice, a condition for diagonalizability of the transition matrix and some techniques for bounding the mixing time. In addition, we discuss several examples, such as Toom-Tsetlin models, an exchange walk for finite Coxeter groups, as well as examples previously studied by the authors, such as nonabelian sandpile models and the promotion Markov chain on posets. Many of these examples can be viewed as random walks on quotients of free tree monoids, a new class of monoids whose combinatorics we develop.