Upper Bounds on Mixing Time of Finite Markov Chains
From MaRDI portal
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 general framework for computing upper bounds on mixing times of finite Markov chains when its minimal ideal is left zero. Our analysis is based on combining results by Brown and Diaconis with our previous work on stationary distributions of finite Markov chains. Stationary distributions can be computed from the Karnofsky--Rhodes and McCammond expansion of the right Cayley graph of the finite semigroup underlying the Markov chain. Using loop graphs, which are planar graphs consisting of a straight line with attached loops, there are rational expressions for the stationary distribution in the probabilities. From these we obtain bounds on the mixing time. In addition, we provide a new Markov chain on linear extension of a poset with vertices, inspired by but different from the promotion Markov chain of Ayyer, Klee and the last author. The mixing time of this Markov chain is .
Recommendations
Cites work
- A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
- A comparative analysis of methods for constructing weak orders from partial orders
- A Mathematical Theory of Communication
- A recurrence for linear extensions
- An exact formula for the move-to-front rule for self-organizing lists
- An extension of a theorem concerning an interesting Markov chain
- Codes and automata.
- Combinatorial Markov chains on linear extensions
- Combinatorial methods in density estimation
- Combinatorial topology and the global dimension of algebras arising in combinatorics
- Counting linear extensions
- Directed nonabelian sandpile models on trees
- Dual equivalence with applications, including a conjecture of Proctor
- Edge flipping in graphs
- Eigenvectors for a random walk on a left-regular band
- Entropy and information theory.
- Evacuation of labelled graphs
- Faster random generation of linear extensions
- From shuffling cards to walking around the building: An introduction to modern Markov chain theory
- Functions of random walks on hyperplane arrangements
- Holonomy theorem for finite semigroups
- scientific article; zbMATH DE number 618821 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 1178976 (Why is no real title available?)
- scientific article; zbMATH DE number 3045112 (Why is no real title available?)
- Locally testable languages
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Markov chains, \(\mathcal{R}\)-trivial monoids and representation theory
- Mixing time for Markov chain on linear extensions
- Normal distributions of finite Markov chains
- Note: random-to-front shuffles on trees
- On the conductance of order Markov chains
- Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
- Promotion and evacuation
- Random walks and hyperplane arrangements
- Random Walks and Plane Arrangements in Three Dimensions
- Random walks on semaphore codes and delay de Bruijn semigroups
- Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-Organizing Libraries
- Semigroups, rings, and Markov chains
- The Basic Theorems of Information Theory
- The Individual Ergodic Theorem of Information Theory
- The stationary distribution of an interesting Markov chain
- Tutorial on large deviations for the binomial distribution
- Unified theory for finite Markov chains
Cited in
(5)
This page was built for publication: Upper Bounds on Mixing Time of Finite Markov Chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5055645)
