权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

New Techniques and Analyses for Random Sampling

随机抽样的新技术和分析

基本信息

批准号：
1954042
负责人：
Persi Diaconis
金额：
$ 57.5万
依托单位：
Stanford University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1954042&HistoricalAwards=false
关键词：
New Techniques Analyses Random Sampling

项目摘要

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.

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