Extreme Values For Random Processes of Tree Structure

树结构随机过程的极值

• 批准号: 1207988
• 负责人: Jian Ding
• 金额: $ 13.19万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1207988&HistoricalAwards=false
• 关键词: Extreme; Values; Random; Processes; Tree

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.

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