DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Font Size:  Small  Medium  Large

A Hopf-power Markov chain on compositions

C.Y. Amy Pang

Abstract


In a recent paper, Diaconis, Ram and I constructed Markov chains using the coproduct-then-product map of a combinatorial Hopf algebra. We presented an algorithm for diagonalising a large class of these ``Hopf-power chains", including the Gilbert-Shannon-Reeds model of riffle-shuffling of a deck of cards and a rock-breaking model. A very restrictive condition from that paper is removed in my thesis, and this extended abstract focuses on one application of the improved theory. Here, I use a new technique of lumping Hopf-power chains to show that the Hopf-power chain on the algebra of quasisymmetric functions is the induced chain on descent sets under riffle-shuffling. Moreover, I relate its right and left eigenfunctions to Garsia-Reutenauer idempotents and ribbon characters respectively, from which I recover an analogous result of Diaconis and Fulman (2012) concerning the number of descents under riffle-shuffling.
Résumé. Dans un récent article avec Diaconis et Ram, nous avons construit des chaînes de Markov en utilisant une composition du coproduit et produit d'une algébre de Hopf combinatoire. Nous avons présenté un algorithme pour diagonaliser une large classe de ces ``chaînes de Hopf puissance", en particulier nous avons diagonalisé le modèle de Gilbert-Shannon-Reeds de mélange de cartes en ``riffle shuffle" (couper en deux, puis intercaler) et un modèle de cassage de pierres. Dans mon travail de thèse, nous supprimons une condition très restrictive de cet article, et ce papier se concentre sur une application de cette amélioration. Nous utilisons ici une nouvelle technique de projection de chaînes de Hopf puissance pour montrer que la chaîne de Hopf puissance sur l'algèbre des fonctions quasi-symétriques est la chaîne de Markov induite sur les ensembles des descentes dans le ``riffle shuffling". De plus, nous faisons le lien entre les fonctions propres à droite et à gauche et respectivement les idempotents de Garsia-Reutenauer et les caractères en rubans, ce qui nous permet de retrouver un résultat analogue à Diaconis et Fulman (2012) concernant le nombre de descentes dans le ``riffle shuffling".

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional