New Techniques and Analyses for Random Sampling

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

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.