Pang, C. Y. Amy - Card-Shuffling via Convolutions of Projections on Combinatorial Hopf Algebras

dmtcs:2511 - Discrete Mathematics & Theoretical Computer Science, January 1, 2015, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Card-Shuffling via Convolutions of Projections on Combinatorial Hopf Algebras

Authors: Pang, C. Y. Amy

Recently, Diaconis, Ram and I created Markov chains out of the coproduct-then-product operator on combinatorial Hopf algebras. These chains model the breaking and recombining of combinatorial objects. Our motivating example was the riffle-shuffling of a deck of cards, for which this Hopf algebra connection allowed explicit computation of all the eigenfunctions. The present note replaces in this construction the coproduct-then-product map with convolutions of projections to the graded subspaces, effectively allowing us to dictate the distribution of sizes of the pieces in the breaking step of the previous chains. An important example is removing one “vertex” and reattaching it, in analogy with top-to-random shuffling. This larger family of Markov chains all admit analysis by Hopf-algebraic techniques. There are simple combinatorial expressions for their stationary distributions and for their eigenvalues and multiplicities and, in some cases, the eigenfunctions are also calculable.


Source : oai:HAL:hal-01337840v1
Volume: DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Section: Proceedings
Published on: January 1, 2015
Submitted on: November 21, 2016
Keywords: shuffling,combinatorial Hopf algebras,Markov chains,noncommutative symmetric functions,hyperplane walks,dual graded graphs,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 21 times.
This article's PDF has been downloaded 19 times.