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

CRII: AF: RUI: Markov Chains and Random Sampling on Graphs

CRII：AF：RUI：马尔可夫链和图上的随机采样

基本信息

批准号：
2104795
负责人：
Sarah Cannon
金额：
$ 17.46万
依托单位：
Claremont McKenna College
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-06-01 至 2024-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2104795&HistoricalAwards=false
关键词：
CRII AF RUI Markov Chains

项目摘要

Given a large collection of mathematical objects, how can you find a "typical" element efficiently? The problem of randomly sampling from a large, complex set arises across many areas including polling, estimating statistics of physical systems, and randomized algorithms; studying randomly selected elements can provide insights about likely properties and behaviors. For example, random samples of political districting plans have been used to build baselines for comparison and detect racial and partisan gerrymandering. However, the problem of efficiently finding random elements in complex settings is often a difficult one, and it can be hard to make rigorous guarantees about the processes involved. More mathematical analysis is needed so that there can be confidence in the conclusions producedOne way to generate random samples is to use a Markov chain: iteratively make random local changes and mathematically bound the mixing time, the number of iterations until the configuration obtained is sufficiently random. Mathematical insight is needed to rigorously understand these Markov chains and their sampling behavior. Another approach is to generate random samples via self-reducibility using approximate counting algorithms. While many approximate counting algorithms come from Markov chains themselves, other approaches include decay of correlations, interpolation, and most recently, the cluster expansion. This project focuses on the following important problems for random sampling on graphs, involving exciting theoretical questions with an eye toward relevant applications: (1) Approximate counting and sampling for spin systems using the cluster expansion; (2) Rigorously analyzing Markov chains used for sampling political-districting plans and other problems with similar structure. This project is strengthening the interdisciplinary connections between the theory of random sampling and other disciplines like statistical physics and political science. The investigator is also working to make this research area more accessible to undergraduate students, through continued mentoring, writing and distributing an undergraduate-level introduction to the theory of Markov chains, and creating and teaching a new elective class related to these topics.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.

给定一个大量的数学对象，如何有效地找到一个“典型”元素？从大型复杂集合中随机抽样的问题出现在许多领域，包括轮询，估计物理系统的统计数据和随机算法;研究随机选择的元素可以提供有关可能的属性和行为的见解。例如，政治选区划分计划的随机样本被用来建立比较基线，并检测种族和党派的不公正划分。然而，在复杂的环境中有效地找到随机元素的问题往往是一个困难的问题，并且很难对所涉及的过程做出严格的保证。产生随机样本的一种方法是使用马尔可夫链：迭代地进行随机局部变化，并在数学上限制混合时间，迭代次数，直到获得的配置足够随机。需要数学上的洞察力来严格理解这些马尔可夫链及其采样行为。另一种方法是使用近似计数算法通过自约简生成随机样本。虽然许多近似计数算法来自马尔可夫链本身，但其他方法包括相关性衰减，插值和最近的聚类扩展。本研究课题主要研究图的随机抽样中的以下重要问题，涉及到令人兴奋的理论问题，并着眼于相关的应用：（1）使用簇展开的自旋系统的近似计数和抽样;（2）严格分析用于政治分区计划抽样的马尔可夫链和其他具有类似结构的问题。该项目正在加强随机抽样理论与统计物理学和政治学等其他学科之间的跨学科联系。调查员还致力于使这一研究领域更容易接触到本科生，通过继续指导，写作和分发本科水平的介绍马尔可夫链理论，该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查进行评估，被认为值得支持的搜索.