Hopf algebras and Markov chains: Two examples and a theory
arXiv:1206.3620 · doi:10.1007/s10801-013-0456-7
Abstract
The operation of squaring (coproduct followed by product) in a combinatorial Hopf algebra is shown to induce a Markov chain in natural bases. Chains constructed in this way include widely studied methods of card shuffling, a natural "rock-breaking" process, and Markov chains on simplicial complexes. Many of these chains can be explictly diagonalized using the primitive elements of the algebra and the combinatorics of the free Lie algebra. For card shuffling, this gives an explicit description of the eigenvectors. For rock-breaking, an explicit description of the quasi-stationary distribution and sharp rates to absorption follow.
51 pages, 17 figures. (Typographical errors corrected. Further fixes will only appear on the version on Amy Pang's website, the arXiv version will not be updated.)
References in corpus (9)
- On the scaling limits of planar percolation
- Exchangeable pairs and Poisson approximation
- Analysis of casino shelf shuffling machines
- A rule of thumb for riffle shuffling
- Riffle shuffles of decks with repeated cards
- Eigenvectors for a random walk on a hyperplane arrangement
- On the convolution powers of complex functions on Z
- Carries, Shuffling and An Amazing Matrix
- Convolution powers of complex functions on Z
Cited by in corpus (12)
- Hopf Algebras in Combinatorics
- A Hopf algebra of subword complexes
- Hopf Algebras and Markov Chains
- The characteristic polynomial of the Adams operators on graded connected Hopf algebras
- Random Walks on Finite Quantum Groups: Diaconis-Shahshahani Theory for Quantum Groups
- Lumpings of Algebraic Markov Chains arise from Subquotients
- Markov Chains from Descent Operators on Combinatorial Hopf Algebras
- Urn models, Markov chains and random walks in cosmological topologically massive gravity at the critical point
- Card-Shuffling via Convolutions of Projections on Combinatorial Hopf Algebras
- Combinatorics of balanced carries
- The one-sided cycle shuffles in the symmetric group algebra
- A Multiresolution Analysis Framework for the Statistical Analysis of Incomplete Rankings