The Mathematics of Mixing

PI提议研究作为蒙特卡罗算法主干的马尔可夫链的混合特性，并用于诸如液体混合等工业任务。一个关键的创新是研究连续问题，这些问题通常使用难以处理的流体力学方程，通过离散近似，允许使用组合学，群论和拓扑学的工具。一个令人兴奋的新工具，使用Hopf代数，提出了统一的离散方法。马尔可夫链蒙特卡罗算法是用于物理、化学、统计学和许多工业应用的科学计算的基本工具。基本的运行时间问题——一个算法应该运行多长时间才能完成它的工作？很大程度上是开放性的研究问题。PI提出了两方面的攻击。第一个是二维网格中示踪粒子在不同搅拌协议下的空间混合：贝克变换、扭曲图和周期性的8字形搅拌。利用拓扑工具对线段的拉伸进行约束，利用遍历理论和概率论工具对拉伸后测度的行为进行约束，给出了分析程序。第二方面使用代数组合学的新工具-组合霍普夫代数来给出一组不可逆马尔可夫链的显式对角化。这些过程包括Kolmogorov研究的碎片化过程、riffle洗牌过程以及其他许多过程。第一个战线偏重分析，第二个战线偏重代数，但两个战线都使用分析和代数。这项工作在数学和应用的不同领域之间建立了桥梁。在流体混合中使用概率分析和引入新的离散方法来研究连续问题应该有助于实际混合的概率和运动学研究。Hopf代数前沿同样以新的方式将概率和组合学结合起来。PI是一位国际知名的专家，他将继续就这些令人兴奋的新发展向专家、外部科学家和非专业听众发表演讲。目前，他每年要进行大约50场外部演讲。PI目前有8名研究生在这些领域工作，还有相当数量的本科生在做高级论文。他已经接触到更广泛的读者：《神奇的数学：激发伟大魔术的数学思想》（与罗恩·格雷厄姆合著，普林斯顿大学出版社）刚刚出版。

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.