Unified theory for finite Markov chains

DOI10.1016/J.AIM.2019.03.004MaRDI QIDQ1735485zbMATH OpenOpenAlexWikidataFDO

Authors Anne Schilling, John L. Rhodes

Publication date 28 March 2019

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.10689

zbMATH Keywords

Karnofsky-Rhodes expansionMarkov chainsMcCammond expansionsemaphore codesstationary distributionsTsetlin library

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Representation of semigroups; actions of semigroups on sets (20M30) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Combinatorial probability (60C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

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 $mathscrR$-trivial bands) by Brown and Diaconis, extensions to $mathscrR$-trivial semigroups by Ayyer, Steinberg, Thi'ery 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.

Recommendations

• Normal distributions of finite Markov chains
• Upper Bounds on Mixing Time of Finite Markov Chains
• scientific article; zbMATH DE number 2070260
• Semigroups, rings, and Markov chains
• Strong uniform times and finite random walks

Cites work

• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Algebraic properties of a disordered asymmetric Glauber model
• An extension of a theorem concerning an interesting Markov chain
• Codes and automata.
• Combinatorial Markov chains on linear extensions
• Combinatorial topology and the global dimension of algebras arising in combinatorics
• Directed nonabelian sandpile models on trees
• Edge flipping in graphs
• Eigenvectors for a random walk on a hyperplane arrangement
• FINITE AUTOMATA AND MODELS OF SIMPLE FORMS OF BEHAVIOUR
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3514781 (Why is no real title available?)
• scientific article; zbMATH DE number 3287733 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Markov Chains for Promotion Operators
• Markov chains, \(\mathcal{R}\)-trivial monoids and representation theory
• NORMAL FORMS FOR FREE APERIODIC SEMIGROUPS
• Note: random-to-front shuffles on trees
• On noncounting regular classes
• ON THE BURNSIDE SEMIGROUPS xⁿ = x^n+m
• Probability Measures on Semigroups
• Properties of the promotion Markov chain on linear extensions
• Random walks and hyperplane arrangements
• Random walks on semaphore codes and delay de Bruijn semigroups
• Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-Organizing Libraries
• Semigroup expansions using the derived category, kernel, and Malcev products
• Semigroups, rings, and Markov chains
• Stationary distribution and eigenvalues for a de Bruijn process
• THE SOLUTION TO THE WORD PROBLEM FOR THE RELATIVELY FREE SEMIGROUPS SATISFYING T^a = T^a+b WITH a ≥ 6
• The spectrum of an asymmetric annihilation process
• The stationary distribution of an interesting Markov chain
• THE WORD PROBLEM FOR THE RELATIVELY FREE SEMIGROUP SATISFYING T^m=T^m+n WITH m≥3
• THE WORD PROBLEM FOR THE RELATIVELY FREE SEMIGROUP SATISFYING T^m=T^m+n WITH m≥4 OR m=3, n=1

Cited in

(16)

• Random motion on finite rings. I: commutative rings
• Mixing time for Markov chain on linear extensions
• scientific article; zbMATH DE number 2070260 (Why is no real title available?)
• Markov Chains Through Semigroup Graph Expansions (A Survey)
• Upper Bounds on Mixing Time of Finite Markov Chains
• Holonomy theorem for finite semigroups
• Normal distributions of finite Markov chains
• Random shuffles on trees using extended promotion
• Equidivisibility and profinite coproduct
• Rowmotion Markov chains
• Positive varieties of lattice languages
• A study on the composition of elementary cellular automata
• Complexity of finite semigroups: history and decidability
• Probabilizing semigroups???
• Rowmotion Markov chains
• An improved spectral clustering community detection algorithm based on probability matrix

This page was built for publication: Unified theory for finite Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1735485)