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

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

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.