Hopf Algebras and Markov Chains
arXiv:1412.8221
Abstract
This thesis introduces a way to build Markov chains out of Hopf algebras. The transition matrix of a "Hopf-power Markov chain" is (the transpose of) the matrix of the coproduct-then-product operator on a combinatorial Hopf algebra with respect to a suitable basis. These chains describe the breaking-then-recombining of the combinatorial objects in the Hopf algebra. The motivating example is the famous Gilbert-Shannon-Reeds model of riffle-shuffling of a deck of cards, which arises in this manner from the shuffle algebra. The primary reason for constructing Hopf-power Markov chains, or for rephrasing familiar chains through this lens, is that much information about them comes simply from translating well-known facts on the underlying Hopf algebra. For example, there is an explicit formula for the stationary distribution (Theorem 4.5.1), and constructing quotient algebras show that certain statistics on a Hopf-power Markov chain are themselves Markov chains (Theorem 4.7.1). Perhaps the pinnacle is Theorem 2.5.1, a collection of algorithms for a full left and right eigenbasis in many common cases where the underlying Hopf algebra is commutative or cocommutative. This arises from a cocktail of the Poincare-Birkhoff-Witt theorem, the Cartier-Milnor-Moore theorem, Reutenauer's structure theory of the free Lie algebra, and Patras's Eulerian idempotent theory. Since Hopf-power Markov chains can exhibit very different behaviour depending on the structure of the underlying Hopf algebra and its distinguished basis, one must restrict attention to certain styles of Hopf algebras in order to obtain stronger results. This thesis will focus respectively on a free-commutative basis, which produces "independent breaking" chains, and a cofree basis; there will be both general statements and in-depth examples.
arXiv commentRevised version of PhD thesis. 178 pages, 6 figures. Comments are very welcome. For updated version, see my webpage. In v2: fixed references in table at end of Chapter 1
References in corpus (13)
- Hopf Algebras, Renormalization and Noncommutative Geometry
- Hopf Algebras in Combinatorics
- Supercharacters, symmetric functions in noncommuting variables, and related Hopf algebras
- Hopf algebras and Markov chains: Two examples and a theory
- Combinatorial Hopf algebras
- Hopf monoids from class functions on unitriangular matrices
- Polynomial realizations of some trialgebras
- The Hopf monoid on nonnesting supercharacters of pattern groups
- Algebraic Structures on Grothendieck Groups of a Tower of Algebras
- d-Complete Posets Generalize Young Diagrams for the Jeu de Taquin Property
- On Hopf algebra structures over operads
- Eigenvectors for a random walk on a hyperplane arrangement
- A lattice of combinatorial Hopf algebras, Application to binary trees with multiplicities