Source author record

C. Y. Amy Pang

C. Y. Amy Pang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

What is connected

3works

2topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

Card-Shuffling via Convolutions of Projections on Combinatorial Hopf Algebras

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.

preprint2014arXiv

Hopf Algebras and Markov Chains

This thesis introduces a way to build Markov chains out of Hopf algebras. The transition matrix of a "Hopf-power Markov chain" is (the transpose of) the matrix of the coproduct-then-product operator on a combinatorial Hopf algebra with respect to a suitable basis. These chains describe the breaking-then-recombining of the combinatorial objects in the Hopf algebra. The motivating example is the famous Gilbert-Shannon-Reeds model of riffle-shuffling of a deck of cards, which arises in this manner from the shuffle algebra. The primary reason for constructing Hopf-power Markov chains, or for rephrasing familiar chains through this lens, is that much information about them comes simply from translating well-known facts on the underlying Hopf algebra. For example, there is an explicit formula for the stationary distribution (Theorem 4.5.1), and constructing quotient algebras show that certain statistics on a Hopf-power Markov chain are themselves Markov chains (Theorem 4.7.1). Perhaps the pinnacle is Theorem 2.5.1, a collection of algorithms for a full left and right eigenbasis in many common cases where the underlying Hopf algebra is commutative or cocommutative. This arises from a cocktail of the Poincare-Birkhoff-Witt theorem, the Cartier-Milnor-Moore theorem, Reutenauer's structure theory of the free Lie algebra, and Patras's Eulerian idempotent theory. Since Hopf-power Markov chains can exhibit very different behaviour depending on the structure of the underlying Hopf algebra and its distinguished basis, one must restrict attention to certain styles of Hopf algebras in order to obtain stronger results. This thesis will focus respectively on a free-commutative basis, which produces "independent breaking" chains, and a cofree basis; there will be both general statements and in-depth examples.

preprint2013arXiv

Hopf algebras and Markov chains: Two examples and a theory

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.