Random shuffles on trees using extended promotion
From MaRDI portal
(Redirected from Publication:5380266)
Abstract: The Tsetlin library is a very well studied model for the way an arrangement of books on a library shelf evolves over time. One of the most interesting properties of this Markov chain is that its spectrum can be computed exactly and that the eigenvalues are linear in the transition probabilities. In this paper we consider a generalization which can be interpreted as a self-organizing library in which the arrangements of books on each shelf are restricted to be linear extensions of a fixed poset. The moves on the books are given by the extended promotion operators of Ayyer, Klee, and Schilling while the shelves, bookcases, etc. evolve according to the move-to-back moves as in the the self-organizing library of Bj"orner. We show that the eigenvalues of the transition matrix of this Markov chain are integer combinations of the transition probabilities if the posets that prescribe the restrictions on the book arrangements are rooted forests or more generally, if they consist of ordinal sums of a rooted forest and so called ladders. For some of the results we show that the monoids generated by the moves are either -trivial or, more generally, in and then we use the theory of left random walks on the minimal ideal of such monoids to find the eigenvalues. Moreover, in order to give a combinatorial description of the eigenvalues in the more general case, we relate the eigenvalues when the restrictions on the book arrangements change only by allowing for one additional transposition of two fixed books.
Recommendations
- Properties of the promotion Markov chain on linear extensions
- A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
- Stochastic reversibility in self-organizing systems
- Combinatorial Markov chains on linear extensions
- Markov Chains for Promotion Operators
Cites work
- A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
- An extension of a theorem concerning an interesting Markov chain
- Combinatorial Markov chains on linear extensions
- Dual equivalence with applications, including a conjecture of Proctor
- Evacuation of labelled graphs
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- Markov chains, \(\mathcal{R}\)-trivial monoids and representation theory
- Möbius functions and semigroup representation theory.
- Möbius functions and semigroup representation theory. II: Character formulas and multiplicities.
- Note: random-to-front shuffles on trees
- On the matrix occurring in a linear search problem
- On the structure of semigroups
- Primitive orthogonal idempotents for R-trivial monoids.
- Promotion des morphismes d'ensembles ordonnes
- Properties of the promotion Markov chain on linear extensions
- Radical of weakly ordered semigroup algebras.
- Random walks and hyperplane arrangements
- Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-Organizing Libraries
- Semigroups, rings, and Markov chains
- Stochastic rearrangement rules for self-organizing data structures
- The heaps process, libraries, and size-biased permutations
- The stationary distribution of an interesting Markov chain
- Unified theory for finite Markov chains
Cited in
(5)
This page was built for publication: Random shuffles on trees using extended promotion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5380266)
