Title: Unified theory for finite Markov chains,
Abstract: 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 $\mathscr{R}$-trivial
bands) by Brown and Diaconis, extensions to $\mathscr{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.