Lumpings of Algebraic Markov Chains arise from Subquotients
arXiv:1508.01570 · doi:10.1007/s10959-018-0834-0
Abstract
A function on the state space of a Markov chain is a "lumping" if observing only the function values gives a Markov chain. We give very general conditions for lumpings of a large class of algebraically-defined Markov chains, which include random walks on groups and other common constructions. We specialise these criteria to the case of descent operator chains from combinatorial Hopf algebras, and, as an example, construct a "top-to-random-with-standardisation" chain on permutations that lumps to a popular restriction-then-induction chain on partitions, using the fact that the algebra of symmetric functions is a subquotient of the Malvenuto-Reutenauer algebra.
arXiv comment36 pages. Minor update from v2 after peer-review, with numerical sectioning as in the published version. (v2 was majorly reworked from v1, with new results in sections 3.5/II.D and 3.6/II.E, and new examples in Part I/Section 2.)
References in corpus (7)
- Combinatorial Hopf algebras and generalized Dehn-Sommerville relations
- Hopf algebras and Markov chains: Two examples and a theory
- Algebraic and combinatorial structures on pairs of twin binary trees
- Algebraic Structures on Grothendieck Groups of a Tower of Algebras
- Markov chains, -trivial monoids and representation theory
- A rule of thumb for riffle shuffling
- Card-Shuffling via Convolutions of Projections on Combinatorial Hopf Algebras