The PI proposes to study mixing properties of Markov chains used as a backbone of Monte Carlo algorithms and in industrial tasks such as mixing of liquids. A key innovation is studying continuous problems, which normally use the difficult-to-work-with equations of fluid mechanics, by discrete approximations which allow tools from combinatorics, group theory, and topology to be used. An exciting new tool, the use of Hopf algebras, is proposed to unify the discrete methods. Markov chain Monte Carlo algorithms are a basic tool of scientific computing used in physics, chemistry, statistics, and many industrial applications. The basic running time questions - How long should an algorithm be run to do its job? are largely open research problems. The PI proposes attacks on two fronts. The first is spatial mixing of tracer particles in a two-dimensional grid under various stirring protocols: Baker's transformations, twist maps, and periodic figure eight stirring. Using tools from topology to bound stretching of line segments and tools from ergodic theory and probability to bound the behavior of measures after stretching gives a program for analysis. The second front uses new tools from algebraic combinatorics - combinatorial Hopf algebras to give explicit diagonalization of a host of non-reversible Markov chains. These include fragmentation processes studied by Kolmogorov, the riffle shuffling process, and many others. The first front is heavy on analysis, the second on algebra, but both fronts use analysis and algebra.
The work proposed builds bridges between different areas of mathematics and applications. The use of probabilistic analysis in fluid mixing and the new discrete methods introduced to study continuous problems should contribute to both probability and the kinematic study of practical mixing. The Hopf algebra front similarly interfaces probability and combinatorics in new ways. The PI is an internationally visible expert who will continue to give talks to both experts, outside scientists, and lay audiences about these exciting new developments. He currently gives about 50 outside talks per year. The PI currently has eight graduate students working in these areas, as well as a comparable number of undergraduates doing senior theses. He has reached out to a much broader audience: the book Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks (with Ron Graham, Princeton University Press) has just appeared.
