CAREER: Phase Transitions in Some Discrete Random Models and Mixing of Markov Chains

职业：一些离散随机模型中的相变和马尔可夫链的混合

• 批准号: 1554783
• 负责人: Naya Banerjee
• 金额: $ 40万
• 依托单位: University of Delaware
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1554783&HistoricalAwards=false
• 关键词: CAREER; Phase; Transitions; Some; Discrete

Water turning into ice at its freezing point or the magnetization of iron are examples of phase transitions in physical systems. At the transition point, the properties of the system such as the volume or heat capacity may change discontinuously. The aim of our research is to study phase transitions in mathematical models using probabilistic tools in the following three directions. (1) The longest increasing subsequence (LIS) of a permutation is the length of a maximal subsequence of the permutation in which the elements increase. How long is the LIS for a uniformly random permutation? This question has been studied in connection with practical applications such as sorting sequences, disk drive scheduling and airplane boarding times. The mathematical study of the LIS has revealed deep and unexpected connections of the problem with areas such as the theory of random matrices, analytic combinatorics and random polymer models. The proposed research aims to study the LIS when the permutation is drawn from certain non-uniform distributions and associated phase transitions. (2) Many computational problems can be phrased as constraint satisfaction problems (CSPs) where one wants to find a solution to a number of variables with a set of constraints imposed on them. CSPs were first studied in computer science motivated by applications to artificial intelligence. To study the difficulty of finding solutions in typical rather than worst case scenarios, researchers study random CSPs. Using sophisticated heuristics, physicists have made detailed predictions about the location and nature of phase transitions in random CSPs. The accuracy of these heuristic predictions motivates the importance of discovering the rigorous mathematical foundations of these techniques. (3) Interacting particle processes are used to model large, randomly evolving interacting systems of agents that arise in the natural sciences including in physics and in biology. The exclusion and interchange random walks are examples of such interacting particle processes. In the symmetric case the long term mixing behavior of the random walk and the nature of phase transitions is well studied. The goal of this research is to understand the mixing properties of natural asymmetric and weighted versions of these processes. While achieving these three goals, the principal investigator will create exciting research opportunities for graduate and undergraduate students in probability, mentoring programs with the goal of retention of women in mathematics, and the development of online curricular material.The main aim of this project is to develop new theory and analysis for phase transitions in certain discrete probabilistic models. The first problem is to study the limiting distribution of the LIS in non-uniformly random permutations by way of analyzing the fluctuations of the LIS as the parameter of the distribution is varied. The distribution is known to be Gaussian in one regime of the parameter and Tracy-Widom in another and we aim to study this transition. The second problem is to study the condensation and clustering transitions in random CSPs such as the hardcore model on random graphs. The research aims to identify the location of the reconstruction threshold more precisely in these models and to explore the connection to the clustering transition. Finally, the proposal will consider Markov processes such as asymmetric exclusion and interchange and attempt to relate the mixing times and spectral gaps of these processes to the corresponding quantities for a single particle and to understand the cutoff phenomenon for these processes.

水在冰点变成冰或铁的磁化是物理系统中相变的例子。在转变点，系统的属性（例如体积或热容）可能会不连续地变化。我们研究的目的是使用概率工具在以下三个方向研究数学模型中的相变。 (1)排列的最长递增子序列(LIS)是排列中元素增加的最大子序列的长度。均匀随机排列的 LIS 有多长？这个问题已经结合实际应用进行了研究，例如排序顺序、磁盘驱动器调度和飞机登机时间。 LIS 的数学研究揭示了该问题与随机矩阵理论、解析组合学和随机聚合物模型等领域的深刻且意想不到的联系。 拟议的研究旨在研究从某些非均匀分布和相关相变中得出排列时的 LIS。 (2) 许多计算问题可以表述为约束满足问题 (CSP)，其中人们想要找到对多个变量施加一组约束的解决方案。 CSP 最初是在人工智能应用的推动下在计算机科学中进行研究的。为了研究在典型场景而非最坏情况下寻找解决方案的难度，研究人员研究了随机 CSP。物理学家利用复杂的启发法，对随机 CSP 中相变的位置和性质做出了详细的预测。这些启发式预测的准确性激发了发现这些技术的严格数学基础的重要性。 (3) 相互作用的粒子过程用于模拟自然科学（包括物理学和生物学）中出现的大型、随机演化的相互作用的主体系统。排除和互换随机游走是这种相互作用的粒子过程的例子。在对称情况下，随机游走的长期混合行为和相变的性质得到了很好的研究。这项研究的目标是了解这些过程的自然不对称和加权版本的混合特性。在实现这三个目标的同时，首席研究员将为研究生和本科生创造令人兴奋的概率研究机会、以保留女性数学为目标的指导计划以及在线课程材料的开发。该项目的主要目的是开发某些离散概率模型中相变的新理论和分析。第一个问题是通过分析LIS随分布参数变化的波动情况来研究非均匀随机排列中LIS的极限分布。已知在一个参数范围内分布为高斯分布，在另一个参数范围内分布为 Tracy-Widom，我们的目标是研究这种转变。第二个问题是研究随机 CSP 中的凝聚和聚类转变，例如随机图上的硬核模型。该研究旨在更精确地识别这些模型中重建阈值的位置，并探索与聚类转变的联系。最后，该提案将考虑马尔可夫过程，例如不对称排除和互换，并尝试将这些过程的混合时间和光谱间隙与单个粒子的相应量联系起来，并理解这些过程的截止现象。