Markov Chains driven by Permuted and Hyperoctahedral Descent Operators on Combinatorial Hopf Algebras

The aim of this project is to apply algebraic and combinatorial tools to analyse a large class of Markov chains. Markov chains are probabilistic algorithms commonly used in statistical physics, bioinformatics, economics and other sciences to simulate a random process (e.g. changes in demand for various products) or to sample from a desired distribution (e.g. to create typical particle configurations of different densities to study phase transitions). In the majority of applications, there are few theoretical results on how many steps of the algorithm are required to produce a useful result. The situation is being improved by several recent studies of Markov chains with algebraic or geometric connections, where it is possible to obtain exact formulae for many features of their long term behaviour, such as the required runtime. Powerful comparison techniques then extend these results to more realistic and irregular chains which are not so directly tractable.

This project will study Markov chains whose transition probabilities arise from two new families of linear transformations on combinatorial Hopf algebras. The first family comprises permuted descent operators, whose associated Markov chains model breaking a combinatorial object, such as a permutation, tree or graph, into random pieces and reassembling them in a different order. The second family comprises hyperoctahedral descent operators, which in addition apply involutions to some of the pieces before the reassembly. We intend to derive formulae, valid for all combinatorial Hopf algebras, for the eigenvalues and eigenvectors of these linear transformations, using structure theorems of Hopf algebras. We will then specialise this eigendata to numerous particular Hopf algebras to deduce the long term properties of their associated Markov chains. Cases of particular interest include various dynamic storage allocation schemes, the rearrangement of phylogenetic trees, and models of rock-breaking.

In addition to these practical applications, the connection between Markov chains and combinatorial Hopf algebras is expected to also contribute to the theory of the related algebraic combinatorics. The novel probabilistic viewpoint will likely motivate new variations of classical combinatorial Hopf algebras, and identify new subalgebras of the hyperoctahedral Solomon descent algebra. The computation of eigenvectors for the hyperoctahedral descent operators will then illuminate the structure of these new subalgebras, through the construction of idempotents. There will also be results for other branches of mathematics and theoretical physics where combinatorial Hopf algebras appear, including the representation theory of Lie groups over finite fields, Coxeter group theory, and quantum field theory.