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

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

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.