2016/09/14 by C. Y. Amy Pang, Pang, C. Y. Amy
Mathematics · #Advanced Combinatorial Mathematics #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.1609.04312
openalex publication_date 2016/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.