Semigroups, rings, and Markov chains

Abstract

We analyze random walks on a class of semigroups called ``left-regular bands''. These walks include the hyperplane chamber walks of Bidigare, Hanlon, and Rockmore. Using methods of ring theory, we show that the transition matrices are diagonalizable and we calculate the eigenvalues and multiplicities. The methods lead to explicit formulas for the projections onto the eigenspaces. As examples of these semigroup walks, we construct a random walk on the maximal chains of any distributive lattice, as well as two random walks associated with any matroid. The examples include a q-analogue of the Tsetlin library. The multiplicities of the eigenvalues in the matroid walks are ``generalized derangement numbers'', which may be of independent interest.

To appear in J. Theoret. Probab

References in corpus (1)

• Lectures on 0/1-polytopes

Cited by in corpus (11)

• Representation Theory of Finite Semigroups, Semigroup Radicals and Formal Language Theory
• Quivers of monoids with basic algebras
• Primitive orthogonal idempotents for R-trivial monoids
• Markov chains for promotion operators
• A comodule-bialgebra structure for word-series substitution and mould composition
• Eigenvectors for a random walk on a hyperplane arrangement
• Cumulants, Spreadability and the Campbell-Baker-Hausdorff Series
• Linear compactness and combinatorial bialgebras
• Generalizations of an Expansion Formula for Top to Random Shuffles
• Random walks on rings and modules
• Markov chains through semigroup graph expansions (a survey)