Hopf algebras and Markov chains: two examples and a theory

DOI10.1007/S10801-013-0456-7zbMATH Open1291.05220arXiv1206.3620OpenAlexW2081277248MaRDI QIDQ2454080FDOQ2454080

Authors: Persi Diaconis, C. Y. Amy Pang, Arun Ram 

Publication date: 12 June 2014

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

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 explictly 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.

Full work available at URL: https://arxiv.org/abs/1206.3620

Recommendations

• Card-shuffling via convolutions of projections on combinatorial Hopf algebras
• A Hopf-power Markov chain on compositions
• The eigenvalues of hyperoctahedral descent operators and applications to card-shuffling
• Lumpings of algebraic Markov chains arise from subquotients
• Semigroups, rings, and Markov chains

zbMATH Keywords

Hopf algebrasfree Lie algebrasshufflingrock breaking models

Mathematics Subject Classification ID

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Topology and data
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• A symmetric function generalization of the chromatic polynomial of a graph
• Trailing the dovetail shuffle to its lair
• Title not available (Why is that?)
• Analysis of casino shelf shuffling machines
• Percolation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The asymptotic behavior of fragmentation processes
• Hall algebras, hereditary algebras and quantum groups
• Monoidal functors, species and Hopf algebras
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random Fragmentation and Coagulation Processes
• Title not available (Why is that?)
• Introduction to Lie Algebras and Representation Theory
• Title not available (Why is that?)
• Noncommutative symmetric functions
• Coalgebras and Bialgebras in Combinatorics
• Markov Chains
• Random walks and hyperplane arrangements
• Incidence Hopf algebras
• Mixing times of lozenge tiling and card shuffling Markov chains
• On the structure of Hopf algebras
• Quasi-stationary distributions and convergence to quasi-stationarity of birth-death processes
• Group schemes of prime order
• Title not available (Why is that?)
• Representations of finite classical groups. A Hopf algebra approach
• Quantum groups and quantum shuffles
• Title not available (Why is that?)
• The Orlik-Solomon algebra on the partition lattice and the free Lie algebra
• Dual canonical bases, quantum shuffles and \(q\)-characters
• Representations of Khovanov-Lauda-Rouquier algebras and combinatorics of Lyndon words.
• Combinatorial Hopf algebras and generalized Dehn–Sommerville relations
• Title not available (Why is that?)
• Antipodes and incidence coalgebras
• Title not available (Why is that?)
• A primer of Hopf algebras.
• Enriched 𝑃-Partitions
• The weight decomposition of Hopf algebras
• The descent algebra of a graded bialgebra
• A decomposition of the group algebra of a finite Coxeter group
• Carries, shuffling, and symmetric functions
• No-feedback card guessing for dovetail shuffles
• Generalized riffle shuffles and quasisymmetric functions
• Foulkes characters, Eulerian idempotents, and an amazing matrix
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Riffle shuffles of decks with repeated cards
• A better way to deal the cards
• Carries, shuffling, and an amazing matrix
• Lectures on two-dimensional critical percolation
• Title not available (Why is that?)
• Peaks and Eulerian numbers in a random sequence
• A rule of thumb for riffle shuffling
• Exchangeable pairs and Poisson approximation
• Carries, Combinatorics, and an Amazing Matrix
• Structure of the Malvenuto-Reutenauer Hopf algebra of permutations
• Title not available (Why is that?)
• Frobenius-Schur indicators for subgroups and the Drinfel’d double of Weyl groups
• Eigenvectors for a random walk on a left-regular band
• Eigenvectors for a random walk on a hyperplane arrangement
• On the scaling limits of planar percolation
• The action of \(S_ n\) on the components of the Hodge decomposition of Hochschild homology
• Standard Lyndon Bases of Lie Algebras and Enveloping Algebras
• Title not available (Why is that?)
• A Frobenius-Schur theorem for Hopf algebras
• On the Pontryagin product in spaces of paths
• Structure of the Loday-Ronco Hopf algebra of trees.
• Functions of random walks on hyperplane arrangements
• Analysis of Top To Random Shuffles
• A decomposition of Solomon's descent algebra
• Hopf Algebras of Combinatorial Structures
• AN ALGEBRAIC TOPOLOGICAL METHOD FOR FEATURE IDENTIFICATION
• Normal approximations for descents and inversions of permutations of multisets
• Descent algebras, hyperplane arrangements, and shuffling cards
• Construction géométrique des idempotents eulériens. Filtration des groupes de polytopes et des groupes d'homologie de Hochschild
• Hopf powers and orders for some bismash products.
• A generalized power map for Hopf algebras
• Hopf algebra methods in graph theory
• Some applications of quantum shuffles

Cited In (15)

• Combinatorics of balanced carries
• Foulkes characters, Eulerian idempotents, and an amazing matrix
• Lumpings of algebraic Markov chains arise from subquotients
• Card-shuffling via convolutions of projections on combinatorial Hopf algebras
• Algebraic structures underlying quantum independences: theory and applications
• A Hopf-power Markov chain on compositions
• The eigenvalues of hyperoctahedral descent operators and applications to card-shuffling
• Weak Hopf algebras. II: Representation theory, dimensions, and the Markov trace
• On the joint distribution of descents and signs of permutations
• On quantitative convergence to quasi-stationarity
• Shuffling cards by spatial motion
• A Hopf algebra of subword complexes
• Urn models, Markov chains and random walks in cosmological topologically massive gravity at the critical point
• The one-sided cycle shuffles in the symmetric group algebra
• Title not available (Why is that?)

This page was built for publication: Hopf algebras and Markov chains: two examples and a theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2454080)