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）置换的最长增加子序列（LI）是元素增加的置换量的最大子序列的长度。统一随机置换的LIS多长时间？已经研究了与实际应用有关的研究，例如排序序列，磁盘驱动计划和飞机登机时间。 LIS的数学研究揭示了该问题与随机矩阵，分析组合和随机聚合物模型等领域的深刻和意外联系。 拟议的研究旨在研究LIS时，从某些不均匀的分布和相关的相变。 （2）许多计算问题可以用作约束满意度问题（CSP），其中人们想找到对许多变量的解决方案，并在其上施加了一组约束。 CSP首先是在计算机科学领域研究的，该计算机科学是由人工智能应用的。为了研究在典型而不是最坏情况下寻找解决方案的困难，研究人员研究了随机CSP。使用复杂的启发式方法，物理学家对随机CSP中相变的位置和性质做出了详细的预测。这些启发式预测的准确性激发了发现这些技术的严格数学基础的重要性。 （3）相互作用的粒子过程用于模拟自然科学中出现的大型，随机发展的相互作用的药物的相互作用系统，包括物理学和生物学。排除和互换随机步行是这种相互作用的粒子过程的示例。在对称情况下，对随机行走的长期混合行为和相变的性质进行了充分的研究。这项研究的目的是了解这些过程的自然不对称和加权版本的混合特性。在实现这三个目标的同时，首席研究人员将为研究生和本科生创造令人兴奋的研究机会，指导计划以保留女性在数学中的目标以及在线课程材料的发展。第一个问题是通过分析LIS的波动，研究LIS在非均匀随机排列中的限制分布，因为分布的参数各不相同。已知该分布在参数的一个制度中是高斯，在另一个参数中是高斯，我们的目标是研究这种过渡。第二个问题是研究随机CSP中的凝结和聚类转变，例如随机图上的硬核模型。该研究旨在在这些模型中更精确地确定重建阈值的位置，并探索与聚类过渡的联系。最后，该提案将考虑Markov过程，例如不对称排除和互换，并试图将这些过程的混合时间和光谱间隙与单个粒子的相应量相关联，并了解这些过程的截止现象。