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

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

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.