Extreme Values For Random Processes of Tree Structure

该项目旨在研究随机过程的极值，这些随机过程自然地出现在组合优化、纯概率论和统计物理等许多领域。PI和他的合作者最近对这一主题的研究已经导致了许多长期开放问题的解决方案，包括覆盖时间近似于Aldous-Fill提出的乘法常数，Winkler-Zukerman毯子时间猜想，覆盖时间与有界度图的离散高斯自由场之间的渐近关系，二维离散高斯自由场最大值的方差阶，以及平均场条件下平均奥尔德斯渗流的临界行为。上述工作的一般基本原则是使用与随机过程相关的树结构，突出显示了fernicque - talagrand在随机行走覆盖时间研究中的大部分测度理论的应用。该项目的主要重点是通过进一步探索相关的树结构来了解各种过程的极端值。尽管PI和其他研究人员做出了努力，但该领域仍有许多突出的问题有待解决，例如一般图中覆盖时间的渐近性和集中现象，二维离散高斯自由场的中心最大值和极值过程的缩放极限的限制律，以及高维平均值的渗透和社交网络上的第一通道渗透。对极值的研究包括典型幅度、集中现象和法律极限等多个方面。虽然所建议的领域在理论和示例方面都很丰富，但该建议的特点是具有树形结构的模型/过程，隐式地始终隐藏在大多数示例中。将特别关注随机漫步的时间，离散高斯自由场，平均值的渗透，以及社会网络上的第一通道渗透。从理论的角度来看，我们的研究揭示了已经单独研究的主题之间的概念联系，并进一步理解了重要随机过程的有趣方面，如随机漫步（可以说是数学家研究最多的随机过程）和高斯自由场（统计物理学中基本感兴趣的对象）。从实践角度看，本研究主要受计算机科学、运筹学和社会网络等领域的应用驱动。例如，随机漫步的覆盖时间在计算机科学中有应用，如测试图连通性和协议测试；研究社交网络上的第一通道渗透对于理解信息/流行病的传播具有重要意义，反过来可能为管理信息流或防止疾病感染的最佳策略提供见解。

The proposed project aims to study extreme values of random processes, which arise naturally from many areas such as combinatorial optimization, pure probability theory, and statistical physics. Recent study on this topic by the PI and his collaborators has led to solutions for a number of long-standing open problems including an approximation of cover times up to multiplicative constant posed by Aldous-Fill, the Winkler-Zukerman blanket time conjecture, the asymptotic relation between cover times and discrete Gaussian free fields for bounded degree graphs, the order of the variance for the maximum of the two-dimensional discrete Gaussian free field, and the critical behavior for Aldous' percolation of averages in the mean-field setting. A general underlying principle in the aforementioned works is to employ tree structures associated with the random processes, highlighted by an application of Fernique-Talagrand majorizing measure theory in the study of cover times of random walks. The main focus of the project is to understand extreme values of various processes via further exploring associated tree structures. Despite efforts by the PI and a list of other researchers, a number of outstanding questions remain open in this area, such as the asymptotics and concentration phenomenon for cover times in general graphs, the limiting law for the centered maximum and the scaling limit of the extremal process for 2D discrete Gaussian free field, as well as percolation of averages in high dimensions and first passage percolation on social networks.The research on extreme values has a number of facets including the typical magnitude, the concentration phenomenon, and the limit in law. While the proposed area is rich both in theory and examples, the proposal features the models/processes that possess tree structures, implicitly always and well hidden in most examples. Special attention will be devoted to cover times of random walks, discrete Gaussian free field, percolation of averages, as well as first passage percolation on social networks. From a theoretical perspective, our study reveals conceptual connections among topics that have been studied separately, and further understand interesting aspects of important random processes such as random walks (arguably the most studied stochastic processes by mathematicians) and Gaussian free fields (an object that is of fundamental interest in statistical physics). From a practical perspective, the research is motivated by applications in areas including computer science, operation research and social network. For instances, the cover time of a random walk has applications in computer science such as testing graph connectivity and protocol testing; studying first passage percolation on social networks is of significance to understand the spread of information/epidemics, and in turn is likely to provide insight on optimal strategies to manage the flow of information or to preclude infections of diseases.