CRII: AF: RUI: Markov Chains and Random Sampling on Graphs

Given a large collection of mathematical objects, how can you find a "typical" element efficiently? The problem of randomly sampling from a large, complex set arises across many areas including polling, estimating statistics of physical systems, and randomized algorithms; studying randomly selected elements can provide insights about likely properties and behaviors.

For example, random samples of political districting plans have been used to build baselines for comparison and detect racial and partisan gerrymandering. However, the problem of efficiently finding random elements in complex settings is often a difficult one, and it can be hard to make rigorous guarantees about the processes involved. More mathematical analysis is needed so that there can be confidence in the conclusions produced

One way to generate random samples is to use a Markov chain: iteratively make random local changes and mathematically bound the mixing time, the number of iterations until the configuration obtained is sufficiently random. Mathematical insight is needed to rigorously understand these Markov chains and their sampling behavior. Another approach is to generate random samples via self-reducibility using approximate counting algorithms.

While many approximate counting algorithms come from Markov chains themselves, other approaches include decay of correlations, interpolation, and most recently, the cluster expansion. This project focuses on the following important problems for random sampling on graphs, involving exciting theoretical questions with an eye toward relevant applications: (1) Approximate counting and sampling for spin systems using the cluster expansion; (2) Rigorously analyzing Markov chains used for sampling political-districting plans and other problems with similar structure.

This project is strengthening the interdisciplinary connections between the theory of random sampling and other disciplines like statistical physics and political science. The investigator is also working to make this research area more accessible to undergraduate students, through continued mentoring, writing and distributing an undergraduate-level introduction to the theory of Markov chains, and creating and teaching a new elective class related to these topics.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.