Markov chains, $\mathcal{R}$-trivial monoids and representation theory

Abstract

We develop a general theory of Markov chains realizable as random walks on $\mathcal{R}$-trivial monoids. It provides explicit and simple formulas for the eigenvalues of the transition matrix, for multiplicities of the eigenvalues via Möbius 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.

Dedicated to Stuart Margolis on the occasion of his sixtieth birthday; 71 pages; final version to appear in IJAC

References in corpus (2)

• The oriented swap process
• Algebraic Properties of a Disordered Asymmetric Glauber Model

Cited by in corpus (13)

• Unified theory for finite Markov chains
• Multivariate Juggling Probabilities
• Random walks on semaphore codes and delay de Bruijn semigroups
• Lumpings of Algebraic Markov Chains arise from Subquotients
• The Hilbert-Galton board
• Normal distributions of finite Markov chains
• Upper bounds on mixing time of finite Markov chains
• Full Current Statistics for a Disordered Open Exclusion Process
• Holonomy theorem for finite semigroups
• Random motion on finite rings, I: commutative rings
• Markov chains through semigroup graph expansions (a survey)
• A study on the composition of elementary cellular automata
• Thin MC left regular bands