Markov chain simulation is a very general technique applied to a wide spectrum of problems in the physical sciences. From explicit simulations of physical and dynamical processes, such as fluid dynamics and spin systems, to algorithms for sampling from probability distributions over enormous sets of combinatorial objects, Markov chains are ubiquitous. This project will seek to improve the design and analysis of such algorithms, leading to faster running times.
Understanding the performance of a Markov Chain Monte Carlo algorithm involves proving bounds on how quickly it approaches its limiting, or "stationary", distribution. Due to the inherent randomness in any Markov chain simulation, there is often no reliable empirical criterion for measuring this convergence; rather, one must rely on theoretical guarantees. The PI will focus on the twin long-standing problems of how to redesign Markov chains to actually converge faster, and of proving better convergence guarantees, both of which allow us to safely terminate MCMC simulations sooner. Over the course of this work, these goals will be approached using techniques from three main thematic groupings:
1. In the "Coupling Method" for proving convergence bounds, one seeks to show that two copies of a Markov chain can be "made to approach each other" under some metric on the state space. To improve this kind of analysis, the PI seeks to find better metrics, i.e., better definitions of the distance between two states.
2. Several different mathematical notions of duality have played important roles in the analysis of Markov chains. For example, the duality between the spin system and the cluster characterization of the Ising model, a standard model of magnetic materials, the high-temperature/low-temperature duality for the Potts model on a planar graph, and strong stationary duality, which underlies a recently introduced technique called the Evolving Sets method.
3. The PI will attempt to convert reversible Markov chains into non-reversible "lifted" Markov chains, by adding additional "momentum" information to the states. These lifted chains allow sampling from the original distribution, but can run quadratically faster.
The project will include the creation and deployment of a free web resource, "Markov Chains Central," which will include a collection of new and existing laboratory applets for simulating and experimenting with Markov chains and various measures of convergence. These applets will help students visualize Markov chains and understand them through experimentation and play. The project also features an integrated educational plan, which provides for wide dissemination of generated knowledge and educational materials. This work will support undergraduate and graduate student research and mentoring. Effort will be made to maximize involvement of women and minority students.
