Extreme Values For Random Processes of Tree Structure

这项拟议的项目旨在研究随机过程的极值，这些过程自然产生于许多领域，如组合优化、纯概率论和统计物理。最近PI和他的合作者对这一主题的研究导致了一些长期悬而未决的问题的解决，包括Aldous-Fill提出的覆盖时间到乘法常数的近似，Winkler-Zukerman毯子时间猜想，有界度图的覆盖时间和离散高斯自由场之间的渐近关系，二维离散高斯自由场的最大值的方差的阶，以及平均场环境下Aldous平均渗流的临界行为。前述工作中的一个基本原理是利用与随机过程相关的树结构，突出表现在Fernique-TALAGRAND优化度理论在随机游动覆盖时间研究中的应用。该项目的主要重点是通过进一步探索相关的树结构来了解各种过程的极值。尽管PI和其他一些研究人员做出了努力，但这一领域仍有许多悬而未决的问题，如一般图中覆盖时间的渐近和集中现象，2D离散高斯自由场的极值过程的中心最大值的极限律和标度极限，以及高维平均的渗流和社会网络上的首次通过渗流。极值的研究包括典型的量级、集中现象和定律上的极限。虽然建议的领域在理论和实例方面都很丰富，但该提案的特点是具有树结构的模型/流程，在大多数实例中总是隐含且隐藏得很好。将特别关注随机行走的时间、离散的高斯自由场、平均的渗流以及社交网络上的首次通过渗流。从理论的角度来看，我们的研究揭示了已经单独研究的主题之间的概念联系，并进一步了解了重要随机过程的有趣方面，如随机行走(可以说是数学家研究最多的随机过程)和高斯自由场(统计物理学中的一个基本感兴趣的对象)。从实践的角度来看，这项研究的动机是在计算机科学、运筹学和社会网络等领域的应用。例如，随机游走的覆盖时间在计算机科学中有应用，如测试图形连通性和协议测试；研究社交网络上的首次通过渗透对于理解信息/流行病的传播具有重要意义，进而可能为管理信息流或预防疾病感染的最佳策略提供洞察。

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.