New Techniques and Analyses for Random Sampling

现代生活的每一部分都是用计算机模拟来研究的。这包括-医学：用计算机研究蛋白质折叠来设计新药；-物理：质量和电荷的基本估计是通过晶格规范理论最准确地获得的；-业务：将优化客户流量的银行柜员或杂货店收银员的数量；以及几乎所有的社会科学领域。面对庞大、复杂的数据集，需要新的算法来高效、准确地进行这种模拟。与此同时，在这个“一切皆有可能”的世界里，必须研究并回答算法应该运行多长时间才能完成工作的问题。一个非常简单的例子是，“我们要洗牌多少次才能完全混合一副牌？”该奖项支持的研究表明，使用广泛适用的顺序重要性抽样的许多此类算法。它还结合了来自马尔可夫链几何理论的新证明技术，以严格确定运行时间。这项工作解决了研究人员有时过于“快速和松散”的情况，这可能会产生误导性的结果。提出的算法可以帮助检测和解决这些问题。本项目为研究生提供研究训练机会。提出新的研究方向是设计新的算法，并对目前广泛使用的算法进行仿真分析。这围绕着四个主要主题：重要性抽样，在缺少数据和列联表的问题上为所需的样本量制定和试用新的标准；从偏微分方程和几何（惠特尼覆盖，约翰域，Carlesson估计）发展解析和几何技术，以发展马尔可夫链的几何理论；探索由组合学家和拓扑学家开发的马尔可夫过程生成器和代数复合体（Hodge理论）之间的联系；洗牌学对洗牌数学的研究该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Every part of modern life is studied using computer simulation. This includes-medicine: computer studies of protein folding for designing new drugs;-physics: basic estimates of mass and charge are most accurately obtained via lattice gauge theory;-business: the number of bank tellers or grocery checkers that will optimize customer traffic flows;-and virtually every area of the social sciences.In the face of huge, sophisticated data sets, new algorithms are required to efficiently and accurately carry out such simulations. At the same time, in this "anything goes" world, questions of how long an algorithm should be run in order to do its job must be studied-and answered. A very simple example would be, "How many times do we shuffle a deck of cards to completely mix it?" The research supported by this award suggests a host of such algorithms using sequential importance sampling which are broadly applicable. It also incorporates new proof techniques from the geometric theory of Markov chains to rigorously pin down running times. This work addresses those instances when researchers are sometimes too "fast and loose", which can yield misleading results. The proposed algorithms can help detect and fix these issues. The project provides research training opportunities for graduate students.The proposed new research is to design new algorithms, and analyze widely used existing algorithms for simulation. This is centered around four main themes: importance sampling where new criteria for required sample size are developed and tried out in problems of missing data and contingency tables; developing analytic and geometric techniques adapted from partial differential equations and geometry (Whitney covers, John domains, Carlesson estimates) to develop geometric theory of Markov chains; exploring connections between the generators of Markov processes and algebraic complexes (Hodge theory) developed by combinatorialists and topologists; the study of mathematics of shuffling cards.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.