The main theme of this proposal is the development of new theory and applications in the study of Markov random fields (MRFs) and other stochastic processes on networks. One aspect involves studying dynamical processes on such systems, particularly the Glauber dynamics Markov chain. It will consider the question of universality of the cutoff phenomena at high temperatures as well pursuing a better understanding of the dynamics in the low temperature regime. A second theme is the development of new tools for estimating the partition function of MRFs on locally tree-like graphs and inferring their local distributions. Understanding these distributions will enhance the understanding of links between phase transitions and transitions in the computational complexity of combinatorial counting, sampling and randomized optimization problems. The final topic of the proposal is to apply probabilistic theory and results for MRFs to widely used statistical estimators from phylogenetic reconstruction in computational biology and to develop new methods for detection of communities within social and other networks.
Markov random fields (MRFs) are models of random processes on networks which play a major role in a wide range of areas including mathematical physics, machine learning and statistics, theoretical computer science and computational evolutionary biology. This proposal seeks to develop new theory for MRFs to better understand models, algorithms and estimators and other probabilistic techniques in these areas. It considers the problem of how much data is needed for standard statistical procedures, such as maximum likelihood estimation, to recover the underlying evolutionary tree for a collection of species. The proposal addresses questions from computer science about when combinatorial counting problems, such as counting the number of independent sets in a graph, become computationally intractable and how is it related to the transitions of MRFs on trees. It also studies questions of how long it takes random processes on networks, such as the Glauber dynamics Markov chain, to reach their equilibrium distribution and how does this depend on the local interactions of the model. Each of these questions is related to probabilistic properties of MRFs and their transitions between different phases. The proposal focuses on development of mathematical theory with a view to better understanding these problems.
