HackerPapers

arXiv:1206.3620math.CO

Hopf algebras and Markov chains: Two examples and a theory

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

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
51 pages, 17 figures. (Typographical errors corrected. Further fixes will only appear on the version on Amy Pang's website, the arXiv version will not be updated.)
Journal reference
DOI
doi:10.1007/s10801-013-0456-7
Subjects
math.COCombinatorics math.PRProbability

On Hacker News

Linked by 1 identifiable commenter in 5 comments across 4 threads, from Mar 2023 to Apr 2023. Found in 1 HN submission from Mar 2023 to Mar 2023. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. Use Gröbner bases to solve polynomial equations 1 comment

    • Hopf algebra subsumes like all all currently fashionable architectures (transformers, convnets, SSM, diffusion models) and then some. Hopf convolution is a surprisingly general concept, Groebner bases are the thing used to calculate the antipode. Hopf algebra is tensor…

      adamnemecekView on HNParent context

  2. A Baby GPT 1 comment

    • I have written a paper on this recently viewing transformers as Hopf algebras https://arxiv.org/abs/2302.01834. This paper is very relevant https://arxiv.org/abs/1206.3620.

      adamnemecekView on HNParent context

  3. Evidence of a predictive coding hierarchy in the human brain listening to speech 1 comment

    • I don't know how to talk about this without some technical terms. Spend a little bit of time on it, it's a lot more understandable than you think. Peep this paper https://arxiv.org/abs/1206.3620. I have a discord channel if you want to learn more https://discord.cofunctional.ai.

      adamnemecekView on HNParent context

  4. Category Theory ∩ Machine Learning 2 comments

    • I have recently written a paper on understanding machine learning via the lens of Hopf algebra https://arxiv.org/abs/2302.01834. Hopf algebras (which are really just tensors with recurrence relations built in) subsume convnets, transformers and diffusion model and also provide a…

      adamnemecekView on HNParent context

    • Ok read the Persi Diaconis one https://arxiv.org/abs/1206.3620. You are right, it can be more polished but also it covers quite a lot and it was surprisingly hard to fit it all in. The main response I have been getting though is "I won't believe this until I see the…

      adamnemecekView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.