ABSTRACT

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.

Please report errors in award information by writing to: awardsearch@nsf.gov.