Hopf algebras and Markov chains: Two examples and a theory

Persi Diaconis, Chung Yin Amy PANG*, Arun Ram

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

The operation of squaring (coproduct followed by product) in a combinatorial Hopf algebra is shown to induce a Markov chain in natural bases. Chains constructed in this way include widely studied methods of card shuffling, a natural "rock-breaking" process, and Markov chains on simplicial complexes. Many of these chains can be explicitly diagonalized using the primitive elements of the algebra and the combinatorics of the free Lie algebra. For card shuffling, this gives an explicit description of the eigenvectors. For rock-breaking, an explicit description of the quasi-stationary distribution and sharp rates to absorption follow.

Original languageEnglish
Pages (from-to)527-585
Number of pages59
JournalJournal of Algebraic Combinatorics
Volume39
Issue number3
DOIs
Publication statusPublished - May 2014

Scopus Subject Areas

  • Algebra and Number Theory
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Free Lie algebras
  • Hopf Algebras
  • Rock breaking models
  • Shuffling

Fingerprint

Dive into the research topics of 'Hopf algebras and Markov chains: Two examples and a theory'. Together they form a unique fingerprint.

Cite this