Markov Chains from Descent Operators on Combinatorial Hopf Algebras

Abstract

We develop a general theory for Markov chains whose transition probabilities are the coefficients of descent operators on combinatorial Hopf algebras. These model the breaking-then-recombining of combinational objects. Examples include the various card-shuffles of Diaconis, Fill and Pitman, Fulman's restriction-then-induction chains on the representations of the symmetric group, and a plethora of new chains on trees, partitions and permutations. The eigenvalues of these chains can be calculated in a uniform manner using Hopf algebra structure theory, and there is a simple expression for their stationary distributions. For an important subclass of chains analogous to the top-to-random shuffle, we derive a full right eigenbasis, from which follow exact expressions for expectations of certain statistics of interest. This greatly generalises the coproduct-then-product chains previously studied in joint work with Persi Diaconis and Arun Ram.

57 pages. Sections 4.4, 5.3 and 6 are new. Sections 5 and 6 may swap order in a future version, so be sure to cite the version number!

References in corpus (10)

• Hopf Algebras, Renormalization and Noncommutative Geometry
• Hopf Algebras in Combinatorics
• Hopf algebras and Markov chains: Two examples and a theory
• Skew quasisymmetric Schur functions and noncommutative Schur functions
• Cambrian Hopf Algebras
• A Hopf algebra of subword complexes
• The characteristic polynomial of the Adams operators on graded connected Hopf algebras
• d-Complete Posets Generalize Young Diagrams for the Jeu de Taquin Property
• Steady state of Stochastic Sandpile Models
• Eigenvectors for a random walk on a hyperplane arrangement