Semigroups, rings, and Markov chains

2000/06/20 by Kenneth S. Brown, Brown, Kenneth S. · 3 citations
Computer Science · Mathematics · #05A99 #60J10 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR) #math.CO #math.PR #msc:05A99 #msc:60J10 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0006145

To appear in J. Theoret. Probab

arxiv created 2000/06/20 · openalex publication_date 2000/06/20 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Left regular bands with symmetry
• Stochastically Evolving Graphs via Edit Semigroups
• Meet OCL^\sharp , a relational object constraint language

Related

• Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries
• Hypergroups and distance distributions of random walks on graphs
• The Quiver of the Semigroup Algebra of a Left Regular Band
• The adjacency matrices and the transition matrices related to random walks on graphs
• Algebraically recurrent random walks on groups