The Mathematics of Mixing

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

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.